IOI2020集训队作业-5 (CF611G, AGC034D, AGC024F)

A - CF611G New Year and Cake

题意

有一个有$n$个整点顶点凸多边形。定义一种沿着某条对角线把这个凸多边形切成两部分的方案的代价是：两部分的面积的差的绝对值。显然我们有$\frac{n\cdot (n-3)}{2}$种方案。你需要求出所有方案的代价的和乘二对$10^9+7$取模的结果。

$n\le 5\times 10^5$，所有点的坐标的绝对值不超过$10^9$。

Sol

思路是枚举对角线的一个端点$x$，那么多边形上一定存在另一个端点$y$，满足多边形上在$x$到$y$之间的顶点与$x$连的对角线，分出来的是$x$的顺时针方向的那一边更大，从$y$到$x$之间的顶点与$x$连的对角线分出来的是$x$的顺时针方向的那一边的更小。这个$y$对于单调的$x$也具有单调性，可以双指针维护。预处理一系列东西的前缀和就可以快速算出某个对角线分出的多边形的面积，以及一个端点是$x$、另一个端点在一个区间内的所有方案的代价和。

实现细节

我的方法是：设多边形的顶点按照逆时针顺序依次是$p_0,p_1,\cdots p_{n-1}$，对于每一个$i$记录$su{m}_i={\sum }_{j=1}^i{p}_{i-1}\times p_i$，$x,y$，其意义是$p_0,p_1,\cdots p_i$这些顶点和原点围成的凸包的面积。两个点划出的、在$x$的逆时针方向的多边形面积就是$su{m}_y-su{m}_x+p_y\times p_x$。处理出$su{m}_i\cdot i$的前缀和就可以快速算一个端点是$x$、另一个端点在一个区间内的所有方案的代价和。

还有一个细节：这里多边形的面积最大是$4\times 10^{18}$，由于没有除以$2$所以存下来的就会达到$8\times 10^{18}$，要比较划出来部分的二倍和原多边形的面积，划出来部分的二倍可以达到$1.9\times 10^{19}$，超出了long long的范围，但是因为面积一定非负，可以用unsigned long long存储和比较。

Code

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define ll long long #define ull unsigned long long using namespace std; template <class T> inline void rd(T &x) { x=0; char c=getchar(); int f=1; while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f; } const int mod=1e9+7; const int N=1e6+10; int n; struct Point { ll x,y; Point(ll x=0,ll y=0): x(x),y(y) {} friend Point operator +(Point A,Point B) { return Point(A.x+B.x,A.y+B.y); } friend Point operator -(Point A,Point B) { return Point(A.x-B.x,A.y-B.y); } }p[N],sumP[N]; ull sumPQ[N]; ll sumPQI[N]; ll Cross(Point A,Point B) { return A.x*B.y-A.y*B.x; } ll queryPQ(int l,int r) { if(l>=n&&r>=n) return queryPQ(l-n,r-n); if(r>=n) return queryPQ(l,n-1)+sumPQ[r-n]; return sumPQ[r]-sumPQ[l]; // return sumPQ[r]-sumPQ[l]; } ll queryPQI(int l,int r) { return (sumPQI[r]-sumPQI[l])%mod; } Point queryP(int l,int r) { return sumP[r]-sumP[l]; } ull queryA(int l,int r) { // ll a=Cross(p[r],p[l]); // for(int i=l+1;i<=r;++i) a+=Cross(p[i-1],p[i]); // return a; return queryPQ(l,r)+Cross(p[r],p[l]); } ll querySA(int l,int r,int x) { // sum{i\in [l,r]} queryA(x,i) // ll a=0; // for(int i=l;i<=r;++i) a=(a+queryA(x,i))%mod; // return a; ll ans1=queryPQ(x,l)%mod*(r-l+1)+queryPQ(l,r)%mod*(r+1)-queryPQI(l,r); Point tmp=queryP(l-1,r); tmp.x%=mod,tmp.y%=mod; return ans1+Cross(tmp,p[x]); } int main() { rd(n); for(int i=0;i<n;++i) rd(p[i].x),rd(p[i].y); reverse(p,p+n); for(int i=n;i<2*n;++i) p[i]=p[i-n]; sumP[0]=p[0]; sumPQ[0]=Cross(p[2*n-1],p[0]); sumPQI[0]=0; for(int i=1;i<2*n;++i) { sumP[i]=sumP[i-1]+p[i]; ll tmp=Cross(p[i-1],p[i]); sumPQ[i]=sumPQ[i-1]+tmp; sumPQI[i]=(sumPQI[i-1]+tmp%mod*i)%mod; } ull A=sumPQ[n-1]; ll ans=0; int q=0; for(int i=0;i<n;++i) { q=max(q,i+2); while(q<n+i-2&&2ull*queryA(i,q+1)<=A) q++; if(2ull*queryA(i,q)>A) continue; ll tmp1=querySA(i+2,q,i); ans=(ans+((ll)(A%mod))*(q-i-1)-tmp1*2)%mod; } printf("%lld",(ans+mod)%mod); return 0; }

