【Codeforces】Educational Codeforces Round 59/Round1107 D-G题解

传送门:CF1107
有一种CF越来越板/水的感觉，完全是手速场(不看题解就水完了啊

D.Compression

前缀和后$check$的复杂度可以做到 O ( ( n x ) 2 ) O((\dfrac{n}{x})^2) O((xn​)2)。

称矩阵是$k$可行的当且仅当$x=k$时满足题中条件。

若矩阵同时是$a,b$可行的，且$gcd(a,b)=1$，则矩阵也是$a\cdot b$可行的。

分解$n$的质因子后枚举每个质因子的幂次即可。

复杂度玄学能过。

#include
typedef long long ll;
using namespace std;
const int N=5205;int n,s[N][N],p[N],num,ans;char cp;
inline int rd(int &x)
{cp=getchar();x=0;for(;!isdigit(cp);cp=getchar());for(;isdigit(cp);cp=getchar()) x=x*10+(cp^48);
}inline void ins(int x,int y)
{int i,msk;for(cp=getchar();;cp=getchar()){if(cp>='0' && cp<='9'){msk=cp-'0';break;}if(cp>='A' && cp<='F'){msk=10+cp-'A';break;}}for(i=0;i<4;++i) s[x][y+i]=(msk>>(3-i)&1);
}inline bool ck(int x)
{int i,j,k,bs=x*x;for(i=x;i<=n;i+=x)for(j=x;j<=n;j+=x){k=s[i][j]-s[i-x][j]-s[i][j-x]+s[i-x][j-x];if((k!=bs)&&(k!=0)) return false;}return true;
}int main(){int i,j,k;scanf("%d",&n);for(i=1;i<=n;++i)for(j=1;j<=n;j+=4) ins(i,j);for(i=1;i<=n;++i)for(j=1;j<=n;++j)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];k=n;for(i=2;i*i<=k;++i) if(!(k%i)){p[++num]=i;for(;!(k%i);k/=i);}if(k>1) p[++num]=k;ans=1;for(i=1;i<=num;++i){for(k=p[i],j=k;!(n%j);j*=k){if(!ck(j)) break;}ans*=(j/k);}printf("%d",ans);return 0;
} 

E.Vasya and Binary String

先完全背包求出 C i C_i Ci​表示删除连续一段$0/1$的最大花费。

$dp[l][r][0/1][len]$表示将区间$[l,r]$删除到只剩下$len$个$0/1$的最大代价，$g[l][r]$表示将区间$[l,r]$全部删除的最大代价。

d p [ l ] [ r ] [ S r ] [ l e n ] = m a x ( d p [ l ] [ k ] [ S r ] [ l e n − 1 ] + g [ k + 1 ] [ r − 1 ] ) dp[l][r][S_r][len]=max(dp[l][k][S_r][len-1]+g[k+1][r-1]) dp[l][r][Sr​][len]=max(dp[l][k][Sr​][len−1]+g[k+1][r−1])
g [ l ] [ r ] = m a x ( d p [ l ] [ k ] [ 0 / 1 ] [ l e n ] + C l e n + g [ k + 1 ] [ r ] ) g[l][r]=max(dp[l][k][0/1][len]+C_{len}+g[k+1][r]) g[l][r]=max(dp[l][k][0/1][len]+Clen​+g[k+1][r])

复杂度 O ( n 4 ) O(n^4) O(n4)

#include
typedef long long ll;
using namespace std;
const int N=105;int n,a[N];
char s[N];
ll dp[N][N][2][N],g[N][N],nf,cn[2],c[N];inline void upp(ll &x,ll y){if(y>x) x=y;}int main(){int i,j,k,l,r;memset(dp,-0x3f,sizeof(dp));memset(g,-0x3f,sizeof(g));nf=g[0][0];scanf("%d%s",&n,s+1);for(i=1;i<=n;++i) scanf("%d",&a[i]),s[i]-='0';for(i=1;i<=n;++i)for(j=n;j>=i;--j) c[j]=max(c[j],c[j-i]+a[i]);for(i=1;i<=n;++i) dp[i][i][s[i]][1]=0,g[i+1][i]=0;g[1][0]=0;for(l=n;l;--l)for(r=l;r<=n;++r)for(i=1;l+i-1<=r;++i){for(k=0;k<2;++k) cn[k]=dp[l][r][k][i];for(k=r+1;k<=n;++k) if(cn[s[k]]>nf)upp(dp[l][k][s[k]][i+1],cn[s[k]]+g[r+1][k-1]);for(k=r;k<=n;++k)upp(g[l][k],max(cn[0],cn[1])+c[i]+g[r+1][k]);}printf("%I64d",g[1][n]);return 0;
} 

F.Vasya and Endless Credits

