前行 - CSP-S 2019 | Lucky_Glass's Blog
0%

前行 - CSP-S 2019

似乎 CSP 已经过去有一段时间了……心情(无论是写爆了的烦闷还是AC了的欣喜)都已经平复下来了,是时候写题解了 awa
Day1Day2 的 T3 仍然不知道怎么做,只有先写 T1T2 了


Part1.简单小结

这次CSP-S非常明显地表现了“正解结论化”以及树形题愈发恶心的趋势……

今年的两道压轴题都是树嘛,似乎都很难的样子。隐隐约约感觉有一些结论性的东西,但是实在没能推导出来……

很扫兴但也很幸运的是这次并没有考数论……考前慌得一bi —— 莫比乌斯反演、斯特林数什么的啥都不会……
但是毕竟花了大量的时间复习数论,简单的扩展欧几里得、中国剩余定理、高斯消元也并没有考到(或者说我没看出来),还是有一点郁闷的。

可能这也说明了出题人认为数论知识的难度还是偏高,可能出现在省选难度的考试中更为合适。(反正不能因为 CSP 没考就把数论放掉)


Tab. 题面的话……洛谷、LOJ、牛客上面都有的,就不附了

Part2. CSP-S Day1

Part2/1. 格雷码(code)

非常开心,今年Day1T1放水 awa
但是也挂在了大众分上……

同校的一个 OIer 有一个结论性的做法,很简单,但是我没有弄懂,就不写了。

不难想到逐个求每个数位上的数字。然后就得到一个初步的思路 —— 如果位置处于当前数列的后半段,那么最高位应为 1,否则为 0。
考虑递归地处理这个问题,即求出最高位后,删去最高位,求剩下的数字在 n-1 位格雷码数列中 所处的位置,非常简单:

  • 如果位置在原数列的前半段,则在 n-1 位格雷码数列中位置不变;
  • 如果位置在原数列的后半段,则在 n-1 位格雷码数列中的位置和原位置关于原数列的中心位置对称

于是就可以递归出解了。

Part2/2. 括号树

考场上栈的回溯写挂了,调了好久……

对于括号序列,我们常用 来处理,这道题也不例外。考虑从根出发 DFS,对于每个节点计算从根到它的括号序列的答案。

要处理出两个东西:

  1. ans[u]:从根节点到点u的括号序列中有多少个符合要求的子串,那么最后的答案即是 $\bigoplus_{u=1}^n(u\times ans[u])$
  2. dp[u]:从根节点到点u的括号序列中,最长的合法后缀最外层括号数量。比如括号序列是 ())()(()()) 那么最长的合法后缀应该是 ()(()()),最外层括号数量有两对。

那么需要用一个栈来维护从根到当前点的括号序列:

  1. 如果当前是 (,则将当前点 push 到栈里;
  2. 如果当前是 )

    • 如果栈空了,那么久不能匹配,则 dp[u]=0、当前点不会造成新的贡献,ans[u]=ans[fa[u]]fa[u] 是 u 的父节点,ans[u] 无论如何都会包含 ans[fa] 的部分嘛);
    • 否则 u 与栈顶点匹配,设该点为 las,弹出栈;
      dp[u]=dp[fa[las]]+1,即考虑 las 与 u 匹配后,说明 las,u 之间的括号也都匹配,但是还要与 fa[las] 之前的 dp[fa[las]] 接上;
      ans[u]=ans[pre[u]]+dp[u],即加上以 u 结尾的合法括号序列数量 dp[u]

    这样久可以计算出每个点的 ans[u],进而求出答案了~
    记得 DFS 回溯时要把对栈的操作回退一下。


Part3. CSP-S Day2

Part3/1. Emiya 家今天的饭

—— 正难则反!(一个稍微有点基础的 OIer 应该一眼判断出这是一道容斥)

不难发现,如果确定了菜的个数,那么最多只会有一种食材是不合法的(用该食材做的菜超过了半数)。
一开始可以简单地做一个背包,求出不考虑不合法情况下,做 i 道菜的方案数是 ans[i]

然后对于每个食材,求出该食材不合法的所有不合法方案数。有一个暴力的 DP 思路:
枚举不合法的食材 t,设立 DP 状态 dp[i][j][k] 表示前 i 种烹饪方法做了 j 道菜,用食材 t 做了 k 道菜。其实 DP 转移非常简单:

  • 第 i 种烹饪方法不做菜:dp[i-1][j][k]
  • 第 i 种方法用食材 t 做菜:dp[i-1][j-1][k-1]*A[i][t]
  • 第 i 种方法不用食材 t 做一道菜:dp[i-1][j-1][k]*(S[i]-A[i][t])

