ARC板刷计划-526互联

板刷自 ARC104 起所有 ARC 的 \(\text{C}\sim\text{E}\) 题。

进度：https://kenkoooo.com/atcoder/#/table/lsj2009。

ARC104

https://atcoder.jp/contests/arc104/tasks/arc104_c。

ARC104C

首先观察性质。容易发现的是，如果两个人在电梯上的时间段有交，必然只会是如下可能：

也就是说所有人在电梯上的时间段只有可能是长这样子的：

考虑枚举每个图中所画的分割线，具体而言，设 \(f_i\) 表示前 \(i\) 个时刻是否有合法答案，那么可以得到转移方程：

\[f_i=\bigvee_{j=1}^{i} f_{j-1}\wedge\text{check}(j,i) \]

那么关键在于这个 check 函数怎么写。如果说要求这个区间内所有人均满足条件，那么需要符合以下要求：

左端点在这个区间内的，右端点也必须要在这个区间内。
右端点在这个区间内的，左端点也必须要在这个区间内。
左端点必须在前半段。
右端点必须在后半段。
如果某个已知的区间在这个范围内，则其左端点相对于前半段和右端点相对于后半段位置应当是相等的。

然后就做完了，再判一下边界即可。

点击查看代码

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=2e2+5;
int p[N],cnt[N],l[N],r[N],n;
bool f[N];
bool check(int ql,int qr) {
    rep(i,ql,qr) {
        if(p[i]<0&&r[-p[i]]!=-1&&r[-p[i]]>qr)
            return false;
        if(p[i]>0&&l[p[i]]!=-1&&l[p[i]]<ql)
            return false;
    }
    int len=(qr-ql+1)>>1;
    rep(i,ql,ql+len-1) {
        if(p[i]>0)
            return false;
        if(p[i+len]<0)
            return false;
        if(p[i]!=0&&p[i+len]!=0&&p[i]+p[i+len]!=0)
            return false;
    }
    return true;
}
signed main() {
    scanf("%d",&n);
    rep(i,1,n) {
        scanf("%d%d",&l[i],&r[i]);
        if(l[i]!=-1&&r[i]!=-1&&l[i]>=r[i])
            return 0&puts("No");
        if(l[i]!=-1)
            p[l[i]]=-i,++cnt[l[i]];
        if(r[i]!=-1)
            p[r[i]]=i,++cnt[r[i]];
    }
	n<<=1;	
    rep(i,1,n) {
        if(cnt[i]>1)
            return 0&puts("No");
    }
    f[0]=true;
    rep(i,1,n) {
        for(int j=(i&1? 2:1);j<=i;j+=2)
            f[i]|=f[j-1]&check(j,i);
    }
    puts(f[n]? "Yes":"No");
    return 0;
}

ARC104D

应该算是比较套路的题。

遇到平均数，我们考虑将所有数字全部减掉 \(x\)，则平均数 \(=x\) 就变成了和为 \(0\)。我们定义一个状态 \(f_{i,j}\) 表示考虑只使用第 \(1\sim i\) 这几个数，每个数至多用 \(k\) 次，使得和为 \(j\) 的方案总数。

首先考虑这个东西有什么用。观察一下减 \(x\) 之后得到的数：

\[-(x-1),-(x-2),\cdots,-1,0,1,2,\cdots (n-x) \]

那么如何让这几个数和 \(=0\)？考虑在 \([-(x-1),-1]\) 中选几个数，在 \([1,n-x]\) 选几个数，使得选出来的数的和互为相反数，然后再选若干个 \(0\)，那么可以得到平均数 \(=x\) 时的答案：

\[ans=\sum\limits_j f_{x-1,j}\cdot f_{n-x,j}\cdot(k+1)-1 \]

其中最后一个 \(-1\) 是代表什么都不选的情况。

然后再考虑 \(f_{i,j}\) 怎么求。这一个是个典题（？，可以直接容斥做到 \(\Theta(n^2k)\)。

点击查看代码

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e2+5,M=1e6+5;
int f[N][M],n,k,MOD;
void add(int &a,int b) {
    a+=b;
    if(a>=MOD)
        a-=MOD;
}
void sub(int &a,int b) {
    a-=b;
    if(a<0)
        a+=MOD;
}
signed main() {
    scanf("%d%d%d",&n,&k,&MOD);
    f[0][0]=1;
    int sum=0;
    rep(i,1,n) {
        rep(j,0,sum)
            f[i][j]=f[i-1][j];
        sum+=i*k;
        rep(j,i,sum)
            add(f[i][j],f[i][j-i]);
        per(j,sum,i*(k+1))
            sub(f[i][j],f[i][j-i*(k+1)]);
    }
    rep(i,1,n) {
        int res=0;
        rep(j,0,sum)
            add(res,1ll*f[i-1][j]*f[n-i][j]%MOD*(k+1)%MOD);
        printf("%d\n",(res-1+MOD)%MOD);
    }
    return 0;
}

ARC104E

说实话感觉这个题质量不是很高，不如与它相似的 P3643 和 CF1295F。

