#include<bits/stdc++.h> using namespace std; const int N=100010,M=400010; int h[N],e[M],ne[M],idx; int din[N]; int dout[N]; bool st[M]; int cnt; int type; int ans[M]; int p[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u) { //cout<<u<<endl; for(int &a...

https://codeforces.com/contest/1493/problem/C给定一个字符串，让你重新构造出一个和他等长的字符串，并且每个单词出现次数都是k的倍数。思路：从后往前贪心，我们枚举每个要第一次修改的点k，然后让1k-1都不相等，记录1k-1每个单词需要补的次数，然后从小到大枚举该位要修改的单词，并且更改cnt，然后sum=需要修改的值，如果sum+目前的位数（位数>=1）小于等于该字符串，就说明可以了。剩下的位置都填a就行了，有个疑问，剩下的位置为什么%k==0呢？其实蛮明显的，因为sum%k==0 && n%k==0 所以(n-sum)%k==0...

从1开始走，每次走两步，给定一个图，求最少加多少边，让整个图每个点都可以被遍历。思路：奇数环可以改变走的次序，然后整个图要联通，所以先把联通块变成树，如果存在奇数环那就不用加1，不存在再加1构造出奇数环就可以了～ #include<bits/stdc++.h> using namespace std; typedef long long ll; #define debug printf("---\n"); #define int long long const int N=1000010,M=2020; int a[N]; //vector<pair<int,int&g...

链接：https://ac.nowcoder.com/acm/contest/3800/F来源：牛客网 clccle一行𝑛个人来到了一个诡异的世界，她们需要去寻找逃出这个地方的方法——找到神秘的所罗门之匙她们决定从中随机选出一些人去寻找钥匙，并在其中选出一个队长，clccle不想知道自己有多大几率被选中，她只想知道一共有多少种选择的方案 （选出的人数要在1−𝑛之间，不同的队长算不同的方案）。方案数对1000000007取模  题目就是求看了大佬化简，真nb

链接戳这题意：给定n1,n2,n3,n4种菜肴和m1,m2,m3之间的关系来说明两者不能共存，求最小的花费。思路：这题需要数据结构来优化，由于这题符合动态规划的性质，例如abcd数组，a对b数组的影响对c是不具有后效性的，所以我们可以先从a出发递推到d，然后如果暴力咋做呢，也就是对于 ，那复杂度是 ,如何优化呢。我们把每条不符合的边插入到每个b的set中，然后对于a按照val来排序，枚举每个b，然后从小到大枚举a，如果b的set中不存在就可以提前break，这不仔细看复杂度比之前还高啊， 但是由于不符合题目要求的边的个数是 ,也就是第二层循环总共加起来不会超过m，那么复杂度就是代码： #inc...

题意：给定一个图，让最小生成树唯一，问最小去掉边权和。思路：在kruskal的思想下，重复的边一定是和已经合并两个集合之间的边权相等的。然后我看了大佬代码发现可以双指针？ #include<bits/stdc++.h> using namespace std; const int N=400010; typedef long long ll; int p[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } struct node{ int a; int b; int c; bool operator&l...