Tab. $S[i]=\sum_{j=1}^m A[i][j]$

DP 是 $O(n^3)$ 的,枚举 t 是 $O(m)$ 的,总共 $O(n^3m)$,可得 84pt。

考虑优化这一状态 —— 其实一个食材的菜超过半数,就是 用这种食材做的菜的数量严格大于用其他食材做的菜的数量,于是可以只存储 食材 t 做的菜比用其他食材做的菜多多少份(当然可以是负数)。

于是 dp[i][j] 表示用前 i 种烹饪方式做的菜中,“食材 t 做的菜 - 不是食材 t 做的菜 = j” 的方案数。类似的三种转移:

  • dp[i-1][j]
  • dp[i-1][j-1]*A[i][t]
  • dp[i-1][j+1]*(S[i]-A[i][t])

然后 $O(n^2m)$ 就可过了。

Part3/2. 划分

看了其他 OIer 的博客,知道了一个比较感性但是不会证明的结论,即最优解一定是最后取的一段之和最小 的解。

Tab. 考场上也是因为不知道这个结论,就很难想出来

那么知道这个结论,就可以设计 DP :f[i] 表示 1 到 i 的部分已经分割完,分出来的最后一段长度最小是多少。再先统计一下前缀和 S[i]

转移的话,f[i]=min(S[i]-S[j]),其中 j 要满足 f[j]<=S[i]-S[j](也就是题目的限制条件),移项可得 f[j]+S[j]<=S[i]
不难发现,j 一定是越大越好。又因为 S[i] 是单调递增的,可以单调队列维护一个 f[j]+S[j] 递增的序列。

