NOI2019省选模拟赛第六场

心已赠人 2022-01-12 09:39 293阅读 0赞

[传送门][Link 1]

又炸了……

## \\(A\\) 唐时月夜 ##

不知道改了什么东西之后就\\(A\\)掉了\\(.jpg\\)

首先，题目保证“如果一片子水域曾经被操作过，那么在之后的施法中，这片子水域也一定会被操作”

这个意思就是说，如果一个点\\((x,y)\\)被操作过，那么它被进行的操作一定是所有操作的一个后缀和

这样的话我们只要对于每个点维护一下它有几个操作，并把操作的后缀和维护起来，就能知道它到底被怎么操作了

维护有几个操作的话二维前缀和就行了

然后关键是后缀和我们应该怎么处理

因为这是一个矩阵，那么我们考虑用矩阵来维护

定义初始向量\\((i,j,1)\\)，然后我们要计算出一个向量\\((ii,jj,1)\\)，其中\\((ii,jj)\\)表示\\((i,j)\\)经过这么多乱七八糟的操作之后到了哪里。（为啥向量的最后要加个\\(1\\)？因为你会发现后面线性变换的时候会加上一堆常数）

不难发现三个线性变换都可以表示成矩阵的形式，具体看代码好了

然后没有然后了

//minamoto #include<bits/stdc++.h> #define R register #define uint unsigned int #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res;R char ch; while((ch=getc())>'9'||ch<'0'); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res; } uint readu(){ R uint res;R char ch; while((ch=getc())>'9'||ch<'0'); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res; } inline int getop(){R char ch;while((ch=getc())>'9'||ch<'0');return ch-'0';} const int N=4005,M=2e5+5; struct Matrix{ int a[3][3]; inline Matrix(){memset(a,0,sizeof(a));} inline int* operator [](const int &x){return a[x];} Matrix operator *(Matrix &b){ Matrix res; res[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0]+a[0][2]*b[2][0], res[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1]+a[0][2]*b[2][1], res[0][2]=a[0][0]*b[0][2]+a[0][1]*b[1][2]+a[0][2]*b[2][2], res[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0]+a[1][2]*b[2][0], res[1][1]=a[1][0]*b[0][1]+a[1][1]*b[1][1]+a[1][2]*b[2][1], res[1][2]=a[1][0]*b[0][2]+a[1][1]*b[1][2]+a[1][2]*b[2][2], res[2][0]=a[2][0]*b[0][0]+a[2][1]*b[1][0]+a[2][2]*b[2][0], res[2][1]=a[2][0]*b[0][1]+a[2][1]*b[1][1]+a[2][2]*b[2][1], res[2][2]=a[2][0]*b[0][2]+a[2][1]*b[1][2]+a[2][2]*b[2][2]; return res; } }suf[M]; int a[N][N],n,m,q,op,x,y,xx,yy;uint f[N*N],A,B,res; int main(){ // freopen("testdata.in","r",stdin); read(),n=read(),m=read(),q=read(); A=readu(),B=readu(),f[0]=readu(); fp(i,1,n*m)f[i]=A*f[i-1]+B; fp(i,1,q){ op=getop(),x=read(),y=read(),xx=read(),yy=read(); ++a[x][y],--a[xx+1][y],--a[x][yy+1],++a[xx+1][yy+1]; switch(op){ case 1:{ suf[i][0][0]=1,suf[i][1][1]=-1,suf[i][2][1]=y+yy,suf[i][2][2]=1; break; } case 2:{ suf[i][0][0]=-1,suf[i][1][1]=1,suf[i][2][0]=x+xx,suf[i][2][2]=1; break; } case 3:{ suf[i][0][1]=1,suf[i][1][0]=1,suf[i][2][0]=x-y,suf[i][2][1]=y-x,suf[i][2][2]=1; break; } } } fd(i,q-1,1)suf[i]=suf[i]*suf[i+1]; fp(i,1,n)fp(j,1,m)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; fp(i,1,n)fp(j,1,m){ if(!a[i][j])res+=f[(i-1)*m+j]*f[(i-1)*m+j]; else{ int t=q-a[i][j]+1; int ii=i*suf[t][0][0]+j*suf[t][1][0]+suf[t][2][0]; int jj=i*suf[t][0][1]+j*suf[t][1][1]+suf[t][2][1]; res+=f[(i-1)*m+j]*f[(ii-1)*m+jj]; } } printf("%u\n",res); return 0; }

