板刷自 ARC104 起所有 ARC 的 \(\text{C}\sim\text{E}\) 题。
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;
}