排名45，我是弟弟。
C题，求凸多边形最大的四边形面积。
我们可以枚举两个点，然后在其两端找距离这两个点组成的直线最远的点，由于是个凸包，所以面积具有一个最大值，也意味著当只有枚举两个点再找另外两个点不用从头开始找，只用再往后就行。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
struct Point
{int x,y;Point(){}Point(int _x,int _y):x(_x),y(_y){}void read(){scanf("%d %d",&x,&y);}Point operator-(const Point &b)const{return Point(x-b.x,y-b.y);}int operator*(const Point &b)const{return x*b.x+y*b.y;}int operator^(const Point &b)const{return x*b.y-y*b.x;}int len2(){return x*x+y*y;}
};Point p[maxn];
Point ch[maxn];
int n;
int solve()
{ch[1]=p[1];ch[2]=p[2];int top=2;for(int i=3;i<=n;i++){while(top-1>=1&&((p[i]-ch[top-1])^(ch[top]-ch[top-1]))>=0)top--;ch[++top]=p[i];}return top;
}bool cmp(Point a,Point b)
{Point x=a-p[1];Point y=b-p[1];int tmp=x^y;if(tmp>0)return 1;else if(tmp<0)return 0;return x.len2()<y.len2();
}int S(int a,int b,int c)
{return abs((ch[a]-ch[b])^(ch[c]-ch[b]));
}void solve2(int num)
{if(num==3){int area=S(1,2,3);if(area%2)printf("%.1f\n",1.0*area/2);else printf("%d\n",area/2);}else{n=num;int res=0;for(int i=1;i<=n;i++){int idx1=i+1,idx2=(i+2)%n+1;for(int j=i+2;j<=n;j++){while((S(i,j,idx1)-S(i,j,idx1+1))<0)idx1++;while((S(i,j,idx2)-S(i,j,idx2%n+1))<0)idx2=idx2%n+1;int area=S(i,j,idx1)+S(i,j,idx2) ;if((res-area)<0){res=area;}}}if(res%2)printf("%.1f\n",1.0*res/2);else printf("%d\n",res/2);}
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){p[i].read();if(p[i].y<p[1].y||p[i].y==p[1].y&&p[i].x<p[1].x)swap(p[i],p[1]);}sort(p+2,p+1+n,cmp);int num=solve();solve2(num);}
}
D题题意有点晦涩。看题解代码才看懂题意的。。
给出的点实际上是一个十字路口，走的时候只能往十字路口对面走，问需要设置即可指示可以使得不管从哪里开始走都能到达一个目的地十字路口。
我们可以先算出从目的地十字路口出发能走到的十字路口，标记一下，还没被标记的就ans++即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
bool vis[2][maxn];
int n,g;
int Map[maxn][4];
void walk(int &go,int &now)
{int last=now;now=Map[now][go];for(int i=0;i<4;i++)if(Map[now][i]==last){go=(i&1);break;}if(Map[now][go]==last)swap(Map[now][go],Map[now][go+2]);
}void solve()
{int now=g;int go=0;while(!vis[go][now]){vis[go][now]=1;walk(go,now);}go=1;while(!vis[go][now]){vis[go][now]=1;walk(go,now);}int ans=0;for(int i=0;i<2;i++)for(int j=1;j<=n;j++)if(!vis[i][j]){//cout<<i<<' '<<j<<endl;//vis[i][j]=1;ans++;go=i,now=j;while(!vis[go][now]){vis[go][now]=1;walk(go,now);}}printf("%d\n",ans);
}int main()
{int T;scanf("%d",&T);while(T--){memset(vis,0,sizeof(vis));scanf("%d %d",&n,&g);for(int i=1;i<=n;i++)for(int j=0;j<4;j++)scanf("%d",&Map[i][j]);solve();}return 0;
}
E题一开始看了题目突然感觉像半平面交，结果想了想不是。。
做的时候其实想到了题解上的那个图。也想到了先将第一个排序。但没有想到一起。我想的是如果只有两个值，那么将一个值排序，然后单调栈就能搞定。这样做法如何引申到三个值就没想到了。
正确做法先将所有的值按照第三个从小到大排序。那么在二维坐标系中加入点时，后加的点已经在一个值处于劣势地位，如果能找到一个点另外两个值都小于它，那么他就不行。否则就可以，可以的话我们要更新处于坐标系中的点，所有坐标系中另外两个值都大于它的都将被删掉，因为它对后来的影响面积比这些点都要大，所以这些点相当于没用了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{int a,b,c;node(int _a,int _b,int _c):a(_a),b(_b),c(_c){}node(){}void read(){scanf("%d %d %d",&a,&b,&c);}bool operator<(const node &b)const{return c<b.c;}}nodes[maxn];map<int,int>M;bool insert(int a,int b)
{if(M.empty()){M[a]=b;return 1;}auto it=M.upper_bound(a);if(it!=M.begin()){auto tmp=it;tmp--;if(tmp->second<b)return 0;}auto st=it,ed=it;while(ed!=M.end()){if(ed->second<b)break;ed++;}M.erase(st,ed);M[a]=b;return 1;
}
int n;
void solve()
{int ans=0;for(int i=1;i<=n;i++){int a=nodes[i].a,b=nodes[i].b;if(insert(a,b))ans++;//else cout<<i<<endl;}printf("%d\n",ans);
}int main()
{int T;scanf("%d",&T);while(T--){M.clear();scanf("%d",&n);for(int i=1;i<=n;i++)nodes[i].read();sort(nodes+1,nodes+1+n);solve();}return 0;
}
K题做法也很有意思。将问题分成两个部分，然后这两个部分分开求解。对于每个部分我们枚举所有情况，将所有情况对应的每个人的答对的个数进行hash，而hash方式由于该题给的数据范围特别巧妙，我们可以将每个人的答对的个数用5位来存，那么所有人的情况可以用一个longlong值表示出来。将两边都这样处理完后，接下来的问题实际上就是2-sum问题了。
#include<bits/stdc++.h>
using namespace std;const int maxn=15;
const int maxm=35;
char s[maxn][maxm];
int sco[maxn];long long getcode(int tsco[],int n)
{long long res=0;for(int i=0;i<n;i++)res=res*(1<<5)+tsco[i];return res;
}
pair<long long,int>P1[(1<<maxn)],P2[(1<<maxn)];
int main()
{int T;scanf("%d",&T);while(T--){int n,m;scanf("%d %d",&n,&m);for(int i=0;i<n;i++)scanf("%s %d",s[i],&sco[i]);long long code=0;code=getcode(sco,n);int m1=m/2,m2=m-m1;for(int i=0;i<(1<<m1);i++){int thesco[30];memset(thesco,0,sizeof(thesco));for(int j=0;j<n;j++)for(int k=0;k<m1;k++)if(s[j][k]-'0'==((i>>k)&1))thesco[j]++;long long thecode=getcode(thesco,n);P1[i]=make_pair(thecode,i);}for(int i=0;i<(1<<m2);i++){int thesco[30];memset(thesco,0,sizeof(thesco));for(int j=0;j<n;j++)for(int k=0;k<m2;k++)if(s[j][k+m1]-'0'==((i>>k)&1))thesco[j]++;long long thecode=getcode(thesco,n);P2[i]=make_pair(thecode,i);}sort(P1,P1+(1<<m1));sort(P2,P2+(1<<m2));int ans=0;int Leftans,Rightans;int i=0,j=(1<<m2)-1;while(i<(1<<m1)&&j>=0){long long tmp1=P1[i].first,tmp2=P2[j].first;if(tmp1+tmp2==code){Leftans=P1[i].second,Rightans=P2[j].second;int Leftnum=0,Rightnum=0;while(i<(1<<m1)&&P1[i].first==tmp1)i++,Leftnum++;while(j>=0&&P2[j].first==tmp2)j--,Rightnum++;ans+=Leftnum*Rightnum;}if(i<(1<<m1)&&tmp1+tmp2<code)i++;if(j>=0&&tmp1+tmp2>code)j--;}if(ans==1){for(int i=0;i<m1;i++)printf("%d",((Leftans>>i)&1));for(int i=0;i<m2;i++)printf("%d",((Rightans>>i)&1));puts("");}elseprintf("%d solutions\n",ans);}return 0;
}
比赛的时候只出了4个题，和17级学弟一个水平。感觉自己好菜，还得加油啊。