2025.7.13~2025.8.2 我在rdfz完成了为期20天的集训生活,见识到了全国各地的优秀选手,同时写了一些题单，以下就一些好题稍作整理
[ P6240 好吃的题目 ]
-
猫树分治板子题
在猫树上维护每个区间的前后缀背包
即设f为当前区间中点到左端点的前缀背包，g为当前中点到右端点的后缀背包，有-
\(f_{i,j} = max(f_{i+1,j},f_{i+1,j-c_i}+w_i)\)
-
\(g_{i,j} = max(g_{i-1,j},g_{i-1,j-c_i}+w_i)\)
那么所有落在该分治区间内且跨过区间中点询问(l,r,t)，其对应答案ans，皆有
-
\(ans = \max_{i=0}^{t}f_{l,i}+g_{r,t-i}\)
考虑将所有询问离线，存入一个vector,最初从左端点1，右端点n开始分治，对于右端点小于mid或左端点大于mid的询问进行下一层的递归。时间复杂度\(O(nt\log n)\)
-
[ P7300 [USACO21JAN] No Time to Paint S ]
- 考场没切的简单题
本题最值得思考的实际上在于对前后缀的处理上
挖掉一段（l,r）实际上等价于前缀（1,l-1）和后缀（r+1,n）的并
于是我们考虑dp预处理出一个前缀和一个后缀，用\(k_i\)来表示当前i颜色可否从上一个位置一笔画得
code
for(int i=1;i<=n;i++){if(!k[s[i]-'A']) l[i]=l[i-1]+1;else l[i]=l[i-1];k[s[i]-'A']=1;for(int j=s[i]-'A'+1;j<26;j++) k[j]=0;}for(int i=0;i<26;i++) k[i]=0;for(int i=n;i>=1;i--){if(!k[s[i]-'A']) r[i]=r[i+1]+1;else r[i]=r[i+1];k[s[i]-'A']=1;for(int j=s[i]-'A'+1;j<26;j++) k[j]=0;}
[ 游走(walk) ]
- 诈骗题
考虑最大值和最小值一定在同一边，于是答案就是另一边的元素与最大值或最小值差的最大值
那么最值所在集合扩展必然不劣
所以对答案有贡献的只有只取左上角和只取右上角两种情况
[ Contests ]
- 使人眼前一亮的倍增技巧
考虑每个人只有m个后继，即为每个序列中可以到达的最前点
一切固定的东西，都可以用倍增来维护
于是我们可以预处理出每个人走\({2^n}\)步后到达的m个后继，然后判断这m个后继中有没有排名比y高的即可，时间复杂度\(O((n+q)m^2\log n)\)
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,a[7][N],c[7];
int pos[7][N],f[N][23][7];
inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
signed main(){n=rd(),m=rd();for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)a[i][j]=rd(),pos[i][a[i][j]]=j;for(int i=1;i<=m;i++){memset(c,0,sizeof c);for(int j=n;j>=1;j--){for(int k=1;k<=m;k++) if(!c[k]||pos[k][c[k]]>pos[k][a[i][j]]) c[k]=a[i][j];for(int k=1;k<=m;k++){if(!f[a[i][j]][0][k]||pos[k][f[a[i][j]][0][k]]>pos[k][c[k]]) f[a[i][j]][0][k]=c[k];}}}for(int i=1;i<23;i++){for(int j=1;j<=n;j++){for(int k=1;k<=m;k++){for(int o=1;o<=m;o++){int u=f[f[j][i-1][o]][i-1][k];if(!f[j][i][k]||pos[k][f[j][i][k]]>pos[k][u]) f[j][i][k]=u;}}}}int q=rd();while(q--){int x=rd(),y=rd();bool fg=0;for(int i=1;i<=m;i++) if(pos[i][x]<pos[i][y]) fg=1;if(fg){printf("1\n");continue;}else{int ans=N,cnt=0,cc[7],kk[7];for(int i=1;i<=m;i++) cc[i]=x;for(int i=22;i>=0;i--){bool flag=0;for(int j=1;j<=m;j++){for(int k=1;k<=m;k++)if(pos[k][f[cc[j]][i][k]]<=pos[k][y]) flag=1;} if(flag) continue;cnt+=1<<i;for(int i=0;i<6;i++) kk[i]=cc[i];for(int j=1;j<=m;j++)for(int k=1;k<=m;k++){int nxt=f[cc[k]][i][j];if(pos[j][nxt]<pos[j][kk[j]]) kk[j]=nxt;}for(int i=0;i<6;i++) cc[i]=kk[i];}cnt+=2;ans=min(ans,cnt);if(ans==N) printf("-1\n");else printf("%lld\n",ans);}}return 0;
}