看完题第一反应线段树。 然后 copy 了一个朴素板子过来发现数据范围 10610^6106，怀疑出题人可能卡常。 然后就想到了 zkw 的非递归式写法，常数很小。 复制完了模板之后反应过来好像可以差分数组 O(n)O(n)O(n) 做（大雾） 线段树做法不讲了，来说说差分数组： 设 d[i]=a[i]−a[i−1]d[i]=a[i]-a[i-1]d[i]=a[i]−a[i−1] 那么一次修改就可以等效成两个点的加减法 一次查询就直接把差分数组做一遍前缀和，就可以算出来原数组了 #include<cmath> #include<cstdio> #define int...

根据题意模拟即可，注意以下几点： 用 int 型存储，高位用 x / 10 取出来，低位用 x % 10 取出来。 判断回文时第一个数的高位和第二个数的低位相同，反之亦然。 向后枚举时碰到 24:0024:0024:00 就加一个 if 语句强制钦定成 00:0000:0000:00 即可。 #include<cstdio> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -...

(a,b)×[a,b]=a×b(a,b)\times[a,b]=a\times b(a,b)×[a,b]=a×b 证明： 记 a=∏i=1kpiαi,b=∏i=1kpiβia=\prod\limits_{i=1}^{k}p_i^{\alpha_i},b=\prod\limits_{i=1}^{k}p_i^{\beta_i}a=i=1∏k​piαi​​,b=i=1∏k​piβi​​ 则有： (a,b)×[a,b]=(∏i=1kpimin⁡(αi,βi))×(∏i=1kpimax⁡(αi,βi))=∏i=1kpimin⁡(αi,βi)+max⁡(αi,βi)=∏i=1kpi(αi+βi)=a×b\...

考虑 x!→(x+1)!x!\rightarrow (x+1)!x!→(x+1)! 有什么贡献。 首先 (x+1)!(x+1)!(x+1)! 一定包含了 x!x!x! 中所有的 555，也就是说直接把 x+1x+1x+1 自己里面的 555 加入到答案即可。 时间复杂度不会算，但显然大于 O(n)O(n)O(n)。 能过 10810^8108 我只能赞美评测机了 ∼\sim∼ #include<cstdio> #define int long long int init(){ char c = getchar(); int x = 0, f = 1; for (; c &lt...

首先容斥。 定义与 AAA 有关的数组成的集合是无关的补集。 考虑如何求有关的数的个数，由 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A∪B|=|A|+|B|-|A∩B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ 可知，直接枚举所有 2k2^k2k 种情况并去掉重复的即可。 考虑如何计算 L∼RL\sim RL∼R 中能被 xxx 整除的数的个数，直接差分成 1∼R1\sim R1∼R 中能被 xxx 整除的数的个数即可，这个直接就 Rx\dfrac{R}{x}xR​。 最后就是剪枝，如果现在统计的质数乘积已经超过了 RRR，直接退出不予计算即可，如果现在没有数相乘，也不计入答案就好。 #inclu...

01 背包模板。 设 dpi,jdp_{i,j}dpi,j​ 表示前 iii 个物品是否能组成重量 jjj： dpi,j←dpi−1,j&nbs***bsp;dpi−1,j−aidp_{i,j}\leftarrow dp_{i-1,j}~\text{OR}~dp_{i-1,j-a_i}dpi,j​←dpi−1,j​ OR dpi−1,j−ai​​ 然后从 sum2\dfrac{sum}{2}2sum​ 处开始找到的第一个最优答案就好了。 #include<cstdio> int init(){ char c = getchar(); int x = 0, f...

按照题意模拟即可。 函数 B 用于判断一个字符是否是 B 的大小写。 函数 O 同理。 通过一个 for 循环找到我们要的答案，如果这一位是 b，下一个是 o，下下一个是 b 则输出当前位置。 都没有找到就输出 -1 即可。 #include<cstdio> #include<cstring> void print(int x){ if (x < 0) x = -x, putchar('-'); if (x > 9) print(x / 10); putchar(x % 10 + '0'); } const int N = (int) 1e2 + 5;...

若 n=1n=1n=1 则任务已经完成； 否则，若 m=1m=1m=1 则任务无法完成；（做不了任何事情） 否则，由于最终要消除恰好 n−1n-1n−1 个硬币，每次操作恰好消除 m−1m-1m−1 个硬币，只需要判断 m−1m-1m−1 是否能整除 n−1n-1n−1 即可。 #include<cstdio> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1; for (; c &g...

A 打中瓶子的概率是： 第一次打中：a%a\%a% 第三次打中：(1−a%)×(1−b%)×a%(1-a\%)\times(1-b\%)\times a\%(1−a%)×(1−b%)×a%（第一、二次都没打中） 第五次打中：(1−a%)×(1−b%)×(1−a%)×(1−b%)×a%(1-a\%)\times(1-b\%)\times(1-a\%)\times(1-b\%)\times a\%(1−a%)×(1−b%)×(1−a%)×(1−b%)×a%（第一、二、三、四次都没打中） ⋯\cdots⋯ B 打中瓶子的概率相似，注意这个循环不能无限持续，可以考虑设定一个 eps 值，当影响小于...

基础的博弈论，如果我可以通过一个状态让对方必死，我就能活；反之我必死。 值得注意的是： 调快 [a,b][a,b][a,b] 秒，也可以不调。 据此设 life(x)life(x)life(x) 表示剩余 xxx 秒时先手是否能活，加一个记忆化即可保证每个状态的计算只进行一次，据此复杂度为 O(n∣a−b∣)O(n|a-b|)O(n∣a−b∣)。 实现细节可以参见代码。 #include<cstdio> #include<cstring> int t, a, b; const int N = (int) 1e5 + 5; int ok[N]; bool life(i...

不知道题面中的代码是什么逻辑。 但是可以通过尝试，发现只要 n≥20182017n\ge20182017n≥20182017 时的输出均为 201820172018201720182017，据此模拟这个过程即可。 （只需要把题面中给的代码加上一个特判，时间复杂度即为正确的） #include<iostream> using namespace std; long long f(long long n) { if (n < 20180001) return n + 2017; return f(f(n - 2018)); } int main() { l...

考虑这个操作的本质，就是任意选一组 i,ji,ji,j，令 ai←ai+aja_i\leftarrow a_i+a_jai​←ai​+aj​。 那么一次至多消除一个重复的数字，所以最优的次数就是重复数字的个数。（例如 1 1 1 11~1~1~11 1 1 1 就认为有 333 次重复，2 2 22~2~22 2 2 就认为有 222 次重复） 考虑证明这个解存在： 把原序列排序，把重复的数字标记出来，然后从后往前做一波 +=+=+= 的操作就可以了： 例如： 1 1 1&n...

按照题意原样输出即可。 #include<cstdio> char str[100]; int main(){ scanf("%s", str + 1); printf("%s\n", str + 1); }

考虑类似 bfs 的过程，通过一个队列去扩展我们的答案就好。 一个格子被感染，可以影响到它周围的 444 个格子，而一个格子周边一旦存在 ≥2\ge2≥2 个格子被感染那么它也会被感染，这个直接建图，类似一个拓扑排序，入度 =0=0=0 就拓扑过去就好了。 时间复杂度 O(nm)O(nm)O(nm)。 #include<cstdio> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1; ...