A、Anti-knapsack 题意：给我们一个n，一个k(n,k<=1000)，需要我们得到一个集合，集合的元素全部小于n，并且任意子集相加不等于k，而且这个集合元素相加尽可能大。 思路：大于的数全取，小于的的数只能取一半，所以取大的一半。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7; typedef long long int ll; #define eb emplace_back #define ef emplace_front #define ep emplace...

题意：从(0,0)走到(n,m)，选择一个中转点(x1,y1)，然后从(x0,y0)沿直线走到中转点且中间不经过任何一个点称为一次散步，输出所有散步的最小总长度。 思路：要记的结论：一对不互质的数(n,m)一定可以被分解为两对互质的数(i,j)和(n-i,m-j)之和( (i,j)与就在(0,0)和(n,m)的直线附近 )。(因为不会证) MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=2e5+7,mod=999911659; typedef long long int ...

题意：找斐波那契序列里有多少对数相乘为偶数 思路：其实就是奇数x偶数+偶数乘以奇数个数考虑到奇奇偶的性质，可以求出奇数和偶数的个数。 MyCode: #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; #define int long long #define sc(x) scanf("%lld", &(x)) signed main() { int n; cin >> n; int num = n / 3, num1 = n % 3; int a = 2 * num + nu...

题意：给定整数，计算 思路：若，则上式为0。否则互质，可以用欧拉降幂: 较大，可以考虑用定理 定理要求模数是质数，尝试分解质因数，发现。 MyCode：  ```#include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=2e5+7,mod=999911659; typedef long long int ll; #define eb emplace_back #define ef emplace_front #define ep emplace #define fi first #define s...

筛法： vector<int>prime; bool vis[maxn]; void initial() { for (int i = 2; i < maxn ; ++i) { if (!vis[i]) prime.push_back(i); for (int j = 0,size=prime.size(); j < size; ++j) { if (i * prime[j] >= maxn) break; vis[i * prime[j]] = true; if (i % prime[j] == 0) break; } } }

题意：给定平面直角坐标系中的个矩形，求它们的面积并，即这些矩形的并集在坐标系中覆盖的总面积。输入接着输入行，每行输入表示矩形的左下角、右下角顶点坐标，这些坐标不一定是整数。 用一条竖直直线从左到右扫过整个坐标系，那么直线上被并集图形覆盖的长度只会在矩形的左右边界出发生变化(废话)。也就是说，整个并集图形可以被分成段，每一段在直线上的长度(记为)是固定的，因此该段的面积就是该段的宽度，各段面积之和即为所求。这些直线被称为扫描线，这种解题思路被称为扫描线法。 取出个矩形的左右边界作为扫描线(又是废话)，若一个矩形的左下角角顶点为、右下角顶点为，那么左右边界分别是四元组。Stars in Your ...

题意：在一个天空中有颗星星(看作平面直角坐标系)，已知每颗星星的坐标和亮度(都是整数)。求用宽为、高为的矩形(都是整数)能圈住的星星的亮度总和最大是多少(矩形边界上的星星不算)。 ，应该是不大于的 思路： 因为矩阵大小固定，所以矩形可以由它的任一顶点确定。我们可以考虑把矩形的右上角顶点放在什么位置，圈住的星星亮度最大。对一个星星，能圈住它的矩形右上角的顶点范围是：在左下角顶点为，右上角顶点为的矩形内，不包括边界上的点。这里用区域代指这个范围。 “矩形边界上的星星不算”，这个边界需要处理一下。因为星星的坐标都是整数，所以矩形右上角的顶点和和 的结果都是一样的，那么我可以区域是：在左下角顶点为，右...

总结：A、B、C不是白给题吗，D题dp，需要一些思维，E题拓扑排序(+dfs+字典树)，还是要转个弯cf的题都要转个弯 A. K-divisible Sum 题目大意:构造一个长度为n的数组,每个数是正整数,要求整个数组的和是k的倍数,并且整个数组最大的数最小.输出数组的最大值。 思路： 首先数组的和越小越好，同时数组的和肯定要比大，算出数组最小的和，最后再平均分配，如果有多则部分数组加一 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long int ll; inline ll read() ...

题意：给n个需要忽视的目录，m个需要保护的目录，求Gitignore的最小行数(有多少文件路径没被忽视--本应该被忽视的) 思路： 比赛的时候写了个神仙代码正解应该就是模拟，标记被保护了的路径名父级目录(a/b/c就只标记a、b)，因为输入保证不会同时出现:。接着枚举应该忽略的文件路径，如果某个父级目录或子级目录没有被保护，那么这个父级目录后面的子目录都要被忽视。 Code: #include <bits/stdc++.h> using namespace std; vector<string>v1,v2; map<string,bool>vis,pro; ...

题意: 给两个的扫雷图，问能不能至多反转个格子，把图B的的空白区权值和变成和图A相同。 思路： 这题有浓厚的气息，可惜打的有点少，没做出来，一看代码秒懂。既然是式的，样例必然是误导性的，就怕样例给好了让人一眼给看出来。其实答案只要输出A的原图或者反图即可，选原图还是反图不难，原图和反图是互补的，B不能改成A的原图，那么就一定能改成反图，反之亦然。下面证明反图的可性性：非地雷单元中的数字之和其实就相邻格子(八个方向上的相邻)不同点对的个数，'.'和'X'对换后相邻格子上的点该不同的还是不同、该相同的还是相同，不影响非地雷单元中的数字之和。 MyCode: #include <bits/st...

思路：由于，所以+1其实就是之中最大的那个数的二进制位加一，这个比赛的时候就想到了。直接写状态，上板子即可。比赛的时候只会求单个区间的问题，叠加的没想过，然后死活想不出来怎么去数位dp。叠加的不就是多个数随机组合吗，也就是对应二进制位的随机组合，居然没想到，2333。补题时的时候数位dp的状态不敢多开几维，状态一多就怕超时，忘了算复杂度数位dp的状态是： ，表示当前是第位，表示有效长度，表示的上界，表示的上界补了数位dp入门题后，能独立写出来，但是这题有个地方可以优化的，开始没优化超时了，嫖了一眼别人的代码，有效长度确定，且如果的高位都没有达到上界的话，假设现在是第位，那么第，太菜了。（好像不...

思路： 官方的题解：  没想过加下界，加上下界确实很简单。枚举的上下界，状态为： 写出状态后发现复杂度其实很低的，只要确保状态没问题就行了。 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long int ll; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch ...

思路： 借鉴某位大佬博客，很详细：点击这是一个进阶版的走网格，现在是从上面往左右或者下方走，而且起点和终点是不固定，但起点和终点所在的行数是固定的，同时，还有一些地方是不能走的。我们主要考虑行与行之间的关系，很明显，下一行的某个位置子肯定是由上一行的一些位置走过有来的。假设第行的情况为：  那么状态转移方程:(先大概了解下就行，最右边的矩阵是到的转移矩阵)举例子： 表示的是从起点到蓝色格子的方案数，看下图就能发现，它的值就是(假设不是第一行)前面所有路径经过绿色格子然后经过到达蓝色格子的方案数。(之所以用矩阵求，就是因为第行可以由第行线性表示，这种情况一般会用到矩阵) 由矩阵相乘的性质，可以求...

题意： 给你六个个数字，求对取余 ， 思路： 求广义斐波那契数列的第项，因为比较大，需要去找循环节，或者二进制转十进制运算，后者不注意容易T，但是我只会十进制，广义斐波那契数列的循环节是神仙找的规律。类比二进制的快速幂，有如下例子： 设，则：1、2、3、4、 MyCode： #include <bits/stdc++.h> using namespace std; typedef long long int ll; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch &gt...