思路  先通过打表求出前几项 再利用oeis得出规律 https://oeis.org/A070775 找出公式  代码 // Problem: 组合数问题 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/F // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace st...

思路  因为cnt>=11,所以找到一个cnt后把所有的数加起来取模即可 如果只有两个数，则输出另一个数  代码 // Problem: 划数 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #...

思路 把每一个都算出来发现之后发现有规律，前面的特判就行 代码 // Problem: 末三位 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/C // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define pb push_back #define...

思路  如果是括号序列必然满足是开头为'('结尾是')' 把括号序列回文后开头为')'结尾是'('，显然必不满足括号序列 所以当n>0不存在回文括号序列  代码 // Problem: 回文括号序列计数 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/A // Memory Limit: 1048576 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc...

做法：字典树  先把单词反向并转成小写存入字典树中，然后通过深搜的方式来匹配合适的单词 在搜索的过程中，如果找到一个符合的单词，不要直接输出，要找到最合适的那个，如下面这组易错组 易错组：Input 7 kirkirk 2 rik krikOutput rik krik  代码 // Problem: Spy Syndrome 2 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/111339 // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Power...

思路  因为树是二分图，所以只用两种颜色染色就行了特判下只有一个点的时候  代码 // Problem: 我的心是冰冰的 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/F // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define pb push...

前不久刚做了一题差分的题，看到这题联想起来了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...