链接：https://vjudge.net/contest/303190#overview
A - New Year Transportation
A题水题；
此题是一道模拟题，类似于飞行棋的形式，从1开始，每次按照位置上标注出来的数目向前走，判断能否走到自己想到的位置。
#include<bits/stdc++.h> using namespace std; const int N=3e4+10; int a[N]; int n,t; int main() { cin>>n>>t; for(int i=1;i<n;i++) scanf("%d",&a[i]); int now=1; bool flag=0; int i=1; for(;i<n;) { //printf("i:%d\n",i); if(i==t) { flag=1; break; } i+=a[i]; } if(i==t) flag=1; if(flag) printf("YES\n"); else printf("NO\n"); }n个顶点，m条边，每次只能去掉一个点，消耗得能量为与它相邻得其他点的权值之和。求去掉所有点最小消耗。
转换一下：去掉每一条边，每条边的贡献值就是两端顶点权值最小的一个。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+10,M=2e3+10; struct edge { int u,v,next; }e[M*2]; int n,m; ll val[N]; int head[N]; bool vis[M*2]; int cnt; void add(int u,int v) { e[cnt]=(edge){u,v,head[u]};head[u]=cnt++; e[cnt]=(edge){v,u,head[v]};head[v]=cnt++; } ll bfs() { ll ans=0; for(int i=0;i<cnt;i++) { //printf("i:%d\n",i); if(vis[i]==0) { vis[i]=1; vis[i^1]=1; ans+=min(val[e[i].u],val[e[i].v]); } } return ans; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1;i<=m;i++) { int u,v;scanf("%d%d",&u,&v); add(u,v); } printf("%lld\n",bfs()); }构造新的字典序方式，使得输入的字符串是按照新的字典序排好的。
做法：找到每两个相邻串第一个字符不同的位置连一条无向边，然后拓扑排序
#include<bits/stdc++.h> using namespace std; const int N=120; char s[N][N]; int ma[30][30],du[30],n; vector<int>ans; bool topu() { for(int k=1;k<=26;k++) { int pos=-1; for(int i=0;i<26;i++) { if(du[i]==0) { pos=i; break; } } if(pos==-1) return 0; ans.push_back(pos); du[pos]=-1; for(int i=0;i<26;i++) if(ma[pos][i]) du[i]--; } return 1; } int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%s",s[i]+1); bool flag=1; for(int i=2;i<=n;i++) { int l1=strlen(s[i-1]+1); int l2=strlen(s[i]+1); int j=1; for(;j<=min(l1,l2);j++) { int c1=s[i-1][j]-'a'; int c2=s[i][j]-'a'; if(c1!=c2) { if(ma[c1][c2]==0) { ma[c1][c2]=1; du[c2]++; } break; } } if(j==min(l1,l2)+1&&l1>l2) { flag=0; break; } } if(!flag) { printf("Impossible\n"); exit(0); } if(topu()) { for(int i=0;i<ans.size();i++) printf("%c",ans[i]+'a'); } else printf("Impossible\n"); }D - Strongly Connected City
结论题。
题意，能否从任意一个十字路口到达所有的十字路口。
做法：最外围的是一条回路即可
#include<bits/stdc++.h> using namespace std; const int N=30; char s1[N],s2[N]; int n,m; int main() { cin>>n>>m; cin>>s1+1; cin>>s2+1; bool flag=0; if(s1[1]=='<'&&s1[n]=='>'&&s2[1]=='v'&&s2[m]=='^') flag=1; if(s1[1]=='>'&&s1[n]=='<'&&s2[1]=='^'&&s2[m]=='v') flag=1; if(flag) printf("YES\n"); else printf("NO\n"); }给出树的顶点数n和树的直径d和最深深度h。构造这么一棵树。不能构造输出-1；
做法：若d！=h，先构造最深的h，然后构造d-h，剩余的全部连在1的下面
若d==h，先构造h，剩余的全部连在1的某个孩子下且该孩子不能为叶子结点
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int du[N],n,d,h; struct node { int a,b; }; vector<node>que; int isyezi=0; void slove1() { int cnt=1; for(int i=1;i<=h;i++) que.push_back((node){cnt,++cnt}); if(cnt==2&&cnt<n) { printf("-1\n"); exit(0); } int t=cnt; for(int i=t+1;i<=n;i++) que.push_back((node){2,++cnt}); } void slove2() { int cnt=1; for(int i=1;i<=h;i++) que.push_back((node){cnt,++cnt}); que.push_back((node){1,++cnt}); for(int i=2;i<=d-h;i++) que.push_back((node){cnt,++cnt}); int t=cnt; for(int i=t+1;i<=n;i++) que.push_back((node){1,++cnt}); } int main() { cin>>n>>d>>h; if(d-h>h) { printf("-1\n"); exit(0); } if(d==h) slove1(); else slove2(); for(int i=0;i<que.size();i++) printf("%d %d\n",que[i].a,que[i].b); }题意：构造一个图，给出节点数n和边m。
每个顶点只能有三个字母：a,b,c；其中a与c不能相邻。
做法。补图为二分图即可。若是孤立点，则赋值为b。若不是二分图，不符合题意输出-1.若是二分图，染色法赋值a和c。剩余的全部赋值b，最后bfs_1判断是否合法即可
#include<bits/stdc++.h> using namespace std; const int N=550; int ma[N][N]; int newma[N][N],ans[N]; int vis[N]; int n,m; bool bfs(int x) { vis[x]=1; queue<int>que; que.push(x); ans[x]=3;// bool flag=1; while(que.size()) { int u=que.front();que.pop(); for(int i=1;i<=n;i++) { if(i==u) continue; if(newma[u][i]) { flag=0; vis[i]=1; if(ans[i]==0)// { que.push(i); if(ans[u]==1) ans[i]=3; else if(ans[u]==3) ans[i]=1; else ans[i]=2; } else if(ans[u]==ans[i]) { //printf("u:%d i:%d\n",ans[u],ans[i]); return 0; } } } } if(flag) ans[x]=2; return 1; } bool bfs_1(int x) { vis[x]=1; queue<int>que; que.push(x); while(que.size()) { int u=que.front();que.pop(); for(int i=1;i<=n;i++) { if(i==u) continue; if(ma[u][i]) { if(!vis[i]) { que.push(i); vis[i]=1; } if(abs(ans[u]-ans[i])>=2 )return 0; } } } return 1; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); ma[u][v]=ma[v][u]=1;//原图 } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j) continue; if(ma[i][j]==0) newma[i][j]=newma[j][i]=1;//补图 } for(int i=1;i<=n;i++) { if(!vis[i]) if(!bfs(i)) printf("No\n"),exit(0);//判断二分图 } memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) if(!ans[i]) ans[i]=2; int flag=1; for(int i=1;i<=n;i++)//判断原图中染色是否合法 { if(!vis[i]) if(!bfs_1(i)) printf("No\n"),exit(0); } if(!flag) printf("No\n"),exit(0);//不合法 printf("Yes\n"); for(int i=1;i<=n;i++) printf("%c",ans[i]+'a'-1); }
题目大意：Jzzhu是一个国家的总统，这个国家有N座城市，以1为首都，已经存在了M条公路，给定M条路。并且还有K条铁轨，铁轨均有首都出发，连接si，距离为yi。现在Jzzhu想要节省经费，拆除一些铁轨，问说最多能拆除多少个铁轨，要求每座城市与首都的最短距离不变。
解题思路：最短路，多加一个标记数组，每个si标记1，如果这些点的最短距离被更新，则将对应si的标记清为0，最后统计一下剩余的标记，即为不能拆除的铁轨
不能先跑最短路，然后判断输入的火车距离与最短路比较ans++。因为这些最短路没有算铁路的路径。有可能某个点到1的最短路刚好要经过另一个火车铁路
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=1e18; const int N=1e5+10,M=3e5+10; int n,m,k; ll dis[N]; vector<int>G[N]; vector<ll>val[N]; int vis[N],p[N]; struct node { int a; ll w; bool operator <(const node &o) const { return o.w<w; } }; int bfs() { priority_queue<node>que; que.push((node){1,0}); for(int i=1;i<=n;i++) dis[i]=inf; dis[1]=0; for(int i=1;i<=k;i++) { int u;ll w; scanf("%d%lld",&u,&w); if(dis[u]>w) { dis[u]=w; p[u]=1; if(vis[u]==0) vis[u]=1,que.push((node){u,dis[u]}); } } while(!que.empty()) { node u=que.top();que.pop(); vis[u.a]=0; for(int i=0;i<G[u.a].size();i++) { int v=G[u.a][i]; ll w=val[u.a][i]; if(dis[v]>=dis[u.a]+w&&p[v]) { p[v]=0; } if(dis[v]>dis[u.a]+w) { dis[v]=dis[u.a]+w; if(vis[v]==0) que.push((node){v,dis[v]}),vis[v]=1; } } } int ans=0; for(int i=1;i<=n;i++) ans+=p[i]; return k-ans; } int main() { cin>>n>>m>>k; for(int i=1;i<=m;i++) { int u,v; ll w; scanf("%d%d%lld",&u,&v,&w); G[u].push_back(v); G[v].push_back(u); val[u].push_back(w); val[v].push_back(w); } printf("%d\n",bfs()); } /* */题意 给出一张图，现在某些点之间的边染色。问两点路径中有几种颜色。
可以转换成不同颜色设一个连通块。问两个点在哪几个连通块出现过
做法：根据不同的颜色设一个单独的并查集即可
#include<bits/stdc++.h> using namespace std; const int N=120; struct node { int fa[N],n; void init(int n) { this->n=n; for(int i=1;i<=n;i++) fa[i]=i; } int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } void unit(int x,int y) { int fx=find(x); int fy=find(y); if(fx!=fy) fa[fx]=fy; } bool same(int x,int y) { return find(x)==find(y); } }e[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=100;i++) e[i].init(100); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); e[w].unit(u,v); } int q; cin>>q; while(q--) { int u,v,ans=0; scanf("%d%d",&u,&v); for(int i=1;i<=100;i++) if(e[i].same(u,v)) ans++; printf("%d\n",ans); } }
