Parallelist

浅い夢だから 胸をはなれない

Atcoder Regular Contest 107 题解

发布于 2020-11-01 | 分类于 比赛报告 | 14分钟 | 2685字数 | 浏览量：

Pro A Simple Math

题意：给定 a,b,ca,b,c ，求 ∑i=1a∑j=1b∑k=1ci×j×k(mod998244353)\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}\sum\limits_{k=1}^{c}i\times j\times k\pmod{998244353} 的值。

数据范围：1≤a,b,c≤1091\leq a,b,c\leq10^9

简单的提取公因式可得原式等价于求 ∑i=1ai∑j=1bj∑k=1ck\sum\limits_{i=1}^{a}i\sum\limits_{j=1}^{b}j\sum\limits_{k=1}^{c}k 。

代码：

const int Mod=998244353;
int a,b,c;
int main(){
	
	r(a,b,c);
	a=(1ll*(a+1)*a/2)%Mod;
	b=(1ll*(b+1)*b/2)%Mod;
	c=(1ll*(c+1)*c/2)%Mod;
	w(1ll*a*b%Mod*c%Mod);
	return 0;
}

Pro B Quadruple

题意：给定 n,kn,k ，求有多少有序四元组 (a,b,c,d)(a,b,c,d) ，满足 1≤a,b,c,d≤n,a+b−c−d=k1\leq a,b,c,d\leq n,a+b-c-d=k 。

数据范围：1≤n≤105,−2(n−1)≤k≤2(n−1)1\leq n\leq 10^5,-2(n-1)\leq k\leq 2(n-1)

首先可以发现等于 kk 和等于 −k-k 的方案是一样的。我们把四元组看成两部分，分别是两个数的和。于是求出 ∀i∈[2,2n],a+b=i\forall i\in[2,2n],a+b=i 的二元组 (a,b)(a,b) 的方案就可以了。

代码：

const int N=2e5+5;
using namespace std;
int n,k,t[N];
long long ans;
int main(){
	
	r(n,k);
	k=abs(k);
	for(int i=2;i<=n+1;++i)
		t[i]=t[2*n-i+2]=i-1;
	for(int i=k+2;i<=2*n;++i)
		ans+=1ll*t[i]*t[i-k];
	w(ans);	
	return 0;
}

Pro C Shuffle Permutation

题意：给一个 n×nn\times n 的矩阵 aa 和正整数 kk 。Sigma 每次刻意任意选择下述一种操作来变换这个矩阵：（1）选择两个数 x,yx,y ，满足 ∀i∈[1,n] ax,i+ay,i≤k\forall i\in [1,n]\ a_{x,i}+a_{y,i}\leq k ，交换这两行；（2）选择两个数 x,yx,y ，满足 ∀i∈[1,n] ai,x+ai,y≤k\forall i\in[1,n]\ a_{i,x}+a_{i,y}\leq k ，交换这两列。请问 Sigma 总共可以获得多少种本质不同的矩阵。

数据规模：1≤n≤50,1≤k≤2×n2,ai,j1\leq n\leq 50,1\leq k\leq 2\times n^2,a_{i,j} 保证是 1∼n21\sim n^2 的一种重排

首先，由于 ai,ja_{i,j} 保证是 1∼n21\sim n^2 的一种重排，所以只要在两次变换中，存在任意一个操作只在两次变换中的一个出现时，得到的两个矩阵就是必然不同的。进一步观察发现，如果第 i,ji,j 行可以交换，第 j,kj,k 行可以交换，那么这三行的位置是可以任意重排的，对于列而言也是如此。同时，当交换任意两行时，是不会改变列的可换的方案的。所以我们分别用并查集维护行和列就行了。

代码：

