CSP-S 2019 题解（部分）& 游记（伪）

\(\text{day 0 - 8:00 a.m.}\)

GM: 欸童鞋们我们今天不学新知识点哦！

We: ヾ(✿ﾟ▽ﾟ)ノ好吔！

GM: \(\cdots\) 我们要考 \(\text{CSP-S 2019}\)。

We: 鄵儞亇cào nĭ mā！

\(\text{day 1 - 8:10 a.m.}\)

一眼望去，啊，这就是传说中的 \(\text S\) 组难度吗？

T1 格雷码

Problem Link 双倍经验 三倍经验

心路历程

看题比做题久系列

好险，还好敲完了闲着没事自己乱造数据玩，玩出来一组hack

估分 \(\text{100 pts}\) 吧。

Solution

题目大意：

给定 \(n\) 和 \(k\) ，求按指定规则生成的 \(n\) 位 \(0\sim 2^n-1\) 的二进制码中的第 \(k\) 个元素。规则如下：

对于长度为 \(2^n\) 的 \(n\) 位二进制码序列，\(0\sim 2^{n-1}-1\) 个元素为长度为 \(2^{n-1}\) 的序列做高位加上一个 \(0\) 的结果；

后面的元素为长度为 \(2^{n-1}\) 的二进制序列倒置后最高位加上一个 \(1\) 的结果。

\(1\) 位二进制码序列为 \(0,1\)。

---

数据范围：\(1\leqslant n\leqslant 64,0\leqslant k<2^n\)

不可能模拟啦~

众所周知，数据范围在 long long 规模的，基本上就是 \(\log\) 级的做法了。

这里提供一个码量较少的做法。（不要跟我扯那些大佬们的 \(\Theta(1)\) 做法）

对于 \(n\) 位二进制序列，我们简称 \(0\sim 2^{n-1}-1\) 这一段为前半段，剩余部分为后半段。

如果要求的 \(k\) 在前半段，那说明不是由 \(n-1\) 位序列翻转最高位置 \(1\) 得到的，那么最高位就会被置 \(0\)，也就是说第 \(n\) 位为 \(0\)。

否则，最高位为 \(1\)，\(k\) 会变成 \(2^{n-1}-[k-(2^{n-1}-1)]=2^n-1-k\) 。

然后就没了。

假代码

#include<cstdio>
#define int long long
int n,k;
signed main(){
	scanf("%lld%lld",&n,&k);
	while(n){
		if(k>=(1<<n-1)){
			putchar('1');
			k=(1<<n)-k-1;
		}
		else putchar('0');
		n--;
	}
	return 0;
}

你 以 为 这 题 就 这？

有两个问题。

1. 题目中的 \(k<2^n\)，而 \(n\) 最多可以取到 \(64\)。

   long long 的范围是 \(-2^{63}\sim 2^{63}-1\)，而 unsigned long long 才能达到 \(0\sim 2^{64}-1\)。

   所以 \(k\) 要用 unsigned long long 存。

   这样想，代码中的 1<<n-1 范围 int 类型的结果，会直接溢出然后 \(\text{UB}\)。

   所以保险和节省码量起见，使用 const unsigned long long x 存储 (unsigned long long)1 的值，然后将 1<<n-1 替换为 x<<n-1。

2. 注意到这一行语句：

   k=(x<<n)-k-1;
   

   数据出的好，可以卡住 x<<n。（事实上第 \(20\) 个点确实卡了）

   x<<64，ull 刚好溢出。直接自然溢出啥事没有

   所以只好把 x<<64 拆成 (x<<63)+(x<<63)。

   但是这并没有实质性地解决问题，虽然两个加数都没有爆，但它们之间的和却挂了。

   我们开心地发现后面做了一个减法，于是我们完全可以先 \(-\) 后 \(+\)。

真代码

#include<cstdio>
#define int unsigned long long
const int x=1;
int n,k;
signed main(){
	scanf("%llu%llu",&n,&k);
	while(n){
		if(k>=(x<<n-1)){
			putchar('1');
			k=(x<<n-1)+((x<<n-1)-1)-k;
		}
		else putchar('0');
		n--;
	}
	return 0;
}

关于 hack：

问题一可以用 64 999999999 和 64 10000000000 hack，你会发现它们的值差的不是一点两点。。。

（题目中提到格雷码的一个性质：相邻两个数码恰好一位的值不同）

问题二，可以用 64 18446744073709551615 hack，标答是 \(1\) 后面全是 \(0\) 。

---

T2 括号树

Problem Link 双倍经验 三倍经验

心路历程

我鄵cào，T2难度骤增。

先打了个链的部分分，推广到树上就是正解了。

但是我的树形DP（or 树上DP？反正都差不多）传参传的是个长度为 \(n\) 的 stack，应该会T。

