思路  先判断从s开始是不是能走到t 二分中位数的大小如果相邻的两个点都大于等于mid，中位数能达到mid如果大小大小交替走也成立  代码 // Problem: 美丽的路径 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/A // Memory Limit: 524288 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using nam...

题意 给你一个序列，问你有多少个子序列它们的最大公约数为1 思路  先求出这些数中有多少个数含因子i 公约数为i的序列数为  代码 #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++) #define per(i,b,a) for(int i=(b)...

题意 每走一条边都需要花费1点能量。每经过一个特殊点都可以将当前能量值补充到能量上限。给定起点s和终点t，求可从点s到达点t的最小能量上限。 做法：二分 思路  对能量上限答案进行二分 按照能量花费跑最短路，每次遇到特殊点能量恢复到能量上限  代码 // Problem: Weak Memory // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/109519 // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Powered by CP Editor (h...

思路  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; #...