构造二分图，左部$n$个点分别表示$n$个贷，右部$n$个点中第$i$个点表示倒数第$i$个月借贷。 g ( i , j ) = m a x ( 0 , a i − m i n ( j − 1 , k i ) × b i ) g(i,j)=max(0,a_i-min(j-1,k_i)\times b_i) g(i,j)=max(0,ai​−min(j−1,ki​)×bi​)

那么就是裸的二分图最大权匹配。费用流会T，跑个KM即可。

#include
typedef long long ll;
using namespace std;
const int N=505;
const ll inf=1e18;int n,tim,vs[2][N],bel[N];
ll g[N][N],tg[2][N],slack[N],ans;inline void upp(ll &x,ll y){if(y>x) x=y;}
inline void dnn(ll &x,ll y){if(y<x) x=y;}bool dfs(int x)
{int i;ll v;vs[0][x]=tim;for(i=1;i<=n;++i) if(vs[1][i]!=tim){v=tg[0][x]+tg[1][i]-g[x][i];if(v==0){vs[1][i]=tim;if((!bel[i])||dfs(bel[i])){bel[i]=x;return true; } }else dnn(slack[i],v);}return false;
} int main(){int i,j,x,y,z;ll d;scanf("%d",&n);for(i=1;i<=n;++i){scanf("%d%d%d",&x,&y,&z);for(j=1;j<=n;++j) g[i][j]=max(0LL,x-(ll)y*min(j-1,z));}for(i=1;i<=n;++i){for(d=0LL,j=1;j<=n;++j)upp(d,g[i][j]);tg[0][i]=d;	}for(x=1;x<=n;++x){memset(slack,0x7f,sizeof(slack));for(;;){tim++;if(dfs(x)) break;d=inf;for(i=1;i<=n;++i) if(vs[1][i]!=tim) dnn(d,slack[i]);for(i=1;i<=n;++i) if(vs[0][i]==tim) tg[0][i]-=d;for(i=1;i<=n;++i) vs[1][i]==tim?tg[1][i]+=d:slack[i]-=d;}}for(i=1;i<=n;++i) ans+=g[bel[i]][i];printf("%I64d",ans);return 0;
}

G - Vasya and Maximum Profit

设 e i = d i − d i − 1 e_i=d_i-d_{i-1} ei​=di​−di−1​。单调栈对于求出 [ l i , r i ] [l_i,r_i] [li​,ri​]表示 m a x j = l i r i e j = e i max_{j=l_i}^{r_i} e_j=e_i maxj=li​ri​​ej​=ei​的最大区间。

再线段树维护一下区间前缀和后缀和最大值即可。

#include
typedef long long ll;
using namespace std;
const int N=3e5+10;int n,a,lf[N],rt[N];
ll v[N],prf[N],suf[N],ans;
int c[N],d[N],stk[N],top;char cp;
inline void rd(int &x)
{cp=getchar();x=0;for(;!isdigit(cp);cp=getchar());for(;isdigit(cp);cp=getchar()) x=x*10+(cp^48);
}#define lc k<<1
#define rc k<<1|1
#define mid (l+r>>1)
#define pu(k) mx[k]=max(mx[lc],mx[rc])
struct seg{ll mx[N<<2];void build(int k,int l,int r){if(l==r) {mx[k]=v[l];return;}build(lc,l,mid);build(rc,mid+1,r);pu(k);}ll ask(int k,int l,int r,int L,int R){if(L<=l && r<=R) return mx[k];if(R<=mid) return ask(lc,l,mid,L,R);if(L>mid) return ask(rc,mid+1,r,L,R);return max(ask(lc,l,mid,L,R),ask(rc,mid+1,r,L,R));}}qz,hz;int main(){int i,j,k,pre=0;ll res;rd(n);rd(a);v[0]=v[n+1]=0LL; for(i=1;i<=n;++i){rd(d[i]);rd(c[i]);k=d[i];d[i]-=pre;pre=k;c[i]=a-c[i];v[i]=v[i-1]+c[i];ans=max(ans,(ll)c[i]);}qz.build(1,1,n);memcpy(prf,v,sizeof(prf));	for(i=n;i;--i) v[i]=v[i+1]+c[i];hz.build(1,1,n);memcpy(suf,v,sizeof(suf));stk[0]=1;for(i=2;i<=n;++i){for(;top && d[stk[top]]<=d[i];--top)rt[stk[top]]=i-1;lf[i]=stk[top];stk[++top]=i;}for(;top;--top) rt[stk[top]]=n;for(i=2;i<=n;++i){res=max(0LL,qz.ask(1,1,n,i,rt[i])-prf[i-1]);res+=hz.ask(1,1,n,lf[i],i-1)-suf[i];ans=max(ans,res-(ll)d[i]*d[i]);}printf("%I64d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！