a ZOJ 3860
求和大家不一样的那个数，签到，map水之
1 #include<cstdio> 2 #include<map> 3 using namespace std; 4 map<int,int> mp; 5 int main(){ 6 int t,n,x; 7 while(~scanf("%d",&t)){ 8 while(t--){ 9 scanf("%d",&n); 10 mp.clear(); 11 while(n--){ 12 scanf("%d",&x); 13 mp[x]++; 14 } 15 if(mp.begin()->second==1){ 16 printf("%d ",mp.begin()->first); 17 } 18 else{ 19 printf("%d ",mp.rbegin()->first); 20 } 21 } 22 } 23 return 0; 24 }
b ZOJ 3861
求输入的整数串有多少种合法的排列，枚举所有排列判断合法
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<map> 5 #include<vector> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int M=16; 9 int a[M]; 10 vector< vector<int> > ans; 11 vector<int> v; 12 int n; 13 bool vis[M]; 14 bool good(int x,int y){ 15 if(x>y) swap(x,y); 16 if(x==1&&y==3) return vis[2]; 17 if(x==4&&y==6) return vis[5]; 18 if(x==7&&y==9) return vis[8]; 19 if(x==1&&y==7) return vis[4]; 20 if(x==2&&y==8) return vis[5]; 21 if(x==3&&y==9) return vis[6]; 22 if(x==1&&y==9) return vis[5]; 23 if(x==3&&y==7) return vis[5]; 24 return true; 25 } 26 bool judge(){ 27 mt(vis,0); 28 for(int i=1;i<n;i++){ 29 if(good(a[i-1],a[i])){ 30 vis[a[i-1]]=true; 31 vis[a[i]]=true; 32 } 33 else return false; 34 } 35 return true; 36 } 37 int main(){ 38 int t; 39 while(~scanf("%d",&t)){ 40 while(t--){ 41 scanf("%d",&n); 42 for(int i=0;i<n;i++){ 43 scanf("%d",&a[i]); 44 } 45 sort(a,a+n); 46 ans.clear(); 47 do{ 48 if(judge()){ 49 v.clear(); 50 for(int i=0;i<n;i++){ 51 v.push_back(a[i]); 52 } 53 ans.push_back(v); 54 } 55 }while(next_permutation(a,a+n)); 56 int la=ans.size(); 57 printf("%d ",la); 58 for(int i=0;i<la;i++){ 59 for(int j=0;j<n;j++){ 60 printf("%d%c",ans[i][j],j==n-1?' ':' '); 61 } 62 } 63 } 64 } 65 return 0; 66 }
c ZOJ 3862
有n个线段，知道每个线段端点的编号和坐标，每一步能交换一对编号的坐标，问能否在n+10步内使得所有线段不相交。
按点排序，x小，x相同y小，然后依次遍历，每次取两个点，若恰好是一对，无需操作，若不是一对，将第二个点与第一个点的对应点交换。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<map> 5 #include<vector> 6 #define mt(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int M=2e5+10; 9 struct point{ 10 int x,y; 11 friend bool operator <(const point &a,const point &b){ 12 return a.x<b.x||(a.x==b.x&&a.y<b.y); 13 } 14 }p[M],s[M]; 15 int to[M]; 16 typedef pair<int,int> pii; 17 map<pii,int> mp; 18 vector<point> ans; 19 int main(){ 20 int t,n,x,y; 21 while(~scanf("%d",&t)){ 22 while(t--){ 23 scanf("%d",&n); 24 int n2=n*2; 25 mp.clear(); 26 for(int i=0;i<n2;i++){ 27 scanf("%d%d",&p[i].x,&p[i].y); 28 s[i]=p[i]; 29 mp[make_pair(p[i].x,p[i].y)]=i; 30 } 31 sort(s,s+n2); 32 for(int i=0;i<n;i++){ 33 scanf("%d%d",&x,&y); 34 x--; 35 y--; 36 to[x]=y; 37 to[y]=x; 38 } 39 ans.clear(); 40 for(int i=0;i<n2;i+=2){ 41 point a=s[i]; 42 point b=s[i+1]; 43 int aid=mp[make_pair(a.x,a.y)]; 44 int bid=mp[make_pair(b.x,b.y)]; 45 if(to[aid]==bid) continue; 46 int cid=to[aid]; 47 mp[make_pair(p[cid].x,p[cid].y)]=bid; 48 swap(p[bid],p[cid]); 49 a.x=bid; 50 a.y=cid; 51 ans.push_back(a); 52 } 53 int la=ans.size(); 54 printf("%d ",la); 55 for(int i=0;i<la;i++){ 56 printf("%d %d ",ans[i].x+1,ans[i].y+1); 57 } 58 } 59 } 60 return 0; 61 }
end