信友队 2023 游记
lzyqwq
·
·
个人记录
cnblogs
7.9 \text{ Day } 0
下午去学校讲课，然后坐地铁去杭师大。坐了一个小时到了。到了宿舍，就吃饭去了。吃完饭换队服，遇到了室友。室友是 Axiomatic（zhc）和佬♂头（qsj）。晚上 19:00\sim 20:30 是开营仪式，然后回宿舍，写题解，洗漱，收手机，睡大觉。
7.10\text{ Day }1
几乎没睡着。上午讲主定理和复杂度分析，根本不会，用递归树和单点乱搞。然后讲了 CF949E，*2700 的构造，听懂了，胡了一个证明，还过得去。但是写假了 \text{TLE on test 15}。wtcl /kk。
中午吃饭，人十分甚至九分的多，zhc 甚至没拿到筷子，不过还算好吃。这时候信友队真神省选队的人来了 /bx。下午说说是做题，实际上前几个小时都是模拟赛。由于一直在调 CF949E，晚了 10\text{min}。/fn。
先看 \text{A}。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,a[N],b[N];
priority_queue<pair<int,pair<int,int>>>q;
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
cin>>b[i];
}
sort(b+1,b+1+n,greater<int>());
for(int i=1;i<=n;++i){
q.push({a[i]*b[1],{1,i}});
}
for(int i=1;i<=n;++i){
pair<int,pair<int,int>>p=q.top();
q.pop();
cout<<p.first<<' ';
q.push({a[p.second.second]*b[p.second.first+1],{p.second.first+1,p.second.second}});
}
}
```
$score=100+0+0+0=100$。
然后看了一会 [$\text{B}$](https://www.xinyoudui.com/contest?courses=573&books=513&pages=15873&fragments=49404&problemId=7495 "$\text{B}$")。感觉题意暧昧不清 ，于是去看 [$\text{D}$](https://www.xinyoudui.com/contest?courses=573&books=513&pages=15873&fragments=49404&problemId=7799 "$\text{D}$")。
> - 给出 $n$ 个点的树，根为 $1$。点有点权 $a_i$，有两种操作：
>
> - $1,x,v$，$a_x\leftarrow a_x+v$。
>
> - $2,x$，查询 $x$ 到根路径上的点的点权和。
这不是树剖模板题吗？过了样例，兴致勃勃交了一发结果爆 $0$。自己造了个二叉树，发现边界搞错了，改了就过了。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,a[N],d[N],sz[N],f[N],t[N],h[N],dfn[N],cnt,bit[N];
vector<int>g[N];
void modify(int x,int k){
for(int i=x;i<=n;i+=i&(-i)){
bit[i]+=k;
}
}
int query(int x){
int ret=0;
for(int i=x;i;i-=i&(-i)){
ret+=bit[i];
}
return ret;
}
void dfs1(int u,int fa){
sz[u]=1;
for(int v:g[u]){
if(v^fa){
d[v]=d[u]+1;
dfs1(v,f[v]=u);
sz[u]+=sz[v];
}
}
}
void dfs2(int u,int fa){
for(int v:g[u]){
if(v^fa){
if((sz[v]<<1)>sz[u]){
t[h[u]=v]=t[u];
}else{
t[v]=v;
}
dfs2(v,u);
}
}
}
void dfs3(int u,int fa){
dfn[u]=++cnt;
modify(cnt,a[u]);
if(h[u]){
dfs3(h[u],u);
}
for(int v:g[u]){
if((v^fa)&&(v^h[u])){
dfs3(v,u);
}
}
}
int Query(int x){
int ret=0;
while(x){
ret+=query(dfn[x])-query(dfn[t[x]]-1);
x=f[t[x]];
}
return ret;
}
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1,u,v;i^n;++i){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(t[1]=1,0);
dfs3(1,0);
for(int op,x,v;m--;){
cin>>op>>x;
if(op&1){
cin>>v;
modify(dfn[x],v);
}else{
cout<<Query(x)<<'\n';
}
}
}
```
$score=100+0+0+100=200$。
然后 $\text{B}$ 修正过来了，始做之。
> - 给出 $n$ 个点的序列 $h_1\sim h_n$，求出最长的波形序列长度（即对于非两侧的数均大于或小于其两边的数）。
>
> - $n\le 10^5$，$0\le h_i\le 10^6$。
像 dp。设以 $f_{i,0/1}$ 表示以 $i$ 结尾且 $i$ 为最小于/大于前一个数的最长波形序列。有 $f_{i,0}=\max\limits_{j<i\land h_j>h_i}\{f_j\}+1$，$f_{i,1}$ 类似。树状数组维护之。答案为 $\max\limits_{i=1}^n\{\max\{f_{i,0},f_{i,1}\}\}$。一开始把 $i$ 打成 $x$ 了，只有 $10\text{pts}$，改了过了发现还是只有 $50\text{pts}$，特判了一下发现 $h$ 的值域是自然数题面又出锅了。然后经过调整值域就过了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,h[N],bit[6][N*10],f[N][2],ans=1;
void modify(int id,int x,int k){
for(int i=x;i<=1e6+2;i+=i&(-i)){
bit[id][i]=max(bit[id][i],k);
}
}
int query(int id,int x){
int ret=0;
for(int i=x;i;i-=i&(-i)){
ret=max(bit[id][i],ret);
}
return ret;
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>h[i];
++h[i];
f[i][0]=f[i][1]=1;
}
for(int i=1;i<=n;++i){
f[i][0]=max(f[i][0],query(1,1e6+1-h[i])+1);
f[i][1]=max(f[i][1],query(0,h[i]-1)+1);
modify(0,h[i],f[i][0]);
modify(1,1e6-h[i]+2,f[i][1]);
}
for(int i=1;i<=n;++i){
ans=max({ans,f[i][0],f[i][1]});
}
cout<<ans;
}
```
$score=100+100+0+100=300$。
最后看 [$\text{C}$](https://www.xinyoudui.com/contest?courses=573&books=513&pages=15873&fragments=49404&problemId=7499 "$\text{C}$")。
> - 给出长度为 $n$ 的字符串 $A$ 和长度为 $m$ 的字符串 $B$。从左至右依次选取 $K$ 个 $A$ 的**不相交子串**，然后将它们依次首尾相连。求出使得连接后的串等于 $B$ 的方案数，模 $10^9+7$。
>
> - $n\le 10^3$，$K\le m\le 200$。
又是 dp，还是计数。以为自己要寄。还是硬着头皮推了一下方程。设 $f_{i,j,k}$ 为 $A$ 中前 $i$ 个字符，选取 $k$ 段，使得得到的串等于 $B$ 的前 $j$ 个字符。
考虑是否选取 $A$ 第 $i$ 位，不选则 $f_{i,j,k}\leftarrow f_{i,j,k}+f_{i-1,j,k}$，若选取，则找到 $A$ 的第 $i$ 位和 $B$ 的第 $j$ 位往前完全匹配的子段的最大长度 $p$，$f_{i,j,k}\leftarrow f_{i,j,k}+\sum\limits_{q=1}^pf_{i-q,j-q,k-1}$。测了一发样例，没过。慌了，发现初始化忘了。改了一下，这次过了两个。先交一发，$30\text{pts}$，又 $\text{WA}$ 又 $\text{TLE}$，还没卡过。/fn。原来初始化错了，应该是 $f_{i,0,0}=1$。交了一发，$\text{TLE }90\text{pts}$。/fn。原来这玩意时间复杂度是 $\mathcal{O}(nm^2k)$ 的，寄。
真的寄了吗?发现第二类转移是一个求区间和的形式。具象成网格图，就是过格子 $(i,j)$ 往左上、右下走的一条斜线上，求一段连续格子权值的和，格子 $(x,y)$ 权值是 $f_{x,y,k-1}$。维护斜线的前缀和。把 $k$ 的循环放在最外面。设 $s_{i,j}$ 表示这条斜线一直到 $(0,j-i)$ 这些格子的值的和，有 $s_{i,j}=s_{i-1,j-1}+f_{i,j,k-1}$，注意一下边界 $0$。然后还要处理一下 $A_i$ 和 $B_j$ 往前的最长匹配 $pip_{i,j}$，就是预处理之前的 $p$。这玩意写寄了调了好久。最后把那个 $\sum$ 表示成差分就行了。
测一发样例，挂得离谱。啊，每次求 $s$ 忘记清空了。还不对！额，右下端点搞错了应该是 $(i-1,j-1)$。所以第二个转移应该是 $f_{i,j,k}\leftarrow f_{i,j,k}+s_{i-1,j-1}-s_{i-pip_{i,j}-1,j-pip_{i,j}-1}$，同样注意边界，以及负数取模。时间、空间复杂度均为 $\mathcal{O}(nmk)$。终于过了。
```cpp
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1005,M=205;
const ll mod=1e9+7;
ll f[N][M][M],s[N][M];
int n,m,K,pip[N][M];
string A,B;
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m>>K>>A>>B;
A=' '+A;
B=' '+B;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
bool ok=1;
for(int k=1;k<=min(i,j);++k){
if(A[i-k+1]^B[j-k+1]){
pip[i][j]=k-1;
ok=0;
break;
}
}
if(ok){
pip[i][j]=min(i,j);
}
}
}
for(int i=0;i<=n;++i){
f[i][0][0]=1;
}
/*for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
for(register int k=1;k<=min({K,j,i});++k){
f[i][j][k]+=f[i-1][j][k];
f[i][j][k]%=mod;
int y,res=0;
for(register int p=1;p<=min(i,j)&&A[i-p+1]==B[j-p+1];++p){
f[i][j][k]+=f[i-p][j-p][k-1];
res+=f[i-p][j-p][k-1];
f[i][j][k]%=mod;
y=p;
}
cout<<i<<' '<<j<<' '<<k-1<<' '<<res<<'\n';
}
}
}*/
for(int k=1;k<=min({n,m,K});++k){
memset(s,0,sizeof s);
for(int i=k-1;i<=n;++i){
for(int j=k-1;j<=m;++j){
s[i][j]=f[i][j][k-1]+(i&&j?s[i-1][j-1]:0);
s[i][j]%=mod;
//cout<<i<<' '<<j<<' '<<k-1<<' '<<s[i][j]<<'\n';
}
}
for(int i=k;i<=n;++i){
for(int j=k;j<=m;++j){
f[i][j][k]+=f[i-1][j][k];
f[i][j][k]%=mod;
f[i][j][k]+=s[i-1][j-1]-(i-pip[i][j]&&j-pip[i][j]?s[i-pip[i][j]-1][j-pip[i][j]-1]:0)+mod;
f[i][j][k]%=mod;
}
}
}
cout<<f[n][m][K];
}
```
$score=100+100+100+100=400$。AK 了！
但是老师说本来要卡 $\mathcal{O}(nmk)$ 的空间的，于是把 $k$ 这一维滚掉，时间复杂度不变，空间复杂度为 $\mathcal{O}(nm)$。一开始数组开小 $\text{RE}$ 了一发，随后过了。
```cpp
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1005,M=205;
const ll mod=1e9+7;
ll f[N][M],s[N][M],g[N][M];
int n,m,K,pip[N][M];
string A,B;
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m>>K>>A>>B;
A=' '+A;
B=' '+B;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
bool ok=1;
for(int k=1;k<=min(i,j);++k){
if(A[i-k+1]^B[j-k+1]){
pip[i][j]=k-1;
ok=0;
break;
}
}
if(ok){
pip[i][j]=min(i,j);
}
}
}
for(int i=0;i<=n;++i){
f[i][0]=1;
}
/*for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
for(register int k=1;k<=min({K,j,i});++k){
f[i][j][k]+=f[i-1][j][k];
f[i][j][k]%=mod;
int y,res=0;
for(register int p=1;p<=min(i,j)&&A[i-p+1]==B[j-p+1];++p){
f[i][j][k]+=f[i-p][j-p][k-1];
res+=f[i-p][j-p][k-1];
f[i][j][k]%=mod;
y=p;
}
cout<<i<<' '<<j<<' '<<k-1<<' '<<res<<'\n';
}
}
}*/
for(int k=1;k<=min({n,m,K});++k){
for(int i=0;i<=n;++i){
for(int j=0;j<=m;++j){
g[i][j]=f[i][j];
f[i][j]=0;
}
}
memset(s,0,sizeof s);
for(int i=k-1;i<=n;++i){
for(int j=k-1;j<=m;++j){
s[i][j]=g[i][j]+(i&&j?s[i-1][j-1]:0);
s[i][j]%=mod;
//cout<<i<<' '<<j<<' '<<k-1<<' '<<s[i][j]<<'\n';
}
}
for(int i=k;i<=n;++i){
for(int j=k;j<=m;++j){
f[i][j]+=f[i-1][j];
f[i][j]%=mod;
f[i][j]+=s[i-1][j-1]-(i-pip[i][j]&&j-pip[i][j]?s[i-pip[i][j]-1][j-pip[i][j]-1]:0)+mod;
f[i][j]%=mod;
}
}
}
cout<<f[n][m];
}
```
总结一下，$\text{A}<\text{B}<\text{D}<\text{C}$。/cf。
继续调 CF949E，还是老样子 /fn。老师让我上去讲一下 $\text{C}$ 做法。
晚上吃饭，肉全是骨头 /fn。遇见~~邂逅~~了 [Stasis](https://www.luogu.com.cn/user/363149 "Stasis")（th）。晚自习打了把初赛，阅读程序是啥啊 /kk。根本看不懂 /lb。不过完善程序板的要死 /cf。测出来居然有 $79\text{pts}$。
然后就回宿舍洗漱、睡觉了。总结一下，第一天旗开得胜，但是过几天就要被薄纱了 /ll。