注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

WC 2013 小Q运动季 sports 题解  

2013-02-13 00:02:37|  分类: WC |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目大意:
超模糊的题目大意:
N个未知数,M个同余方程,求最多能满足多少个。提交答案题。

这题真囧……
不过感觉这才叫做OI的提交答案题嘛!之前几乎都是玩游戏啊囧。

由于要高精度直接上了python。太爽了。
出题人陈许旻表示他本意是想让大家写高精度,没想到NOI Linux自带python。

先说我考试时解决掉的几个:
【sports1.in】
只有1个未知数,5000个方程,模的数均为1058400。
暴力从0枚举到1058400就行了囧。

【sports2.in】
只有1个未知数,50个方程,模的数互不相同,均为某个质数的次幂。
中国剩余定理的裸数据。

【sports9.in】
只有1个未知数,100个方程,模的数均为19337。
暴力从0枚举到19337就行了囧。

其它的都不是一元的了,考试的时候畏惧写高斯消元,因为没写过高斯消元解同余方程组。
所以其它的都是骗了2分。

考完后我写了个高斯消元解同余方程组。
【sports3.in】
有300个未知数,300个方程,模的数均为1000000007。
1000000007是喜闻乐见的质数嘛。
上高斯消元解同余方程组,发现有解。
于是所有方程都满足了。

【sports4.in】
有20个未知数,845个方程,模的数均为1000000007。
发现有些方程重复了20次。
抽取出来,发现都形如:
0 0 0 0 0 ... 0 XXX XXX XXX ... XXX 1000000007 XXX
且对于每一个这样的方程,都有另外一个这样的方程使得它们左边相同而右边不同。
这样的方程共40种,每种重复20次,显然就是要你满足它们的需求的姿态。
剩下45个是杂乱无章的。
于是O(2^n)枚举每对方程取哪一个,这样就形成了三角形矩阵。
解出来再看看满足了多少个杂乱无章的方程,取个最大值就行了。

【sports5.in】
有100个未知数,100个方程,模的数均为223092870。
223092870是喜闻乐见的……合数?!!!
没关系……223092870 = 2×3×5×7×11×13×17×19×23。
拆成质数,然后一个方程裂成9个。
得到9个方程组,分别解出来,然后中国剩余定理合并之。
100个方程都能满足。

【sports6.in】
有50个未知数,50个方程,模的数很凌乱
还是一样的拆方程嘛……
分别解出来,然后中国剩余定理合并之。
发现都能满足。

【sports7.in】
有50个未知数,200个方程,模的数均为176400。
其中有一个方程重复了50次,剩下的方程三个组成一组,每组里面挑一个方程,正好是方程组的左边是单位矩阵。
即每组里面都是这样的方程:
x[i] = a
这个重复了50次的是一定要满足的嘛……就是每个未知数的值三选一,使得目标方程成立。
orz hzhwcmhf考试时用dfs搜出了这个点。
陈许旻表示:“数据水了把搜索的给放过去了。”
其实这个点是dp。
dp下然后输出方案就能过了。

【sports8.in】
有50个未知数,50个方程,模的数很凌乱
这个和第6个点特征是一样的。
于是我拿第6个点的程序来跑第8个点……
./checker 8了一下,发现只满足了49个。
那说明最后一个确实是解不了~
我记得陈许旻讲题时说要枚举下哪个方程不行~
结果我直接就解出来了囧。

【sports10.in】
有50个未知数,90个方程,模的数很凌乱。
没啥思路,果断上爆搜……
拆成质数,看每个质数是哪几个方程的子方程的模。
依次枚举每个质数,决定每个质数对应的方程的取舍。
一些方程之前已经枚举过了,暴力O(2^k)枚举剩下的k个方程哪些选中,哪些不选中。
然后慢得像地上爬……
地上爬的背后肯定有天大的阴谋……
我把每个质数对应的方程的系数模了这个质数打出来看,发现了方程左边都是一样的,只有右边有点不同。
于是把方程看成结点,最优解就是最大点独立集,然后中国剩余定理合并。
我是状压20个点,然后剩余70个暴力搜索,用那个20个点来剪枝搞出来的这个点。dfs调用了约197.8亿次,跑了12分钟。
跑完了发现自己忘记开O2了……瞎了。
update:开了O2……只要4min38s了……太神了orz。

至此,这题解决了。
  评论这张
 
阅读(1226)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017