Preface
补题,这场比赛的时候被拉去开科研组会了,所以就没现场打了
这两天军训在伤病连划水,白天可以好好想题目舒服的一批
这场D题确实很妙,需要一些竞赛图相关的知识才能想到转化,不过也算是学到一个重要trick了吧
A - Divide String
显然只要考虑能否分成两个串即可,首先如果存在\(i\in[2,n]\)使得\(s_i>s_1\)则直接以\(i\)为开头断开即可
否则对于所有\(s_i=s_1\)的位置,暴力检验从这里分开是否合法即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int t,n; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; bool flag=0; scanf("%d%s",&n,s+1);
for (i=2;i<=n&&!flag;++i) if (s[i]>s[1]) puts("Yes"),flag=1;
if (flag) continue;
for (i=2;i<=n&&!flag;++i) if (s[i]==s[1])
{
int sign=0; for (j=1;j<=min(i-1,n-i+1);++j)
if (s[j]!=s[i+j-1]) { sign=s[j]-s[i+j-1]; break; }
if (sign<0||(sign==0&&i-1<n-i+1)) flag|=1;
}
puts(flag?"Yes":"No");
}
return 0;
}
B - Favorite Game
首先我们肯定只对\(a_1,a_2\)修改是最优的,然后刚开始一眼想到二分答案,再感觉可以三分一下\(a_1\)减少的次数
然后写了一发发现样例都过不去,遂赶紧发现是个丁真题
我们给\(a_3\sim a_n\)排序后,枚举所有长度为\(m\)的区间\(a_i\sim a_{i+m-1}\),考虑把\(a_1,a_2\)变成这个能涵盖区间所需的最小代价即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,m,a[N],ans=2e9;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
for (sort(a+3,a+n+1),i=3;i+m-1<=n;++i)
ans=min(ans,max(0,a[1]-a[i])+max(0,a[i+m-1]-a[2]));
return printf("%d",ans),0;
}
C - Harmonic Mean
有意思的构造题,首先不难想到用裂项公式来构造,因为\(\frac{1}{x(x+1)}=\frac{1}{x}-\frac{1}{x+1}\),所以我们总有如下构造方案(在\(n\ge 3\)时):
不难发现如果\(n\)不能表示成\(k(k+1)\)的形式的话就已经做完了,现在就是要考虑重复的情况
由于\(k(k+1)\)一定是偶数,那么如果\(n\)可以被这样表示那么\(n-1\)就一定不能被这样表示,因此我们可以先用\(n-1\)个数表示出\(\frac{1}{2}\),然后再填一个\(\frac{1}{2}\)上去即可
举个例子对于\(n=6=2\times 3\),按照上面的方法分解出就是\(1=\frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}+\frac{1}{30}+\frac{1}{6}\)是不合法的
那么我们可以先处理\(n=5\)的情况,\(1=\frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}+\frac{1}{5}\),然后两边同乘上\(\frac{1}{2}\)得到\(\frac{1}{2}=\frac{1}{4}+\frac{1}{12}+\frac{1}{24}+\frac{1}{40}+\frac{1}{10}\),最后再加上\(\frac{1}{2}\)就可以用\(6\)个数表示\(1\)了
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
if (scanf("%d",&n),n==1) { puts("Yes\n1"); continue; }
if (n==2) { puts("No"); continue; }
RI i; int t=0; for (i=1;i*(i+1)<=n;++i) if (n==i*(i+1)) t=i;
if (!t)
{
for (puts("Yes"),i=1;i<n;++i)
printf("%d ",i*(i+1)); printf("%d\n",n); continue;
}
for (puts("Yes"),printf("%d ",2),i=1;i<n-1;++i)
printf("%d ",2*i*(i+1)); printf("%d\n",2*(n-1)); continue;
}
return 0;
}
D - Sum of SCC
首先有一个关于竞赛图的SCC的重要结论:
竞赛图强连通缩点后的DAG呈链状,前面的所有点向后面的所有点连边。
证明其实也很简单,利用归纳法逐一加入每个SCC即可,具体可以看这里
然后利用这点我们就可以把统计SCC数目转化为另一个问题了
设将图的点集\(V\)划分为\(A,B\)两个集合,且满足\(A\)中的所有点与\(B\)中的所有点的边的方向均为\(A\to B\),则这种点集划分的方案数即为图的SCC个数加\(1\)
证明的话就考虑上面的结论,我们将缩点后的DAG链记为\(s_1,s_2,\cdots,s_k\),当\(i<j\)时,边的方向均为\(s_i\to s_j\)
则对于\(t\in [0,k]\),\(A=\{s_1,s_2,\cdots,s_t\}\)和\(B=\{s_{t+1},s_{t+2},\cdots,s_k\}\)均为满足上述要求的划分方案,且不存在在这之外的方案了
因此我们只要统计上面的问题的答案即可,这个很容易通过DP算出
设\(f_{i,j,k}\)表示以及处理了前\(i\)个点,其中有\(j\)条边的方向是从小到大的,且集合\(A\)的大小为\(k\)的方案数
转移的话就考虑\(i+1\)号点放在集合\(A\)还是集合\(B\)即可:
- 若放在集合\(A\),枚举原来\(A\)集合中的边有\(t\in[0,k]\)条方向为从小到大,则\(f_{i,j,k}\times C_k^t\to f_{i+1,j+t,k+1}\)
- 若放在集合\(B\),枚举原来\(B\)集合中的边有\(t\in[0,i-k]\)条方向为从小到大,则\(f_{i,j,k}\times C_{i-k}^t\to f_{i+1,j+k+t,k}\)
最后答案就是\((\sum_{i=0}^n f_{n,m,i})-C_{\frac{n(n-1)}{2}}^m\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=35,mod=998244353;
int n,m,C[N][N],f[N][N*N][N],ans;
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k,t; for (scanf("%d%d",&n,&m),i=0;i<=n;++i)
for (C[i][0]=j=1;j<=i;++j) C[i][j]=sum(C[i-1][j],C[i-1][j-1]);
for (f[0][0][0]=1,i=0;i<n;++i) for (j=0;j<=m;++j)
for (k=0;k<=i;++k) if (f[i][j][k])
{
for (t=0;t<=k;++t) inc(f[i+1][j+t][k+1],1LL*f[i][j][k]*C[k][t]%mod);
for (t=0;t<=i-k;++t) inc(f[i+1][j+k+t][k],1LL*f[i][j][k]*C[i-k][t]%mod);
}
for (ans=1,i=m+1;i<=n*(n-1)/2;++i) ans=1LL*ans*i%mod*quick_pow(i-m)%mod;
for (ans=(mod-ans)%mod,i=0;i<=n;++i) inc(ans,f[n][m][i]);
return printf("%d",ans),0;
}
Postscript
好题很多,慢慢补吧
- AtCoder Regular Contest 163atcoder regular contest 163 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder subsegments atcoder regular contest