## \\(B\\) 附耳而至 ##

这建图实在是太鬼畜了点儿……

首先题目很明显地告诉了你这是一个平面图，所以我们把平面图转对偶图

对于每一个区域（在对偶图中代表一个点），我们需要求出它的光明值和黑暗值，以及和它相邻的区域同时被选时要扣除的代价（即两个区间公共边的权值）

在对偶图里，我们从源点向每个点连边，容量为光明值，从每个点向汇点连边，容量为黑暗值。点与点之间连无向边，容量为这两个点都被选时扣除的代价。很明显用光明值和黑暗值之和减去最小割就是答案了

所以如果不用建图的话我们可以轻轻松松地切掉这道题

问题是这怎么平面图转对偶图啊……

忘了哪里看到的了，总之有一个结论：对于一个平面图，我们把它的边连为两条单向边，那么一定存在一种方法使得所有边拆分成若干个环，且若以每个环上有向边的左边为内部，这些环的内部一定是这个平面图上所有的区域

然后……自己看代码吧……虽然我觉得不太可能看得懂就是了……

//minamoto #include<bits/stdc++.h> #define R register #define inf 0x3f3f3f3f #define IT vector<int>::iterator #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) #define gg(u) for(int &i=cur[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R int x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=1e6+5; struct eg{int v,nx,w;}e[N<<1];int head[N],cur[N],tot=1; inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;} int S,T,h,t,dep[N],q[N]; bool bfs(){ fp(i,S,T)dep[i]=-1,cur[i]=head[i]; q[h=t=1]=S,dep[S]=0; while(h<=t){ int u=q[h++]; go(u)if(e[i].w&&dep[v]<0){ q[++t]=v,dep[v]=dep[u]+1; if(v==T)return true; } } return false; } int dfs(int u,int lim){ if(u==T||!lim)return lim; int fl=0,f; gg(u)if(dep[v]==dep[u]+1&&(f=dfs(v,min(lim,e[i].w)))){ fl+=f,lim-=f,e[i].w-=f,e[i^1].w+=f; if(!lim)break; } if(!fl)dep[u]=-1; return fl; } int dinic(){int flow=0;while(bfs())flow+=dfs(S,inf);return flow;} struct node{ int x,y; node(){} node(R int xx,R int yy):x(xx),y(yy){} inline node operator +(const node &b)const{return node(x+b.x,y+b.y);} inline node operator -(const node &b)const{return node(x-b.x,y-b.y);} inline double ang(){return atan2(y,x);} }p[N]; int eu[N],ev[N],ec[N],pu[N],pv[N],idu[N],idv[N],rvs[N],rvt[N],sv[N],tv[N],vis[N]; vector<int>G[N]; int cnt,sum,n,m;double tmp[N]; inline bool cmp(const int &x,const int &y){return tmp[x]<tmp[y];} void find(int i){ vis[i]=1; int id=(i+1)>>1,u=(i&1?ev:eu)[id],p=(i&1?pv:pu)[id]; (i&1?idv:idu)[id]=cnt,rvs[cnt]+=sv[u],rvt[cnt]+=tv[u]; p=G[u][p?p-1:G[u].size()-1]; p=p*2-(eu[p]==u); if(!vis[p])find(p); } int main(){ // freopen("testdata.in","r",stdin); read(),n=read(),m=read(); fp(i,1,n)p[i].x=read(),p[i].y=read(),sv[i]=read(),tv[i]=read(); fp(i,1,m)eu[i]=read(),ev[i]=read(),ec[i]=read(),G[eu[i]].push_back(i),G[ev[i]].push_back(i); fp(u,1,n){ for(IT it=G[u].begin();it!=G[u].end();++it) tmp[*it]=((eu[*it]==u?p[ev[*it]]:p[eu[*it]])-p[u]).ang(); sort(G[u].begin(),G[u].end(),cmp); fp(i,0,G[u].size()-1) (eu[G[u][i]]==u?pu[G[u][i]]:pv[G[u][i]])=i; } fp(i,1,m<<1)if(!vis[i])++cnt,find(i); S=0,T=cnt+1; fp(i,1,cnt){ sum+=rvs[i]+rvt[i], add(S,i,rvs[i]),add(i,S,0), add(i,T,rvt[i]),add(T,i,0); } fp(i,1,m)add(idu[i],idv[i],ec[i]),add(idv[i],idu[i],ec[i]); printf("%d\n",sum-dinic()); return 0; }