const int N=55,Mod=998244353;
using namespace std;
int n,m,ans=1;
int f[N],fac[N],siz[N],a[N][N];
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
int main(){
	
	scanf("%d%d",&n,&m);
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=1ll*fac[i-1]*i%Mod;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
		scanf("%d",&a[i][j]);
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<=n-1;++i)
	for(int j=i+1;j<=n;++j){
		bool flag=true;
		for(int k=1;k<=n&&flag;++k)
			if(a[i][k]+a[j][k]>m) flag=false;
		if(flag) f[Find(i)]=Find(j);
	}
	for(int i=1;i<=n;++i) siz[Find(i)]++; 
	for(int i=1;i<=n;++i) ans=1ll*fac[siz[i]]*ans%Mod;
	for(int i=1;i<=n;++i) f[i]=i,siz[i]=0;
	for(int i=1;i<=n-1;++i)
	for(int j=i+1;j<=n;++j){
		bool flag=true;
		for(int k=1;k<=n&&flag;++k)
			if(a[k][i]+a[k][j]>m) flag=false;
		if(flag) f[Find(i)]=Find(j);
	}
	for(int i=1;i<=n;++i) siz[Find(i)]++; 
	for(int i=1;i<=n;++i) ans=1ll*fac[siz[i]]*ans%Mod;
	printf("%d\n",ans);
	return 0;
}

Pro D Number of Multisets

题意：给定 n,kn,k ，问有多少种选出 nn 个数的方案，满足 nn 个数的和为 kk 。这 nn 个数都须是 12i(i∈[0,∞))\frac{1}{2^{i}}(i\in[0,\infin)) 的形式。

范围：1≤k≤n≤3×1031\leq k\leq n\leq 3\times 10^3

当前处理的问题为选出 nn 个数满足和为 kk 。我们记这个的方案数为 f(n,k)f(n,k) 。我们可以把这个方案分成两类情况：

  • 至少选择一个 11 。此时问题转化为求解 f(n−1,k−1)f(n-1,k-1)
  • 不选择 11 。此时问题转化为：问有多少种选出 nn 个数的方案，满足 nn 个数的和为 kk 。这 nn 个数都须是 12i(i∈[1,∞))\frac{1}{2^{i}}(i\in[1,\infin)) 的形式。我们考虑这个子问题的限制条件与原问题的限制条件的关系。如果我们将这 nn 个数同时乘以二，那么子问题的限制条件就和原问题的限制条件一致了。此时问题转化为求解 f(n,2k)f(n,2k)

边界条件：f(n,k)=0(n<k),f(n,0)=[n=0]f(n,k)=0(n<k),f(n,0)=[n=0]

代码：

const int N=3e3+5,Mod=998244353;
using namespace std;
int f[N][N];
int solve(int n,int k){
    if(n<=k) return n==k;
    if(k==0) return 0;
    if(f[n][k]!=-1) return f[n][k];
    return f[n][k]=(solve(n-1,k-1)+solve(n,2*k))%Mod;
}
int main(){

    int n,k;r(n,k);
    memset(f,-1,sizeof f);
    w(solve(n,k));
    return 0;
}

Pro E Mex Mat

题意：给定一个 n×nn\times n 的矩阵 aa 的第一行和第一列，ai,j=mex(ai−1,j,ai,j−1)(i,j≥2)a_{i,j}=\text{mex}(a_{i-1,j},a_{i,j-1})(i,j\geq 2) 。第一行和第一列中只有 0,1,20,1,2 ，求这个矩阵中 0,1,20,1,2 的个数。

数据范围：1≤n≤5×1051\leq n\leq 5\times 10^5

mex\text{mex} 这个函数挺玄学的。我们打表可以发现，当 n≥4n\ge 4 后，恒有 ai,j=ai−1,j−1(i,j≥4)a_{i,j}= a_{i-1,j-1}(i,j\ge 4) 。

代码：

const int N=5e5+5;
using namespace std;
const int mex[3][3]={{1,2,1},{2,0,0},{1,0,0}};
int n;
int a[N],b[N];
long long c[3];
void run(int x){
    for(int i=2;i<=x;++i){
        a[i-1]=b[i];
        for(int j=i;j<=n;++j) 
            a[j]=mex[a[j-1]][a[j]],++c[a[j]];
        b[i]=a[i];
        for(int j=i+1;j<=n;++j)
            b[j]=mex[b[j-1]][b[j]],++c[b[j]];
    }
}
int main(){

    r(n);
    for(int i=1;i<=n;++i) r(a[i]),++c[a[i]];
    for(int i=2;i<=n;++i) r(b[i]),++c[b[i]];
    if(n<=5) run(n);
    else{ 
        run(5);
        for(int i=5;i<=n;++i)
            c[a[i]]+=n-i;
        for(int i=6;i<=n;++i)
            c[b[i]]+=n-i;
    }
    w(c[0],' '),w(c[1],' '),w(c[2],'\n');
    return 0;
}

