Codeforces Beta Round #29 (Div. 2,Codeforces format) http://codeforces.com/contest/29 A 1 #inc
... .
Codeforces Beta Round #29 (Div. 2,Codeforces format)
http://codeforces.com/contest/29
A
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,mid,rt<<1 4 #define rson mid+1,r,rt<<1|1 5 #define sqr(x) ((x)*(x)) 6 #define pb push_back 7 #define maxn 1000005 8 typedef long long ll; 9 typedef unsigned long long ull;10 const ull MOD=257;11 /*#ifndef ONLINE_JUDGE12 freopen("1.txt","r",stdin);13 #endif */14 15 16 int main(){17 #ifndef ONLINE_JUDGE18 // freopen("1.txt",stdin);19 #endif20 std::ios::sync_with_stdio(false);21 int n;22 cin>>n;23 int a[105],b[105];24 for(int i=1;i<=n;i++){25 cin>>a[i]>>b[i];26 }27 int flag=0;28 for(int i=1;i<=n;i++){29 for(int j=1;j<=n;j++){30 if(i!=j){31 if(a[i]+b[i]==a[j]&&a[j]+b[j]==a[i]){32 flag=1;33 }34 }35 }36 }37 if(flag) cout<<"YES"<<endl;38 else cout<<"NO"<<endl;39 }. View Code .
B
模拟
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin);19 #endif20 std::ios::sync_with_stdio(false);21 double l,d,v,g,r;22 cin>>l>>d>>v>>g>>r;23 double ans=0;24 if(v*g>d) ans=l/v;25 else{26 l-=d;27 double t=d/v;28 ans=t;29 double tt=g+r;30 int flag=0;31 while(t>=0){32 t-=g;33 if(t>=0){34 t-=r;35 }36 if(t<0) flag=1;37 }38 // cout<<t<<endl;39 if(flag==1){40 ans-=t;41 }42 ans+=l/v;43 }44 printf("%.7f/n",ans);45 }. View Code .
C
找出一个度为1的点，然后跑dfs。因为值为1e9，所以需要离散化
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin);13 #endif */14 15 int n;16 vector<int>ve;17 int a[100005];18 int b[100005];19 int d[100005];20 vector<int>V[100005];21 22 int getid(int x){23 return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;24 }25 26 void dfs(int pos,int pre){27 cout<<ve[pos-1]<<" ";28 for(int i=0;i<V[pos].size();i++){29 if(V[pos][i]!=pre){30 dfs(V[pos][i],pos);31 }32 }33 }34 35 int main(){36 #ifndef ONLINE_JUDGE37 // freopen("1.txt",stdin);38 #endif39 std::ios::sync_with_stdio(false);40 cin>>n;41 for(int i=1;i<=n;i++){42 cin>>a[i]>>b[i];43 ve.pb(a[i]);44 ve.pb(b[i]);45 }46 sort(ve.begin(),ve.end());47 ve.erase(unique(ve.begin(),ve.end()),ve.end());48 int pos,pos1,pos2;49 for(int i=1;i<=n;i++){50 pos1=getid(a[i]);51 pos2=getid(b[i]);52 d[pos1]++,d[pos2]++;53 V[pos1].pb(pos2);54 V[pos2].pb(pos1);55 }56 for(int i=1;i<=n;i++){57 pos1=getid(a[i]);58 pos2=getid(b[i]);59 if(d[pos1]==1){60 pos=pos1;61 break;62 }63 if(d[pos2]==1){64 pos=pos2;65 break;66 }67 }68 dfs(pos,0);69 }. View Code .
D
跑两个叶子结点的最短路，看看最后的个数是不是2*n-1
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin);13 #endif */14 15 int n;16 vector<int>ve[305];17 int vis[305];18 int d[305];19 vector<int>ans;20 21 22 void dfs(int pos,int pre,int last,vector<int>tmp){23 vis[pos]=1;24 if(pre!=0) {25 tmp.pb(pos);26 }27 if(pos==last){28 for(int i=0;i<tmp.size();i++){29 ans.pb(tmp[i]);30 }31 return;32 }33 for(int i=0;i<ve[pos].size();i++){34 if(!vis[ve[pos][i]]&&ve[pos][i]!=pre){35 dfs(ve[pos][i],pos,last,tmp);36 }37 }38 }39 40 int main(){41 #ifndef ONLINE_JUDGE42 freopen("1.txt","r",stdin);43 #endif44 std::ios::sync_with_stdio(false);45 cin>>n;46 int u,v;47 for(int i=1;i<n;i++){48 cin>>u>>v;49 ve[u].pb(v);50 ve[v].pb(u);51 d[u]++,d[v]++;52 }53 int co=0;54 for(int i=2;i<=n;i++){55 if(d[i]==1){56 co++;57 }58 }59 vector<int>son;60 son.pb(1);61 for(int i=1;i<=co;i++){62 cin>>u;63 son.pb(u);64 }65 son.pb(1);66 ans.pb(1);67 for(int i=0;i<son.size()-1;i++){68 memset(vis,0,sizeof(vis));69 vector<int>tmp;70 tmp.clear();71 dfs(son[i],son[i+1],tmp);72 }73 if(ans.size()==2*n-1){74 for(int i=0;i<ans.size();i++){75 cout<<ans[i]<<" ";76 }77 cout<<endl;78 }79 else{80 cout<<-1<<endl;81 }82 }. View Code .
E
bfs搜索，思路很有趣
标记是用A和B的相对位置进行标记的，懂了这一点这题就解决了
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,rt<<1|1 5 #define sqr(x) ((x)*(x)) 6 #define pb push_back 7 #define maxn 1000005 8 typedef long long ll; 9 typedef unsigned long long ull;10 /*#ifndef ONLINE_JUDGE11 freopen("1.txt",stdin);12 #endif */13 int n,m;14 vector<int>ve[505];15 int pre[505][505][2];16 bool book[505][505];17 vector<int>ans[2];18 19 bool bfs(){20 pre[1][n][0]=-1;21 pair<int,int>p,pp;22 p=make_pair(1,n);23 queue<pair<int,int> >Q;24 Q.push(p);25 while(!Q.empty()&&pre[n][1][0]==0){26 p=Q.front();27 Q.pop();28 int p1=p.first,p2=p.second;29 for(int i=0;i<ve[p1].size();i++){30 if(!book[ve[p1][i]][p2]){31 book[ve[p1][i]][p2]=1;32 for(int j=0;j<ve[p2].size();j++){33 if(ve[p1][i]!=ve[p2][j]){34 if(pre[ve[p1][i]][ve[p2][j]][0]==0){35 pre[ve[p1][i]][ve[p2][j]][0]=p1;36 pre[ve[p1][i]][ve[p2][j]][1]=p2;37 pp=make_pair(ve[p1][i],ve[p2][j]);38 Q.push(pp);39 }40 }41 }42 }43 }44 }45 if(pre[n][1][0]==0) return false;46 int x=n,y=1,z;47 while(x>0){48 ans[0].pb(x);49 ans[1].pb(y);50 z=x;51 x=pre[x][y][0];52 y=pre[z][y][1];53 }54 return true;55 }56 57 int main(){58 #ifndef ONLINE_JUDGE59 freopen("1.txt",stdin);60 #endif61 std::ios::sync_with_stdio(false);62 cin>>n>>m;63 int u,v;64 for(int i=1;i<=m;i++){65 cin>>u>>v;66 ve[u].pb(v);67 ve[v].pb(u);68 }69 if(bfs()){70 cout<<ans[0].size()-1<<endl;71 for(int i=0;i<2;i++){72 for(int j=ans[i].size()-1;j>=0;j--){73 cout<<ans[i][j]<<" ";74 }75 cout<<endl;76 }77 }78 else{79 cout<<-1<<endl;80 }81 82 }. View Code . . .. ...
