本次题目难度顺序基本从难到易,在这里非常感谢出题组同学的真情付出。此博客原文地址:https://www.cnblogs.com/BobHuang/p/12610801.html
这个题目是4140: Trojke的一个扩展,在这个题目里由于可以匹配的棋子很多,我们应该想的是去遍历这个棋盘的所有线。这就是格点问题:从(0,0)到(x,y)的线段,经过的格点数目是gcd(x,y)+1。比如(3,5)是两个;(2,4)就是3个,因为过了(1,2);(8,20)是5个,因为还过了(2,5)、(4,10)、(6,15)。这个的证明可以从相似三角形下手,比较简单。
所以这个题目我们预处理出所有的线就可以了,具体实现思路可以看代码。我们可以查一条线上的点的个数x,然后C(x,3)就是当前点构成三胞胎的个数。
复杂度分析:
直接三个字符求解
m * m * m 如果满数据就是n6,1006= 1012=1e12
考虑所有的斜线,就是已知100以内互质对数 * n2
100以内互质对数为6087,实际可能的是1547(优化过的)
1547 * n * n = 1e7,当然还有常数,但是足够通过这个题目了
出题人的代码为预处理欧拉,枚举所有欧拉再枚举点,用的dp转移
python实在太慢了,这个代码本地跑一个大样例要7s
这个是位运算的题目,这是“按位或”运算符,||是逻辑或,两个相应的二进制位中只要有一个为1,该位的结果值为1,即有1得1。曾经写过一个operator的理解,有兴趣可以看看。
我们可以以当前数字作为下标进行统计个数。或会让这个数字变大(有些位上多1),所以我们从小的数字开始枚举,如果或的值不为i,说明异或的新值可以多a[i]个,当前清空,如果这个数字恰巧只有一个,那只能当读出现了,统计下来。
update: 要么a[i]不或m,要么或m,如果存在显然或m,这样会减少。一个数字或上两次并不会变得更大,所以一次处理也可以。
100000 并不是一个规整的数,我们可能或为2倍(其实就是1<<17=131072,略大于是最省的),也就是你要找到大于他的二进制数
非常抱歉这个题目出现了问题,影响了ydqdsg非常抱歉
py的int很大很大,我们可以直接使用,但是他没有很方便的函数,转到r2进制需要手写
你可以看看cpp的实现修改代码尝试下AC6222终极版
Java写起来很容易
这个题目可以广搜解答,广搜可以保证每次搜到的都是最近的,且每个点只会被访问一次
当然也可以记忆化搜索。
当然也可以dp解答,因为每个点只访问一次,而且最小
dp[i]代表i~n的最小步数。
这个题目略微困难,y= - x³ - bx和 y = x³ + bx是等价的,因为他们的函数图像是对称的,x1³ + bx1 - x2³ + bx,有立方差公式(a-b)(a²+ab+b²)=a³-b³,以上进行合并为 ( X1 - X2 ) * ( X1 * X1 + X1 * X2 + X2 * X2 + b)
update:感谢liqiyao0430hack了标程,时间仓促,出题人没有考虑到(写的不等式错了)。
1.后面部分为1,假设(X1-X2)为素数P,后面为1,X1=P+X2
代入得到3X2 * X2+3PX2 +P*P+b为二次函数,开口向上对称轴为-2/P,最低点为
P=2且b=0,最小值为1,X1=1,X2=-1,所以这个需要特判掉。
2.前面部分为1,X1-X2=1代入可得
是对函数3 * i * i + 3 * i = p +1 -b存在解,当然也可以直接二分,也可以判断根。判断根会超过ll,需要unsiged,当然你也可以给他进行因式分解为3i * (i+1)= = p+1-b
(p-1-c)%3 == 0 and int(sqrt((p-1-c)/3)) * (int(sqrt(p-1-c)/3))+1)==(p-1-c)/3
我们可以对24点的代码进行改造,我们可以判断是是不是有4和9然后进行变换就可以了。
当然也可以带上flag搜,dfs就是这样,暴力和好写的一个平衡。
排成圈,其实就是扩展一次。所以可以边扩展边记录,找到最大值即可。
这个题目很多人被卡超时,如果使用C++请关闭输入输出同步,尽量使用scanf和printf。不要混用。如果使用JAVA你可以去codeforces看下peter的代码,把它的Java读入抄下来。
这个自己也可以百度,也是考点,如果还不能通过就要考虑使用快读
这个题目可以循环判断,也可以直接搜索
这个就是方程的判断,y=ax+b,斜率为无穷对应无数个解,如果a=0,且y!=b是无解
python可以直接除,默认就是得到小数
可以直接勾股定理,也可以相似(两小三角形相似,另一直角边为(b*a/c)),而且怎么AC都能对。勾股数恰好满足可以凑答案,甚至正好整除。
这个题错误的是因为多组数据。