[CSP-S模拟测试72]题解 A.简单的序列 B.简单的期望 C.简单的操作
遇到括号匹配，先将左右括号转化为1和-1。
那么一个括号序列合法的必要条件：总和为0且所有时刻前缀和$ge 0$。
用dp预处理出长度为$i$，总和为$j$的括号序列数量。那么如果p的方案数为$dp[i][j]$，与之匹配的q的方案数即为$dp[n-m-i][j+串m的总和]$。
注意需要保证统计的方案前缀和处处$ge 0$。用原串的最小前缀和限制一下即可。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
typedef long long ll;
const ll mod=1e9+7;
int n,m,sum,minx;
ll dp[2005][2005];
char s[N];
int main()
{
/*freopen("dt.in","r",stdin);
freopen("my.out","w",stdout);*/
scanf("%d%d%s",&n,&m,s+1);
if(s[1]=='(')sum=minx=1;
else sum=minx=-1;
for(int i=2;i<=m;i++)
{
if(s[i]=='(')sum++;
else sum--;
minx=min(minx,sum);
}
//cout<<sum<<' '<<minx<<endl;
dp[0][0]=1;
for(int i=1;i<=n-m;i++)
for(int j=0;j<=i;j++)
dp[i][j]=((j?dp[i-1][j-1]:0)+dp[i-1][j+1])%mod;//cout<<dp[i][j]<<endl;
ll ans=0;
for(int i=0;i<=n-m;i++)
{
for(int j=0;j<=i;j++)
{
if(j+sum>n-m||j+minx<0)continue;
(ans+=dp[i][j]*dp[n-m-i][sum+j]%mod)%=mod;
}
}
cout<<ans<<endl;
return 0;
}
B.简单的期望
设$dp[i][j][k][0/1]$为进行i次操作，得到数值的二进制后八位为j，第九位开始有几位相同，第九位是0 or 1的概率。
为什么取后八位呢？
一个数含2的多少次幂其实就是它二进制表示下末尾有多少连续的0。由于只有200次操作，取后8位可以保证高于8位的进位最多发生一次，避免未知数量的1变成0对答案的影响。
大力分类讨论转移即可。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int side=(1<<8)-1,U=230;
int n,x;
double p,dp[202][(1<<8)+5][235][2],q,ans=0.0;
int cacl(int x)
{
int res=0;
for( ;x%2==0;x>>=1)res++;
return res;
}
int main()
{
scanf("%d%d%lf",&x,&n,&p);
p/=100.0;q=1.0-p;
int bit=x&(1<<8);
int cnt=1;
if(!(x>>8))goto ak;
for(int i=9;i<=30;i++)
{
int now=x&(1<<i);
if(now!=bit)break;
else cnt++;
}
ak:
//cout<<(x&side)<<' '<<cnt<<' '<<bit<<endl;
dp[0][x&side][cnt][bit]=1.0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<side;j++)
{
for(int k=1;k<=U;k++)
dp[i][j+1][k][0]+=dp[i-1][j][k][0]*q,dp[i][j+1][k][1]+=dp[i-1][j][k][1]*q;
}
for(int j=1;j<=U;j++)
dp[i][0][j][0]+=dp[i-1][side][j][1]*q;
for(int j=1;j<=U;j++)
dp[i][0][1][1]+=dp[i-1][side][j][0]*q;
for(int j=0;j<128;j++)
for(int k=1;k<=U;k++)
dp[i][j<<1][1][0]+=dp[i-1][j][k][1]*p,dp[i][j<<1][k+1][0]+=dp[i-1][j][k][0]*p;
for(int j=128;j<=side;j++)
for(int k=1;k<=U;k++)
dp[i][j<<1&side][1][1]+=dp[i-1][j][k][0]*p,dp[i][j<<1&side][k+1][1]+=dp[i-1][j][k][1]*p;
}
for(int i=1;i<=side;i++)
for(int j=1;j<=U;j++)
ans+=dp[n][i][j][0]*cacl(i)+dp[n][i][j][1]*cacl(i);
for(int i=1;i<=U;i++)
ans+=dp[n][0][i][0]*(8+i)+dp[n][0][i][1]*8;
printf("%.8lf
",ans);
return 0;
}
C.简单的操作
首先很容易发现奇环是无法处理的，一个大奇环再怎么合并也会剩下一个长度为3的奇环而无法成链。
如果是一棵树，那显然可以把枝杈往直径上合并得到最优答案。
对于图也一样，偶环一定可以缩到任意一条边所在的链上。这样一个联通块的答案就是它的直径。(“最长的最短路”)
如果是不同联通块，那就把两个端点直接连起来。答案相加即可。
//不要卡spfa啊!!!
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<queue>
#define re register
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=1e3+5,M=2e5+5;
int n,m;
int to[M],head[N],nxt[M],tot;
int col[N],bel[N],part,dis[N],v[N],len[N],ans;
inline void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int c,int now)
{
bel[x]=now;col[x]=c;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(!col[y])dfs(y,-c,now);
else if(col[x]==col[y])
{
puts("-1");exit(0);
}
//cout<<x<<' '<<y<<endl;
}
}
inline int spfa(int s)
{
queue<int> q;
for(re int i=1;i<=n;i++)
dis[i]=0x3f3f3f3f,v[i]=0;
dis[s]=0;q.push(s);v[s]=1;
int maxx=0;
while(!q.empty())
{
int x=q.front();q.pop();
maxx=max(maxx,dis[x]);
for(re int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(dis[y]>dis[x]+1)
{
dis[y]=dis[x]+1;
if(!v[y])v[y]=1,q.push(y);
}
}
v[x]=0;
}
return maxx;
}
int main()
{
/*freopen("dt.in","r",stdin);
freopen("my.out","w",stdout);*/
n=read();m=read();
for(re int i=1;i<=m;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
for(re int i=1;i<=n;i++)
if(!col[i])dfs(i,1,++part);
for(re int i=1;i<=n;i++)
len[bel[i]]=max(len[bel[i]],spfa(i));
for(re int i=1;i<=part;i++)
ans+=len[i];
cout<<ans<<endl;
return 0;
}
即可真是个美妙的词语