Codeforce 水题报告(2)

又水了一发Codeforce ，这次继续发发题解顺便给自己PKUSC攒攒人品吧

CodeForces 438C：The Child and Polygon:

描述：给出一个多边形，求三角剖分的方案数（n<=200）。

首先很明显可能是区间dp，我们可以记f[i][j]为从i到j的这个多边形的三角剖分数，那么f[i][j]=f[i][k]*f[j][k]*(i,j,k是否为1个合格的三角形)

Code：

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 typedef pair<double,double> ii;
 #define fi first
 #define se second
 #define maxn 410
 #define mod 1000000007
 int f[maxn][maxn],n;
 ii a[maxn];
 inline double cross(ii x,ii y,ii z) {
     return (y.fi-x.fi)*(z.se-x.se)-(y.se-x.se)*(z.fi-x.fi);
 }
 inline bool check() {
     double ans=;
     for (int i=;i<=n;i++) ans+=cross(a[],a[i-],a[i]);
     return ans>;
 }
 inline void revice(){
     for (int i=,j=n;i<j;i++,j--) swap(a[i],a[j]);
 }
 int main(){
     scanf("%d",&n);
     for (int i=;i<=n;i++) scanf("%lf%lf",&a[i].fi,&a[i].se);
     if (check()) revice();
     for (int i=;i+<=n;i++) f[i][i+]=;
     for (int l=;l<=n-;l++)
         for (int i=;i+l<=n;i++)
             for (int j=i+;j<i+l;j++)
                 (f[i][i+l]+=f[i][j]*1ll*f[j][i+l]%mod*(cross(a[i],a[j],a[i+l])<?:))%=mod;
     printf("%d\n",f[][n]);
     return ;
 }

CodeForces 438D：The Child and Sequence

描述：给一个序列，要求支持区间取模，区间求和，单点修改（n<=10^5）

考虑如何用线段树来搞这个东西，很明显对于所有区间取模操作都必须用搞到点，但是如果我们加入一个小优化（只有区间序列的最大值大于那个区间的话，才往下传递）然后我们就可以解决这个问题啦。

为啥？我们可以发现当一个数取模的时候至少变小一半，因此每个数最多取模log a[i]次，所以总的时间复杂度为n log^2 n

Code:

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 #define maxn 101000
 typedef long long ll;
 struct node {
     int l,r,lz,mx;bool b;ll s;
 }t[maxn*];
 int a[maxn];
 #define lc (x<<1)
 #define rc (lc^1)
 #define mid ((l+r)>>1)
 inline void update(int x){
     t[x].s=t[lc].s+t[rc].s;
     t[x].mx=max(t[lc].mx,t[rc].mx);
     t[x].b=t[lc].b&t[rc].b;
 }
 inline void pb(int x) {
     if (!t[x].lz) return ;
     if (t[x].l==t[x].r) {
         t[x].b=;t[x].lz=;return ;
     }
     pb(lc);pb(rc);
     if (t[lc].mx>=t[x].lz) {
         t[lc].mx%=t[x].lz;
         t[lc].lz=t[x].lz;
         t[lc].s%=t[x].lz;
         t[lc].b=;
     }if (t[rc].mx>=t[x].lz) {
         t[rc].mx%=t[x].lz;
         t[rc].lz=t[x].lz;
         t[rc].s%=t[x].lz;
         t[rc].b=;
     }
     t[x].lz=;
     update(x);
 }
 void build(int x,int l,int r) {
     t[x].l=l,t[x].r=r;
     t[x].lz=;t[x].b=;
     if (l==r) {t[x].s=t[x].mx=a[l];return ;}
     build(lc,l,mid);build(rc,mid+,r);
     update(x);
 }
 ll sum(int x,int x1,int y1) {
     int l=t[x].l,r=t[x].r;
     if (y1<l||x1>r) return ;
 //    pb(x);
     if (x1<=l&&r<=y1) return t[x].s;
     ll ans=sum(lc,x1,y1)+sum(rc,x1,y1);
     update(x);
     return ans;
 }
 void set(int x,int y,int z){
     int l=t[x].l,r=t[x].r;
     if (l>y||r<y) return;
     if (l==r) {t[x].s=t[x].mx=z;return ;}
 //    pb(x);
     set(lc,y,z);set(rc,y,z);
     update(x);
 }
 void mod(int x,int x1,int y1,int z){
     int l=t[x].l,r=t[x].r;
     if (y1<l||x1>r) return ;
 //    pb(x);
     if (t[x].mx<z) return ;
     if (l==r) {
         t[x].mx%=z;t[x].s%=z;return ;
     }
     mod(lc,x1,y1,z);mod(rc,x1,y1,z);
     update(x);
 }
 int main(){
     int n,m;
     scanf("%d%d",&n,&m);
     for (int i=;i<=n;i++) scanf("%d",a+i);
     build(,,n);
     while (m--) {
         int opt,l,r,x,y;
         scanf("%d",&opt);
         switch(opt) {
             case :
                 scanf("%d%d",&l,&r);
                 printf("%I64d\n",sum(,l,r));
                 break;
             case :
                 scanf("%d%d%d",&l,&r,&x);
                 mod(,l,r,x);
                 break;
             case :
                 scanf("%d%d",&x,&y);
                 set(,x,y);
                 break;
         }
     }
     return ;
 }

