艾雨青+IPSC趣题讨论.ppt

《艾雨青+IPSC趣题讨论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IPSC趣题讨论清华大学艾雨青MYIOI2012MYIOI2012MYIOI2012MYIOI2012MYIOI2012MYIOI2012MYIOI2012IPSCIPSC全称InternetProblemSolvingContest组队参加，每队1~3人总时间5小时，题量较大，一般12~13道可下载输入数据，只需提交答案每题分为Easy和Hard两个子问题解决一个Easy得到1分，解决一个Hard得到2分题目形式丰富多彩，解法不只限于写程序可借助人力、强大的工具软件、耐心的人肉没有奖金Justforfun~~~最有趣的编程比赛IPSC2012-F-Faircoi

2、ntoss有n枚硬币，组成一个集合，第i枚有Pi的概率正面朝上使用多枚硬币来决定得到的随机数把正面朝上看做1，把背面朝上看做0把所有硬币得到的数异或起来决定最后得到的数Easy：询问是否存在一个子集合使得得到0和1的概率是相等的?n<=10Hard：询问有多少个子集合使得得到0和1的概率是相等的?n<=60IPSC2012-F-Faircointoss其实...使用一个集合内硬币公平的充要条件是集合内有一枚公平的硬币证明？p=0.5+aq=0.5+b(a,b≠0)pq+(1-p)(1-q)=1-p-q+2pq=-a-b+0.5+a+b+2ab=0.5+2ab≠0.

3、5IPSC2012-E-EvilMatching考虑两个正整数串T,P如果存在一个序列ak=a0

4、T

5、<=5000，

6、P1

7、,

8、P2

9、<=600，所有输入数字

10、的和不超过11000Hard：

11、T

12、<=11000000，

13、P1

14、,

15、P2

16、<=2000000，所有输入数字的和不超过22000000IPSC2012-E-EvilMatchingEasy:subtask1、2枚举每一个位置开始匹配subtask3、4两重循环枚举P1、P2的开始匹配位置Hard:前2问？IPSC2012-E-EvilMatchingx是一个正整数记E(x)为1后面跟x-1个0的01串E(5)=10000S是一个正整数序列s1,s2,...,sn记E(S)为E(s1)·E(s2)·...·E(sn)·1E({1,2,3})=1101001如果E(P

17、)里的每一个1都对上了E(T)里的1那么P能匹配上TIPSC2012-E-EvilMatching记SR为S的翻转，SN为S取反考虑E(T)N与E(P)R多项式乘法!!!FFT/Karatsuba后面两问在得到了前两问每个位置是否匹配的信息之后再做一遍多项式乘法IPSC2011-B-BFSKiller设计一个大小不超过600*600的地图，有一个起点S(Start)，一个终点T(Treasure)，若干障碍'#'和空地'.'，让下面这份BFS代码的最大队列长度：Easy：爆掉5000Hard：爆掉15000IPSC2011-B-BFSKiller分形甲...874

18、7空间似乎利用得不够充分...IPSC2011-B-BFSKiller分形乙16383^_^IPSC2011-I-Invertingbits一种语言，可以开26个变量(A~Z)，每个可存8个二进制位,可以使用下面的操作:andRX将R&X的值赋给RorRX将R

19、X的值赋给RnotR将~R的值赋给RshlRC将R<>C的值赋给RmovRX将X的值赋给RgetR读入一个数，储存在R中putR输出R的值IPSC2011-I-Invertingbits请你用此语言编写程序，完成下面两个子问题：Easy:读入正好7个非0即1的数，将读入的数取反

20、输出Hard:读入正好19个非0即1的数，将读入的数取反输出限制条件：Subtask1中，使用not最多1次，代码长度<=100行Subtask2中，使用not最多2次，代码长度<=300行IPSC2011-I-InvertingbitsEasy:7个数存到一个变量里，一次取反就够了Hard:每个变量只能存储1个二进制位，用最多2次not，将3个输入变量(ABC)取反输出。若能做到，对于原问题可做到最多取反24位。IPSC2011-I-Invertingbitsex3=A&B&C---正好3个为1mo1=A

21、B

22、C---不少于1个为1mo2=(A&B)

23、(B&C)

24、

25、(C&A