今天题很不错啊！就是我 T1 写挂了）
后浪
痛苦面具。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int n,m,ans,sum,ans1[500010],ans2[500010],a[500010],suf[500010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
int cnt=0;
for(int j=1;j<=m;j++)scanf("%d",&a[j]),cnt+=a[j];
ans1[i]=max(cnt,m-cnt);suf[m+1]=0;sum+=ans1[i];
for(int j=m;j>=1;j--)suf[j]=suf[j+1]+a[j];cnt=0;
for(int j=1;j<=m;j++)cnt+=(!a[j]),ans2[i]=max(ans2[i],cnt+suf[j+1]);
}
for(int i=1;i<=n;i++)ans=max(ans,sum-ans1[i]+ans2[i]);
printf("%d\n",ans);
return 0;
}
脑力
很好玩。
首先看到 \(n\le 12\) 猜测是个指数算法。然后想了半天怎么 trie 上合并问号无果。
往指数上考虑，枚举子集，然后套下经典容斥原理，拿 lcp 容斥一下就行了。
代码 2k 多，有一半多是脑力。
// ubsan: undefined
// accoders
/*
Are you ready ×60
Adrenaline is pumping
Adrenaline is pumping
Generator
Automatic Lover
Atomic Atomic
Overdrive
Blockbuster
Brainpower
Call me a leader
Cocaine
Don't you try it
Don't you try it
Innovator
Kill machine
There's no fate
Take control
Brain power
Let the bass kick
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
AAAAE-A-A-I-A-U
JO-oooooooooooo
AAE-O-A-A-U-U-A
E-eee-ee-eee
AAAAE-A-E-I-E-A
JO-ooo-oo-oo-oo
EEEEO-A-AAA-AAAA
O-oooooooooo
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int mod=998244353,inv26=729486258;
char s[15][1010];
int n,m,ans;
int calc(int S){
int len=0,p=1;
for(int i=1;i<=m;i++){
char ch=0;
for(int j=1;j<=n;j++){
if(!((S>>j-1)&1))continue;
if(!ch){
if(s[j][i]=='?')p=1ll*p*inv26%mod,ch='?';
else ch=s[j][i];
}
else{
if(ch=='?'){
if(s[j][i]=='?')p=1ll*p*inv26%mod;
else ch=s[j][i];
}
else{
if(s[j][i]=='?')p=1ll*p*inv26%mod;
else if(s[j][i]!=ch)return len;
}
}
}
if(ch=='?')p=26ll*p%mod;
len=(len+p)%mod;
}
return len;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<(1<<n);i++){
int ret=calc(i);
if(__builtin_popcount(i)&1)ans=(ans+ret)%mod;
else ans=(ans-ret+mod)%mod;
}
ans=(ans+1)%mod;
printf("%d\n",ans);
return 0;
}
道路
P5513。
铸币时刻。写了个 bitset 暴力以为没啥问题结果挂了，一分没有。
首先对于这种二叉树一类东西，每个点可以映射为一个 01 串。容易发现复杂度瓶颈在于怎么找这个 01 串。
借助打 lazy 标记的思想，我们可以如此维护：
- 加减 \(1\)：改最后一位。
- 乘法：最后添一个数。
- 除法：将 \(a_n\) 下推使得 \(a_n\) 的值在 \([0,1]\) 中，并改变 \(a_{n-1}\) 使得数不变。
最后从后往前推一遍标记就好了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
char s[100010];
int a[100010],b[100010],lena,lenb;
void get(int a[],int pos){
a[pos-1]+=(a[pos]-(a[pos]&1))>>1;
a[pos]&=1;
}
void init(char s[],int a[],int &len){
int n=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i]=='1')a[++len]=0;
if(s[i]=='2')a[++len]=1;
if(s[i]=='0')get(a,len),len--;
if(s[i]=='L')a[len]--;
if(s[i]=='R')a[len]++;
}
for(int i=len;i>1;i--)get(a,i);
}
int main(){
scanf("%s",s+1);init(s,a,lena);
scanf("%s",s+1);init(s,b,lenb);
int ans=1<<20,dep=0,len=min(lena,lenb);
for(int i=0;i<=len&&abs(dep)<(1<<20);i++){
dep=(dep<<1)+(a[i]-b[i]);
ans=min(ans,abs(dep)+2*(len-i));
}
printf("%d\n",ans+abs(lena-lenb));
return 0;
}
光学实验室
CF578F。好题。
赛时看着每次连边像划分网格然后试图套生成树计数一类的东西，未果，寻病终。看题解发现想的不太对劲。
首先显然你不能有环。然后你黑白染色一下发现每种合法情况唯一对应一棵黑树或者白树（因为一棵生成树确定以后另一种点只有一种连法）。那并查集缩点跑矩阵树就行了。
放心对着贺是过不去 CF 原题的。
// ubsan: undefined
// accoders
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n,m,mod,num,fa[100010],id[610][610],to[100010];
char s[610][610];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(y)]=find(x);
}
struct node{
int a[610][610],n;
void add(int u,int v){
a[u][u]++;a[v][v]++;a[u][v]--;a[v][u]--;
}
int det(){
int ans=1,w=1;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
while(a[i][i]){
int rate=a[j][i]/a[i][i];
for(int k=i;k<=n;k++){
a[j][k]=(a[j][k]-1ll*rate*a[i][k]%mod+mod)%mod;
}
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
w=-w;
}
for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);
w=-w;
}
}
for(int i=1;i<=n;i++)ans=1ll*ans*a[i][i]%mod;
ans=(1ll*ans*w%mod+mod)%mod;
return ans;
}
}g[2];
int main(){
scanf("%d%d%d",&n,&m,&mod);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n+1;i++){
for(int j=1;j<=m+1;j++)id[i][j]=++num;
}
for(int i=1;i<=(n+1)*(m+1);i++)fa[i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='/'&&s[i+1][j]=='\\'&&s[i][j+1]=='\\'&&s[i+1][j+1]=='/'){
puts("0");return 0;
}
if(s[i][j]=='/')merge(id[i+1][j],id[i][j+1]);
if(s[i][j]=='\\')merge(id[i][j],id[i+1][j+1]);
}
}
for(int i=1;i<=n+1;i++){
for(int j=1;j<=m+1;j++){
if(find(id[i][j])==id[i][j]){
g[(i+j)&1].n++;to[id[i][j]]=g[(i+j)&1].n;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='.'){
g[(i+j)&1].add(to[find(id[i][j])],to[find(id[i+1][j+1])]);
g[(i+j+1)&1].add(to[find(id[i+1][j])],to[find(id[i][j+1])]);
}
}
}
g[0].n--;g[1].n--;
printf("%d\n",(g[0].det()+g[1].det())%mod);
return 0;
}