丁力煌省队模拟赛题解

2018-04-28 13:12:14 By babblishu

game:

10:直接dp每个状态

30:注意到两个人得分的异或和是一个定值【等于所有数的异或和】,设这个定值为S,则S的最高位两个人不同,这一位之上都相同,故大小关系由这一位直接决定,故可以把所有数转化为0和1,dp[i][j][a]表示区间[i,j],先手是a【此时后手可以算出】的答案。

100:根据这个观察打表找规律,规律如下:偶数先手必胜,奇数时候先手胜当且仅当以下两种情况至少一个成立并且1的个数形如4k+1:

1、开头是1,把第2个到第n个拿出来不断删除头尾相同的数,剩余不能删的部分【一定偶数个】每连续两个【第2i个和第2i+1个】相同;

2、结尾是1,把第1个到第n-1个拿出来不断删除头尾相同的数,剩余不能删的部分【一定偶数个】每连续两个【第2i-1个和第2i个】相同;

证明是显然的,首先,偶数的时候先手可以考虑所有奇数位上的数的异或和和所有偶数位上的数的异或和,这两个一定一个0一个1,先手可以选择其中之一,使得后手每次拿数的时候只能拿另一个奇偶性位置上的数,故先手必胜。【注:此时如果规则是拿到0的获胜也是先手必胜】

其次,由上面分析知道先手第一次一定拿的是一个1【否则变成刚才分析过的情况】,分别考虑先手拿第一个还是最后一个。不妨设先手拿的是第一个,如果某一步先手行动之后先后手当前的异或和一样,那么由第一种情况及注知后手获得胜利。故先手必须每次拿后手刚拿过的数,读者沉思半晌即可明白以上条件成立。

math: 20:暴搜,枚举ai和bi,暴力判断是否合法。

50:观察一下题目中的提示【或者打个100的表】发现要么k=2要么k=4。k=2时即不退化成同一个,k=4时观察得一定是sqrt(a1)+sqrt(a2)+sqrt(a3)-sqrt(a4),其中a1a4=a2a3,枚举一下前三个数就能算出第四个数,复杂度O(n^3*logn)【log n的来源是要球gcd

100:分别考虑两个数和四个数的情况怎么算。两个数即为枚举一个公因子反演两个不等价的数量。四个考虑容斥原理,则只需要计算四种情况:无特殊要求,a1等价于a2且a3等价于a4;a1等价于a4且a2等价于a3;a1等价于a2等价于a3等价于a4。第一种直接使用a1=uv,a2=uw,a3=vx,a4=wx,其中(v,w)=1,(u+x)*(v+w)<=n计算;第二种枚举a1/a2=a3/a4化简后的值;第三种枚举x=sqrt(a1a4)<=O(n),再枚举a1和a4公共的无平方因子,算出所有合法的a1和a4,再对a2和a3同样计算,最后扫一遍即可,第四种枚举公共的无平方因子部分然后类似第三个部分做。其中第一第二部分的复杂度是O(n),第三第四部分的复杂度是O(nlog^2n)。由容斥原理得最终答案等于这四个答案的线性组合,列方程解得四个系数。

【注1:本题中证明k=2或4是一个有些困难的问题。初等证明过于复杂,在此不做赘述。事实上这个问题可以使用伽罗瓦理论轻松解决。 【注2:注意代码的常数。 【注3:这个nlog^2n中的n其实是输入的n的1/4。

mogic: 30:手动模拟 100:等价于计算 $\sum_{i} p(i步之后不联通)= \sum_{i} \sum_{j} p(i步中施法成功j次)*p(连j条边不联通)= \sum_{j} p(连j条边不联通) * E(维持在施法成功j次的时间)$。考虑分别计算两部分,假设迭代到j=N,则前一部分可以在O(n^2N^2)内用容斥原理dp算出。下面考虑计算后一部分,假设刚进入施法成功j次的状态的时候的概率分布为p=(p1,...,pn)^T,则这个期望显然是关于p的线性函数,并且j步结束后的概率分布q=(q1,...,qn)^T显然也是关于p的线性变换,即左乘上一个矩阵。第一部分左乘的向量即为(1,1,...,1)(1/(I-A))^T,第二部分的矩阵即为B(1/(I-A)),其中A为含有施法失败概率的转移矩阵,B为施法成功后一步的转移矩阵。

总复杂度为O(n^2N^2+n^3N).

【注:分析一下N需要多少,由于加入一条边连接了两个联通块的概率至少约为2/20=0.1,故连了m条边还不连通的概率大约不超过\sum_{i=0}^{n-1}C(m,i)0.9^(m-i)0.1^i<=nm0.9^m,第二部分算出来的期望时间至多是1000,所以m>N的部分全部舍去带来的误差大约是20N0.9^N*1000,故令N=300即可控制住相对误差不超过1e-5.

如何以正确姿势过掉每个题:

t1:

1、20min观察出t1中只和异或最高位相关然后打个表;

1.5、20min写一个n^2的dp并获得30分;

2、10min观察出偶数先手赢并想出道理;

3、20min观察出奇数时先手必须先拿一个1然后必须每次那和后手相同的数;

4、5min写一个check对拍去了。

//共75min

t2:

1、盯着看20min,什么都没看出来;

2、20min写一个爆搜,把所有可能的解【左右两边】搜出来,并观察到右边要么是2个要么是4个,并且观察出4个一定有最小的乘最大的等于中间两个;

3、10min写一个三方暴力,获得50分;

3.5、放弃此题

4、10min把2个的部分优化到O(nlogn);

5、20min想容斥原理并把前两部分优化到O(n);

6、30min把后两部分优化到O(nlog^2n);

//共110min

t3:

1、5min注意到最后一句话,知道这是一道爆精度题;

2、20min猜想经过若干步之后收敛并写一个最裸的状压dp获得30分;

3、30min做出转化并发现可以看起来很线性;

4、10min试图写出矩阵形式;

5、20min写一个标算并获得100分;

//共85min

//三题加起来总共270min

//得出劼论,这些时间还是挺宽松的

评论

avatar
BillXu2000
“读者沉思半晌即可明白以上条件成立“

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。