分享好友 最新动态首页 最新动态分类 切换频道
2020年常熟理工学院第一届线上ACM选拔赛题解(Python版)
2024-12-27 02:15

本次题目难度顺序基本从难到易,在这里非常感谢出题组同学的真情付出。此博客原文地址: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都能对。勾股数恰好满足可以凑答案,甚至正好整除。
这个题错误的是因为多组数据。

最新文章
网站发布排名优化,提升网站在搜索引擎中的可见性与权威度,网站发布排名优化方案
网站发布排名优化方案旨在提升网站在搜索引擎中的可见性与权威度。通过优化网站内容、建立高质量外部链接、提升网站速度、增强用户体验以及定期更新网站信息,可以有效提高网站在搜索引擎中的排名。还需关注竞争对手的动态,及时调整优化策
非华为电脑管家 V11.1.6.30 汉客儿版免费软件全功能绿色商业破解版注册码下载
非华为电脑管家 V11.1.6.30 汉客儿版免费软件宁缺见识多(见多识广)果实累累毋滥32. 在我们的城市里,夏季上演得太长,秋色就不免出场得晚些。但秋实永远不会被混淆的——这坚硬明朗的金属季。让我们从微凉的松风中去任取,让我们从新刈的
苹果采集插件全套教程-苹果cmsV10采集插件
最近几年随着互联网时代的发展,做电影网站的站长越来越多了,加入此行列的人也是与日俱增!但是很多站长都是跟风来做电影站的,怎么做一点思路都没有。电影资源都不知道怎么来的。今天就教大家怎么做好电影站,文章有点长请大家耐心观看,
【纵深推进“三抓三促”行动】庄浪:解难题办实事暖人心
  原标题:【纵深推进“三抓三促”行动】庄浪:解难题办实事暖人心  新甘肃·甘肃日报记者 田丽媛  窗外,雪花飞舞;室内,温暖如春。  “今年暖气真暖和!”说起今冬供暖,家住庄浪县朝阳社区水利小区的李明月老人感慨地说。  
天眼3D高清卫星地图下载
下载天眼3D高清卫星地图到手机上面的方法有很多。 安卓系统的手机可以在豌豆荚或者PP助手等手机助手里面一键下载安装!也可以通过电脑端用手机扫描天眼3D高清卫星地图下载的二维码获取下载链接!有手机端直接访问网页下载也是可以的,下面
预测模型自变量太多怎么筛选?这篇Lancet子刊如何从249个变量筛出11个
基于传统危险因素的风险预测模型虽然也能够有效的区分未来低风险和高风险的个体,但由于缺乏特异性和对复杂风险因素的不完整描述,临床适用性受到限制。因此越来越多的学者引入蛋白质组学、循环代谢物等分子层面信息作为预测因子提高模型的
营口SEO推广收费揭秘,解析奥秘与明智选择之道
营口SEO推广收费标准揭秘:本文深入剖析营口SEO推广行业收费规则,揭示行业奥秘,为企业和个人提供合理选择SEO推广服务的指南。通过对比分析,助您了解费用构成,避免陷入陷阱,实现高效SEO推广。随着互联网的快速发展,越来越多的企业开始
百度上网页快照是什么意思(网站图片优化主要方法)
在做网络推广网站优化的过程中,网站快照也是对网站优化的一大评判标准,针对网站快照也可以了解到有关网站的一些状态和信息,来对网站进行更及时合理的优化调整,下面就跟随做网络推广一起来看一下。1、通过快照可了解搜索引擎抓取频次通
搜狗搜索优化策略,如何提升网站搜狗搜索引擎排名?
在这个信息爆炸的时代,每一个网站都渴望在搜索引擎中脱颖而出,吸引更多的目光和流量。而我,作为一名在SEO领域摸爬滚打多年的从业者,深知搜狗搜索引擎优化的重要性。搜狗搜索,凭借其强大的自然语言处理和机器学习能力,不断优化搜索算
相关文章
推荐文章
发表评论
0评