mikeni2006的个人资料 - RAT

mikeni2006 mikeni2006

`~!@#$%^&*()_+[]\\;',./{}|:"<>?

关注数: 22 粉丝数: 117 发帖数: 3,259 关注贴吧数: 7

冒泡 rt

NOI Day1第一题简要题解鉴于NOI吧已死，LZ就来这里讲(pian)讲(pian)题(jing)目(yan) = =。。。首先呢，暴力O(N^2D)就不用说了……压位的暴力也不用说了……不过k=3的位运算优化还是要略微费点脑筋的…… 接下来的高端做法呢大概我现在想到看到的就两种： 1）标程的做法：随机先看k=2。以下在模2意义下讨论。假设以这些向量为列向量的矩阵为A=(a1,a2,...,an)，那么这题也就是说要找出A'*A除了对角线上的元素以外为0的一个元素，这里A'是将A行列对换所得矩阵（转置）。首先要去掉【不在对角线】的限制。这个比较简单，暴力求出对角线上的元素，然后如果该元素为0，在新矩阵B的这个位置放上1。当然B是个对角矩阵，只有对角线上有元素，可以用数组存……下面其实就是寻找J-A'*A-B的非零元，其中J是所有元素都是1的矩阵。注意到这个矩阵我们其实不能算出来，但是对于向量X，A'*A*X是可以很快算出的。这是由于矩阵乘法有结合律，右结合地算（A'*(A*X)）复杂度只有O(ND)。于是随机一个向量X，求J*X-A'*A*X-B*X，三项都能很快求出，然后看所得的向量哪个元素不为0，所求的位置肯定在A'*A对应的那一行上，然后暴力枚举即可。复杂度是O(CND)，其中C是随机次数。再看k=3。k=3的问题在于，如果看A'*A，这题还是要求一个不在对角线上的零元素，但是A'*A每个元素在模3意义下除了可能为0、1，还可能是2，不能转化为求J-A'*A-B的非零元，比较难办。注意到1*1=1,2*2=1(mod 3)，内积平方不是0就是1，因而我们可以考虑判定是否内积平方是0。然而(x1y1+...+xnyn)^2=x1^2y1^2+x1x2y1y2+...+x1xny1yn+x2x1y2y1+...+x2xny2yn+...+xnx1yny1+...+xn^2yn^2，(x1,...,xn)与(y1,...,yn)内积平方转化成(x1^2,x1x2,...,x1xn,x2x1,...,x2xn,xnx1,...,xn^2)与(y1^2,y1y2,...,y1yn,y2y1,...,y2yn,yny1,...,yn^2)的内积。这些导出向量是D^2维的，于是问题转化成D^2维下类似k=2的情况。复杂度是O(CND^2)。另外对于非零矩阵，一次随机乘出来恰好是零向量的概率<=1/k(?)，所以随机10次以后仍然判定失误的概率还是很低的。 ================================================================================= =====================对于只想AC的同学，以下的就不用看了。。。==================== ===================================高能慎入。。================================== ================================================================================= 2）另一种确定性做法还是先看k=2。如果真的没有两个向量正交，也就是A'*A除了对角线都是1，那么对角线上的0个数不可能多于D+1。这是由于rank(A'*A)<=rank(A)，rank(A)<=D，所以rank(A'*A)<=D。又可以发现，如果对角线上有k个0，这k行向量组的秩最少为2[k/2]>=k-1。如果有多于D+1个0在对角线上，其秩必然大于D，矛盾。所以先把对角线上是0，也就是自身内积是0的向量单独分出来，这些向量若多于D+1个，其中肯定有与其他向量正交的向量。这时候将前D+2个与所有向量暴力检查一遍，如果找到了直接输出。下面只考虑自身内积为1的向量。用高斯消元求出这些向量的一个极大无关组，并同时求出每个向量在这个极大无关组下的坐标。首先检验，极大无关组内是否有正交的。对于其他向量，若X、Y是某两个向量在这个无关组下的坐标，那么由于该极大无关组度量矩阵是J，则它们的内积可以表示为X'*J*Y，可以发现，它们内积为1当且仅当X、Y每一维加起来都是奇数。但是，如果X（或Y）每一维加起来是偶数，那么X'*J*X已经为0，也就是它代表的向量的自身内积为0，矛盾。所以此时不可能找到正交向量对。时间复杂度：自身内积0的向量检查O(ND^2)，高斯消元O(ND^2)，检验O(D^3)，总复杂度O(ND^2)，比随机做法慢一截。再看k=3。这里思路就差不多了，和之前随机做法一样转化成D^2维的问题，然后仿照之前的做。但是这里总复杂度要达到O(ND^4)，对于这题完全无法承受。最后是，此题完全可以构造只有一对向量正交的情况，所以不要抱有过多侥幸心理。。。最后的最后是，如果有人能想到时间复杂度更低的随机/确定性做法，欢迎与我讨论。

Vani成年了这个吧还没有新帖…… RT

前12 clj qmd wd xhr wzy gsh hym zwt wkn lg pty ljq （其实这个帖子的目的很显然只是为了给吧里除除草 TAT

黑vani有妹子专帖 rt

请教关于GNOME 3.6下蓝牙的问题一个月前GNOME升级后蓝牙就用不了了……连接一个配对的手机后，它总是出各种各样的错误，比如Gio.DBusError: message did not receive a reply (timeout by message bus)，又比如成功连接后nautilus会报错找不到/run/user/1000/gvfs/obex:[XX:XX:XX:XX:XX:XX]之类的…… 但是命令行sudo obexfs -b就没有任何问题……请教这个问题如何解决？我google了好多次都找不到类似的问题

最近突然冒出来一堆发增高广告的如何破

秀新头像 >_<

个人贴吧么= =

> < 纯属无聊。。。 @广陵lonely散

国家队名单产生恭喜lich(@ws1192 ) 7k+(@中国脑筋 ) ayq zpl进队

[集训队]hw2出题互测资料集 115 behyqavv 包括网页版和部分pdf/doc版题目，题解和部分标程，以及除zl外所有人的数据（zl的部分为数据生成器）

Violet系列比赛合集 115 dpzmm2z2 （已同步自助资源站）

用新头像卖个萌走人~

[项目]BZOJ题解共享平台 rt 该项目为受BZOJ root委托所作的[临时]平台, 先做预告

关于bzoj 这次bzoj调整并不是关闭,只是将版权不明的题目隐去(只对内部开放)

关于bzoj 这次bzoj调整并不是关闭,只是将版权不明的题目隐去(只对内部开放)

颓废的少年们,关了你们的动漫,删了你们的游戏![wzk版] 在我们颓废成shi的时候 wzk大神默默地学霸着都赶紧跪下吧

[转]OIroom FTP空间 rt

求解一不定积分 RT (个人感觉这积不出,但是它出现在了某书的练习题里)

WC2012资料合集(updated) rt 加了ld&syj的交流资料以及提交答案题的checker

WC2012资料合集 rt

唉. 就要到和OI说再见的时候了... 真的有点伤感啊...这一段人生就要结束了...

函数式编程太犇了 rt 三行秒杀平衡树!!!

呀,新年到,我7级了~~~

辛卯-->壬辰

球建设

围观这个吧谁建的?

LF你是想和Vani抢贴吧? rt @云の彼端CZ

原来还有这个吧!!! @妖娆红尘醉 @广陵lonely散

这个吧刚建就被水军盯上了?

aha,居然6级了好高欣~~~~~~~~~~~~`