看到 \(n\le 6\)，这几乎所有和值域无关的做法都能跑过去，所以给了我们充足的乱搞空间。

首先考虑暴力钦定每个数的相对大小 \(\{rk_n\}\)，需要 \(\Theta(n^n)\) 的时间（因为可能有数相等，所以不是 \(\Theta(n!)\)）。

然后丢与每个下标，我们取排名等于他的最小值。即 \(a_i=\min\limits_{rk_j=i} A_j\)，然后 \(m=\max\limits_{i=1}^n rk_i\)。

那么我们就把问题转换成了：

求有多少个序列 \(\{b_m\}\) 满足：

\(b_i\in[1,a_i]\)。

\(\forall i\in[1,m-1]\) 满足 \(b_i<b_{i+1}\)。

然后这个东西就和 CF1295F 基本上一样啊，只不过前者要求严格单调，后者要求非严格单调。简单来说就是，先把 \(a_i\) 离散化出来，变成若干个值域段，设 \(f_{i,j}\) 为对于前 \(i\) 个数而言，第 \(i\) 个数在第 \(j\) 段的方案总数。

那么我们考虑去枚举一个 \(k\)，让前 \(k-1\) 个数在第 \(1\sim j-1\) 段；第 \(k\sim i\) 个数在第 \(j\) 段。而前 \(k-1\) 个数在第 \(1\sim j-1\) 段的方案总数即为 \(\sum\limits_{x=1}^{j-1} f_{k-1,x}\)；第 \(k\sim i\) 个数在第 \(j\) 段的方案总数为 \(len_j \choose i-k+1\)。当然还需要判断的是第 \(k\sim i\) 个是否都可以取到第 \(j\) 段。

对于这个组合数的计算，虽然 \(len_j\) 很大，但是 \(i-k+1\) 确很小，所以每次可以直接 \(\Theta(n)\) 去暴力算。

所以得到方程：

\[f_{i,j}=\sum\limits_{k=1}^i {len_j \choose i-k+1}\sum\limits_{x=1}^{j-1} f_{k-1,x} \]

最终答案即为 \(\sum\limits_{i=1}^{a_m} f_{m,i}\)，由于本题数据范围非常小，所以也不需要 P3643 的前缀和优化，直接 \(\Theta(n^5)\) 暴力 dp 即可，最终复杂度是 \(\Theta(n^{n+5})\)。

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=10,MOD=1e9+7;
int qpow(int a,int b) {
	int res=1,base=a;
	while(b) {
		if(b&1)
			res=res*base%MOD;
		base=base*base%MOD; b>>=1;
	}
	return res;
}
int t[N],len;
int get_id(int x) {
	return lower_bound(t+1,t+len+1,x)-t;
}
void add(int &a,int b) {
	a+=b;
	if(a>=MOD)
		a-=MOD;
}
int C(int n,int m) {
	if(n>m)
		return 0;
	if(n>m-n)
		n=m-n;
	int res=1;
	rep(i,1,n)
		res=res*(m-i+1)%MOD*qpow(i,MOD-2)%MOD;
	return res;
}
int b[N],s[N],g[N],a[N],f[N][N],ans,n;
int solve() {
    cl(a,0x3f);
	int m=0;
    rep(i,1,n) {
        chkmin(a[s[i]],b[i]);
        chkmax(m,s[i]);
    }
	t[++len]=0;
	rep(i,1,m) 
		t[++len]=a[i];
	sort(t+1,t+len+1);
	len=unique(t+1,t+len+1)-t-1;
	rep(i,1,m)
		a[i]=get_id(a[i]);
    cl(f,0);
	f[0][1]=1;
	rep(i,1,m) {
		rep(j,2,a[i]) {
			int res=INFLL;
			per(k,i,1) {
				chkmin(res,a[k]);
				if(j>res)
					break;
				rep(x,1,j-1)
					add(f[i][j],C(i-k+1,t[j]-t[j-1])*f[k-1][x]%MOD);
			}
		}
	}
	int ans=0;
	rep(i,2,len)
		add(ans,f[m][i]);
	return ans;
}
int c[N];
bool check() {
	rep(i,1,n)
		c[i]=s[i];
	sort(c+1,c+n+1);
	rep(i,1,n) {
		if(c[i]-c[i-1]>1)
			return false;
	}
	return true;
}
void dfs(int x) {
    if(x==n+1) {
        if(!check())
			return;
        int res=0;
		cl(g,0);
        rep(i,1,n) {
            rep(j,0,i-1) {
                if(s[i]>s[j])
                    chkmax(g[i],g[j]+1);
            }
            chkmax(res,g[i]);
        }
        add(ans,res*solve()%MOD);
        return;
    }
    rep(i,1,n) {
        s[x]=i; dfs(x+1);
    }
}
signed main() {
    scanf("%lld",&n);
    rep(i,1,n)
        scanf("%lld",&b[i]);
    dfs(1);
    rep(i,1,n)
        ans=ans*qpow(b[i],MOD-2)%MOD;
    printf("%lld\n",ans);
    return 0;
}

板刷题解round educational

板刷2023 10 04