1.Codeforces Global Round 15 B. Running for Gold
大意：有五项比赛，给出n个运动员在这五项比赛中的排名，运动员A战胜B当且仅当在这五项比赛中至少有三项成绩A在B之上，夺冠必须战胜其他所有人，输出夺冠的运动员，若无人夺冠，输出-1。
题解：设置一个可能夺冠的人w，w从1开始，O(n)枚举2到n每个运动员，若w能战胜 i ，则 i 不可能夺冠；若 i 战胜w，则把w设置为 i ，继续比较。最后得到的 w 是唯一可能夺冠的人，再将w与其他所有运动员比一次，判断w是否能夺冠。
#include<cmath> #include<cstdio> #include<queue> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define ll long long const int maxn=50000+50; int T,n,a[maxn][6]; bool p[maxn]; template<typename T>void inline read(T &aa){ ll ff=1;char cc=getchar();aa=0; while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar(); if(cc==‘-‘) ff=-1,cc=getchar(); while(cc<=‘9‘&&cc>=‘0‘) aa=aa*10+cc-48,cc=getchar(); aa*=ff; } bool pd(int x,int y){ int ans=0; for(int i=1;i<=5;i++) if(a[x][i]<a[y][i]) ans++; if(ans>=3 ) return true; return false; } int main(){ cin>>T; while(T--){ memset(p,false,sizeof(p)); cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=5;j++){ read(a[i][j]); } bool q=0; if(n==1){ cout<<1<<endl; continue; } int w=1; for(int i=2;i<=n;i++){ if(pd(w,i)) continue; else w=i; } for(int i=1;i<=n;i++){ if(i==w) continue; if(!pd(w,i)){ cout<<-1<<endl; q=1; break; } } if(!q) cout<<w<<endl; } return 0; }
2.Codeforces Global Round 15 C. Maximize the Intersections
大意：圆上有2n个点，按顺时针方向给出，给出k次操作，每次操作将指定的两个点相连，剩下的点*相连，使用过的点不能再使用，求最多能有多少交点？
题解：连接1，3，相当于加入一个 [ 1, 3 ] 的区间，对于两个区间，若他们完全包含或者没有公共部分，则这两条弦没有交点。对于剩下的点，下右连上左，下左连上右。
#include<cmath> #include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define ll long long const int maxn=300; int T,n,k,down[maxn],up[maxn]; bool p[maxn]; struct node{ int l,r; }a[maxn]; bool pd(int x,int y){ if(a[x].l<a[y].l&&a[x].r>a[y].r) return false; if(a[y].l<a[x].l&&a[y].r>a[x].r) return false; if(a[x].r<a[y].l||a[y].r<a[x].l) return false; return true; } template<typename T>void inline read(T &aa){ ll ff=1;char cc=getchar();aa=0; while((cc<‘0‘||cc>‘9‘)&&cc!=‘-‘) cc=getchar(); if(cc==‘-‘) ff=-1,cc=getchar(); while(cc<=‘9‘&&cc>=‘0‘) aa=aa*10+cc-48,cc=getchar(); aa*=ff; } int main(){ cin>>T; while(T--){ int ans=0; cin>>n>>k; memset(p,false,sizeof(p)); for(int i=1;i<=k;i++){ int x,y; cin>>x>>y; if(x>y) swap(x,y); p[x]=true;p[y]=true; a[i].l=x;a[i].r=y; if(i>=2){ for(int j=1;j<i;j++){ if(pd(i,j)) ans++; } } } int t=1; for(int i=1;i<=2*n;i++){ if(!p[i]&&t<=n-k){ down[t]=i; t++; } else if(!p[i]&&t>n-k){ up[t-(n-k)]=i; t++; } } t=k; for(int i=1;i<=n-k;i++){ a[++t].l=down[i]; a[t].r=up[i]; for(int j=1;j<t;j++) if(pd(t,j)) ans++; } cout<<ans<<endl; } return 0; }