解题报告…

A. Convert to Ones

签到题。容易发现,设连续的 \(0\) 的段数为 \(cnt\) ,翻转操作可以合并两段,反转操作可消去一段。

若反转代价小,就反转 \(cnt\) 次,否则翻转 \(cnt-1\) 次合成一段,最后反转一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=300005;
int n,x,y,cnt;
char a[maxn];
int main(){
scanf("%d%d%d%s",&n,&x,&y,a+1);
for(int i=1;i<=n;i++){
if(a[i]=='0'&&(i==1||a[i-1]=='1')) cnt++;
}
if(!cnt) puts("0"); else
if(y<=x) printf("%lld\n",(LL)cnt*min(x,y));
else printf("%lld\n",(LL)(cnt-1)*x+y);
return 0;
}

B. Roman Digits

这题我打 \(VP\) 的时候分析半天弄不清楚,打表找规律发现后面答案都是每次多 \(49\)

还不太懂为什么……

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
map<LL,int> M;
map<LL,int> :: iterator it;
int n;
int main(){
scanf("%d",&n);
if(n==1) puts("4");
if(n==2) puts("10");
if(n==3) puts("20");
if(n==4) puts("35");
if(n==5) puts("56");
if(n==6) puts("83");
if(n==7) puts("116");
if(n==8) puts("155");
if(n==9) puts("198");
if(n==10) puts("244");
if(n==11) puts("292");
if(n==12) puts("341");
if(n>12){
LL ans=(LL)(n-12)*49+341;
printf("%lld\n",ans);
}
return 0;
}

C. Sky Full of Stars

tag: 容斥

不算太难的容斥,为啥我写了这么久。

我们要求至少一行或一列同色的方案,容易想到求 \(f(i,j)\) 表示至少 \(i\)\(j\) 列是同色的方案。

显然如果行列都有同色的,那么所有同色行列都互相同色。所以分两种:

\[ f(i,0)={n\choose i} 3^{(n(n-i)+i)} \]

上面的直接乘上容斥系数 \(O(n)\) 求和就好了,下面看 \(i,j\) 都大于 \(0\) 的情况: \[ f(i,j)={n\choose i}{n\choose j}3\ 3^{(n-i)(n-j)} \\ ans=\sum_{i=1}^n\sum_{j=1}^n=(-1)^{i+j+1}{n\choose i}{n\choose j}3\ 3^{(n-i)(n-j)} \\ \] 一眼看上去不好求,其实就是个二项式定理搞一下…. \[ =\sum_{i=1}^n 3^{n^2-ni+1}(-1)^{i+1}{n \choose i}\sum_{j=1}^n(-1)^j {n \choose j}3^{ij-nj} \\ =\sum_{i=1}^n 3^{n^2-ni+1}(-1)^{i+1}{n \choose i}((1-3^{i-n})^n-1) \]