## \\(C\\) 星辰大海 ##

论我的经历：

比赛的时候想去抄一下半平面交的板子，结果到洛谷上一看发现原来的板子被人\\(Hack\\)掉了

无奈只能当场重新学了一下板子（虽然我知道这样是不对的），然后打满暴力分之后信心满满地交上去。比赛结束之后发现我的板子爆精度了

怎么找一个正常点的半平面交板子就这么难呢……顺便我总算知道计蒜几盒那令人闻风丧胆的精度问题是怎么来的了……

然后是题解：

首先我们可以发现，如果\\(1\\)号点和另外两个点三点共线，那么它只能在这条线上，所以答案必定是\\(0\\)

否则的话，显然\\(1\\)号点和每条直线之间的相对关系是不变的，也就是说，如果有两个点\\(ij\\)构成了一条直线，\\(1\\)号点原来在这条直线左边，移动之后还是只能在它左边，也就是说它只能在这条直线左边了

那么我们很容易想出一个\\(O(n^2\\log n)\\)的办法，直接暴力枚举所有点对求出所有直线，然后半平面交就可以了

然而这样肯定布星啊……

我们发现有很多半平面是多余的，那么我们能不能试着把半平面的个数优化到\\(O(n)\\)呢

其实是可以的，先说结论：

我们把\\(1\\)号点作为新的圆点，再把其它所有点按照极角排序，记为\\(p\_2,p\_3,...,p\_n\\)

1.加入半平面\\(p\_2-p\_3,p\_3-p\_4,...,p\_n-p\_2\\)

2.对于每一个点\\(p\_i\\)，令\\(p\_j\\)为与\\(p\_i\\)极角相差不超过\\(\\pi\\)，且极角相差最大的点，加入半平面\\(p\_i-p\_j\\)

然后跑个半平面交就可以出答案了

啥？你确定这样就行了？不会漏么？

比方说下面这种情况，在执行第二步的时候，对于\\(2\\)来说，\\(4\\)是满足条件的点，然后显然\\(24\\)这个半平面没有包含\\(23\\)这个半平面啊？

![5ca194d938ae4.png][]

那么我们来康康好了

具体来说，我们假设\\(3\\)是满足\\(∠123\\)最小的点，也就是说它不存在点\\(x\\)使得\\(23\\)这个半平面包含\\(2x\\)，而\\(4\\)是\\(2\\)此时对应的点

如果极角排序之后\\(23\\)之间没有点，那么它们显然会在第一步连边，所以我们假设中间会有那么一坨点

我们需要满足这个半平面能被完全覆盖

![5ca195fb1e555.png][]

设一个在\\(3\\)前面的点为\\(x\\)，那么我们发现\\(x3\\)这个半平面和\\(24\\)这个半平面刚好可以把\\(23\\)完全覆盖

![5ca1966babdb3.png][]

所以上面的方法就不会有问题啦！

