看着题目挺有意思，于是做了做，结果发现题解只给出了第二种做法的代码，所以几乎所有人的代码都是第二种做法，但这道题目的价值真的是得满分吗？ 不难发现，出题人细心规划的部分档非常细，并且在最后的数据范围中成功卡掉了 ，所以以下都是部分分的档，正解未写出，只想到了的做法，若有大佬可以解答一下题解中前缀和优化是如何做，请私信我。 8 pts 对于暴力， 分好成绩，不过不是我关注的重点，重点如何DP，以及 DP 优化。 20 pts 对于 20% 的数据，有 1 ≤ n ≤ 100。 表示前 个数，子集最后一个是 前一个是 的合法方案数。转移枚举 作为更靠前的一个数。 其中 表示是否满足题...

20 pts 暴力 (实际80) include <bits/stdc++.h> #define int long long using namespace std; int n; int c[3][200]; int a[2000]; int b1,b2; int d[3][200]; int u[3][200]; int ans=1e15; int dis,wk; int ned1,ned2; void dfs(int now) { if (dis+wk>ans) return; if (ned1>b1 || ned2>b2) return; ...

T1 做不出来，崩溃，连暴力都不会，

【小y的质数.题解】 看题解代码冗杂，我是没有看懂，所以就按着他的大部分意思在加上自己 YY 的想法给搞出来了。 我们都知道，对于 是恒成立的，不会的同学自行百度吧，基础知识。那么我们最终可以将给出的柿子化简成 我考场上也化简出这个柿子了，直观的讲就是在区间中找出和 互质的数，然后就是最简单的筛！ 没错，就是暴力筛，我还以为需要反演或者欧拉之类的东西，因为以前见过一个类似的题目只不过 并不是给定的，所以就因为这我就没有去想筛..... 我们看怎么筛，简单，将 进行质因数分解，暴力的用每个素因子对区间进行筛除。只要和 有相同的质因子都晒去，不过可以发现，有重复。考虑容斥。 本以为这玩意...

【数字染色题解】 前言 考场时看做完大部分人做的题以后随便点开了一道题，没想到是到防 AK 题，但是看一眼，容斥？ 不好求，我求出 的不就行了，然后我感觉我可以 A 掉，所以就在疯狂写 DP ,统计各个其前缀，和当前 位置互质的个数，DP 柿子我都想好了，结果上个厕所发现，没法去重啊！当时人都崩了，也没有在做题。 正解 看到清新的题解后感觉自己想难了，根本没有往莫比乌斯函数去想。 我们考虑若一个序列中只用 以及他的倍数，那么我们的 必然 ，考虑选择方案 。我们再考虑 ，貌似也是这样，在考虑其他素因子，貌似还是这样。 但是不难想到会用重复， 会被 算两边，考虑去重。 根据容斥原理，...

RMQ + kusal 重构树 有没有大佬解决一下 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int B=2e5+10; int read() {int x;scanf("%d",&x);return x;} int n,m,k; struct node{int v,nxt;} e[B<<1]; int head[B<<1 ],cnt; void modify(int u...

【网格图.题解】 思路 对于图表类问题，给多少信息就直接放在 DP 维度中就好了，由于题目中新填了一个限制，所以对于当前的位置 来说，可能需要知道上一次转移的具体信息，所以在开一维度记录有那个方向的数转移而来 表示 到 且是由 的方向转移而来的方案数，那么答案就是 对于 我们有五中状态，分别对应 上下左右，以及停留。 转移过程，考虑转移到他的那个对象是否是在距离 中的，如果在范围内，那么他会有两种选择 保持和当前的转移方向一致（题目给的 变成停留状态 分别对应的状态为 f[i-1][rx][ry][d],f[i-1][rx][ry][4] 这里 表示停留的意思，这些变量都...

Kus 重构树 + 倍增LCA 不会超时吧 ，求助 #include #include #include //#define int unsigned long long //#define int long long using namespace std; const int B=5e5+10; typedef unsigned long long ull; ull myRand(ull &k1, ull &k2){ ull k3 = k1, k4 = k2; k1 = k4; k3 ^= (k3 <<23); k2...

感觉是 LCT 由于没有做过关于维护连通块以及子树内部信息类的 LCT，放弃了，前来询问一下

【B.寻寻觅觅寻不到】 题解 看有位大佬写的题解挺长的，感觉这题目考察点就一个：区间字符串哈希对于区间的字符串哈希值，公式如下： 题目也就是从字串中取出长度为 的子串，将其放在主串的后面构成新的串，看是否和文本串匹配，这里指 串。 所以就是拼接的问题了，由于我们取了长度为 的子串，那么整个主串就分成三分，分别是 ，对应的我们分别用 表示。那么组合成的新的主串的哈希值我们可以比着区间的去做： 其中 表示进制， 表示区间长度。实现的思路主要就是往前进位嘛。看数据范围非常友好，就直接暴力枚举区间，判断时否和 的哈希值相同就好了。 清奇的码风 #include <iostream&g...

【C.踩不出足迹】题解 通过题目我们可以知道对于每到达一个数我们都会有两种操作 异或 同或 我们来看同或的性质，就拿题目给出的样例来说 ，经观察发现，这种操作等价于异或操作 位取反操作。 知道这个性质之后，发现每次操作都会异或，不同的是是否选择将 位进行取反操作。因为异或存在交换律，所以我们可以将所有取反操作拿到最后，由于相同的数异或偶数次等于没有异或，所以我们只有取反或者不取反两种选择。 所以答案就是 其中 为前缀疑异或和 #include <iostream> #include <cstdio> #include <algorithm> ...