就好了。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1000015,P=998244353;
LL n,fac[maxn],inv[maxn],fac_inv[maxn],ans;
LL C(int n,int m){
return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
LL Pow(LL a,LL b){
LL res=1; a%=P;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
int main(){
scanf("%lld",&n);
fac[0]=1; for(int i=1;i<=n+5;i++) fac[i]=fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=n+5;i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=n+5;i++) fac_inv[i]=fac_inv[i-1]*inv[i]%P;
for(int i=1;i<=n;i++) ans+=(LL)2*((i&1)?1:-1)*C(n,i)%P*Pow(3,n*(n-i)+i)%P;
for(int i=1;i<=n;i++){
ans+=Pow(3,n*n+1)*C(n,i)%P*((i&1)?1:-1)*Pow(inv[3],n*i)%P*(Pow(1-Pow(inv[3],n-i),n)-1)%P;
ans%=P;
}
printf("%lld\n",(ans+P)%P);
return 0;
}

D. Cycles in product

tag: 点分治 DP

题意可以看作,一个点对是一个状态,每走一步可以选某个点在对应树上走一条边。

显然可以考虑把两棵树独立开。设 \(ans1(i)\) 表示第一颗树,长度为 \(i\) 的环的个数,

总答案显然为 \(\sum_{i+j=K} ans1(i) ans2(j) {K\choose i}\) 。现在问题是怎么求 \(ans\)

考虑 \(DP\) ,发现直接搞的话好像怎么样都有 \(n^2\) ,可以考虑点分,每次求过重心的环。

然后枚举起点 \(x\) ,需要求从 \(x\) 出去回来,经过 \(G\) 的方案数。

然后就很套路了,把路拆成 \(x\)\(G\)\(G\)\(x\) ,为了避重,把贡献记在第一次到 \(G\) 的地方。

所以只要求 \(f(i,j)\) 表示 \(G\)\(i\)\(j\) 步的路径数,\(g(i,j)\)\(f\) 多了中途不能经过 \(G\) 的限制。

\(O(nK)\) 随便求,合并出 \(ans\) 需要 \(O(nK^2)\) ,可以 \(FFT\) 加速一下,但这题直接能过。

复杂度 \(O(nK^2\log n)\)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=4005,maxe=maxn*2,maxk=80,P=998244353;
int n1,n2,n,K;
int fir[maxn],nxt[maxe],son[maxe],tot=1;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int allsz,Maxsz,nowG,sz[maxn];
bool vis[maxn];
void dfsG(int x,int pre){
sz[x]=1; int _max=0;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre&&!vis[son[j]])
dfsG(son[j],x), sz[x]+=sz[son[j]], _max=max(_max,sz[son[j]]);
if(max(allsz-sz[x],_max)<Maxsz)
nowG=x, Maxsz=max(allsz-sz[x],_max);
}
int getG(int x,int sz_x){
allsz=sz_x; Maxsz=1e9; dfsG(x,0); return nowG;
}
int v[maxn],id[maxn];
int ans[2][maxn],f[maxn][maxk],g[maxn][maxk];
vector<int> Con[maxn];
void dfs_info(int x,int pre){
sz[x]=1; v[++v[0]]=x; id[x]=v[0];
for(int i=0;i<=K;i++) f[id[x]][i]=g[id[x]][i]=0;
Con[id[x]].clear(); if(pre) Con[id[x]].push_back(id[pre]);
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre&&!vis[son[j]]){
sz[x]+=sz[son[j]], dfs_info(son[j],x);
Con[id[x]].push_back(id[son[j]]);
}
}
void Divide(int G,int _typ){
v[0]=0; dfs_info(G,0);
f[1][0]=g[1][0]=1;
for(int j=1;j<=K;j++){
for(int i=1;i<=v[0];i++){
for(int k=0;k<Con[i].size();k++) (f[i][j]+=f[Con[i][k]][j-1])%=P;
if(i>1) for(int k=0;k<Con[i].size();k++) (g[i][j]+=g[Con[i][k]][j-1])%=P;
}
}
for(int i=0;i<=K;i++) (ans[_typ][i]+=f[1][i])%=P;
for(int x=2;x<=v[0];x++)
for(int i=0;i<=K;i++)
for(int j=0;i+j<=K;j++)
(ans[_typ][i+j]+=(LL)f[x][i]*g[x][j]%P)%=P;

vis[G]=true;
for(int j=fir[G];j;j=nxt[j])
if(!vis[son[j]]) Divide(getG(son[j],sz[son[j]]),_typ);
}
LL fac[maxk],fac_inv[maxk],inv[maxk];
LL C(int n,int m){
return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
int allans;
int main(){
scanf("%d%d%d",&n1,&n2,&K);
fac[0]=1; for(int i=1;i<=K;i++) fac[i]=fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=K;i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=K;i++) fac_inv[i]=fac_inv[i-1]*inv[i]%P;
for(int i=1;i<=n1-1;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
Divide(getG(1,n1),0);
memset(fir,0,sizeof(fir)); tot=1;
for(int i=1;i<=n2-1;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
memset(vis,0,sizeof(vis));
Divide(getG(1,n2),1);
for(int i=0;i<=K;i++) (allans+=(LL)ans[0][i]*ans[1][K-i]%P*C(K,i)%P)%=P;
printf("%d\n",allans);
return 0;
}

E. Good Subsegments

离线 线段树

求整个的答案,是以前做过的经典题。我考虑类似的分治思路,但因为太菜了弄不出来。

题解有分治加莫队的做法,但根本看不懂。还有一种更好的线段树做法。

考虑离线然后扫描线的套路,需要求 \(max-min=len-1\) 的子区间。

注意到一个重要的性质,枚右端点,后缀最值变化中次数是 \(O(n)\) 的。

所以我们维护单调栈,然后直接线段树维护 \(max-min-len\)

这样现在的线段树状态就是当前右端点的贡献,即值为 \(-1\) 的位置有 \(1\) 的贡献。

然后发现,处理询问需要在线段树每个节点记录历史贡献和。

所有我们每次打个标记,把当前值为 \(-1\) 的位置贡献和加 \(1\) 就好了。都是可以维护的,具体看代码。

这种记录历史贡献和的思路感觉挺有用的…

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<vector>
#include<algorithm>
#define mp make_pair
#define X first
#define Y second
typedef long long LL;
using namespace std;
const int maxn=200005;
int N_seg,Min[maxn*2],cnt[maxn*2],ch[maxn*2][2];
int tag[maxn*2],tim[maxn*2];
LL res[maxn*2];
void Plus(int p,int val){ Min[p]+=val; tag[p]+=val; }
void Plus_time(int p,int val){ tim[p]+=val; res[p]+=(LL)cnt[p]*val; }
void pushdown(int p){
if(tag[p]) Plus(ch[p][0],tag[p]), Plus(ch[p][1],tag[p]), tag[p]=0;
if(tim[p]){
if(Min[p]==Min[ch[p][0]]) Plus_time(ch[p][0],tim[p]);
if(Min[p]==Min[ch[p][1]]) Plus_time(ch[p][1],tim[p]);
tim[p]=0;
}
}
void maintain(int p){
Min[p]=min(Min[ch[p][0]],Min[ch[p][1]]);
res[p]=res[ch[p][0]]+res[ch[p][1]];
cnt[p]=0;
if(Min[p]==Min[ch[p][0]]) cnt[p]+=cnt[ch[p][0]];
if(Min[p]==Min[ch[p][1]]) cnt[p]+=cnt[ch[p][1]];
}
int Build(int L,int R){
int p=++N_seg;
if(L==R) return cnt[p]=1, Min[p]=-1, p;
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
maintain(p); return p;
}
void Update(int p,int L,int R,int qL,int qR,int val){
if(R<qL||qR<L) return;
if(qL<=L&&R<=qR) return Plus(p,val),void();
pushdown(p); int mid=(L+R)>>1;
Update(ch[p][0],L,mid,qL,qR,val); Update(ch[p][1],mid+1,R,qL,qR,val);
maintain(p);
}
void Update_ans(int p,int L,int R,int qL,int qR,int val){
if(R<qL||qR<L) return;
if(qL<=L&&R<=qR) return (Min[p]==-1)?Plus_time(p,val):void();
pushdown(p); int mid=(L+R)>>1;
Update_ans(ch[p][0],L,mid,qL,qR,val); Update_ans(ch[p][1],mid+1,R,qL,qR,val);
maintain(p);
}
LL Query(int p,int L,int R,int qL,int qR){
if(R<qL||qR<L) return 0;
if(qL<=L&&R<=qR) return res[p];
pushdown(p); int mid=(L+R)>>1;
return Query(ch[p][0],L,mid,qL,qR)+Query(ch[p][1],mid+1,R,qL,qR);
}
int n,m,a[maxn];
vector< pair<int,int> > q[maxn];
int stk[maxn],top,stk2[maxn],top2;
LL ans[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x,y; scanf("%d%d",&x,&y);
q[y].push_back(mp(x,i));
}
Build(1,n);
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<a[i])
Update(1,1,n,stk[top-1]+1,stk[top],a[i]-a[stk[top]]), top--;
stk[++top]=i;
while(top2&&a[stk2[top2]]>a[i])
Update(1,1,n,stk2[top2-1]+1,stk2[top2],a[stk2[top2]]-a[i]), top2--;
stk2[++top2]=i;
Update_ans(1,1,n,1,i,1);
for(int j=0;j<q[i].size();j++)
ans[q[i][j].Y]=Query(1,1,n,q[i][j].X,i);
Update(1,1,n,1,i,-1);
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}