题目链接题意：有一棵树每个点有权值，有红色点和蓝色点从1出发，每次操作远离根走一步，红色点可以选择往自己子树走一步，蓝色点可以走到他的深度+1的节点，不一定要是子树，每次操作还可以交换蓝色和红色点，每次的贡献是｜aj-ai|，问和的最大值。思路：dp[i]代表红色点走到i的最大答案，转移有四种，有两种是不交换，也就是dp[fa[i]]+abs(a[i]-a[j]),由于dp[fa[i]]已经知道，那么最大值无非就是这一层的最大值或者最小值。还有另外两种是交换红蓝点，那么就是max(dp[fa[j]]+a[j]-a[u],dp[fa[j]]-a[j]+a[u]),那么就要维护每一层的dp[fa[...

链接戳这题意：给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。思路：由于区间异或和我们可以提前预处理前缀sum数组然后o（1）得到，我们可以先枚举右区间，然后由于两个不相交，我们要用个桶数组预处理出x-1之前某个相同区间异或值出现的次数，可以在for里面并排预处理完，x向前进一步说明x-1也进了一步，也就是说多出来的贡献就是以x-1为右端点的区间，我们只需要枚举左端点预处理出多出来的数就可以了。感悟：没想到可以先枚举左端点，思维还是老化了。ac代码： #include<bits/stdc++.h> using namespace std; ...

https://ac.nowcoder.com/acm/problem/50940思路：维护个对顶堆就行了。 #include<bits/stdc++.h> //#pragma GCC optimize ("O2") #define x first #define y second #define lson u<<1 #define rson u<<1|1 #define pb push_back #define pu pushup #define mk make_pair using namespace std; #define ll ...

https://ac.nowcoder.com/acm/problem/13249  题意：把整棵树涂黑，每个点都可以往根上涂k[i]个点，选最少的点。思路：可以想到叶子节点必须要选，然后一开始觉得没被选的点一定要被选其实是错的，例如该图  如果有部分点k很大不选就亏了，这样我们可以通过k[u]=max(k[u],k[son]-1)来更新最优的k，如何判断某点是否被覆盖？用个dp数组就行了，如果!dp[u]那么就选择该点，同时维护个数量就可以啦。 #include<bits/stdc++.h> using namespace std; const int N=100010; int...

题意：把每段区间第k大的数放到集合中，求集合中的第m大数。思路：二分+尺取，二分答案，然后算出第k大数大于等于x的区间数量，我们发现mid越大满足条件的数量越来越少，这就符合二分的单调性，同时尺取的话，也是满足的，i和j两个指针只会往右走，复杂度O（nlog(n)) 挺无语的，这个check函数写不明白，乱调调出来的。 #include<bits/stdc++.h> using namespace std; const int N=100010; #define int long long int n,k,m; int a[N]; bool check(int x)//第k大值大于...

https://atcoder.jp/contests/abc191/tasks/abc191_f有n个数，有n-1个操作，要么就是把两个数变成gcd，要么就是取min，问最后出现的数有多少种。思路：由于gcd(x,y)<=min(x,y),那么我们取的最大的数就是都取min，然后就是一些数的因数了，然后我们看看能不能凑成这个数，也就是这个数的所有倍数中是否gcd等于这个数，这个数j肯定是大于等于他在map中存的值的，因为我们 枚举a[i]的因数然后取讲mp[j]与a[i]取gcd，这个值是越来越非递增的。代码： #include<bits/stdc++.h> using n...

题意：给树上联通块染色，染色颜色不超过k的方案数.思路：按照dfs序便利，用dp[i][j]代表考虑前i个的dfs序列涂j种颜色的方案数，初始状态，dp[1][1]=k,转移呢，dp[i][j]=dp[i-1][j-1]+（k-j+1)dp[i-1][j-1].为什么这么转移呢，一种是用新的颜色，另一种是用与他的父节点相同的颜色。 #include<bits/stdc++.h> using namespace std; const int N=310; #define int long long const int mod=1e9+7; int dp[N][N]; int n,k;...

链接戳这题意：求 l<=x<=r 中 x的所有约数的最高位出现的次数思路：一开始以为是通过枚举因子反着枚举，看了题解才发现是暴力枚举每个最高数位，然后枚举范围通过整除分块来做，复杂度是 然后呢，枚举最高位，整除分块的思想就马上体现了，由于是求l～r中的，那么数位dp中的思想就马上体现出来了，l～r就是等价于solve(r)-solve(l-1),如何写solve呢，solve函数的含义就是1～x中能被最高位i整除的最高位出现的个数，显而易见一个因数p能把1～x中数整除的个数是 ,那么n/p这个值会出现在一段l～r的区间，这个右区间就是 我们慢慢得跳即可。代码： #include&l...