前不久刚做了一题差分的题，看到这题联想起来了AcWing 100. 增减序列  做法：差分 思路：  每次操作把连续相邻的k个石子堆中的每堆石子数目加一,联想到差分设左右端点分别为l,r时，每次操作b[l]+=c;b[r+1]-=c;根据这一特性，模拟即可最后检查一遍可行性  代码 // Problem: 石子游戏 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP...

思路  先特判的情况，此时答案为0 我们可以枚举的值(0可以忽略)，并可知一共有n-1~1种情况因为最大值和最小值已经定了，那么其他的数在这两个值之间就行了我们可以枚举m,有多少种情况打表+oeis 可得当时，即枚举0个数，可得 推出当时，即枚举1个数，可得 推出当时，即枚举2个数，可得 推出当时，即枚举3个数，可得 推出很容易看出规律  所以最终答案为  如果T的话，预处理下逆元  代码 // Problem: 比武招亲（上） // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/B // Memory L...

题意 有样物品，对于第个物品，你需要买个，每个物品在非打折日买是2块钱，在打折日买是1块钱。每天你可以赚1块钱。一共有个打折日，在第天第种物品打折，最少需要多少天可以买完你需要的物品 做法：二分 思路  sale[]表示在允许天数内最晚打折时间 buy[]表示当前购买该物品的数量 二分天数，判断这些天数里能否买完所有物品  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int ...

做法：树形dp 思路  设dp[u][0]为以u为根的偶数个点的子树 dp[u][1]为以u为根的奇数个点的子树因为刚开始不存在奇数个点的子树，所以赋值为-inf 之后更新即可 转移按照规则偶=奇+奇=偶+偶奇=奇+偶=偶+奇  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i...

做法：字符串哈希+二分 思路：  我们可以先枚举两个字符串相同前缀的长度然后再枚举s前缀和t剩余后面部分有多少相同的部分，每次加上这一部分长度即可这一部分可以采用二分这部分长度来优化  // Problem: 武辰延的字符串 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/B // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bi...

比赛时只想到把表达式存起来，再转化成后缀表达式计算的方式，结果MLE了最后一个点看了题解之后还能这么维护 思路  我们可以维护一个的表达式 第一个值即为   如果后面接了一个 ，则变成 如果后面接了一个 ，则变成 如果后面接了一个 ，则变成 ；如果后面接了一个 ，则变成 。-----by九峰  代码 // Problem: 吴楚月的表达式 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/H // Memory Limit: 524288 MB // Time Limit: 2000 ms // // P...

思路  我们可以先求如果它的值为1，那么值也应该为1否则我们可把的值进行质因数分解分别求出每一个数的中有多少个质因数对每一个质因数的幂次取最小，再用快速幂乘起来即可  代码 // Problem: 邬澄瑶的公约数 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/J // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/std...

思路 关键点在任意时间内都通过率大于等于50%的题为签到题这句话每一次都进行判断是不是满足条件即可 代码 // Problem: 九峰与签到题 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/A // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #def...

思路  我们可以把所有人的不同等级的分数用结构体存起来然后根据分数大小及进行排序 根据双指针的做法来模拟这里注意：如果j遍历到等级A的分数，此前没有他的分数时，需要cnta++(cnta表示当前A等人数)如果j遍历到不是等级A的分数，此前有且仅有他的等级A的分数，需要cnta--如果i遍历到等级A的分数，此前没有他的分数时，需要cnta--如果i遍历到不是等级A的分数，此前有且仅有他的等级A的分数，需要cnta++  代码 // Problem: 内卷 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9983/B...

做法：动态规划 思路  用pre[i]存上一次'a'+i这个字母出现的位置，设dp[i][j]:前i个字符中长度为j的数量 如果一个字母上次出现过，需要减去dp[pre[s[i]-'a']-1][j-1]重复的子序列 每次删最少的字符即长度越长的子序列优先  代码 // Problem: Subsequences (hard version) // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/113788 // Memory Limit: 524288 MB // Time Limit: 4000 ms // //...

做法：01背包 思路   所以设,把a[i]看作价值，c[i]看作容量又因为c[i]有正有负，所以我们正负分开求求的是当容量为0时，价值最大。我们分别把对应的正负容量相加为0时价值相加求最大即可  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i...

思路  先把所有点为圆心的攻击范围能够消灭敌人的情况用二进制存下来（状态压缩，消灭用1表示），并去重 在这种几种情况从中选取k种，求消灭了敌人的人数<===> 二进制中1的个数  代码  // Problem: 重力坠击 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9983/C // Memory Limit: 524288 MB // Time Limit: 4000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor...

做法  因为中间的字符都可以被‘#’代替，所以只要考虑开头和尾端，并且答案一定是不存在或者无穷多个把每个字符串的前缀和后缀提取起来，然后比较依次比较每一位，如果其中有一位不同的话就一定不存在  代码 // Problem: 匹配串 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9983/F // Memory Limit: 524288 MB // Time Limit: 2000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor)...

思路   所以最后一次合成必须是牛牛合成且那时候存在至少奇数。又因为牛妹最优是每次都会选择两张奇数牌来使得合成一张偶数，奇数的数量一定要大于n-2.需要特判n=1的情况  代码 // Problem: 加法和乘法 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9983/J // Memory Limit: 524288 MB // Time Limit: 2000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #include...