10.8 c
https://vjudge.net/contest/332874#problem/C
#include<iostream > using namespace std; const int maxn=2e5+10; char a[2][maxn]; int len,n; bool flag; void dfs(int x,int y,int d)//x,y为坐标点，d=1向上，d=2向下，d=3向右（由于可以旋转，3，4，5，6可以当成一个） { if(y>=len) return; if(x==1&&y==len-1&&d==3)//到达"终点" { flag=1; return; } if(x==0)//在第一行，向右或向下 { if(d==3) { if(a[x][y+1]=='1'||a[x][y+1]=='2') dfs(x,y+1,3); else dfs(x,y+1,2); } else if(d==2) { if(a[x+1][y]!='1'&&a[x+1][y]!='2') dfs(x+1,y,3); } } else if(x==1)//在第二行，向右或向上 { if(d==3) { if(a[x][y+1]!='1'&&a[x][y+1]!='2') dfs(x,y+1,1); else dfs(x,y+1,3); } else if(d==1) { if(a[x-1][y]!='1'&&a[x-1][y]!='2') dfs(x-1,y,3); } } } int main() { cin>>n; while(n--) { flag=0; cin>>len; cin>>a[0]; cin>>a[1]; if(a[0][0]=='1'||a[0][0]=='2') dfs(0,0,3); else dfs(0,0,2); if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
10.9
https://vjudge.net/contest/333223#problem/B
这道题考查的是最短路，floyd算法的应用
由于对于任意一条至少包含两条边的路径i--j，一定存在一个中间点，使得i--k+k--j=i--j，当然，对于不同的点k，i--k和k--j的长度值可能不同，
所以需要取一个最小值才是最短路径
e[i][j]=min(e[i][j],max(e[i][k],e[k][j]));
max是取从i--j中，以k为节点，能承受的最大噪音分贝值，然后从这些最大中再选出最小的那个路径，就是最短路径
#include<iostream> using namespace std; int e[1010][1010]; int inf=0x3f3f3f3f; int c,s,q; int main() { int c1,c2,d,x=1,a,b; while(cin>>c>>s>>q) { if(c==0&&s==0&&q==0)break; if(x!=1)cout<<endl; //初始化 for(int i=0;i<=c;i++) for(int j=0;j<=c;j++) if(i==j)e[i][j]=0; else e[i][j]=inf; for(int i=1;i<=s;i++) { cin>>c1>>c2>>d; e[c1][c2]=d; e[c2][c1]=d; } cout<<"Case #"<<x<<endl; for(int k=0;k<=c;k++) for(int i=0;i<=c;i++) for(int j=0;j<=c;j++) e[i][j]=min(e[i][j],max(e[i][k],e[k][j])); for(int i=0;i<q;i++) { cin>>a>>b; if(e[a][b]==inf) cout<<"no path"<<endl; else cout<<e[a][b]<<endl; } x++; } return 0; }
10.11
A - Slim Span
给你一个图，点以及权值，找出查找的两点间最小差值
kruskal算法，
#include<iostream> #include<algorithm> using namespace std; #define inf 0x3f3f3f3f int n,m,flag,f[5500]; struct node { int u,v,w; }s[5500]; bool cmp(node x,node y) { return x.w<y.w; } int getf(int v)//并查集找祖先 { if(f[v]==v) return v; else { f[v]=getf(f[v]); return f[v]; } } void kruskal() { for(int i=0;i<m;i++) { int cnt=0; for(int j=0;j<=n;j++) f[j]=j; for(int j=i;j<m;j++)//并查集合并 { int t1=getf(s[j].u); int t2=getf(s[j].v); if(t1!=t2)//两个点是否在一个集合里 { cnt++; f[t2]=t1; if(cnt==n-1) { flag=min(flag,s[j].w-s[i].w); break; } } } } } int main() { while(cin>>n>>m&&(n||m)) { for(int i=0;i<m;i++) cin>>s[i].u>>s[i].v>>s[i].w; sort(s,s+m,cmp); flag=inf; kruskal(); if(flag==inf) cout<<"-1"<<endl; else cout<<flag<<endl; } return 0; }
B - Resort
Valera's finally decided to go on holiday! He packed up and headed for a ski resort.
Valera's fancied a ski trip but he soon realized that he could get lost in this new place. Somebody gave him a useful hint: the resort has n objects (we will consider the objects indexed in some way by integers from 1 to n), each object is either a hotel or a mountain.
Valera has also found out that the ski resort had multiple ski tracks. Specifically, for each object v, the resort has at most one object u, such that there is a ski track built from object u to object v. We also know that no hotel has got a ski track leading from the hotel to some object.
Valera is afraid of getting lost on the resort. So he wants you to come up with a path he would walk along. The path must consist of objects v1, v2, ..., vk (k ≥ 1) and meet the following conditions:
- Objects with numbers v1, v2, ..., vk - 1 are mountains and the object with number vk is the hotel.
- For any integer i (1 ≤ i < k), there is exactly one ski track leading from object vi. This track goes to object vi + 1.
- The path contains as many objects as possible (k is maximal).
Help Valera. Find such path that meets all the criteria of our hero!
Input
The first line contains integer n (1 ≤ n ≤ 105) — the number of objects.
The second line contains n space-separated integers type1, type2, ..., typen — the types of the objects. If typei equals zero, then the i-th object is the mountain. If typei equals one, then the i-th object is the hotel. It is guaranteed that at least one object is a hotel.
The third line of the input contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ n) — the description of the ski tracks. If number ai equals zero, then there is no such object v, that has a ski track built from v to i. If number ai doesn't equal zero, that means that there is a track built from object ai to object i.
Output
In the first line print k — the maximum possible path length for Valera. In the second line print k integers v1, v2, ..., vk — the path. If there are multiple solutions, you can print any of them.
Examples
5
0 0 0 0 1
0 1 2 3 4
5
1 2 3 4 5
5
0 0 1 0 1
0 1 2 2 4
2
4 5
4
1 0 0 0
2 3 4 2
1
1
题意：n为所给数长度
第一排数0是表示山，1表示酒店
第二排数是表示可走的滑道
如样例2
5
序号 1 2 3 4 5
0 0 1 0 1
二排 0 1 2 2 4
0--1
1--2
2--3
2--4
4--5（只有3和5是酒店，2既可以到3又可以到4，不满足题目条件，所以选择包含尽可能多的节点）
答案为4--5
两个代码，思路异曲同工
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5+10; int n; int a[maxn],b[maxn],c[maxn],p[maxn]; bool vis[maxn]; int main() { cin>>n; memset(c,0,sizeof(c)); memset(vis,false,sizeof(vis)); for(int i=0;i<maxn;i++) p[i]=i; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { cin>>b[i]; c[b[i]]++;//记录出度 } for(int i=1;i<=n;i++) { if(c[b[i]]<=1) { p[b[i]]=i;//记录满足的节点 } } int dx=0,dc=1; for(int i=1;i<=n;i++) { if(vis[i]) continue; if(c[i]<=1) { int t=i,z=1;//z控制可执行的点，从一个跳到可执行的点 while(p[t]!=t&& !vis[i]) { if(c[t]>1)break; z++,t=p[t]; vis[t]=true; } if(a[t]==1&&z>dx) dx=max(dx,z),dc=i; } vis[i]=true; } cout<<dx<<endl; while(p[dc]!=dc) { cout<<dc<<" "; dc=p[dc]; } cout<<dc<<endl; return 0; }
将可执行的点存数组，倒序查找
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn=100000; int n,a[maxn],b[maxn],c[maxn]; int main() { scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&a[i]); for (int i=0;i<n;i++){ scanf("%d",&b[i]); b[i]--; } for (int i=0;i<n;i++) c[i]=0; for (int i=0;i<n;i++) if (b[i]!=-1) c[b[i]]++;//可走的路 int ret=0,reti=-1; for (int i=0;i<n;i++) if (a[i]==1){ int x=1; int j=i; while (b[j]!=-1 && c[b[j]]==1){//查到酒店跳转查看前一个 j=b[j]; x++;//记录次数 } if (x>ret){//最长 ret=x; reti=i; } } printf("%d ",ret); vector<int> output; for (int i=0;i<ret;i++){ output.push_back(reti);//倒序放入 reti=b[reti]; } for (int i=0;i<ret;i++){ if (i) printf(" "); printf("%d",output[ret-1-i]+1); } puts(""); return 0; }