因为如果 a=f[b]+S[b]`,那么 a 一定没有 b 优。

每次判断队头的下一个元素是否可以满足条件,如果可以,就弹掉队头。最后队头就是最优转移点。

如果要 100pt 的话,别忘了写高精度!(推荐压位,不知道不压位能不能过)


Part4. 源代码

都在洛谷测的……

> Day1T1

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=64;

int ans[N*2];

int Solve(unsigned long long n,unsigned long long m){
if(n==1){
ans[1]=m;
return 1;
}
unsigned long long fn=n/2;
int res;
if(m>=n){
res=Solve(fn,n-(m-n)-1)+1;
ans[res]=1;
}
else{
res=Solve(fn,m)+1;
ans[res]=0;
}
return res;
}

int main(){
//freopen("code.in","r",stdin);
//freopen("code.out","w",stdout);
unsigned long long n,m;
cin>>n>>m;
int res=Solve((unsigned long long)1<<(n-1),m);
for(int i=res;i>=1;i--)
printf("%d",ans[i]);
printf("\n");
return 0;
}

> Day1T2

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=5e5;

struct NODE{
int to;NODE *nxt;
NODE(){}
NODE(int _t,NODE *_n):to(_t),nxt(_n){}
};
struct TREE{
NODE pol[N+3],*head[N+3],*ncnt;
void Init(){
ncnt=pol;
}
void AddEdge(int u,int v){
NODE *p=++ncnt;
*p=NODE(v,head[u]);
head[u]=p;
}
}Tr;

int n;
char sg[N+3];
int stk[N+3],pre[N+3],nstk;
long long dp[N+3],ans[N+3];

void DFS(int u,int fa){
pre[u]=fa;
int las=-1;
if(sg[u]=='('){
stk[++nstk]=u;
ans[u]=ans[fa];
dp[u]=0;
}
else{
if(nstk){
las=stk[nstk--];
dp[u]=dp[pre[las]]+1;
ans[u]=ans[pre[u]]+dp[u];
}
else{
ans[u]=ans[fa];
dp[u]=0;
}
}
for(NODE *it=Tr.head[u];it;it=it->nxt){
int v=it->to;
DFS(v,u);
}
if(las!=-1)
stk[++nstk]=las;
if(sg[u]=='(') stk[nstk--]=0;
}
int main(){
//freopen("brackets.in","r",stdin);
//freopen("brackets.out","w",stdout);
scanf("%d%s",&n,sg+1);
Tr.Init();
for(int i=2;i<=n;i++){
int fa;scanf("%d",&fa);
Tr.AddEdge(fa,i);
}
DFS(1,0);
long long prt=0;
for(int i=1;i<=n;i++)
prt^=(i*ans[i]);
printf("%lld\n",prt);
return 0;
}

> Day2T1
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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100,M=2000,MOD=998244353;

int n,m;
int Ca[N+3][M+3],f[N+3][2*N+3],sum[N+3],ans[N+3][N+3];

int main(){
scanf("%d%d",&n,&m);
ans[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&Ca[i][j]);
sum[i]=(1ll*sum[i]+Ca[i][j])%MOD;
}
for(int j=0;j<=n;j++){
ans[i][j]=ans[i-1][j];
if(j) ans[i][j]=(ans[i][j]+1ll*ans[i-1][j-> 1]*sum[i]%MOD)%MOD;
}
}
int prt=0;
for(int i=1;i<=n;i++)
prt=(1ll*prt+ans[n][i])%MOD;
for(int t=1;t<=m;t++){
for(int i=0;i<=n;i++)
for(int j=0;j<=2*n;j++)
f[i][j]=0;
f[0][n]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=2*n;j++){
//do nothing
f[i][j]=f[i-1][j];
//cook meal t
if(j>0) f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*Ca[i][t]%MOD)%MOD;
//cook except t
if(j<=2*n) f[i][j]=(f[i][j]+1ll*f[i-> 1][j+1]*((1ll*sum[i]-Ca[i][t])%MOD+MOD)%MOD)%MOD;
}
int res=0;
for(int i=n+1;i<=2*n;i++)
res=(1ll*res+f[n][i])%MOD;
prt-=res;
prt=(prt+MOD)%MOD;
}
printf("%lld\n",prt);
return 0;
}

> Day2T2
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef unsigned long long ull;
const int N=4e7,PER=1e8,M=1e5;

struct BNUM{
long long num[7];
int len;
void TIME(const BNUM &B){
long long sav[7]={};
int slen=1;
for(int i=0;i<B.len;i++)
for(int j=0;j<len;j++){
sav[i+j]+=num[j]*B.num[i];
if(i+j+1>slen && sav[i+j]) slen=i+j+1;
}
for(int i=0;i<slen;i++){
sav[i+1]+=sav[i]/PER;
sav[i]%=PER;
num[i]=sav[i];
if(sav[slen]) slen++;
}
len=slen;
}
void ADD(const BNUM &B){
len=max(len,B.len);
for(int i=0;i<B.len;i++){
num[i]+=B.num[i];
if(num[i]>=PER) num[i+1]++,num[i]-=PER;
if(num[len]) len++;
}
}
void GetBNUM(long long x){
len=0;
while(x){
num[len++]=x%PER;
x/=PER;
}
}
void Print(){
printf("%lld",num[len-1]);
for(int i=len-2;i>=0;i--) printf("%08lld",num[i]);
}
}ans;

int n;
long long Ca[N+3],Ef[N+3];
int Cb[N+3];
int que[N+3],las[N+3],fro,bck;

int main(){
int typ;
scanf("%d%d",&n,&typ);
if(typ){
int x,y,z,m;
scanf("%d%d%d%d%d%d",&x,&y,&z,&Cb[1],&Cb[2],&m);
const ull Xmod=1ull<<30;
for(int i=3;i<=n;i++)
Cb[i]=(int)(((ull)x*Cb[i-1]%Xmod+(ull)y*Cb[i-> 2]%Xmod+(ull)z)%Xmod);
int p,l,r,las=1;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&p,&l,&r);
int Ymod=r-l+1;
while(las<=p){
Ca[las]=(Cb[las]%Ymod)+l;
Ca[las]+=Ca[las-1];
las++;
}
}
}
else{
for(int i=1;i<=n;i++)
scanf("%lld",&Ca[i]),
Ca[i]+=Ca[i-1];
}
que[fro=bck=1]=0;
for(int i=1;i<=n;i++){
while(fro<bck && Ca[que[fro+1]]+Ef[que[fro+1]]<=Ca[i])
fro++;
int j=que[fro];
Ef[i]=Ca[i]-Ca[j];
las[i]=j;
// printf("%d\n",j);
while(fro<=bck && Ca[que[bck]]+Ef[que[bck]]>=Ca[i]+Ef[i])
bck--;
que[++bck]=i;
}
int pos=n;
while(pos){
// ans+=Ef[pos]*Ef[pos];
BNUM op;op.GetBNUM(Ef[pos]);
// printf("? %lld\n",pos);
// op.Print();printf("\n");
op.TIME(op);
// op.Print();printf("\n");
ans.ADD(op);
pos=las[pos];
}
ans.Print();
printf("\n");
return 0;
}


The End

Thanks for reading!

告一段落……