div3真好啊 养老
A. Boring Apartments 直接模拟
B. Yet Another Bookshelf 模拟
C. Dominant Piranha 不会
D. Districts Connection 模拟，按树每个deep去分层连就行了
#include<bits/stdc++.h> #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll qpow(ll a,ll n){ll r=1%P;for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} const int maxn=3e5+10; int a[maxn]; int pre[maxn]; int suf[maxn]; int id[maxn]; bool cmp(int x,int y) { return a[x]<a[y]; } int main() { int t; cin>>t; while(t--) { int n; cin>>n; int flag=1; int s; for(int i=1;i<=n;i++) {cin>>a[i]; if(a[i]!=a[i-1]&&i!=1) { flag=0; } id[i]=i; } if(flag) cout<<"NO"<<endl; else { cout<<"YES"<<endl; sort(id+1,id+1+n,cmp); /*for(int i=1;i<=n;i++) cout<<id[i]<<' '; cout<<endl;*/ int root=id[1]; for(int i=2;i<=n;i++) { if(a[id[i]]!=a[root]) {s=i;break;} } for(int i=s;i<=n;i++) { if(a[id[i]]!=a[id[i-1]]&&i!=s) root=id[i-1]; cout<<root<<' '<<id[i]<<endl; } root=id[n]; for(int i=2;i<s;i++) { cout<<root<<' '<<id[i]<<endl; } } } }
E. Two Round Dances 不会
F. Zero Remainder Sum 四维DP 复杂度70^5
开个dp[i][j][t][p] i代表第几行 j代表当前dp到第几列 t代表当前选了多少个，然后p代表余数，dp[i][j][t][p] 就是第i行 到j列时，选个t个数，这些数%k的余数是p的最大值
然后dp就行了
dp完了统计一下答案 再按行dp一下就行了 f[i][p] 同理，i是第i行 p是余数 所以最后答案是f[n][0]
#include<bits/stdc++.h> #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll qpow(ll a,ll n){ll r=1%P;for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} const int maxn=3e5+10; int a[80][80]; int pre[maxn]; int suf[maxn]; int id[maxn]; int dp[80][80][80][80]; int f[80][80]; int main() { int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int v=a[i][j]; for(int jj=0;jj<j;jj++) for(int t=0;t<=jj;t++) { if(t+1>m/2) break; for(int p=0;p<k;p++) { if(p>0&&dp[i][jj][t][p]==0) continue; dp[i][j][t+1][(p+v)%k]=max(dp[i][j][t+1][(p+v)%k],dp[i][jj][t][p]+v); //printf("%d %d %d %d %d ",i,j,t+1,(p+v)%k,dp[i][j][t+1][(p+v)%k]); } } } for(int p=0;p<k;p++) for(int j=1;j<=m;j++) { for(int t=0;t<=m/2;t++) { dp[i][0][0][p]=max(dp[i][0][0][p],dp[i][j][t][p]); } } } /*for(int i=1;i<=n;i++) { for(int j=0;j<k;j++) cout<<dp[i][0][0][j]<<' '; cout<<endl; }*/ for(int i=1;i<=n;i++) { for(int p1=0;p1<k;p1++) { for(int p2=0;p2<k;p2++) { if(p2>0&&f[i-1][p2]==0) continue; if(p1>0&&dp[i][0][0][p1]==0) continue; f[i][(p1+p2)%k]=max(f[i][(p1+p2)%k],dp[i][0][0][p1]+f[i-1][p2]); } } /*for(int p=0;p<k;p++) cout<<f[i][p]<<' '; cout<<endl;*/ } cout<<f[n][0]<<endl; }
G. Reducing Delivery Cost 最短路板子题
先把那k个route给跑完 求出最短路，（正着跑一边倒着跑一边）
然后这样枚举删去那个边然后每次更新就行了（你要记录每次跑完的最短路）
复杂度（2*k*m*logn+m*k） k*m*logn这个是跑2k次最短路 m*k是枚举每条边然后更新的复杂度
10.21更新：
然后这里可能有萌新看博客学习的 我也友好的解释一下 ；；
你删边的时候，比如你从1 为源点开始跑最短路 求1-n的最短路，然后从n为源点跑一次最短路
然后我们发现 如果把一条 边置成0 ，这条边链接的是x，y点，只需要把最短路更新成 dis（1，x） 和从dis（n，y） 相加就可以了 中间的dis（x，y）就被置成0了
所以要正反跑最短路 就是这个原理。
#include<bits/stdc++.h> #define fi first #define se second #define io std::ios::sync_with_stdio(false) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll qpow(ll a,ll n){ll r=1%P;for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} const int maxn=1e3+10; int n,m,k; vector<int> G[maxn]; ll d[maxn][maxn][2]; ll dis[maxn][maxn]; void djs(int s,int id,int f) { priority_queue<pii,vector<pii>,greater<pii> > que; for(int i=1;i<=n;i++) { d[id][i][f]=INF; } // memset(d,INF,sizeof(d)); d[id][s][f]=0; que.push(make_pair(0,s)); while(!que.empty()) { pii p=que.top(); que.pop(); int v=p.second; if(d[id][v][f]<p.first)continue; for(int i=0; i<G[v].size(); i++) { int to=G[v][i]; if(d[id][to][f]>d[id][v][f]+dis[to][v]) { d[id][to][f]=d[id][v][f]+dis[to][v]; que.push(make_pair(d[id][to][f],to)); } } } } vector<pii> aa; vector<pii> g; ll dd[maxn]; int main() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; dis[x][y]=dis[y][x]=z; G[x].push_back(y); G[y].push_back(x); g.push_back({x,y}); } for(int i=1;i<=k;i++) { int x,y; cin>>x>>y; aa.push_back({x,y}); djs(x,i,0); djs(y,i,1); dd[i]=d[i][y][0]; } ll _min=1e18; for(auto i:g) { ll t=0; int x=i.fi; int y=i.se; for(int j=1;j<=k;j++) { t+=min(d[j][x][0]+d[j][y][1],min(dd[j],d[j][x][1]+d[j][y][0])); } _min=min(t,_min); } cout<<_min<<endl; }