[CSP-S模拟测试ex]题解 A.Antipalindrome B.Randomwalking C.String
爆零了。少特判见祖宗。还好这场不计入总分。
考场上什么都没想。感觉考试状态又回到了两个月前。
手玩样例，不难发现题目中要求的合法串的充要条件是：对于任意$i in [2,n]$，有$ s[i] eq s[i-1] and s[i-1] eq s[i+1]$
那么第一个位置有$m$种选择，第二个位置有$m-1$种，第三个位置往后都有$m-2$种。
$ans=m(m-1)(m-2)^{n-2}$
注意特判。如果判少会直接爆0。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int T;
ll n,m;
ll qpow(ll a,ll b)
{
ll res=1;a=a%mod;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void work()
{
scanf("%lld%lld",&n,&m);
m%=mod;
if(m==1)
{
if(n==1)puts("1");
else puts("0");
return ;
}
if(n==1)
{
cout<<m<<endl;
return ;
}
ll ans=m*(m-1)%mod;
ans*=qpow(m-2,n-2),ans%=mod;
cout<<ans<<endl;
}
int main()
{
scanf("%d",&T);
while(T--)work();
return 0;
}
B.Randomwalking
明显的换根dp。设$f[x]$表示x的子树对答案的贡献，$g[x]$表示x子树之外的部分对答案的贡献。那么$f[]$可以先用一遍dfs求得，然后在换根过程中求$g[]$顺便统计答案。
设$son[x]$为x的儿子数，显然这个要对根节点特判一下。那么可得$f[x]=a[x]+sum frac{f[y]}{son[x]}$，y是x的儿子。
然后考虑怎么换根。设fa为x的父亲，方程为$g[x]=frac{g[fa]+(f[fa]-a[fa])*son[fa]-f[x]}{son[fa]}+a[fa]$。
解释一下，$(f[fa]-a[fa])*son[fa]$
相当与先还原出 $sum f[s]$ (s为fa的儿子，包括x)，
然后去掉$f[x]$的贡献，把剩下的作为x外部的点重新计算入$g[x]$。
最后统计答案的时候要比较的是$frac{g[x]+(f[x]-a[x])*son[x]}{son[x]+1}+a[x]$，也相当与一个还原的过程。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=1e6+5;
const double inf=9999999999999.0;
typedef long long ll;
int n,a[N];
int to[N<<1],head[N],nxt[N<<1],tot,deg[N],minn;
double dp[N],g[N],minx=inf;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
deg[x]++;
}
void dfs1(int x,int f)
{
dp[x]=a[x];
int d=f?deg[x]-1:deg[x];
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)continue;
dfs1(y,x);
dp[x]+=dp[y]/(1.0*d);
}
}
void dfs2(int x,int f)
{
int df=(f==1?deg[f]:deg[f]-1);
g[x]=(g[f]+(dp[f]-a[f])*df-dp[x])/df+a[f];
double now=(g[x]+(dp[x]-a[x])*(deg[x]-1))/deg[x]+a[x];
if(minx>now)minx=now,minn=x;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=f)dfs2(to[i],x);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
dfs1(1,0);
minx=dp[1],minn=1;
for(int i=head[1];i;i=nxt[i])
dfs2(to[i],1);
cout<<minn<<endl;
return 0;
}
C.String
记录一下每个原来的位置被翻转到了哪里，用并查集维护一定相同的位置对应关系。如果一个联通块中有一个确定了，那么就都确定了。对于剩下的'?'，用26进制的思想逐位填。
区间反转上Splay。卡常。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
const int L=1<<20|1;
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
const int N=5e5+5,inf=0x3f3f3f3f;
typedef long long ll;
int n,m,a[N],b[N],tot,fa[N],vis[N],unsu[N],cnt;
ll K;
char str[N],s[N];
inline int rint()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll rll()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void read(char x[])
{
char ch=getchar();int now=0;
while(ch!='?'&&(ch>'z'||ch<'a'))ch=getchar();
while(ch=='?'||(ch>='a'&&ch<='z'))x[++now]=ch,ch=getchar();
}
int findf(int x)
{
if(fa[x]==x)return x;
return fa[x]=findf(fa[x]);
}
namespace Splay
{
int fa[N],son[N][3],size[N],key[N],v[N],type,root;
inline bool judge(int x){return son[fa[x]][1]==x;}
inline void up(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}
inline void down(int x)
{
if(x&&v[x])
{
v[son[x][0]]^=1;v[son[x][1]]^=1;
swap(son[x][0],son[x][1]);v[x]=0;
}
}
inline void rotate(int x)
{
int old=fa[x],oldf=fa[old],lr=judge(x);
down(old);down(x);
son[old][lr]=son[x][lr^1];
fa[son[old][lr]]=old;
son[x][lr^1]=old;fa[old]=x;
fa[x]=oldf;
if(oldf)son[oldf][son[oldf][1]==old]=x;
up(old);up(x);
}
inline void splay(int x,int goal)
{
for(int f;(f=fa[x])!=goal;rotate(x))
if(fa[f]!=goal)
rotate(judge(x)==judge(f)?f:x);
if(!goal)root=x;
}
int build(int f,int l,int r)
{
if(l>r)return 0;
int mid=l+r>>1,x=++type;
key[x]=a[mid];fa[x]=f;
v[x]=0;
son[x][0]=build(x,l,mid-1);
son[x][1]=build(x,mid+1,r);
up(x);
return x;
}
inline int getrank(int x)
{
int now=root;
while(1)
{
down(now);
if(x<=size[son[now][0]])now=son[now][0];
else
{
x-=size[son[now][0]]+1;
if(!x)return now;
now=son[now][1];
}
}
}
inline void rev(int l,int r)
{
l=getrank(l),r=getrank(r+2);
splay(l,0);splay(r,l);
down(root);
v[son[son[root][1]][0]]^=1;
}
void print(int now)
{
down(now);
if(son[now][0])print(son[now][0]);
if(key[now]!=-inf&&key[now]!=inf)b[++tot]=key[now];
if(key[son[now][1]])print(son[now][1]);
}
}
int main()
{
n=rint();m=rint();K=rll();
read(str);
for(re int i=1;i<=n;i++)
fa[i]=a[i+1]=i;
a[1]=-inf;a[n+2]=inf;
Splay::root=Splay::build(0,1,n+2);
for(re int i=1;i<=m;i++)
{
int l=rint(),r=rint();
Splay::rev(l,r);
}
Splay::print(Splay::root);
/*for(int i=1;i<=n;i++)
cout<<b[i]<<' ';
puts(" ");*/
for(re int i=1;i<=n;i++)
{
int fx=findf(b[i]),fy=findf(i);
if(fx==fy)continue;
if(str[fy]=='?')str[fy]=str[fx];
fa[fx]=fy;
}
for(re int i=1;i<=n;i++)
{
int fx=findf(i);
s[i]=str[fx];
if(s[i]=='?'&&!vis[fx])vis[fx]=1,unsu[++cnt]=fx;
}
K--;int now=cnt;
while(K)
{
str[unsu[now]]='a'+K%26;
now--;
K/=26;
}
while(now>0)str[unsu[now]]='a',now--;
for(re int i=1;i<=n;i++)
{
if(s[i]=='?')s[i]=str[findf(i)];
putchar(s[i]);
}
putchar('
');
return 0;
}