思路  010会分出两种情况100和001100会分出两种情况100和010001会分出两种情况100和001  经过i次交换后，可以得到个010 当n为偶数，当n为奇数，  代码 // Problem: PLEASE // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/111563 // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/...

思路 dp[i][j]表示到第i个字符串匹配到k串第j位的方案数我们可以优化第一维利用字符串哈希匹配两个字符串是否相等 代码 // Problem: 九峰与子序列 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/E // Memory Limit: 262144 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace...

思路  先按照颜色把每条狗存放起来 对它们的亲密度进行二分，求出第 k 对亲密关系的狗的亲密度是多少 calc表示求小于等于x的有多少对数，我们利用异色点对数=总点对数-同色点对数来求 然后在枚举该其亲密度，把第 k 对亲密关系的狗输出  代码 // Problem: 温澈滢的狗狗 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://...

思路  根据贪心的策略，优先装备战斗力大的装备。 用连通块的思想把符合装备的两人相连，如果是一人则自环利用连通块和st数组来维护这个人有没有装备  代码 // Problem: 魏迟燕的自走棋 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/F // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> ...

思路  因为具有覆盖性，所以从后往前填最优 如果一个位置没有被填过，则用nex记录这个矩形的最右端（因为之前的位置已经被填过了，之后填这后面的位置就行了） 否则就转移到之前记录的nex的位置  代码 // Problem: 九峰与蛇形填数 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9984/G // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include...

做法  先把原始边存起来方便修改 需要查询只用编号在[l,r]范围内的边时，再把这些边提取出来跑最小生成树即可  代码 // Problem: 动态最小生成树 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/H // Memory Limit: 1048576 MB // Time Limit: 10000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace...

思路  因为走重复的路不被计算，所以很容易看出这是求最小生成树 注意用long long  代码 // Problem: 天空之城 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/J // Memory Limit: 1048576 MB // Time Limit: 10000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define ...

思路  因为求到达终点的最短距离，所以我们用bfs来求 注意单位转换  代码 // Problem: 贪吃蛇 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/I // 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 ...

思路  根据嵌套得出不等式 化简后得出贪心策略后排序 因为会爆long long，用__int128替换即可  代码 // Problem: 机器人 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/G // Memory Limit: 1048576 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; ...

思路  先通过打表求出前几项 再利用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...