Codeforces Beta Round #27 (Codeforces format,Div. 2) http://codeforces.com/contest/27 A 1 #inc
... .
Codeforces Beta Round #27 (Codeforces format,Div. 2)
http://codeforces.com/contest/27
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 maxn 1000005 7 typedef long long ll; 8 typedef unsigned long long ull; 9 const ull MOD=257;10 /*#ifndef ONLINE_JUDGE11 freopen("1.txt","r",stdin);12 #endif */13 14 int a[3005];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 for(int i=1;i<=n;i++){24 cin>>a[i];25 }26 sort(a+1,a+n+1);27 int i;28 for(i=1;i<=n;i++){29 if(a[i]!=i){30 cout<<i<<endl;31 break;32 }33 }34 if(i==n+1) cout<<n+1<<endl;35 }. View Code .
B
找出度数大的那个点
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin);12 #endif */13 14 int book[55][55];15 int n;16 int d[55];17 18 void Check(int &x,int &y){19 for(int i=1;i<=n;i++){20 for(int j=1;j<=n;j++){21 if(i==j) continue;22 if(!book[i][j]){23 x=i,y=j;24 return;25 }26 }27 }28 }29 30 int main(){31 #ifndef ONLINE_JUDGE32 freopen("1.txt","r",stdin);33 #endif34 std::ios::sync_with_stdio(false);35 cin>>n;36 int nn=n*(n-1)/2-1;37 int u,v;38 for(int i=1;i<=nn;i++){39 cin>>u>>v;40 book[u][v]=book[v][u]=1;41 d[u]++;42 }43 int x,y;44 Check(x,y);45 if(d[x]>d[y]){46 cout<<x<<" "<<y<<endl;47 }48 else{49 cout<<y<<" "<<x<<endl;50 }51 }. View Code .
C
模拟
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin);12 #endif */13 14 int a[100005];15 int n;16 17 int Check(){18 int flag=0;19 for(int i=1;i<n;i++){///<<<<<<20 if(a[i]>a[i+1]){21 flag=1;22 }23 }24 if(flag==0){25 return 1;26 }27 flag=0;28 for(int i=1;i<n;i++){///>>>>>>29 if(a[i]<a[i+1]){30 flag=2;31 }32 }33 if(flag==0) return 2;34 return -1;35 }36 37 struct sair{38 int v,pos;39 }b[100005];40 int main(){41 #ifndef ONLINE_JUDGE42 // freopen("1.txt",stdin);43 #endif44 std::ios::sync_with_stdio(false);45 cin>>n;46 int co=1;47 for(int i=1;i<=n;i++){48 cin>>a[i];49 if(a[i]!=a[i-1]){50 b[co].v=a[i];51 b[co].pos=i;52 co++;53 }54 }55 co--;56 int flag=Check();57 if(flag==1||flag==2){58 cout<<0<<endl;59 }60 else{61 cout<<3<<endl;62 63 for(int i=2;i<co;i++){64 if(b[i-1].v>b[i].v&&b[i].v<b[i+1].v){65 cout<<b[i-1].pos<<" "<<b[i].pos<<" "<<b[i+1].pos<<endl;66 break;67 }68 if(b[i-1].v<b[i].v&&b[i].v>b[i+1].v){69 cout<<b[i-1].pos<<" "<<b[i].pos<<" "<<b[i+1].pos<<endl;70 break;71 }72 }73 }74 }. View Code .
D
用类似二分染色的思想，把交叉的道路染成不同的颜色，如果判断的时候出现交叉的道路有相同的颜色，就输出Impossible
.
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 const ull MOD=257;11 /*#ifndef ONLINE_JUDGE12 freopen("1.txt",stdin);13 #endif */14 15 vector<int>ve[105];16 int n,m;17 int s[105],t[105];18 int vis[105];19 int col[105];20 21 void dfs(int pos,int c){22 if(vis[pos]) return;23 vis[pos]=1;24 col[pos]=c;25 for(int i=0;i<ve[pos].size();i++){26 dfs(ve[pos][i],c^1);27 if(col[pos]==col[ve[pos][i]]){28 cout<<"Impossible"<<endl;29 exit(0);30 }31 }32 }33 34 int main(){35 #ifndef ONLINE_JUDGE36 // freopen("1.txt",stdin);37 #endif38 std::ios::sync_with_stdio(false);39 cin>>n>>m;40 for(int i=1;i<=m;i++){41 cin>>s[i]>>t[i];42 if(s[i]>t[i]) swap(s[i],t[i]);43 }44 for(int i=1;i<=m;i++){45 for(int j=1;j<=m;j++){46 if(s[i]<s[j]&&t[i]<t[j]&&s[j]<t[i]){47 ve[i].pb(j);48 ve[j].pb(i);49 }50 }51 }52 for(int i=1;i<=m;i++){53 dfs(i,0);54 }55 for(int i=1;i<=m;i++){56 if(col[i]) cout<<‘i‘;57 else cout<<‘o‘;58 }59 }. View Code .
E
知识点：反素数
参考博客：https://www.cnblogs.com/handsomecui/p/5017484.html
.
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lson l,stdin);12 #endif */13 14 int prim[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};15 int n;16 ull ans=-1;17 18 void dfs(int pos,ull v,int num){19 if(num==n&&ans>v) ans=v;20 for(int i=1;i<=63;i++){21 if(num*(i+1)>n||v*prim[pos]>ans) break;22 v*=prim[pos];23 dfs(pos+1,v,num*(i+1));24 }25 }26 27 int main(){28 #ifndef ONLINE_JUDGE29 // freopen("1.txt",stdin);30 #endif31 std::ios::sync_with_stdio(false);32 cin>>n;33 dfs(0,1,1);34 cout<<ans<<endl;35 }. View Code . . .. ...