---

B - AGC034D - Manhattan Max Matching

题意

有$n$个三元组$(R{X}_i,R{Y}_i,R{C}_i)$表示在$(R{X}_i,R{Y}_i)$这个位置上有$R{C}_i$个红色的球；另有$n$个三元组$(B{X}_i,B{Y}_i,B{C}_i)$表示在$(B{X}_i,B{Y}_i)$这个位置上有$B{C}_i$个蓝色的球。保证$\sum B{C}_i=\sum R{C}_i$。你需要把红色的球和蓝色的球两两配对，使得配对的球两两之间的曼哈顿距离之和最大。$n\le 1000,1\le R{X}_i,R{Y}_i,B{X}_i,B{Y}_i\le 10^9,R{C}_i\le 10$。

Sol

考虑在$(x,y)$位置的一个球最终对答案的贡献，一定是下列四种类型中的一种：

1）$x+y$

2）$x-y$

3）$-x+y$

4）$-x-y$

我们只需要知道每个点的类型，就可以知道最终的答案。

而一种合法的确定类型的方案，则要求：1.红色中的1）和蓝色中的4）的数量相同，2.红色中的4）和蓝色中的1）数量相同，3.红色中的2）和蓝色中的3）的数量相同，4.红色中的3）和蓝色中的2）数量相同。

我们并不需要要求存在一种让$x+y$和$-x-y$配对的方式，使得$x_i+y_i$匹配到的$-x_j-y_j$满足$x_i\ge x_j,y_i\ge y_j$。这是因为这道题要求最大化答案，对于$x_i<x_j$或者$y_i<y_j$的情况显然有更优的方案使这一对的贡献为$|x_i-x_j|+|y_i-y_j|$，所以不考虑这种情况对我们求解是没有影响的。

建三排点，第一排$n$个点表示每个位置的红色球；第二排建$4$个点分别代表1),2),3),4)，第三排$n$个点表示蓝色的球。源点向第一排点连容量为球数费用为$0$的边，第一排点向1)连容量为$\infty$，费用为$x+y$的边，1)向第三排点连流量为$\infty$费用为$-x-y$的边，2)，3)，4)同理，最后第三排点向汇点连流量为球的数量、费用为$0$的边。跑最小费用最大流即可。

Code

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <queue> #define PII pair<int,int> #define MP make_pair #define fir first #define sec second #define PB push_back #define db long double #define ll long long using namespace std; template <class T> inline void rd(T &x) { x=0; char c=getchar(); int f=1; while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f; } const int N=1010,inf=1e9; inline int Abs(int x) { return x>0?x:-x; } int S,T; namespace Flow { const int N=5010; int head[N],cur[N],vis[N]; ll dis[N]; struct ed { int to,next,f; ll w; }; vector<ed> e; void init() { e.clear(); memset(head,-1,sizeof(head)); } void ad(int x,int y,int f,ll w) { e.PB((ed){y,head[x],f,w}); head[x]=e.size()-1; e.PB((ed){x,head[y],0,-w}); head[y]=e.size()-1; } queue<int> q; bool bfs() { memset(dis,-0x3f,sizeof(dis)); memcpy(cur,head,sizeof(cur)); dis[S]=0,q.push(S),vis[S]=1; while(!q.empty()) { int u=q.front(); q.pop(),vis[u]=0; for(int k=head[u];~k;k=e[k].next) if(e[k].f) { int v=e[k].to; if(dis[v]<dis[u]+e[k].w) { dis[v]=dis[u]+e[k].w; if(!vis[v]) q.push(v),vis[v]=1; } } } return dis[T]>-1e16; } int dfs(int u,int f) { if(u==T||!f) return f; int ret=0,tmp; vis[u]=1; for(int &k=cur[u];~k;k=e[k].next) if(e[k].f) { int v=e[k].to; if(dis[v]==dis[u]+e[k].w&&!vis[v]&&(tmp=dfs(v,min(f,e[k].f)))) { f-=tmp,ret+=tmp; e[k].f-=tmp,e[k^1].f+=tmp; if(!f) break; } } vis[u]=0; return ret; } ll work() { ll ans=0; while(bfs()) ans+=dis[T]*dfs(S,1e9); return ans; } } int rx[N],ry[N],rc[N]; int bx[N],by[N],bc[N]; int n; int main() { rd(n); for(int i=1;i<=n;++i) rd(rx[i]),rd(ry[i]),rd(rc[i]); for(int i=1;i<=n;++i) rd(bx[i]),rd(by[i]),rd(bc[i]); S=2*n+1,T=2*n+2; int p[4]; for(int i=0;i<4;++i) p[i]=2*n+3+i; Flow::init(); for(int i=1;i<=n;++i) { Flow::ad(S,i,rc[i],0); Flow::ad(i+n,T,bc[i],0); } for(int i=1;i<=n;++i) { Flow::ad(i,p[0],inf,rx[i]+ry[i]); Flow::ad(i,p[1],inf,rx[i]-ry[i]); Flow::ad(i,p[2],inf,-rx[i]+ry[i]); Flow::ad(i,p[3],inf,-rx[i]-ry[i]); Flow::ad(p[0],i+n,inf,-bx[i]-by[i]); Flow::ad(p[1],i+n,inf,-bx[i]+by[i]); Flow::ad(p[2],i+n,inf,bx[i]-by[i]); Flow::ad(p[3],i+n,inf,bx[i]+by[i]); } printf("%lld",Flow::work()); return 0; }

