瑟瑟发抖,考场想出正解打炸了。。
T1.计数
题目大意:给出一个字符串,字符串的(S)的每个本质不同的子串都对应一个节点,且子串(x)对应的节点连向子串(y)对应的节点当且仅当(|x| = |y| + 1),且(y)是(x)的子串,求(S)对应节点为起点的简单路径条数。
考场上花一小时想出正解,可之后打炸了,就得了(15)分,呜呜呜~
整体来说不算太难 (不然我怎么能想得出正解?。
把整个图拉出来,并且相同的出边相同的节点不连在同一个节点,整个图就变成了一个以(S)为根的满二叉树,而答案求的就是把不符合题意的删去之后整棵树的大小。
所以就有思路了:用整棵树的大小减去不符合题意的贡献就是答案了。
我们画图可以知道,不符合题意当且仅当这个节点对应的字符串的所有字符均相等。这是我们就要剪去一个它的子树大小的贡献,但它另外一个子树也是均相等的,所以要重复以上操作。
但我们可以换个角度思考,直接把以这个节点为根的子树整个删掉,再加上正确的个数即可。
然后就是算有多少个相等的字符的节点了。
我们又回到字符串中,当一个子串相等时,设整个字串左边还有(n)个字符,右边还有(m)个字符,则这个子串在树中出现的次数就为(C_{n+m}^n),因为我们如果从树上看的话,要从根节点走到这种节点,要向右走(n)步(每向右走一步相当于去掉最左边字符),向左走(m)步,而只要有一步走的不一样,到达的节点就不一样,所以总共走(n+m)步,向右走了(n)步,而且何时向右走都可以,所以总共的方案数就为(C_{n+m}^n)。
要注意的是,我们仔细观察一下图,还是有一些节点我们没有计算到的,就是在整个相同的字串中与边界相接的节点,我们也要把这个贡献算上,而且因为相接,所以最后一步是确定的,所以每一个相接子串的贡献为(C_{n-size-1}^{l-2}),其中(size)为子串长度,(l)为子串左端点。
然后就完美的AC啦!时间复杂度为(O(n))
小结:
解题关键:想到题目给出模型与二叉树和组合数学的关系
芝士点:组合数
手起,码落:
#include<bits/stdc++.h>
#define re register
#define mod 998244353
using namespace std;
inline long long Pow(long long x,int y)
{
re long long sum=1;
for(;y;x=(x*x)%mod,y>>=1)
if(y&1)sum=(sum*x)%mod;
return sum;
}
const int N=500005;
int n,l,r,len;
long long ans,jc[N],mid,sum[N];
char a[N];
inline long long C(int m,int n)
{
if(m<0||n<0)return 0;
return jc[m]*Pow(jc[m-n]*jc[n]%mod,mod-2)%mod;
}
int main()
{
scanf("%s",a+1);n=strlen(a+1);
jc[0]=1,l=1,ans=Pow(2ll,n)-1;
for(re int i=1;i<=n;i++)jc[i]=jc[i-1]*i%mod;
for(re int i=1;i<=n;i++)
if(a[i]!=a[i+1])
{
r=i;
len=r-l+1;
ans=(ans-C(n-len,l-1)*((Pow(2ll,len)-len-1+mod)%mod)%mod+mod)%mod;
for(re int j=len-1;j>0;j--) ans=(ans-(C(n-j-1,l-2)+C(n-j-1,n-r-1))%mod*((Pow(2ll,j)-j-1+mod)%mod)%mod+mod)%mod;
l=i+1;
}
printf("%lld",ans);
return 0;
}
T2。博弈
题目大意:(n)个人分(m)枚金币,每个人足够聪明,给出分金币提案(方法)的顺序为(1,2,3...n,1,2...)。当所有人都同意这个提案时则开始分金币,否则丢弃(k)枚金币,换下一个人分,求每个人最后得到的金币数量。(当一个人否决这个提案时最后得到的金币会比现在要少时,他就会同意这个提案
考场上连题目都没看懂的蒟蒻瑟瑟发抖。。
这题可以使用DP的方式,(f[i][j])表示还剩下(i)枚硬币时,第(j)个人期望得到的金币数。显然(f[i])是从(f[i+k])转移过来,然后我们发现其实根本不需要开数组,直接用一个变量保存就好了,加上路径压缩维护就完事了。
小结:
解题关键:看懂题目,想到路径压缩加速DP
芝士点:路径压缩DP
手起,码落:
#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=200005;
long long Rounds,rest,m,k,mid,eve;
long long luck,oth,All,a[N],sum,lazy;
int n,x,per,sta;
int main()
{
scanf("%d%lld%lld",&n,&m,&k);
Rounds=m/k,rest=m%k,per=Rounds%n+1;
for(;rest<n&&Rounds;)
{
per=(per-1>0?per-1:n);
rest+=k,Rounds--;
}
if(rest>=n)All=1,lazy=rest-n,x=per;
sum=eve=ceil(n*1.0/k);
per=(per-eve>0?per-eve:per-eve+n),sta=per,mid+=1,a[per]+=eve*k-n;
for(;;)
{
per=(per-eve>0?per-eve:per-eve+n);
if(per==sta)break;
mid++,a[per]+=eve*k-n,sum+=eve;
}
rest=Rounds%sum,Rounds/=sum;
mid*=Rounds,All+=mid,mid=0;
for(re int i=1;i<=n;i++)a[i]*=Rounds;
a[x]+=lazy;
Rounds=rest/eve,per=(per+eve-1)%n+1;
for(re int i=1;i<=Rounds;i++)
{
per=(per-eve>0?per-eve:per-eve+n);
All++,a[per]+=eve*k-n;
}
for(re int i=1;i<=n;i++)
printf("%lld ",a[i]+All);
return 0;
}
T3.划分
还不会,咕咕咕~~