H - Truck History （最小生成树&Prim） 题意：给定n个字符串，任意两字符串直接的距离为相同位置不同 字符的个数。求生成n个字符串所需要最小的权值和。 思路：显然是最小生成树问题，只是距离转化一下。n个字符串看成n个结点，任选一个结点进行prim算法即可。 AC代码： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e3+5; int a[N][N],n...

P - Vases and Flowers （线段树&二分） 思路：给定n个花瓶，m个操作，1：从L开始插F朵花，给花瓶中花为0的插入花，插入到不能插入为止。2：区间求和，并清零。 第二个操作简单，第一个操作要用到二分，查找最左端第一个插入花的位置和最后一个插入花位置。 AC代码： #include<cstdio> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int N=5e5+5; struct node{ //结构体线段...

A.牛妹的游戏（拉姆塞理论） 题目传送门 题意：给一无向无权图 n个点，m条边，问是否有长度为3的环或者3个点都互相不相连。 思路：当n>=6时，必定存在3个点互相相连或者互相不相连。当n<6时暴力即可。 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) #define jg(i,j,k) (a[i][j]&&a[i][k]&&a[j]...

B.病毒扩散(组合数学） 题目传送门 题意：本题的题意可以转换为t秒内走到(x,y)的病毒有多少。即可转化有多少种路径走到(x,y)（可以选择x+1,y+1,或不动） 显然根据乘法原理有：  AC代码： #include<bits/stdc++.h> using namespace std; const int mod=998244353,N=5e3; typedef long long ll; int c[N+5][N+5]; void fun(){ for(int i=0;i<=N;i++) c[i][0]=c[i][i]=1; for(int i=2;i<=N;i...

Q - Can you answer these queries? （线段树&区间开平方修改） 思路：线段树模板改编，需要对update进行剪枝，因为一个数最多开平方到1就为止了，判断一下这个区间和是否等于该区间长度即可。还有需要注意一点得是x,y未知，若x>y,需要swap一下。。。。 AC代码： #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; cons...

R - Transformation （线段树&lazy标记） 思路：由于都是对区间进行修改和询问，所以可以用lazy标记该区间是否相等。若不相等总能分成若干个相等小的区间进行求和。具体看代码。 AC代码： #include<cstdio> #include<cstring> using namespace std; const int N=8e6+5,mod=1e4+7; struct node{ int l,r,lz,s;//这里的a[i].s表示的是这个区间的数等于s 而不是这个区间的总和。  }a[N]; int n,m,op,x,y,c; int ks...

HDU1520.Anniversary party(树形DP&DFS） 题目传送门 思路：状态转移方程有两个：1.不选父结点，则加上子结点选或者不选的最大值，2.选父结点，则加上不选子结点的最大值。具体看代码。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=6e3+5; int dp[N][2],n,w[N],fa[N],a,b; vector<int>e[N]; void dfs(int u){ dp[u][0]=0,dp[u][1]=w[u]; for(auto v:e[u]){...

HDU2196.Computer(树形DP） 题目传送门 思路：每个结点的最大距离转化为到子树结点的最大距离与到上部最大的距离的较大值。到上部最大距离要分两种情况（在最长距离子树上和不在最长距离子树上）通过两次DFS就可完成状态转移。具体看代码。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+5; struct node{ int id,d; }; vector<node>e[N]; int dp[N][3],n; //dp[i][0],dp[i][1],dp[i][2] 分别表示结...

牛牛染颜色 （树形DP） 题目传送门 思路：  AC代码： #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int mod=1e9+7,N=1e6+5; typedef long long ll; int dp[N][2],h[N],cnt=1; struct edge{int to,nt;}e[N<<1]; void add(int u,int v){e[cnt]={v,h[u]},h[...

A. Road To Zero (贪心） 题目传送门 题意：给定非负整数x,y,两个操作1(花费a)：其中一个数加1或减1，操作2(花费b)：全部加1或减1，问让x=y=0的最少花费是多少。PS:坑爹题意：此处不需要让x=y=0为同时到达 思路：由于最后X=Y=0，显然X与Y的差值带来的花费是必须的，所以贡献1为abs(x-y) * a,其次再贪心比较一下花费2a都减1和花费b都减1谁小就行了。 AC代码: #include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int t; ci...

B. Binary Period（思维&字符串) 题目传送门 思路：显然最小周期不会超过2.pos1:全为1或全为0，只用输出本身即可，pos2:其他情况，显然由于s可以为两倍t长度，只用构造01即可，因为对于当前位的字符只能选择0或1，所以长度为2|t|的010101……串刚好满足条件。 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) int main(){ int ...

C. Yet Another Counting Problem（数论&取模） 题目传送门 思路:  AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b,q,c; ll fun(ll x){ ll cnt=x/c; ll re=x%c+1; return x-cnt*b-min(re,b); } int main(){ int t; cin>>t; while(t--){ cin>>a>>b>>q; if(a>b) ...

G - 免费馅饼 (DP&数塔） 思路：从最大时间开始倒序DP，状态转移即由前一时刻周围的三个位置得到。具体看代码。PS：一开始看成1e6，已知MLE。 AC代码： #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=1e5+5; int dp[N][12];//dp[i][j]第i时刻位置j的最大接到馅饼数.  int main(){ int n; while(~scanf("%d",&n)&amp...

P1004 方格取数 (双状态DP&四维DP） 题目传送门 思路：由于两个路径的最优值会互相影响，所以同时走选择最优方案才是正确解法，这样保证不会将一个数加两遍。若走两遍可能不是最优方案（因为第一次会影响第二次的方案）复杂度O(9^4)还是很小的。因为是滚动数组，所以可以降到三维，但没必要。 AC代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[10][10][10][10],a[10][10]; int main(){ int...