似乎 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,对于每个节点计算从根到它的括号序列的答案。
要处理出两个东西:
ans[u]
:从根节点到点u的括号序列中有多少个符合要求的子串,那么最后的答案即是 $\bigoplus_{u=1}^n(u\times ans[u])$dp[u]
:从根节点到点u的括号序列中,最长的合法后缀 的最外层括号数量。比如括号序列是())()(()())
那么最长的合法后缀应该是()(()())
,最外层括号数量有两对。
那么需要用一个栈来维护从根到当前点的括号序列:
- 如果当前是
(
,则将当前点 push 到栈里; 如果当前是
)
:- 如果栈空了,那么久不能匹配,则
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*/
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*/
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*/
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*/
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!
告一段落……