题目 思路：每一次求取一个范围，然后判断之后的小方格是否满足范围。对于最后和第一个方格已经取定，需要特殊判断，细节见代码。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #define pii pair<int,int> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.ti...

题目 思路：要想差值最小，那么我们肯定是要使得这个二维数组的数尽可能平均起来，再看一下数据k<=n*n，故我们往数组中填1，并且要尽可能让每一行每一列的值相差最小，所以我们先将所有行和列的R C值先将其变为1，2，3，4…直到填完k个数。 填的方式如图： Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #define pii pair<in...

题目 思路： 首先可以知道如果我们要消灭长度>=4的回文串，那么这个大的回文串必然包含小的回文串。所以我们其实只要消灭小的回文串就可以了。其实就是干掉aaa、aba、aa这三种。那么对于很长的一串回文串我们要使其任何子串都无长度>=2的回文串，我们从头开始遍历。如果开始出现aa,贪心一下我们干掉第二个字符，这样会尽可能减少a与之后的形成回文串。类似，aaa干掉后两个，aba干掉第三个，细节见代码。 Code: #include<iostream> #include<string> using namespace std; int main() {  int ...

题目 题意：我有n个朋友，商店有m种商品，这m种商品按序号价格从小到大排列，对于每一个朋友我给出一个序号k，我可以直接给朋友序号k的商品价格的金钱或给朋友买一个序号小于k的商品，且每种商品最多只能买一次，问我需要花费的最少金钱？ 思路：将朋友的序号从大到小排序，由题意序号大的商品花费的金钱一定大于等于序号小的，所以我们只需要让序号大的朋友优先选用前面序号小的商品替代使花费金钱减少，直到前面的商品都已经被买了一次，然后后面的朋友直接给出对应序号金钱即可。 Code: #include<iostream> #include<algorithm> #define FAST i...

题目 思路：求一遍因数，取其中最小且满足<=k即可。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #define pii pair<int,int> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typede...

题目 题意：要做N天活，其中质量好至少(n+1)/2天，然后先g天好,b天不好。 思路：找出至少需要(n+1)/2天好的最少天数S，如果>n天，则答案为S,如果小于n天则剩下还要干活的天数全用质量差的也可，答案为n。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #define pii pair<int,int> #define F...

题目 思路：这是一道图论题，通过观察我们可以发现如果一个字母旁边出现过三种及以上的其他字母则无解，并且出现环时也无解如：ABCA因为如果有一个环，那必然有两条边，而这个环想要跳到下一个字母必然还需要一条边.其实正确的答案就是链和一些孤立的点了。那么我们就可以把相邻的两个字母连线，统计度数，DFS遍历一遍度数<2的点，链从度为1开始及度为0的孤立点。最后再判断是否有点没被访问到，当出现环时（因为不dfs度为2的点）会出现有点没被访问，细节见代码。 Code: #include<iostream> #include<string> #include<map&gt...

题目 老实说一开始并不知道这题是整除分块，就打表找规律做出来的。想着当一个数15 先除以15/1 = 15 15 /2=7 15/3=5 15/4=3 15/5=3 15/6=2 15/7=2 15/8=2…可以知道除到前面一定只有一个值，到了后面出现出现重复的后从3开始2 1 都会存在且重复。所以把从重复的数比其小的取完，再把前面分散的大的也取完就可以，因为有剪枝不会T掉。 最开始的代码： #include<iostream> #include<string> #include<map> #include<algorithm> #include...

题目 思路：从答案上来看我们可以知道密码数最多只有26种即26个字母，然后根据可以等效的的密码(即直接或间接拥有相同的字母)，我们让可以等效的密码放在一个集合里(对每个密码让每一个字母与第一个字母连边构成一个连通图（并查集）)，然后最后的集合数即为答案。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #define pii pair<int,i...

题目 思路：一开始我想错方向了，以为是向动态规划一样找递推然后推公式，后来发现其实只要用能得到最大的值减去最小的值就可以得出答案，然后找规律发现先下再右最大，先右再下最小，而且每次两个数相差为1 2 3 … x … x…3 2 1但是会到达一个峰值–min(x2-x1,y2-y1),维持这个峰值，再递减回到1，答案等于(1+2+…+x-1)*2+（x2+y2-x1-y1-1）*x。 这个大大写的很好 #include<iostream> #include<string> #include<map> #include<algorithm> #inc...

Beautiful Numbers 思路：先想想暴力的方法，对于m把从一到m每个数的位置求出来，如果最右边的减最左边的数+1等于m,则说明所有数覆盖的范围刚好是m不会有其他的数是一个1–m的置换。但暴力会T掉，我们再优化一下，其实我们求m+1是否满足可以利用前面求到的范围，只需对m+1这个数更新一下范围，再看是否符合即可，细节见代码。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #inclu...

题目 思路：要求每个金牌切的题高于银牌，银牌高于铜牌，铜牌高于铁牌，那么必然对于切题一样的队伍只会获得相同的牌。此时我们把切题一样的队看作一个个打包好了的队伍堆，给牌必须一堆一堆的给。且要求金牌一定小于铜牌和银牌，最后要使给出的牌子最多，且给的牌子<=总数/2，每个牌子>0。那么先贪心一下，让金牌只取一个切题最高的堆（留下更多的堆，为了满足每种牌子都有的给，且有多余的堆就给铜和银，不会造成牌子浪费），然后再给银牌取到正好大于金牌，剩下的还能给牌子且使牌子总数<=n/2全给铜牌，如果最终答案银牌或铜牌少于金则不存在，细节见代码。 Code: #include<iostre...

题目 思路：贪心一下，要使拥抱次数最多必然是以每一个月的末尾为最后一天时，假设b(n-3) b(n-2) b(n-1) b(n) …c(1) c(2)… c(n)…a(n-4) a(n-3) 完后挪一个 b(n-2) b(n-1) b(n) …a(n-3) a(n-2) 当a(n-2)>b(n-3)时会使值增加，那么肯定继续挪到最后一个时a(n)最优。而a(n-2)<b(n-3)时我们往回挪使值增大，也挪到c(n)时最优。 现在可以知道我们只需枚举每一个最后的点即可，再前缀和记录预处理一下，求每个截至时贪心比较即可得出答案，细节见代码。 Code: #include<iost...

列举大于等于2的整数，将其倍数划掉，往后遍历发现被划掉的直接略过，还没被划掉的则是质数（表示其不是前面任何一个数的倍数，也即没有除1和本身外的因子）。时间复杂度 O(NloglogN)，空间 O(N). Code:  int prim[Max], vis[Max], x = 0; //prim[x]第x个质数 void eratos(int n) {  for (int i = 2;i <= n;i++) {  if (!vis[i])prim[++x] = i; if (vis[i])continue; for (int j = 2;j * i <= n;j++) {  vis[...