这道题有点像工程题的dp版本 特点就是比较繁琐 首先先枚举选取出来的行，列也行 然后定义状态f[i][j],表示前i列中选出j列时的最小分差和 然后状态转移即可 如果看不懂，说明基础不行，回去多补补题 #include<bits/stdc++.h> using namespace std; vector< vector<int> >gen(vector <vector<int> >matri,int row,int k){ int n=matri.size(),m=matri[0].size(); vector< vector&...

这个没有说明按顺序旅行

#include<bits/stdc++.h> using namespace std; #define ll long long ll a[101]; int main(){ int n; cin>>n; ll res=0; priority_queue<ll>q; for(int i=1;i<=n;i++) { cin>>a[i]; q.push(a[i]); } for(int i=35;i>=0;i--){ ll c=q.top(); if((1ll<<i)<=c){ if((1ll<<i+1)&...

这道题一遍就过，切水题真爽 这道题考察树上贪心，没看出是dp 对于遍历到每个节点的时候，如果发现当前没有变黑则选择 一种可以往上程度越高的方案变黑，对未来状态更优 #include<bits/stdc++.h> using namespace std; #define ll long long int a[100010]; vector<int>G[100010]; int res; struct node{ int ex; int now; }f[100010]; void dfs(int u,int cur){ if(G[u].size()==0){ f[u].ex...

结论 奇数加奇数等于偶数 偶数加偶数等于偶数 奇数加偶数等于奇数 我们一遍dfs求出有多少个节点到根的距离为奇数，有多少个节点到根的距离为偶数 若节点到根的距离为偶数，有两种情形 情形1：以根作为其中一个端点 情形二：任选二个节点连成路径 若节点到根的距离为奇数 直接任选二个节点连成路径即可 #include<bits/stdc++.h> using namespace std; #define ll long long #define maxm 100010 struct node{ ll c1,c2; }a[maxm]; ll res; vector<int>G[m...

#include<bits/stdc++.h> using namespace std; const int mo=10007; #define maxm 200010 #define ll long long ll w[maxm]; vector<int>G[maxm]; struct node{ ll v,sum1,sum2; }f[maxm],ne[maxm]; void dfs(int u,int pr){ vector<int>S; for(int i=0;i<(int)G[u].size();i++){ int v=G[u][i]; if(...

#include<bits/stdc++.h> using namespace std; #define ll long long ll f[210][10]; int main(){ int n,k; cin>>n>>k; f[1][1]=1; for(int i=2;i<=n;i++){ f[i][i]=1; f[i][1]=1; for(int j=2;j<i&&j<=k;j++){ f[i][j]=f[i-j][j]+f[i-1][j-1]; } } cout<<f[n][k]; return 0; } ...

这题比较水。 首先考察点就是最小生成树，对吧？ 然后水管相当于一条边 然后每个点可以建立井，那么就新加一个大源点，所有点往大源点连一条边即可 边权就是W[i] #include<bits/stdc++.h> using namespace std; #define s 406 #define ll long long struct node{ int x,y,w; bool operator <(const node&u)const{ return w>u.w; } }; int fa[500]; int Get(int x){ if(fa[x]==x)retu...

这道题是到矩阵生成树的变形题 我们不妨假设能走出去的为连通块1 把平面上的位置当成一个点，它永远指向一个点。而外部也相当于一个点 而它不指向任何一个地方，这就是一颗有向生成树 .相当于其他树的根。我们可以讨论它能指向哪颗树，即可 这样就抽象出矩阵生成树的板子了

#include<bits/stdc++.h> using namespace std; #define ll long long #define maxm 100010 const ll inf=1e12; int n; struct node{ ll p,w; bool operator <(const node &u)const{ return u.w<w; } }; ll dist[maxm]; vector<node>G[maxm]; ll dijk(int s,int t,int k){ for(int i=1;i<=n;i++)d...

这道题怎么想到是区间dp的。 对于长度为1的区间，很容易想到是1， 对于长度等于2的区间，我们要考虑两个因素，1是刷子的长度，2是两个区间 如果超出了刷子的长度，很明显答案要加1， 如果a[i]==a[i+1]a[i]==a[i+1]a[i]==a[i+1]明显答案可以继承， 再考虑长度为3的刷子的时候，也是一样 不妨假设断点设在2位子f[i][k],f[k+1][j]f[i][k],f[k+1][j]f[i][k],f[k+1][j]如果a[i]==a[k+1]a[i]==a[k+1]a[i]==a[k+1] 这里k从左到右，左开右闭，等于f[i+1][k]+f[k+1][j],即可以从f[...

令f[i][j]f[i][j]f[i][j]为长度为i时模3余数为j的方案数 题目要求f[n][0]f[n][0]f[n][0] f[i][j]f[i][j]f[i][j]由f[i−1][j−c]f[i-1][j-c]f[i−1][j−c]转移而来，c为余数 即对于当前数位有两种选择，一种是加入前面的方案中，另外是不加入之前的方案， 自成一组 #include<bits/stdc++.h> using namespace std; #define ll long long const int mo=1e9+7; #define maxm 55 ll f[maxm][3]; int ...

这道题用深搜可以，广搜也行 先找到所以可达的点，反向建图即可 然后从起点扩展，注意是字典序最短，而不是路径最短 在扩展的过程中，如果点没走过并且可达则加入队列，这个时候就可以直接break掉了 因为对于当前可达的点来说一定可达 是按照字典序走的 如果发现某个点的扩展点是遍历过的并且是可达的，那么存在一个循环 否则一定可以得到答案 这里要求记录答案，直接用前项链表即可 #include<bits/stdc++.h> using namespace std; #define maxm 100010 int vis[maxm],st[maxm]; vector<int>G[m...

这道题题意： 人必须从起点到终点，且不能越过墙，即使墙被火烧毁，因为人也不能越过火 火的扩展不受任何限制且往8个方向 #include<bits/stdc++.h> using namespace std; #define maxm 33 struct node{ int x,y,d; }; int dx[]={0,1,0,-1,1,1,-1,-1},dy[]={1,0,-1,0,-1,1,1,-1};//定义方向数组 int n,m; node s,t; node fire; string G[maxm]; int vis[maxm][maxm]; int vis2[maxm][...