（然后下来我就去跟 @Nefelibata 吹自己常数5e5）

链应该是 \(\Theta(n)\) 的，没问题，树有点险。

估分 \(\text{55+rp pts}\)

Solution

先把一条链的情况打出来再说。

因为已确定根节点为 \(1\) 且 \(f_i=i-1\)，所以 \(s_i=S_1\sim S_i\)，其中 \(s\) 的含义题目中有给出，\(S\) 为给定括号串。

\(k_i\) 的含义就可简化为 \(S_1\sim S_i\) 中的合法子串个数。

相信各位都做过括号匹配之类的题目，这里我们也用一个栈处理。

每遇到一个 \(\texttt (\) 就 push 进去，每遇到一个 \(\texttt )\) 就判断栈内是否有 \(\texttt (\) ，有就计算然后 pop。

因为要统计从 \(S_1\sim S_i\) 所有合法括号串，所以定义一个 \(cnt\) 表示从 \(S_1\sim S_i\) 的合法括号串个数，若当前字符可以完成一个匹配，则 cnt+=以第i个元素结尾的合法子串个数。

那么，这个“合法子串个数”应该怎样计算呢？

定义 \(lst\)，表示以当前元素的上一个元素结尾的合法子串个数。

若当前元素是 \(\texttt (\) ，把 \(lst\) 丢进栈里，记录如果当前 \(\texttt (\) 能被匹配，新增的合法括号串个数；

否则当前元素就和之前的合法子串挨不到一起了，\(lst\) 清零。（突然飚方言）

如果当前元素可以完成一个匹配，则栈顶记录的数就是和当前匹配上的括号紧挨着的之前的合法子串个数，由于当前又新增了一个匹配，记录最新的 \(lst\) 为栈顶元素 \(+1\)，同时这也是当前的 \(k_i\)。此时 cnt+=lst。

可得出以下代码：

//55pts 链 
namespace Task1{
	int lst,cnt;
	inline void solve(void){
		for(int i=1;i<=n;++i){
			if(s[i]=='('){
				stk.push(lst);
				lst=0;
			}
			else if(stk.size()){
				lst=stk.top()+1;
				cnt+=lst;
				stk.pop();
			}
			else lst=0;
			ans^=cnt*i;
		}
		printf("%lld",ans);
		return;
	}
}

然后直接把这些搬到树上即可。

其中，\(cnt\) 不能混合起来记了，必须每个点继承一下自己父亲结点的 \(cnt\)，然后自个儿记自个儿的。

\(lst\) 同理。

但是，由于作者清奇的思考方式与码风，她选择了把 \(cnt\) 改成数组，\(lst\) 改成 dfs 时传参。。。

总之，因为dfs在匹配过程中可能出现新增的 \(\texttt (\) 还没匹配完，留在栈里，或是后面一大堆 \(\texttt )\)，把之前的给匹配掉了，所以必须即时传参。

然后最后统一计算 cnt 值即可。

Code

差点被常数从 \(\Theta(n)\) 卡成 \(\Theta(n^2)\)。

#include<stack>
#include<cstdio>
#define int long long 
using std::stack;
const int maxn=5e5+5;
bool SF=1;	//Subtask Flag
int f[maxn];
char s[maxn];
int n,tot,ans;
stack<int>stk;
int h[maxn],to[maxn],nxt[maxn];
inline void add(int x,int y){
	to[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
	return;
}
inline void read(int&x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^48);
		ch=getchar();
	}
	return;
}
int cnt[maxn];
void dfs(int x,int lst,stack<int>st){
	cnt[x]=cnt[f[x]];
	if(s[x]=='('){
		st.push(lst);
		lst=0;
	}
	else if(st.size()){
		lst=st.top()+1;
		cnt[x]+=lst;
		st.pop();
	}
	else lst=0;
	for(int i=h[x];i;i=nxt[i])
		dfs(to[i],lst,st);
	return;
}
inline void solve(void){
	dfs(1,0,stk);
	for(int i=1;i<=n;++i)
		ans^=i*cnt[i];
	printf("%lld",ans);
	return;
}
signed main(){
	freopen("brackets.in","r",stdin);
	freopen("brackets.out","w",stdout);
	read(n);
	scanf("%s",s+1);
	for(int i=2;i<=n;++i){
		read(f[i]);
		add(f[i],i);
	}
	solve();
	return 0;
}
//作者亲自实验：过是一定能过的，出题人不至于来卡我常；但常数确实大得像吃了屎一样。

---

T3 树上的数

Problem Link 双倍经验 三倍经验

心路历程

草草草还剩不到半个小时了快点暴力冲啊！！！

暴力打出来了，开森。

估分 \(\text{10 pts}\)。

Solution

我的暴力和题解说的全排暴力不太一样QwQ

正解先咕着，因为题解基于另一种暴力方法改良出正解导致我看不懂

---

\(\text{day 1}\) 考完即时评测可还行（（（

万恶的NOI赛制。

GM: 你们猜现在榜首是谁？

Me: ™反正不是我。T1有手就行，T2简单树形DP，T3不知道什么辣鸡玩意儿，肯定比我高的一大片片，，，

这个时候出成绩了。

草你奶奶我T1WA了？（刚刚是谁说T1有手就行的？）

好的，\(\text{100 pts}\) 起步，\(\text{200 pts}\) 再见。

事实证明考试的时候反奶自己一口就对了。

GM: 榜首是…… @XSC062！

我 人 傻 了。

然而几秒后我就被 @Rabbit_Mua 以 T1 的五分之差踩到了后面

还好没继续往下掉

有生之年我竟然以 \(5\) 分之差排在@TIANWEN 前面！

开森。（蒟蒻的快乐）

估分：\(\text{100+(55+rp)+10}\approx \text{165 pts}\)

实际：\(\color{SkyBlue}{95}+\color{Orchid}{100}+10=\text{205 pts}\)

---

\(\text{day 2 - 2:10 p.m.}\)

精准预测：上午考那么好，一定把脑子和 \(rp\) 都耗光了，下午一定被 @Nefelibata 吊打。

T1 Emiya 家今天的饭

Problem Link 双倍经验 三倍经验

心路历程

花了接近 \(\text{2.5h}\) 想正解，导致正解没想出来，其他题的暴力分也没时间骗。

时间安排及其不合理，导致与1=失之交臂。。。（莫名押韵）

猜出来了大概是个 \(\Theta(n^2\times m)\) 的DP。

Soution

部分参考了这位金钩爷的博客。

题意简化：

给定一个 \(n\times m\) 的矩阵，从中选取任意多个数（假设为 \(k\)），满足：

1. 每行最多一个数；
2. 每列最多 \(\large\lfloor\frac{k}{2}\rfloor\) 个数。

求 \(\sum\limits_{k=2}^n\) 这些数的乘积（后文称其为总方案数），结果对 \(998244353\) 取模。

首先，我们知道，条件 \(1\) 很好满足；关键是条件 \(2\)。

众所周知，这种求方案数之类的大概率是 DP（而且这道题看起来也挺像的）

首先有一个很简单，但是很重要的性质：不满足条件 \(2\) 的最多只有一列，因为总共就 \(k\) 个数，不可能分割成两个个数都超过 \(\large\lfloor\frac k2\rfloor\) 的组。

但这个性质是关于不满足条件 \(2\) 的，我们要求的却是同时满足条件 \(1\) 和条件 \(2\) 的，这时候怎么办呢？

很简单，我们算出满足条件 \(1\) 的总方案数，减去满足条件 \(1\) 且不满足条件 \(2\) 的方案数不就行了？

1. DP求解满足条件 \(1\) 的总方案数。

   \(dp_{i,j}\) 表示选到第 \(i\) 行，共选了 \(j\) 个数，满足条件 \(1\) 的总方案数。

   \[dp_{i,j}=dp_{i-1,j}+\sum\limits_{j=1}^mdp_{i-1,j-1}\times a_{i,j} \]

   小解释：\(dp_{i-1,j}\) 表示第 \(i\) 行不选的情况，\(\sum\limits_{j=1}^mdp_{i-1,j-1}\times a_{i,j}\) 表示第 \(i\) 行选 \(1\sim m\) 某一列上的数的情况。

   令 \(s_i=\sum\limits_{j=1}^ma_{i,j}\)，则可以优化为：

   \[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times s_i \]

   最终求得满足条件 \(1\) 的总方案数为 \(\sum\limits_{i=1}^mdp_{n,i}\)。

   注意，虽说这里求和是从 \(1\) 开始求的，但 \(j\) 还是得从 \(0\) 开始的异世界生活，所以在 \(j-1\) 那里要特判一下。

   时间复杂度 \(\Theta(n^2)\)。

2. DP求解满足条件 \(1\) 且不满足条件 \(2\) 的总方案数。

   我们设唯一不满足条件的列为 \(r\)。

   枚举每一个 \(r\)，对每一个不同的 \(r\) 进行一次DP。

   令 \(f_{i,j,k}\) 表示选到第 \(i\) 行，\(r\) 上有 \(j\) 个数，其他列一共选了 \(k\) 个数的方案数。

   \[f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k}\times a_{i,r}+f_{i-1,j,k-1}\times (s_i-a_{i,r}) \]

   小解释：\(f_{i-1,j,k}\) 表示第 \(i\) 行不选数，直接继承上一行的情况数；\(f_{i-1,j-1,k}\times a_{i,r}\) 表示选 \(a_{i,r}\) 的情况；\(f_{i-1,j,k-1}\times (s_i-a_{i,r})\) 表示选第 \(i\) 行其他列的情况总数。

   最终不合法方案总数为 \(\large\sum\limits_{j>k} f_{n,j,k}\)。

   为什么是 \(j>k\) ？

   由 \(j>\frac{j+k}2\) 变形得。（无视下取整，反正有没有都差不多）

   时间复杂度 \(\Theta(n^3)\)，在加上枚举 \(r\) 的一个 \(m\)，\(\Theta(n^3\times m)\)，直接炸掉。

   考虑优化。

   上面求不合法方案总数的限制条件是 \(j<k\)，意味着我们并不在意 \(j\) 和 \(k\) 的数值具体是多少，只关心它们之间的大小关系。

   所以可以把 \(f\) 变为二维，\(f_{i,j}\) 表示已经选到第 \(i\) 行，第 \(r\) 列上的数比其他列上的数多 \(j\) 的总情况数。

   则有：

   \[f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_{i,r}+f_{i-1,j+1}\times(s_i-a_{i,r}) \]

   最终答案为 \(\sum f_{n,i}\)。

   枚举到 \(i\) 时，\(j\) 最少可能是 \(0-i\)（全部选其他列上的），以及最多可能是 \(i-0\)（全部选 \(r\) 上的）。为了避免下标出现负数，我们把第二维的下标全部 \(+n\) 处理。（所以开数组时第二维也要多开一个 \(n\) 啦，不要像作者一样净犯这些SB错误还Debug了一个小时就离谱）

   单步时间复杂度 \(\Theta(n^2)\)，总时间复杂度 \(\Theta(n^2\times m)\)。

   可能有些同学会疑惑：\(a,b(a>b)\) 之间的差值与 \(a+1,b+1\) 的差值是一样的，像这样算总感觉怪怪的。。。

   可是，我们想想，就算我们把原来的 \(f_{i,a,b}\) 和 \(f_{i,a+1,b+1}\) 加在一起放在现在的 \(f_{i,a-b}\) 里面，未经优化的方式最终统计总方案数还是会把 \(f_{i,a,b}\) 和 \(f_{i,a+1,b+1}\) 加在一起，现在只是相当于提前加了而已，而且仔细分析式子，会发现不会重复计算。虽然看起来确实很怪异，但这种方法确实是正确的。

Code

#include<cstdio>
#include<cstring>
#define int long long
const int mod=998244353;
int s[105];
int n,m,S,ans;
int a[105][2005];
int f[105][205],dp[105][105];
signed main(){
	#ifdef ONLINE_JUDGE
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	#endif
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%lld",&a[i][j]);
			s[i]=(s[i]+a[i][j])%mod;
		}
	}
	dp[0][0]=1;
	//Step 1: DP求解满足条件1的总方案数
	for(int i=1;i<=n;++i){
		for(int j=0;j<=i;++j){
			dp[i][j]=dp[i-1][j];
			if(j)dp[i][j]=(dp[i][j]+dp[i-1][j-1]*s[i])%mod;
			if(i==n&&j){S+=dp[i][j];S%=mod;}
		}
	}
	//Step 2: DP求解满足条件1且不满足条件2的总方案数
	for(int r=1;r<=m;++r){
		memset(f,0,sizeof(f));
		f[0][n]=1;
		for(int i=1;i<=n;++i){
			for(int j=n-i;j<=n+i;++j){
				f[i][j]=f[i-1][j]+f[i-1][j-1]*a[i][r]%mod
				+f[i-1][j+1]*(s[i]-a[i][r])%mod;
				f[i][j]%=mod;
			}
		}
		for(int i=1;i<=n;++i)
			ans=(ans+f[n][n+i])%mod;
	}
    //众所周知减法取模保险起见要先加模数
	printf("%lld",(S-ans+mod)%mod);
	return 0;
}

T4 划分

Problem Link 双倍经验 三倍经验

心路历程

距离考试结束还有不到半个小时。

心灰意冷地打开T2。

草！好熟悉的题目名字和题面！

草！我做过这道题的简化版！推的式子还在U盘里！证明过程也在！

这道题本来几天前还想做的，也看过题面，翻过题解。。。

但是一看到要用高精连式子都没看就麻溜滚粗了。

此生无憾草你妈要不是旁边的 @Nefelibata 一直用正义猥琐的目光盯着我的电脑屏幕上的题解劳资直接干翻全场！！！

然后在 @Nefelibata 正义的目光下最终没能看成。

Solution

大家可以先去把上文提到的简化版做一遍，和这道题大有联系。

for(;;)puts("gugugu");

先把半成品放这儿骗骗访问量ヾ(≧∇≦*)ヾ