思路  将整个数组进行分割，使每个子数组都包含1~k至少一次 我们可以选取每个子数组最后一个数，再加上任意一个数即可组成最短不存在子序列  代码 // Problem: The Cow Lineup // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/106586 // Memory Limit: 60000 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <iostream> #in...

做法：状压dp 思路 每个点与附近连边的点用二进制状态表示，1表示有边，0表示无边该状态选取的点也用二进制状态表示，1表示选了，0表示没选选取该点的值后的差值为该点的值减去转移前的差值 代码 // Problem: 树上博弈 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/E // Memory Limit: 524288 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bi...

思路  记录怪物的第一次第二次出现时间can[]表示叶妹妹是否具有攻击这个怪物的能力num[]表示叶妹妹不能攻击该怪物的数量sum表示叶妹妹能杀怪物的数量 根据贪心策略，每一次泽鸽鸽优先攻击自己没有攻击过且第二次出现早的怪物，这样子叶妹妹就越早能杀怪如果这一时刻不存在泽鸽鸽优先没有攻击过的怪物，那么泽哥哥就随便杀一只  代码 // Problem: 模仿游戏 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/G // Memory Limit: 524288 MB // Time Limit: 6000 ...

思路  先判断从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 ...