就在前方

这是一道结果填空的题你只需要算出结果后提交即可。

本题的结果为一

个整数,

读文件。

文件有200万个整数只能读文件不能复制到代码中。

素数判断。

判断x是否为素数可以把它除以[2,

sqrt(x)]内的素数如果能整除就不是素数。

素数筛预处理出素数。

文件里99.99%的整数都

所以只要得到内的素数即可。

约1300个素数。

其他0.01%的大于的数数量很少可以单独判断。

计算量:1300×200万。

【代码】

数字字符他最多拼十个。

小蓝会把拼出来的数字字符组合在一起形成一个整数,

例如对于整数

将数字看成价值为1且各有10个的物品需要的火柴棒看成重量这是多重背包问题。

因为是填空题没有用滚动数组优化和二进制优化。

为什么每个数字价值都为1

答因为位数越大这个整数就越大最大的整数肯定是位数最多的。

例如999910000每个数字都相当于给你增加了一位数

位数相同价值相同时怎么选择

]为了拼出最大的整数所以输出最大整数时应该按数字i从大到小考虑。

当位数相同的时候就选择装了更多数字i的dp因为装了更多数字i的dp肯定比装了较少的数字i的dp最后拼出的整数更大。

定义状态dpli][j]表示把前i个数字装进容量j的背包能装进背包的最大价值。

【代码】

答案9999999999777777777755555555554444444444333333333322222222221111

题目三22年省赛C题——近似GCD

数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组。

数组的最大公约数指的是数组中所有元素的最大公约数。

如果最多更改数组中的一个元素之后,

那么称

若a中每一项都是g的倍数只需要将a中某个元素改为g满足要求。

若a中存在一个不是g的倍数把它改为g满足要求。

若a中存在至少2个不是g的倍数无法满足要求。

问题变成求原数组有多少个子数组满足这个数组里最多只有一个元素不是g的倍数编码

用双指针遍历原数组

技巧1用last标记当前的不满足g的倍数的点下次a[i]再次不满足g的倍数时j直接跳到last往后一点确保只有一个不是g的倍数

技巧2

每次i移动一步就记录一下双指针的距离即满足要求的子数组个数然后将它们累加起来就是所有满足要求的子数组个数

a[0]list(map(int,input().split()))

ans0

last标记不满足点下次a[i]再次不满足g的倍数j直接跳到last往后一点if

i-j1