NOIP 2024 游记
cupWolf
·
·
生活·游记
Day -14
在路上偶遇了信竞老师。在他的建议下，我每天晚自习去集训。
Day -12
不用写作业真爽。
Day -5
这一周的所有集训我都是先做出T2再做出T1的，这使我有不祥的预感。
Day 0
所有与具体做法强相关的将放在题解部分。
T1（上）
对着草稿纸比划了 0.5h，打了个贪心，证不出来。
小样例过了，程序在大样例的答案居然比样例输出还大，这使我疑惑，调了 0.5h 没调出来。
T2
正难则反。反着想不久（<0.5h）就想出来了。T2 比 T1 简单，Day -5 的预感成真了。
踩了俩坑。
- 没特判 c_{i}=c_{i+1}, d_{i}= d_{i+1}，最后加了个
unique 去重。
- 写少了俩取模。这个通过
typedef __int128 ll; 发现输出有变化，于是查出来了。
然后第 2, 3 个大样例一起过了。
T3
太长没看。
T4
想出了 ST 表 \Theta(n\log^2n+q[(L-k)+\log n]) 的做法（其中 L=r-l+1），然而写挂了，只有小样例过得去。
在调 T4 和 T1 之间还是选择了 T1，因为就算这种解法调好也不超过 40 pts，事实证明这是明智的。
T1（下）
此时距离结束还有 2h.
首先重构了一下代码。原来的代码是将 s_1 与 s_2 均未被分割的编成一块，统一计算转移，重构之后就是一个一个字符转移的，虽然常数稍大但是更简洁清晰。
然后就是打了几个断点，手造样例。中途一个插曲是造样例的时候把顺序造成 s_1, t_1, s_2, t_2 了，还以为自己发现了症结所在。
最后终于发现自己把 n1 = (t1[i]=='0' || t1[i]!=t1[i-1]) 打成了 n1 = (t1[i]==0 || t1[i]!=t1[i-1])，打少了个单引号，这导致了没有把连续的 0 隔开。
改完之后就过了全部样例，此时距离结束还有 45min.
然后我心情舒坦地上了个厕所。（吸取 CSP 教训，我这次上了 3 次厕所）
等
例行拜了拜电子佛祖。
后
老师请吃了披萨，好耶！
同学们太热情了，刚出炉的披萨立刻被瓜分了，只能等他们吃饱了才能吃到。
肴核既尽，杯盘狼藉。老师先走了，同学们在打牌。我不会打牌，于是也走了。
分
T1 也许是因为贪心难以证明迟迟没出数据。
民间数据 T2 AC.
T4 估计寄了，\le 10\text{ pts}.
一首改编的打油诗
一题夸自己，两题了不起。
T4 写挂了？有写就是牛。
希望能时刻保持良好的心态。
题解
T1
不难发现原题可以转化为： 将 s_1, s_2 分别划成几个区间，区间内打乱。
例如样例
$t_1=$ `111010`
可以划成 $011/1/0/1$.
也就是说，我们在每个 $t_i=0$ 的左右分别划一刀。
接下来就是贪心。
如果 $i$ 所在的段内同时有未匹配的 $s_{1,j}=s_{2,k}$，就把 $s_{1,j}, s_{2,k}$ 挪到 $i$ 的位置并标记为匹配。
考场上粗略地证了一下，但是考完发现有漏洞，所以不发出来误人子弟了。
#### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
char s1[maxn], s2[maxn], t1[maxn], t2[maxn];
struct area {
int cnt[4];
} sa1[maxn], sa2[maxn];
int belong1[maxn], belong2[maxn];
int sa1tot, sa2tot;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
freopen("edit.in", "r", stdin);
freopen("edit.out", "w", stdout);
int t;
cin >> t;
while (t--){
memset(sa1, 0, sizeof sa1);
memset(sa2, 0, sizeof sa2);
sa1tot = sa2tot = 0;
int n;
cin >> n;
cin >> s1+1 >> s2+1 >> t1+1 >> t2+1;
for (int i=1; i<=n; i++){
int n1 = (t1[i]=='0' || t1[i]!=t1[i-1]),
n2 = (t2[i]=='0' || t2[i]!=t2[i-1]);
sa1tot += n1;
sa2tot += n2;
sa1[sa1tot].cnt[s1[i]-'0']++;
sa2[sa2tot].cnt[s2[i]-'0']++;
belong1[i] = sa1tot;
belong2[i] = sa2tot;
}
int ans=0;
for (int i=1; i<=n; i++){
int bl1=belong1[i], bl2=belong2[i];
if (sa1[bl1].cnt[0] && sa2[bl2].cnt[0]){
sa1[bl1].cnt[0]--;
sa2[bl2].cnt[0]--;
ans++;
} else if (sa1[bl1].cnt[1] && sa2[bl2].cnt[1]) {
sa1[bl1].cnt[1]--;
sa2[bl2].cnt[1]--;
ans++;
}
}
cout << ans << '\n';
}
return 0;
}
```
### T2
基本操作：先将限制条件按 $c_i$ 排序。
不难发现，如果一个位置没有被两个限制夹着，那么 $a_i, b_i$ 可以任取，即每个位置有 $v^2$ 种取值。
证明也很简单，如果一个位置的左边没有限制而右边有，那我们只需令 $x_i\ne a_i$，
如果右边没有限制而左边有，那么填什么都不影响。
那如果被两个限制 $c_j, c_{j+1}$ 夹着呢？
正难则反。
我们考虑 $a_i, b_i$ 应该等于什么才能让 $x_{c_{j+1}} \mathop{\ne}\limits^{一定} d_{j+1}$.
那么显然 $a_i, b_i$ 一定是一条完整的逻辑链条，才能把 $x_{c_{j+1}}$ 限制死。
链条的起始端一定为 $d_i$，中间是任意的（有 $v$ 种取值），末端一定不为 $d_{i+1}$（有 $(v-1)$ 种取值）
于是 $negans=v^{\Delta c}(v-1)$，其中 $\Delta c=c_{j+1}-c_j$.
该段的答案为 $v^{2\Delta c}-negans$.
把所有段（包括没有被两个限制夹着的段）的答案乘起来即可。
#### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxm=1e5+100, mod=1e9+7;
struct xianz {
long long c, d;
bool operator < (xianz &other){
return c < other.c;
}
bool operator == (xianz &other){
return c==other.c && d==other.d;
}
} xz[maxm];
ll qpow(ll a, ll b){
ll ans=1;
while (b){
if (b&1){
ans *= a;
ans %= mod;
}
a *= a;
a %= mod;
b >>= 1;
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("assign.in", "r", stdin);
// freopen("assign.out", "w", stdout);
int t;
cin >> t;
while (t--){
ll n, m, v;
cin >> n >> m >> v;
for (int i=1; i<=m; i++){
cin >> xz[i].c >> xz[i].d;
}
sort(xz+1, xz+m+1);
m = unique(xz+1, xz+m+1) - (xz+1);
bool ansis0=false;
ll ans=1;
for (int i=2; i<=m; i++){
if (xz[i].c == xz[i-1].c){
ansis0 = true;
break;
}
ll posans = qpow(v, 2*(xz[i].c-xz[i-1].c)),
negans = qpow(v, xz[i].c-xz[i-1].c-1);
negans *= v-1;
negans %= mod;
ans *= (posans-negans + mod) % mod;
ans %= mod;
}
if (m){
ans *= qpow(v, 2*(xz[1].c-1));
ans %= mod;
ans *= qpow(v, 2*(n-xz[m].c));
ans %= mod;
} else {
ans *= qpow(v, 2*(n-1));
ans %= mod;
}
if (ansis0){
cout << "0\n";
} else {
cout << ans%mod << '\n';
}
}
return 0;
}
```