C
给定序列 $A$ ，通过若干次操作使其变为序列 $B$ 。对于每次操作，选择一个正整数 $k$ ，对于每个数选择将其变为 $a_i\pmod k$ 或不变，这次操作代价 $2^k$ 。总代价为所有操作代价和，球最小总代价
注意这个 $2^k$ 的代价，其意味着从高位到地位贪心
然后对每个 $k$ 建图判断一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| const int N=55;
int n,f[N][N],a[N],b[N];
inline bool check(ll sta){
for(rei i=0;i<N;++i) for(rei j=0;j<N;++j) f[i][j]=i==j ? 1 : 0;
for(rei i=0;i<N;++i) for(rei j=1;j<=i;++j) if(sta & (1ll<<j)) f[i][i%j]=1;
for(rei k=0;k<N;++k) for(rei i=0;i<N;++i) for(rei j=0;j<N;++j) f[i][j]|=(f[i][k] & f[k][j]);
bool ret=true;
for(rei i=1;i<=n;++i) if(!f[ a[i] ][ b[i] ]){ ret=false; break;}
return ret;
}
int main(){
scanf("%d",&n);
for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
for(rei i=1;i<=n;++i) scanf("%d",&b[i]);
ll sta=(1ll<<38)-2;
if(!check(sta)){ return puts("-1"),0;}
for(rei i=37;i;--i){
ll tmp=sta^(1ll<<i);
if(check(tmp)){ sta=tmp;}
}
printf("%lld\n",sta);
getchar(),getchar();
return 0;
}
|
D
$N$ 个商场，第 $i$ 个在数轴的 $x_i$ ，需要花费连续的 $t_i$ 时间购物。一趟火车在 $0,L$ 处往返，行驶一单位长度用一单位时间，在 $0$ 时于 $0$ 处上车，只有在 $商场，0，L$ 处才可下车，求在每个超市购物后返回 $0$ 处的最少时间
有一个神仙思路：
对于每个 $t_i$ ，先 $\% 2\times L$ ，再把 $2\times L\times n$ 加到答案里
考虑一个点，如果从左边进只需要到达依次端点就看作左括号，从右边进只需要依次达到端点就看作右括号
先默认每个点贡献都是 $2\times L$ ，那么左右括号匹配时则可以减少 $2\times L$
某些点可以看作左/右括号，此时考虑最大化匹配数
有性质：当一个节点开始时固定作为左括号，则后面一定没有固定作为右括号的，所以不会有两个固定的括号匹配。
贪心即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| const int N=3e5+10;
int n,len,x[N],t[N],l[N],r[N],ans;
int main(){
scanf("%d%d",&n,&len);
for(rei i=1;i<=n;++i) scanf("%d",&x[i]);
for(rei i=1;i<=n;++i) scanf("%d",&t[i]);
for(rei i=1;i<=n;++i){
ans+=t[i]/(2*len); t[i]%=2*len;
if(!t[i]){ --ans; continue;}
l[i]=(t[i]<=x[i]*2);
r[i]=(t[i]<=(len-x[i])*2);
}
rei lim=n,L=0,R=0;
ans+=n+1-r[n];
for(rei i=1;i<n;++i){
if(!l[i] && !r[i]) continue;
if(!r[i]){ lim=i; break;}
if(!l[i] && L) --L,--ans;
else if(l[i]) ++L;
}
for(rei i=n-1;i>=lim;--i){
if(!l[i] && !r[i]) continue;
if(!l[i]) break;
if(!r[i] && R) --R,--ans;
else if(r[i]) ++R;
}
ans-=(L+R)>>1;
printf("%lld\n",2ll*ans*len);
getchar(),getchar();
return 0;
}
|
E
一个奇数长度的 $01$ 串 $s$ ，其中若干位置是符号 $?$ ，每次将 $3$ 个连续的字符替换成着三个数的中位数，有多少种方案将 $?$ 替换成 $0/1$ 后再进行 $\frac{n-1}{2}$ 次操作后字符串为 $1$
首先考虑没有 $?$ 的情况，考虑其是否合法
维护一个栈，其中包括一段连续的 $0$ 和一段连续的 $1$
- 加入 $0$
- 栈顶 $0$ ：若栈内 $2$ 个 $0$ ，则替换成一个 $0$ ，否则入栈
- 栈顶 $1$ ：直接入栈
- 加入 $1$
- 栈顶 $0$ ：弹出栈顶的 $0$ ，相当于抵消
- 栈顶 $1$ ：若栈内只有一个 $1$ 则入栈，否则不管
那么最后只要 $num_1>num_0$ 则合法
简化一下栈内部：发现 $0,1$ 的个数只可能是 $0\sim 2$ ，设 $f_{i,a,b}$ 表示第 $i$ 位时，栈内有 $a$ 个 $1$ ，$b$ 个 $0$ 的方案数
有转移：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| const int N=3e5+100;
const int mod=1e9+7;
int n,ans;
int f[N][3][3];
char s[N];
inline void fix(int &x){ x>=mod ? x-=mod : 0;}
int main(){
scanf("%s",s+1); n=strlen(s+1);
f[0][0][0]=1;
for(rei i=0;i<n;++i){
if(s[i+1]!='1')
for(rei a=0;a<=2;++a){
fix(f[i+1][a][1]+=f[i][a][2]);
fix(f[i+1][a][1]+=f[i][a][0]);
fix(f[i+1][a][2]+=f[i][a][1]);
}
if(s[i+1] != '0'){
for(rei a=0;a<=2;++a){
fix(f[i+1][a][0]+=f[i][a][1]);
fix(f[i+1][a][1]+=f[i][a][2]);
}
fix(f[i+1][1][0]+=f[i][0][0]);
fix(f[i+1][2][0]+=f[i][1][0]);
fix(f[i+1][2][0]+=f[i][2][0]);
}
}
for(rei a=0;a<=2;++a) for(rei b=0;b<=a;++b) fix(ans+=f[n][a][b]);
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|
F
$x=10^{100}$ ，数轴上有 $n$ 个点，点 $i$ 的坐标为 $x_i$ ，$n-1$ 次操作，每次选择两点 $A,B$ ，将 $A$ 移动到 $B$ 的对称点并删去 $B$ ，求最后剩的数取值的方案数
当 $关于B对称的A$ 变成 $2B-A$ 时，即 $B被消掉$ 时，将 $A$ 视作 $B$ 的父亲，最终形成一颗具有儿子相对顺序的树，如此最终剩下来的点就是根节点
将一个点 $A$ 的贡献视作 $2^{d_A} \times c_A \times x_A$ ，其中 $x_A$ 视作未知数， $d_A$ 为节点 $A$ 深度 ，$c_A$ 为正负号
考虑到 $x_i$ 极大且 $x_{i+1}-x_i$ 也极大，那么不会出现点贡献相互抵消，那么只需要考虑前面的系数即可
深度显然易得，考虑如何求 $c_i$
这里采取间接确定每一项的符号，即，对于点 $i$ 的字节点 $son_1,son_2,…son_k$ ，已知点 $i$ 的符号，观察 $k$ 个子节点符号与 $i$ 的关系
当 $i$ 再向上与 $fa_i$ 连边时，相当于有 $2\times val_i-val_{fa}$ ，而 $son_i$ 又有贡献 $2\times val_{son}-2\times val_i$ ，所以连边后 $i$ 与 $son_i$ 的正负号会同时取反
而当 $son_i$ 连向 $i$ 时，对于 $son_i$ ，其实质相当于 $\times 2$ ，而对于 $i$ ，其实质为 $\times -1$
那么有结论：当且仅当节点 $v$ 有奇数个字节点时，其符号与父节点不一样
考虑 $dp$ 解决：
设 $f_{i,j}$ 表示放了 $i$ 个节点，最后一层有 $j$ 个节点的儿子数量为奇数时的方案数
为了方便将 $c_i$ 差分，与 $fa$ 相同记作 $1$ ，不同记作 $-1$ ，转移时仅关心下一层与 $fa$ 相同/不同的数量
对于点 $v$ 有 $k$ 个儿子，若不考虑儿子的儿子的影响，应该有 $\left\lfloor \frac{k}{2} \right\rfloor$ 个儿子的 $c$ 与 $v$ 不同
设下一层长出 $k$ 个节点，其中 $\frac{k-j}{2}$ 个点正负与父亲不同(此时kj奇偶性不同则跳过)
设考虑儿子的儿子的影响后，点 $v$ 有 $x$ 个儿子与之正负不同，那么就有 $|x-\frac{k-j}{2}|$ 个节点( $son_v$ )的正负性需要修正，即，下一层中的点的儿子个数为奇数的节点数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| const int N=55;
const int mod=1e9+7;
ll c[N][N],f[N][N]; int n;
int main(){
scanf("%d",&n);
for(rei i=0;i<=n;++i){
c[i][0]=1;
for(rei j=1;j<=i;++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
f[1][0]=f[1][1]=n;
for(rei i=1;i<n;++i) for(rei j=0;j<=i;++j) for(rei k=(!j ? 2 : j);i+k<=n;k+=2){
rei t=(k-j)>>1;
for(rei x=0;x<=k;++x) (f[i+k][abs(x-t)]+=f[i][j]*c[n-i][k]%mod*c[k][x]%mod)%=mod;
}
printf("%lld\n",f[n][0]);
getchar(),getchar();
return 0;
}
|