作者:小马不小 | 来源:互联网 | 2023-05-18 09:23
https:www.luogu.com.cnproblemCF1497B 此题的特点是相邻两个数相加必须为m的倍数,多写几个模拟,可以发现:必须是x,y,x,y,x,y,x,y.
https://www.luogu.com.cn/problem/CF1497B
此题的特点是相邻两个数相加必须为m的倍数,多写几个模拟,可以发现:
必须是x,y,x,y,x,y,x,y..的交替形式
其中x为任意mod m=j的数,y为任意mod m=m-j的数
有个小小的证明就是:
a,b,c满足题意;
设a=km+x;
那么b要=k'm+m-x;
那么c=k''M+x;
想到这里我开开心心以为此题结束了,那不就是个对所有读进来的数取mod,然后直接合并嘛。
-----
懒狗去题解区验证自己的想法的时候,发现:
0和m/2要特别讨论;
会出现带不动的情况,也就是在互相穿插出现的过程中,会出现有一组数数目太多。
------
在wa了无数次后,我发现自己跪在:带不动的情况,ans+=a-b,而非加1,因为剩下的数只能一个一组;
交上去t了,发现特判时if(n==1)时我直接输出了,可是..
应该还要读进来一个数的。
....
........