CodeForces 434D：Nanami's Power Plant

描述：有n个节点，每个节点可以取一个xi（li<=xi<=ri）xi为整数，然后对于每个节点的权值为ai*x^2+bi*x同时需要满足某些xu-xv<=w的限制

既然是整数那么我们就可以直接用网络流啦，对每个节点的每个取值拆下，然后连边权为权值的边，然后就是最小割啦。接下来再考虑那些限制的条件，我们可以对所有相邻的东西可以直接连一个x[u]->x[v]+w，流量为inf的边，就可以限制到啦

Code:

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 #define maxn 15100
 #define maxm 250000
 struct edges{
     int to,next,cap;
 }edge[maxm*];
 int next[maxn],L,Cnt;
 #define inf 0x7fffffff
 inline void addedge(int x,int y,int z){
     L++;
     edge[L*]=(edges){y,next[x],z};next[x]=L*;
     edge[L*+]=(edges){x,next[y],};next[y]=L*+;
 }
 int h[maxn],gap[maxn],p[maxn],s,t;
 int sap(int u,int flow){
     if (u==t) return flow;
     int cnt=;
     for (int i=p[u];i;i=edge[i].next)
         if (edge[i].cap&&h[edge[i].to]+==h[u]) {
             int cur=sap(edge[i].to,min(flow-cnt,edge[i].cap));
             edge[i].cap-=cur;edge[i^].cap+=cur;
             p[u]=i;
             if ((cnt+=cur)==flow) return flow;
         }
     if (!(--gap[h[u]])) h[s]=Cnt;
     gap[++h[u]]++;p[u]=next[u];
     return cnt;
 }
 inline int maxflow(){
     for (int i=;i<=Cnt;i++) p[i]=next[i];
     memset(h,,sizeof(h));
     memset(gap,,sizeof(gap));
     gap[]=Cnt;
     int flow=;
     while (h[s]<Cnt) flow+=sap(s,inf);
     return flow;
 }
 #define maxk 55
 int a[maxk],b[maxk],c[maxk],st[maxk];
 int l[maxk],r[maxk];
 inline int fun(int x,int y) {return a[x]*y*y+b[x]*y+c[x];}
 inline int id(int x,int y) {return st[x]+y-l[x];}
 int main(){
     int n,m,mx=;
     scanf("%d%d",&n,&m);
     s=++Cnt,t=++Cnt;
     for (int i=;i<=n;i++) scanf("%d%d%d",a+i,b+i,c+i);
     for (int i=;i<=n;i++) {
         scanf("%d%d",l+i,r+i);
         st[i]=Cnt+;
         Cnt+=r[i]-l[i]+;
         for (int j=l[i];j<=r[i];j++) mx=max(mx,fun(i,j));
     }
     for (int i=;i<=n;i++) {
         addedge(s,id(i,l[i]),inf);
         for (int j=l[i];j<=r[i];j++) addedge(id(i,j),id(i,j+),mx-fun(i,j));
         addedge(id(i,r[i]+),t,inf);
     }
     while (m--) {
         int u,v,d;
         scanf("%d%d%d",&u,&v,&d);
         for (int i=l[u];i<=r[u];i++)
             if (i-d>=l[v]&&i-d<=r[v]+)
                 addedge(id(u,i),id(v,i-d),inf);
     }
     printf("%d\n",mx*n-maxflow());
 }

CodeForces 543C:Remembering Strings

描述：给定一堆字符串，改变某个字符需要一定的花费，求使所有的字符串都是好记的（存在一位的字符是该位中的唯一一个）（n<=20,len<=20）

很神奇的一道题，考虑用数位dp来解决这道题。我们考虑如何使一个字符串变成好记的，很简单只要改变某一位的字符即可，或者需要把这种字符都改变的话，那么花费是sum-mx（除了花费最大的不变，其他都需要改变）然后就行啦