这么快吧主就批下来了?

我也来搞个todo list

看来锑度贴吧的验证码很不给力啊

我发现很多人老是喜欢顶坟帖是不是这样可以攒经验啊,有些人都成顶帖专业户了,不水贴吧光顶各种坟看到这种行为就有一种冲动要把这些人给封禁了

AVFun上浏览文章区里的帖子秃然发现这个,还真把我吓到了= = 是不是tooo*ld了...

又发现baidu贴吧的bug... 你们遇到过么...

大家注意保重身体啊... RT 今天听说一个OIer+ACMer+Baiduer去世了,应该是今年才大学本科毕业... 下面试试贴几个传送门

如何比较简便地导出这个等式? (是导出,不是证明)

ACM完挂...大家再见 (以下省去丽洁体若干字) 被E卡的人你伤不起啊......... Cu Rank1你伤不起啊..........................

试试看发个帖 rt

[国家集训队]hw1讨论帖

[传送]ORZ WJMZBMR!!! 详见百度贴吧帖子编号1244888341

ORZ WJMZBMR!!! 1L喂熊

求开zrp膜拜帖 rt

[H2O]大家国庆准备干嘛呢?

大家有木有发现baidu空间的个人中心挂掉了 rt ff表示脚本有语法错误,于是好友动态神马就全木有了

再来一个就CL不250了

新功能bug多多啊 rt 除了一些人莫名其妙消失,还有一些人莫名其妙发了很多帖只有1级之外,我还发现了一个bug

热烈祝贺applepi神犇当选吧主!!! rtrtrtrtrtrtrtrt

求问大家能流畅打开百度空间么... 表示我已经一天没能打开了...IE和FF都卡,难道是我网络的问题?

秃然发现SPOJ GSS4被public了 RT 大家可以切了,补上GSS系列的空缺... 估计是因为被用作ACM上海赛区的题,所以才被hidden了那么长时间亦或是本来管理员觉得这题太傻叉了,然后出现了原题才又public了?

秃然发现LXY=流星雨于是一起来看LXY 一起又看LXY (顺带经济建设)

度受是不是还没起床啊积累了两天多的吧主申请还没处理? 顺带经济建设

一天多不上线,吧里经济建设气氛略有下降啊 rt 话说这次吧主申请发言数终于显示正确了> <

回复悄悄话功能已经被去掉了 RT~ 顺便进行经济建设,十五字十五字十五字

您已尝试提交多次了，请返回后刷新页面，方可重新发贴您已尝试提交多次了，请返回后刷新页面，方可重新发贴

给神龟一个离职期限过了这个期限,采取非常手段;如果在期限前退出吧主职位,noi吧就算完成使命.如何?

膜拜Vani暴虐NOI!!! 上图强势膜拜十五字十五字十五字

1 下一页