Problem A
发现这一场有一点自闭啊，人均题我都不会。
将球桌翻折开，然后只要穿过其中的一个角就是进洞了，可以根据这个列出等式之后变成一个用扩展 (gcd) 能解的方程，然后求最小的整数解就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y,vx,vy;
bool flagx=false,flagy=false;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void exgcd(int a,int b,int &x,int &y){
if(b==0) return x=1,y=0,void();
exgcd(b,a%b,x,y);
int t=x;x=y,y=t-a/b*y;
}
signed main(){
cin>>n>>m>>x>>y>>vx>>vy;
if(vy==0){
if(y==0||y==m) printf("%lld %lld
",vx>0?n:0,y);
else printf("-1
");
return 0;
}
if(vx==0){
if(x==0||x==n) printf("%lld %lld
",x,vy>0?m:0);
else printf("-1
");
return 0;
}
if(vx<0) vx=-vx,x=n-x,flagx=true;
if(vy<0) vy=-vy,y=m-y,flagy=true;
int A,B,C=gcd(n,m);
if((x-y)%C) return printf("-1"),0;
int dA=-m/C,dB=n/C;exgcd(n,m,A,B),B=-B;
if(dA<0) dA=-dA,dB=-dB;
A*=(x-y)/C,A=(A%dA+dA)%dA;
if(!A) A=dA;
B=(A*n-(x-y))/m;
// printf("%lld %lld
",A,B);
printf("%lld %lld
",((A&1)^flagx)?n:0,((B&1)^flagy)?m:0);
}
Problem B
上次好像做过，没做出来，也没订正。
然后你用 (set) 强行维护一下整个过程，得到每一个点最后的点的个数，然后用并查集来维护一下后面的点侵犯前面的点的情况，就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m;
struct Cow{int x,y;}a[N];
bool cmp1(Cow a,Cow b){return a.y>b.y;}
struct Fence{int x,y,id,fa;}b[N];
bool cmp2(Fence a,Fence b){return a.y>b.y;}
struct Point{int x,id;};
bool operator < (Point a,Point b){return a.x<b.x;}
set<Point> bag;
#define It set<Point>::iterator
int fa[N],cnt[N],res[N];
struct DSU{
int fa[N];
void init(int n){for(int i=1;i<=n;++i) fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int u,int v){
int fu=find(u),fv=find(v);
if(fu!=fv) fa[fv]=fu,cnt[fu]+=cnt[fv];
}
}d;
int main(){
cin>>n;
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
cin>>m;
for(int i=1;i<=m;++i) scanf("%d%d",&b[i].x,&b[i].y),b[i].id=i;
sort(a+1,a+1+n,cmp1),sort(b+1,b+1+m,cmp2);
int j=1;
for(int i=1;i<=m;++i){
It tmp;
while(j<=n&&a[j].y>b[i].y){
tmp=bag.lower_bound((Point){a[j].x,0});
j++;if(tmp!=bag.end()) cnt[tmp->id]++;
}
tmp=bag.lower_bound((Point){b[i].x,0});
if(tmp!=bag.end()) fa[b[i].id]=tmp->id;
// printf("fa %d %d
",b[i].id,fa[b[i].id]);
bag.insert((Point){b[i].x,b[i].id});
tmp=bag.find((Point){b[i].x,b[i].id});
while(tmp!=bag.begin()){
tmp--;
if(tmp->id<b[i].id) break;
else bag.erase(tmp);
tmp=bag.find((Point){b[i].x,b[i].id});
}
}
while(j<=n){
It tmp=bag.lower_bound((Point){a[j].x,0});
j++;if(tmp!=bag.end()) cnt[tmp->id]++;
}
d.init(m);
for(int i=m;i>=1;--i) res[i]=cnt[d.find(i)],d.merge(i,fa[i]);
for(int i=1;i<=m;++i) printf("%d
",res[i]);
return 0;
}
Problem E
大水题，从小到大加入然后用并查集和 ( ext{set}) 乱搞一下就可以了？
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,res1,res2;
struct Data{int data,pos;}a[N];
bool cmp(const Data a,const Data b){return a.data<b.data;}
struct DSU{
int fa[N],size[N];multiset<int> bag;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int u,int v){
int fu=find(u),fv=find(v);
if(fu!=fv){
bag.erase(bag.find(size[fu]));
bag.erase(bag.find(size[fv]));
fa[fv]=fu,size[fu]+=size[fv];
bag.insert(size[fu]);
}
}
}d;
int main(){
cin>>n;
for(int i=1;i<=n;++i){
scanf("%d",&a[i].data);
a[i].pos=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i){
d.fa[a[i].pos]=a[i].pos;
d.size[a[i].pos]=1,d.bag.insert(1);
if(a[i].pos>1&&d.fa[a[i].pos-1]) d.merge(a[i].pos,a[i].pos-1);
if(a[i].pos<n&&d.fa[a[i].pos+1]) d.merge(a[i].pos,a[i].pos+1);
set<int>::iterator tmp1=d.bag.begin(),tmp2=d.bag.end();tmp2--;
if(*tmp1==*tmp2){
if((int)d.bag.size()>res1)
res1=d.bag.size(),res2=a[i].data+1;
}
}
return printf("%d
",res2),0;
}