A.阴阳
dp，不会。
B.简单的序列
两种解法。
(large Solution1)
设左括号为 (1) ，右括号为 (-1) ，那么最终合法序列为任意前缀和都不小于 (0) 的方案。
所以先 (n^2) dp一下，处理出来 (i) 个数 ，和为 (j) 的方案数。
处理一下给出的中间序列的前缀和，和中间序列最小的值，下边枚举左边序列长度和和。
枚举序列和为 (j) ，需要满足 (0leqslant j+sum) 且 (0leqslant j+min) 。枚举即可。
(large Solution2)
卡特兰数，可以由中间序列先确定左边序列有多少个左括号，右边序列同理，然后可以枚举左边长度，和左括号的个数。
根据卡特兰数求解。
代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
#define ll long long
ll jc[maxn],jcny[maxn],ny[maxn];
char s[maxn];
inline ll getC(int n,int m){return jc[n] % mod * jcny[n-m] % mod * jcny[m] % mod;}
inline ll calc(int n,int m){
if((n + m) & 1)return 0;
return (getC(n,(n+m)/2) - getC(n,(n+m)/2+1) + mod ) % mod;
}
int main(){
freopen("bracket.in","r",stdin);
freopen("bracket.out","w",stdout);
jc[0] = jcny[0] = ny[1] = 1;
int n,m;
for(int i = 2;i <= 1e5;++i)ny[i] = ny[mod % i] % mod * (mod - mod / i) % mod;
for(int i = 1;i <= 1e5;++i)jc[i] = jc[i-1] * i % mod,jcny[i] = jcny[i-1] * ny[i] % mod;
scanf("%d%d",&n,&m);scanf("%s",s+1);
int cntl = 0,cntr = 0;
for(int i = 1;i <= m;++i){
if(s[i] == '(')cntr++;
else{
if(cntr)cntr--;
else cntl++;
}
}
int sum = n - m;
ll ans = 0;
for(int i = cntl;i <= sum;++i){
for(int j = cntl;j <= i;++j){
ans = (ans + calc(i,j) * calc(sum-i,j-cntl+cntr) % mod) % mod;
}
}
printf("%lld
",ans);
return 0;
}
C.简单的期望
dp神题，由于最多 (200) 次加一，所以可以只记录后八位，然后看第九位是谁，并且有多少个连续的即可。
定义 (f[i][S][k][0/1]) 表示前 (i) 次操作，后八位为 (S) ，第九位后有 (k) 个连续的，第九为是 (0) 或 (1) 。
然后八种转移即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e2+30;
const int mx = (1 << 8) - 1;
#define db double
db f[202][(1<<8)+10][235][4];
inline int calc(int s){
int cnt = 0;
while(s % 2 == 0){
s /= 2;
cnt++;
}
return cnt;
}
int main(){
freopen("exp.in","r",stdin);
freopen("exp.out","w",stdout);
long long x,n;db p;
scanf("%lld%lld%lf",&x,&n,&p);
p = p / 100;
db q = 1.0 - p;
int cnt;
int tmp = x & (1 << 8);
if((x >> 8) == 0)cnt = 1;
else{
cnt = 0;
for(int i = 9;i <= 30;++i){
int jl = x & (1 << i);
cnt++;
if(jl != tmp)break;
}
}
f[0][x & mx][cnt][tmp] = 1.0;
int base = 230;
for(int i = 1;i <= n;++i){
for(int j = 0;j < mx;++j){
for(int k = 1;k <= base;++k){
f[i][j+1][k][0] += f[i-1][j][k][0] * q;
f[i][j+1][k][1] += f[i-1][j][k][1] * q;
}
}
for(int j = 1;j <= base;++j){
f[i][0][j][0] += f[i-1][mx][j][1] * q;
}
for(int j = 1;j <= base;++j){
f[i][0][1][1] += f[i-1][mx][j][0] * q;
}
for(int j = 0;j < 128;++j){
for(int k = 1;k <= base;++k){
f[i][j<<1][1][0] += f[i-1][j][k][1] * p;
f[i][j<<1][k+1][0] += f[i-1][j][k][0] * p;
}
}
for(int j = 128;j <= mx;++j){
for(int k = 1;k <= base;++k){
f[i][(j << 1) & mx][k+1][1] += f[i-1][j][k][1] * p;
f[i][(j << 1) & mx][1][1] += f[i-1][j][k][0] * p;
}
}
}
db ans = 0;
for(int i = 1;i <= mx;++i){
for(int j = 1;j <= base;++j){
ans += (f[n][i][j][0] + f[n][i][j][1]) * calc(i);
}
}
for(int i = 1;i <= base;++i){
ans += f[n][0][i][0] * (i + 8) + f[n][0][i][1] * 8;
}
printf("%.8lf
",ans);
return 0;
}
D. 简单的操作
容易想到奇环一定会转化成三元环导致无解，所以先染色判奇环。
由于图可能不联通，所以根据手模可以得到，每个联通块内的最长路径就是链的最长，最短路求和即可。
(Never Give Up)