Pro F Sum of Abs

题意：给定一张 nn 个点 mm 条边的无向图，每个点有两个值 ai,bia_i,b_i 。你可以选定一些点，每个点花费 aia_i 的代价删除它（以及与它相连的）。你的获利是每个连通块的 bib_i 的和的绝对值。你的收益是总获利减去总代价。求最大收益。

数据范围：1≤n,m≤300,1≤ai≤106,−106≤bi≤1061\leq n,m\leq 300,1\leq a_i\leq 10^6,-10^6\leq b_i\leq 10^6 图无重边无自环。

我们可以将绝对值拆为取 max⁡\max ，于是某一个连通块贡献的权值可以写作 max⁡(∑bi,∑−bi)\max(\sum b_i,\sum -b_i) 。所以，一个点 uu 对于答案的贡献只为三种：−au,bu,−bu-a_u,b_u,-b_u 。三个中选择一个，我们考虑最小割模型。设源点为 ss ，汇点为 tt ，我们将每个点 uu 拆为 u0,u1u_0,u_1 ，并连边 s→u0→u1→ts\rightarrow u_0\rightarrow u_1\rightarrow t ，边权依次为 −bi,ai,bi-b_i,a_i,b_i 。割去 uu 的哪条边，就意味着点 uu 的贡献形式（的负数）。

但是边 (u,v)(u,v) 会对我们割边造成限制。如果我们不删去 u,vu,v ，那么 u,vu,v 的贡献必须同时为 −bi-b_i 或者同时为 bib_i 。针对这条限制，我们新建两条边，分别为 u1→v0,v1→u0u_1\rightarrow v_0,v_1\rightarrow u_0 ，边权均为 ∞\infin 。除了针对限制外，这两条边加的很有讲究：如果直接割去了 u0→u1u_0\rightarrow u_1 或者割去了 v0→v1v_0\rightarrow v_1 ，那么这两条边必定无效，而这恰好也是我们所需要的。所以答案就是最小割的相反数。但是我们的边权中出现了负数，这是不能跑最大流的。故我们将每条非 ∞\infin 边都加上 abs(bi)\text{abs}(b_i) 。复杂度 O(n2(n+m))\mathcal{O}(n^2(n+m)) 。

代码：

const int N=6e2+5,M=3e3+5,INF=1e9;
using namespace std;
int n,m,s,t,ans,num=1;
int a[N],b[N],d[N],head[N],nt[M],to[M],cap[M];
bool BFS(){
    for(int i=s;i<=t;++i) d[i]=0;
    queue<int>q;q.push(s);d[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=nt[i]){
            if(!cap[i]||d[to[i]]) continue;
            d[to[i]]=d[u]+1;q.push(to[i]);
            if(to[i]==t) return true;
        }
    } 
    return false;
}
int dinic(int p,int flow){
    if(p==t) return flow;
    int res=flow;
    for(int i=head[p];i&&res;i=nt[i]){
        if(!cap[i]||d[to[i]]!=d[p]+1) continue;
        int k=dinic(to[i],min(cap[i],res));
        if(!k) d[to[i]]=0;
        cap[i]-=k;cap[i^1]+=k;res-=k;
    }
    return flow-res;
}
void Add(int x,int y,int z){
    ++num;nt[num]=head[x];head[x]=num;to[num]=y;cap[num]=z;
    ++num;nt[num]=head[y];head[y]=num;to[num]=x;cap[num]=0;
}
int main(){

    r(n,m);s=0,t=n+n+1;
    for(int i=1;i<=n;++i) r(a[i]);
    for(int i=1;i<=n;++i) r(b[i]);
    for(int i=1;i<=n;++i){
        ans+=abs(b[i]);Add(i,i+n,abs(b[i])+a[i]);
        if(b[i]>0) Add(s,i,b[i]+b[i]);
        else       Add(i+n,t,-b[i]-b[i]);
    }
    for(int i=1,x,y;i<=m;++i)
        r(x,y),Add(x+n,y,INF),Add(y+n,x,INF);
    int Max=0,flow=0;
    while(BFS())
        while(flow=dinic(s,INF)) Max+=flow;
    w(ans-Max);
    return 0;
}
# 比赛报告
OI 回忆录 上一篇
Atcoder Regular Contest 106 题解 下一篇
0%