实现的话用了一直比较鬼畜的写法，结果意外的短，详情可以看代码

Code:

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 #define maxn 23
 char s[][];
 int f[<<],a[][];
 int n;
 inline int lowbit(int x) {
     for (int i=;i<n;i++) if (!((<<i)&x)) return i;
 }
 int main(){
     int m;
     scanf("%d%d",&n,&m);
     for (int i=;i<n;i++) scanf("%s",s[i]+);
     for (int i=;i<n;i++)
         for (int j=;j<=m;j++) scanf("%d",&a[i][j]);
     memset(f,0x3f,sizeof(f));
     f[]=;
     for (int i=;i<(<<n)-;i++) {
         int x=lowbit(i);
         for (int j=;j<=m;j++) {
             f[i|(<<x)]=min(f[i|(<<x)],f[i]+a[x][j]);
             int y=,sum=,mx=;
             for (int k=;k<n;k++) {
                 if (s[x][j]==s[k][j]) {
                     y|=<<k;
                     sum+=a[k][j];
                         mx=max(a[k][j],mx);
                 }
             }
             f[i|y]=min(f[i|y],f[i]+sum-mx);
         }
     }
     printf("%d\n",f[(<<n)-]);
     return ;
 }

CodeForces 543D：Road Improvement

已知有一颗树，对所有点求删去某些边，使得其他点到该点至多经过一条坏边的方案数（n<=2*10^5）

很明显是树形dp，那么f[x]=pai(f[ch[x]]+1)

考虑怎么从祖先的答案算出自己的答案，很明显吧自己除去就能把祖先当自己的子树干了

除的时候不能直接用乘法逆元（f[x]可能为0 ), 需要存一个前缀和还有后缀和

Code:

     #include<cstdio>
     #include<iostream>
     #include<cstring>
     #include<algorithm>
     #include<vector>
     using namespace std;
     typedef long long ll;
     #define maxn 200100
     #define mod 1000000007
     vector<int> e[maxn];
     vector<ll> s[][maxn];
     #define pb push_back
     ll f[maxn],sum[maxn];
     int ans[maxn],fa[maxn];
     inline ll power(ll x,int y){
         ll ans=;
         for (;y;y>>=) {
             if (y&) (ans*=x)%=mod;
             (x*=x)%=mod;
         }
         return ans;
     }
     int q[maxn];
     int main(){
         int n;
         scanf("%d",&n);
         if (n==) {printf("%d\n",);return ;}
         for (int i=;i<=n;i++) {
             scanf("%d",fa+i);
             e[fa[i]].pb(i);
         }
         q[]=;
         for (int l=,r=,u=q[];l<=r;u=q[++l]) {
             for (int i=;i<e[u].size();i++) q[++r]=e[u][i];
         }
         for (int r=n,u=q[n];r;u=q[--r]) {
             ll sum=;
             s[][u].resize(e[u].size());
             s[][u].resize(e[u].size());
             for (int i=;i<e[u].size();i++) {
                 s[][u][i]=sum;
                 (sum*=f[e[u][i]]+)%=mod;
             }
             sum=;
             for (int i=e[u].size()-;i+;i--) {
                 s[][u][i]=sum;
                 (sum*=f[e[u][i]]+)%=mod;
             }
             f[u]=sum;
         }
         sum[]=;
         for (int l=,u=q[];l<=n;u=q[++l]) {
             ans[u]=f[u]*(sum[u]+)%mod;
             for (int i=;i<e[u].size();i++)
                 sum[e[u][i]]=s[][u][i]*s[][u][i]%mod*(sum[u]+)%mod;
         }
         for (int i=;i<=n;i++) printf("%d ",ans[i]);
         return ;
     }

CodeForces 546E：Soldier and Traveling

描述：有n个城市和m条道路，每个城市有一定的士兵，士兵可以移动到相邻的城市，求是否存在一种移动方式使得每个城市的驻兵数为某个值（n<=100,m<=200)

很明显是网络流吧，拆点然后随便搞搞即可

