题目大意 现在有n个集合，让你完成以下操作 往l~r的集合中加入一个数x 查询l~r的集合内的数是否能构成三角形 解题思路 如果一个集合内构不成三角形，那么要使里面的数最多，集合就形如1,1,2,3,5,8... 不难发现这是个斐波那契数列，可以推出45位以后就大于10910^9109了，所以一个集合只用维护45个数 对于每次查询，只加45个数即可 时间复杂度O(45×n)O(45\times n)O(45×n) code #include<cstdio> #include<cstring> #include<iostream> #include&l...

题目大意 给出一个攻击序列和s，对于一个k，敌人每k秒可以恢复一个大小为s的护盾，而你要找攻击序列的一个子序列来攻击敌人（每个数表示造成的伤害），对于所有k∈[1,n]k\in[1,n]k∈[1,n]，求出最多造成伤害 解题思路 题目可以看作每一轮有一个大小为s的盾，且可以攻击k次 可以先对攻击序列进行排序，枚举攻击多少轮，然后贪心求攻击伤害 当无法破盾时，s会大于攻击伤害，那么会造成负贡献，而在枚举更小的轮数时，这个负贡献会被舍去，所以这种枚举的方法是正确的 枚举攻击轮数的时间复杂度是调和级数，所以时间复杂度是 O(n log n)O(n\ log\ n)O(n&nbs...

题目大意 给你一个01串，如果一位是1，那么可以把当前位和上一位取反，两个人轮流取，取不了时败，问先手是否必胜 解题思路 把当前位和上一位取反可以看做是往前穿一，那么就是阶梯博弈 code #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100100 using namespace std; int T,n,ans; char s[N]; int main() { scanf("%...

题目大意 给你一棵树，让你添加一些边，使原树是严格次小生成树，要求添加的边的边权最小 解题思路 要让原树是次小生成树，那么就要构造一棵最小生成树，又因为要边权最小，那么找一条比边权大于1的边，在两个端点之间连一条边权为1的边即可（要保证更小） 如果没有边权大于1的，那就是无解 code #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n,x,y,z,p,s...

题目大意 给你一个数x，让你将他分成k个质数的和，要求看最小 解题思路 根据哥德巴赫猜想，当x偶数的时可以分成两个质数的和 那么如果x为偶数，就枚举其中一个质数，判断另一个是否为质数，如果是奇数，那么分出一个1再处理 code #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 10000100 #define NN 1000010 using namespace std; ll T,x...

题目大意 初始你在坐标轴的0处，你要走到n处 第x步你可以进行以下操作： 向右走x步 向左走一步 解题思路 先尽量往右走，直到再走一步会超过n，这个过程可以二分处理 设现在走了l步，那么可以在任意一步的前面往左走一步，这样会使后面的步数都+1,那么会造成-1~l-1步的贡献（往左走了一步，所以要减一） 又因为n-l<l+1，如果n-l<l那么答案+1，否则答案+2（往右走一步再往左走一步） code #include<cstdio> #include<cstring> #include<iostream> #include<algo...

题目大意 有一个n*n的网格，现在已经有若干点已经被感染了，每个感染点会对旁边的点进行扩散，每新增一个感染点就有c点代价 或者可以在两个点之间以1点代价建一堵墙，可以防止两个点之间的直接扩散（如果旁边没建那可能会从旁边绕过来） 现在让你求最小代价 解题思路 数据不是很大，可以考虑用网络流最小割 从s对每个感染点建inf的连边（可以无限扩散），对相邻的点之间建一条双向度为1的边（用1的代价可以防止扩散，因为墙的两边分别是感染和未感染的，所以建双向边不会有问题），再让所有原来未感染的点对t连一条c的边（感染代价为c） 建完图后跑最小割即可得到最小代价 code #include<queu...

题目大意 设f(x)函数是x在小数后第几位开始循环（如果不是循环小数即为0），如 现在给出l,r，让你求 解题思路 不难发现，对除数质因数分解，如果存在非2非5的数，那么就是循环的 而每出现一个2或5就会让循环开始的位置往后一位，同时出现则只计算一次，所以总贡献就是 所以只需枚举2和5的个数，然后容斥减去还有2,5没计算的情况和没有别的因数的情况，就是当前方案的数量，再乘上该方案的贡献，最后求和即可 （这里推荐一个更为详细且带有证明的题解，作者QuantAsk orz，题解：https://quant-ask.blog.csdn.net/article/details/120467008 ）...

题目大意 给你n个点，f函数的值，现在你要构造一棵树，一个度数为k的点有f(k)点贡献，问你最大贡献 解题思路 对于一棵树，除了根节点每个点都有一个父亲节点，而一个点的度数就是父亲节点数量+子节点数量 那么可以先构造一颗所有点都连向1的数（1为根节点），且先不计算根节点的贡献，那么贡献就是(n-1)*f(1) 注：下文只对深度为2的点进行修改，深度大于2的点的儿子关系已经确定，无需修改,不然会出现重复计算 之后考虑把一些点移到其他点的儿子中，设为1的儿子有i个时的最大贡献，那么每次可以以x的代价制造f(x+1)-f(1)点贡献（x<i，将1的x个儿子移到某个点的儿子中，该点度数从1变为...

题目大意 给你一个字符串，问你最少交换次字符可以构成“cocacola”（每次交换两个字符） 解题思路 因为数据较小，所以如果一个位置不合法，直接枚举和后面的哪个字符交换（前面的已经构造好了） code #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int ans; char s[100]; string str; void dfs(int x,int now...

题目大意 二进制上的若干位不能为1，问是否能组成x 解题思路 直接判断x的二进制在不能有1的位置上是否有1 code #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define ull unsigned long long using namespace std; int n,k,pp,x; ull s; int main() { scanf("%d%d%llu",&am...

题目大意 有n个数，依次加进栈中，每次加入前将栈顶比大的所有元素弹掉，加入后记为栈的大小 现在给你b中的一些数，让你求a数组的一种合法方案，其中1~n在a中各出现了一次 解题思路 每次把栈顶比大的所有元素弹掉，使得栈是单调递增的 对于所求a数组，可以先连边，表示该点要比哪个点大，然后跑拓扑序 那么可以遍历每个b，如果当前栈中剩余的数大于了个，那么把这些数弹掉，且弹掉的数中最小的数连向i（这些数要比大才能被弹掉），把i加进栈中，然后连向栈顶（栈顶不会被弹掉） 最后跑拓扑序编号 代码 #include<queue> #include<cstdio> #include&l...

路线规划 nowcoder 217603 题目大意 给一个无向连通图，问你在经过的边最少的前提下，从1走过所有点，再走回1的最短距离 解题思路 对于求出来的路线中，设从1到最后一个点的路径为干线（如图下图，最后一个点为5，干线为1-2-3-5）对于干线上的边（如2-3），来回各会走两遍而对于非干线上的边，在去的时候，要离开干线，再回到干线，共两遍而回来的时候不用走所以无论是干线上的边还是非干线上的边，都会走两遍那么对该图做最小生成树，使得所有点都到过一遍，然后乘2即可 代码 #include<cstdio> #include<cstring> #include<i...

照看小猫 nowcoder 217602 题目大意 有n只小猫，对于第i只小猫，给它取一个以小写字母组成的名字（长度不大于），问你使所有小猫名字不同的方案数 解题思路 对于第k只小猫，名字有j位的方案数是那么方案总数为：对于，第j只小猫选的名字不一定在当前小猫的方案总数中而对于，第j只小猫选的名字一定在当前小猫的方案总数中所以可以按a从小到大排序当计算第i只小猫的方案总数时，减去a值比i小的个数因为这些猫选的方案已定会使i的方案总数-1计算完所有小猫的种数后，乘在一起即可 代码 #include<cstdio> #include<cstring> #include&lt...