---

C - AGC024F Simple Subsequence Problem

题意

有一个字符串集$S$和一个整数$K$，你需要求出一个最长的字符串，使得这个字符串是$S$中至少$K$个字符串的子序列。如果有多个，则输出字典序最小的那个。

$S$的给出方式是：给出一个整数$N$，然后给出$N+1$个字符串$X_0,X_1,X_2\cdots X_N$，$X_i$的长度是$2^i$。对于$X_i$的第$j$个字符（0-base），这个字符是$1$则表示$j$的二进制表示这个字符串（可能有前导零，长度为$i$）属于$S$，这个字符是$0$则表示$j$对应的字符串不属于$S$。

$N\le 20,|K|\le |S|$

Sol

只要对每个字符串求出它是多少个字符串的子序列就可以了。

判断一个字符串是否为另一个字符串的子序列，可以贪心地用尽量靠前的字符去匹配。这样去匹配还有一个很好的性质：一个字符串在另一个字符串中匹配得到的结果是唯一的。

考虑将这个匹配的中间结果作为$dp$的状态：设$dp[s_1][s_2]$表示$s_1$是已经完成匹配的部分，$s_2$是剩下的可以用来匹配的部分，达到这种状态的方案数。

则转移有$3$种：1）从$s_2$中选出最靠前的一个$0$加在$s_1$的后面；2）从$s_2$中选出最靠前的一个$1$加在$s_1$的后面；3)结束匹配，转移到$s_2$是空串的状态。

初始化的时候，把$s_1$为空串、$s_2$是$S$中的字符串的状态的$dp$值赋为$1$。

最后字符串$s$作为子序列出现的次数就是$s_1$为$s$、$s_2$为空串的状态的$dp$值。

状态数$O(N{2}^N)$，总复杂度$O(N{2}^N)$。

Code

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define ll long long using namespace std; template <class T> inline void rd(T &x) { x=0; char c=getchar(); int f=1; while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f; } int f[1<<21][22]; char X[1<<20]; int n,K; int main() { rd(n),rd(K); for(int i=0;i<=n;++i) { scanf("%s",X); for(int j=0;j<(1<<i);++j) f[(1<<i)|j][i]=X[j]=='1'; } for(int i=n;i>=0;--i) for(int s=0;s<(1<<i);++s) for(int j=i;j>=0;--j) if(f[(1<<i)|s][j]) { int cur=f[(1<<i)|s][j]; int s1=s>>j; int s2=s&((1<<j)-1); if(j) f[(1<<i-j)|s1][0]+=cur; if(s2) { int p=j-1; while(!((s2>>p)&1)) p--; f[(1<<(i-(j-1-p)))|(s1<<p+1)|(1<<p)|(s2&((1<<p)-1))][p]+=cur; } if(((1<<j)-1)&(~s2)) { int p=j-1; while((s2>>p)&1) p--; f[(1<<(i-(j-1-p)))|(s1<<p+1)|(s2&((1<<p)-1))][p]+=cur; } } for(int i=n;i>=0;--i) for(int j=0;j<(1<<i);++j) if(f[(1<<i)|j][0]>=K) { for(int k=i-1;k>=0;--k) printf("%d",(j>>k)&1); return 0; } return 0; } if(((1<<j)-1)&(~s2)) { int p=j-1; while((s2>>p)&1) p--; f[(1<<(i-(j-1-p)))|(s1<<p+1)|(s2&((1<<p)-1))][p]+=cur; } } for(int i=n;i>=0;--i) for(int j=0;j<(1<<i);++j) if(f[(1<<i)|j][0]>=K) { for(int k=i-1;k>=0;--k) printf("%d",(j>>k)&1); return 0; } return 0; }