Code:

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 #define maxn 300
 #define maxm 10000
 struct edges{
     int to,next,cap;
 }edge[maxm*];
 int next[maxn],L,Cnt;
 #define inf 0x7fffffff
 inline void addedge(int x,int y,int z){
     L++;
     edge[L*]=(edges){y,next[x],z};next[x]=L*;
     edge[L*+]=(edges){x,next[y],};next[y]=L*+;
 }
 int h[maxn],gap[maxn],p[maxn],s,t;
 int sap(int u,int flow){
     if (u==t) return flow;
     int cnt=;
     for (int i=p[u];i;i=edge[i].next)
         if (edge[i].cap&&h[edge[i].to]+==h[u]) {
             int cur=sap(edge[i].to,min(flow-cnt,edge[i].cap));
             edge[i].cap-=cur;edge[i^].cap+=cur;
             p[u]=i;
             if ((cnt+=cur)==flow) return flow;
         }
     if (!(--gap[h[u]])) h[s]=Cnt;
     gap[++h[u]]++;p[u]=next[u];
     return cnt;
 }
 inline int maxflow(){
     for (int i=;i<=Cnt;i++) p[i]=next[i];
     memset(h,,sizeof(h));
     memset(gap,,sizeof(gap));
     gap[]=Cnt;
     int flow=;
     while (h[s]<Cnt) flow+=sap(s,inf);
     return flow;
 }
 #define maxk 110
 int a[maxk][],ans[maxk][maxk];
 int main(){
     freopen("1.in","r",stdin);
     int n,m,sum=,tmp=;
     scanf("%d%d",&n,&m);
     s=++Cnt,t=++Cnt;
     for (int i=;i<=n;i++) a[i][]=++Cnt,a[i][]=++Cnt;
     for (int i=;i<=n;i++) {
         int x;
         scanf("%d",&x);
         tmp+=x;
         addedge(s,a[i][],x);
     }
     for (int i=;i<=n;i++) {
         int x;
         scanf("%d",&x);
         sum+=x;
         addedge(a[i][],a[i][],inf);
         addedge(a[i][],t,x);
     }
     for (int i=;i<=m;i++) {
         int x,y;
         scanf("%d%d",&x,&y);
         addedge(a[x][],a[y][],inf);
         addedge(a[y][],a[x][],inf);
     }
     if (maxflow()!=sum||sum!=tmp) {
         printf("NO\n");
         return ;
     }
     puts("YES");
     for (int i=;i<=L;i++) {
         ans[(edge[i*+].to-)>>][(edge[i*].to-)>>]=edge[i*+].cap;
     }
     for (int i=;i<=n;i++,puts(""))
         for (int j=;j<=n;j++) printf("%d ",ans[i][j]);
     return ;
 }

CodeForces 534D：Handshakes

描述：有个房子，有n个人按顺序进去，一个人进去就会跟房间中空闲的人握手，每3个人可以组队做事，给定握手数，求方案

我们从0开始，每次看+1的有没有人，没有就-3，完了

Code:

 #include<cstdio>
 #include<cstring>
 #include<cstring>
 #include<algorithm>
 #include<stack>
 using namespace std;
 #define maxn 201000
 stack<int> s[maxn];
 int ans[maxn];
 int main(){
     int n,x;
     scanf("%d",&n);
     for (int i=;i<=n;i++) {
         scanf("%d",&x);
         s[x].push(i);
     }
     int t=,cnt=;
     while (t>=) {
         if (s[t].empty()) {t-=;continue;}
         ans[++cnt]=s[t].top();s[t].pop();t++;
     }
     if (cnt!=n) {
         puts("Impossible");
         return ;
     }
     puts("Possible");
     for (int i=;i<=n;i++) printf("%d ",ans[i]);
     return ;
 }

CodeForces 545E：Paths and Trees

给定一个图，求权值和最小的最短路树

那么最短路图建好，模拟克鲁斯卡尔算法，拍个序，又由于是个有向树，所以除了点u外都只有一个父亲，维护这个性质即可

CodeForces 542F:Quest

给定若干个节点作为二叉树的儿子节点，每个节点有其深度限制及权值，求构建一颗二叉树，使其权值最大

按深度限制从大到小干，每次把两个最大的合成一个小的即可

Code:

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<queue>
 using namespace std;
 #define maxn 110
 priority_queue<int> q[maxn];
 int main(){
     int n,t,x,y;
     freopen("1.in","r",stdin);
     scanf("%d%d",&n,&t);
     for (int i=;i<=n;i++) {
         scanf("%d%d",&x,&y);
         q[x].push(y);
     }
     int ans=;
     for (int i=;i<=t;i++) {
         while (!q[i-].empty()) {
             int u=q[i-].top();q[i-].pop();
             if (!q[i-].empty()) {
                 u+=q[i-].top();
                 q[i-].pop();
             }
             q[i].push(u);
         }
         if (!q[i].empty()) ans=max(ans,q[i].top());
     }
     printf("%d\n",ans);
     return ;
 }

好了就写到这里啦，代码回来再贴。回去收东西啦。