这件事情告诉我们码计蒜几盒时一个好用有不会爆精度的板子是多么重要

//minamoto #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } const int N=1e6+5,inf=1e6;const double eps=1e-14; inline double fabs(const double &x){return x<-eps?-x:x;} inline int sgn(const double &x){return x<-eps?-1:x>eps;} struct node{ double x,y,sl; inline node(){} inline node(R double xx,R double yy):x(xx),y(yy){} inline node operator +(const node &b)const{return node(x+b.x,y+b.y);} inline node operator -(const node &b)const{return node(x-b.x,y-b.y);} inline double operator *(const node &b)const{return x*b.y-y*b.x;} inline node operator ^(const double &b)const{return node(x*b,y*b);} inline bool operator <(const node &b)const{return sgn(sl-b.sl)<0;} }s[N],p[N]; struct Line{ node p,v;double sl; Line(){} Line(const node &a,const node &b){p=a,v=b-a,v=v^sgn(v*(s[0]-p)),sl=atan2(v.y,v.x);} inline bool operator <(const Line &b)const{return sgn(sl-b.sl)?sgn(sl-b.sl)<0:sgn(v*(b.p-p))<0;} inline bool Right(const node &b){return sgn(v*(b-p))<0;} inline friend node cross(const Line &a,const Line &b){return a.p+(a.v^(b.v*(b.p-a.p)/(b.v*a.v)));} }L[N],q[N]; int n,m,tot,h,t,T; void HalfPlane(){ fp(i,1,m)if(!sgn(L[i].v.x)&&!sgn(L[i].v.y))return puts("0.0"),void(); sort(L+1,L+1+m); q[h=t=1]=L[1]; fp(i,2,m)if(sgn(L[i].sl-L[i-1].sl)){ while(h<t&&L[i].Right(p[t-1]))--t; while(h<t&&L[i].Right(p[h]))++h; q[++t]=L[i]; if(h<t)p[t-1]=cross(q[t],q[t-1]); } while(h<t&&q[h].Right(p[t-1]))--t; if(t-h<2)return puts("0.0"),void(); p[t]=cross(q[t],q[h]),p[t+1]=p[h]; double res=0; fp(i,h,t)res+=p[i]*p[i+1]; printf("%.10lf\n",res*0.5); } int main(){ // freopen("testdata.in","r",stdin); read(),T=read(); while(T--){ n=read(),m=0,s[1].x=read(),s[1].y=read(); fp(i,2,n)s[i].x=read()-s[1].x,s[i].y=read()-s[1].y,s[i].sl=atan2(s[i].y,s[i].x); sort(s+2,s+n+1); fp(i,2,n-1)L[++m]=Line(s[i],s[i+1]); L[++m]=Line(s[n],s[2]); for(R int i=2,j=2,nxt;i<=n;++i){ while((nxt=(j==n)?2:j+1)!=i&&sgn(s[i]*s[nxt])>=0)j=nxt; if(j!=i)L[++m]=Line(s[i],s[j]); } L[++m]=Line(node(-inf-s[1].x,-inf-s[1].y),node(inf-s[1].x,-inf-s[1].y)), L[++m]=Line(node(inf-s[1].x,-inf-s[1].y),node(inf-s[1].x,inf-s[1].y)), L[++m]=Line(node(inf-s[1].x,inf-s[1].y),node(-inf-s[1].x,inf-s[1].y)), L[++m]=Line(node(-inf-s[1].x,inf-s[1].y),node(-inf-s[1].x,-inf-s[1].y)); HalfPlane(); } return 0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10635701.html

[Link 1]: http://noi.ac/contest/94
[5ca194d938ae4.png]: https://i.loli.net/2019/04/01/5ca194d938ae4.png
[5ca195fb1e555.png]: https://i.loli.net/2019/04/01/5ca195fb1e555.png
[5ca1966babdb3.png]: https://i.loli.net/2019/04/01/5ca1966babdb3.png