tongtong2012 2026-6-17 22:01:12
我应该不会被TA们砍成臊子吧
骗你的其实还有很多，不过被系统吃了而已
我的赚损比≈1:3.7
陈终焉赚损比≈1:20.5
潘总大号极品赚损比≈1：77.1
潘总小号赚损比≈1：13.1
周cc赚损比≈1：7.0
其实cc的菜他自己就没收到几回，全是我代收的
赚损比≈1:8.9
这个老砂子也一样
司马只因锥 2026-6-10 15:51:52
本文去掉代码全文共 4800 字。
这篇博客并非完全意义上的题解，主要是对我学习这道题的思路回顾与总结，基于以下两篇题解融合和补充（所以记号不是我原创的，我觉得尤其是第二篇题解定义的名词非常形象易懂直接抄了），以及一些碎碎念。
写了很多细节问题，都是我在学习这个题时思考过的，所以这篇文章非常长。
两篇神犇的题解：
因为我是蒟蒻，我已经尽量在让这篇题解启发式了qwq，所以对于“显而易见的结论”讲述的废话可能很多，请巨佬们多多批评指教。
由于文章太长，写作周期也长，精修困难。如有不解请敲在讨论区，我若看到一定会尽力修正表述。
| 记号 | 含义 |
|---|---|
| 节点的子节点集 | |
| 节点的子树点集 | |
| 节点的父节点 | |
| 节点的子树点集大小 |
这部分会有两个复杂度的做法，但均为暴力及其优化，与正解关联不大。但能从中初步理解某些性质，个人感觉还是比较重要的。由于本人是蒟蒻，这个暴力对我来说也是个难点之一，本着彻底学透的想法，这部分也会很长，可选择跳过。
考虑一个非常劣的贪心：从下到上对每一层点按层分配数值，叶子结点是 ，其父节点是 ……不用我说也知道这东西没有分。
那么为什么是极劣的呢？我们发现在这个策略里每个点都对自身 有贡献，这使得大量节点没有对祖先进行贡献而被浪费，因此一个特殊点便十分显然：有一些点不对自己的 做贡献，而是留给祖先，这部分点我们称之为“垫脚石”。
垫脚石的严格定义：自身权值 严格大于自身 的点。
因此根据这些特殊点设计状态，设 为 子树根节点 为 ，子树内有 个垫脚石，即有 个点满足 。
两位神犇对于这一暴力是完全口胡的，然而蒟蒻如我连这个暴力都无法写好，因此也将讲解一下。
根节点需要决策自身，所以先不着急考虑根节点以及使用垫脚石。
设临时数组 表示当前合并的所有子树的 为，有 个垫脚石。
初始状态为空，，其余状态全部设置为极小值表示不可能。
合并的过程中，总 为各子树最大的 ，总垫脚石数为各子树垫脚石数之和。
本质上这是一个二维树形背包，容易写出合并转移方程。
注意用临时数组进行背包以隔离新旧状态，具体转移不再赘述，如有需要详见代码。
考虑根节点的转移。如果 不是垫脚石，显然应该枚举使用的垫脚石数量更新状态。
你可能会发现一个问题。如果 自己是垫脚石，那么它到底能不能使用垫脚石呢？
仔细回想垫脚石的定义，它是子树内权值严格大于子树 的点。如果 自己是垫脚石，在使用垫脚石之前它的 必然与各个子树最大的 相等。那根据垫脚石的定义，这部分垫脚石数不能使用的，否则将会违反定义！
难道先合并的做法是错的吗？
实则不然，不妨考虑违反定义意味着什么。
违反定义则意味着在最优解中这个垫脚石实际上在更早之前就应该被使用，这样权值才不会大于此时的 。那这种情况实际上已经在 不是垫脚石的情况里转移过了，因此这种可能是多余的，我们不需要写。
时间复杂度 ，期望得分 ，实际得分 ，和 一个分，常数小快到飞起。
#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=370;
const int MAXM=MAXN;
int T,n,m;
vector<int> a[MAXN];
int dp[MAXN][MAXN][MAXN],siz[MAXN],ans;
int tmp[MAXN][MAXN],dp_v[MAXN][MAXN];
inline void init(){
ans=0;
for(int i=1;i<=n;++i){
a[i].clear();
}
}
void dfs(int u){
for(int v:a[u]){//先递归以防全局数组数据污染
dfs(v);
}
siz[u]=0;//为了服务背包，siz在dfs内表示当前合并了多少个点，根节点的转移特殊所以放最后，siz自然初始为0
for(int i=0;i<=n;++i){//mex最大值是子树大小
for(int j=0;j<=n;++j){
dp_v[i][j]=dp[u][i][j]=INT32_MIN;
}
}
dp_v[0][0]=0;//空状态，无意义，转移用
for(int v:a[u]){//合并子树
for(int i=0;i<=siz[u]+siz[v];++i){
for(int j=0;j<=siz[u]+siz[v];++j){
tmp[i][j]=INT32_MIN;
}
}
for(int i0=0;i0<=siz[u];++i0){
for(int j0=0;j0<=siz[u];++j0){
if(dp_v[i0][j0]==INT32_MIN) continue;//初始状态不合法
for(int i1=0;i1<=siz[v];++i1){
for(int j1=0;j1<=siz[v];++j1){
if(dp[v][i1][j1]==INT32_MIN) continue;
int i2=max(i0,i1),j2=j0+j1;
tmp[i2][j2]=max(tmp[i2][j2],dp_v[i0][j0]+dp[v][i1][j1]);
}
}
}
}
siz[u]+=siz[v];
for(int i=0;i<=siz[u];++i){
for(int j=0;j<=siz[u];++j){
dp_v[i][j]=tmp[i][j];
}
}
}
for(int i=0;i<=siz[u];++i){//考虑根节点u
for(int j=0;j<=siz[u];++j){
if(dp_v[i][j]==INT32_MIN) continue;
dp[u][i][j+1]=max(dp[u][i][j+1],dp_v[i][j]+i);//选择u作为垫脚石
for(int dj=0;dj<=j;++dj){//消耗dj个垫脚石给自己抬升
int i1=i+dj+1,j1=j-dj;
if(i1<=siz[u]+2){
dp[u][i1][j1]=max(dp[u][i1][j1],dp_v[i][j]+i1);
}
}
}
}
++siz[u];//加入根节点
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
init();
for(int i=2;i<=n;++i){
int p;
cin>>p;
a[p].emplace_back(i);
}
dfs(1);
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
ans=max(ans,d
YIZHIYANG初来乍到 2026-6-7 12:03:39
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
int n, rt, tot;
int ch[N][2], sz[N], va[N];
unsigned ky[N], sd = 71236721;
unsigned rd() {
sd ^= sd << 13;
sd ^= sd >> 17;
sd ^= sd << 5;
return sd;
}
int nw(int v) {
++tot;
va[tot] = v;
sz[tot] = 1;
ky[tot] = rd();
return tot;
}
void pu(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
void sp(int u, int v, int &x, int &y) {
if (!u) {
x = y = 0;
return;
}
if (va[u] <= v) {
x = u;
sp(ch[u][1], v, ch[u][1], y);
pu(x);
} else {
y = u;
sp(ch[u][0], v, x, ch[u][0]);
pu(y);
}
}
int mg(int x, int y) {
if (!x || !y) return x + y;
if (ky[x] < ky[y]) {
ch[x][1] = mg(ch[x][1], y);
pu(x);
return x;
} else {
ch[y][0] = mg(x, ch[y][0]);
pu(y);
return y;
}
}
void ins(int v) {
int a, b;
sp(rt, v, a, b);
rt = mg(mg(a, nw(v)), b);
}
void del(int v) {
int a, b, c;
sp(rt, v, a, c);
sp(a, v - 1, a, b);
if (b) b = mg(ch[b][0], ch[b][1]);
rt = mg(mg(a, b), c);
}
int kth(int u, int k) {
while (1) {
int lz = sz[ch[u][0]];
if (k <= lz) u = ch[u][0];
else if (k == lz + 1) return va[u];
else {
k -= lz + 1;
u = ch[u][1];
}
}
}
int rk(int v) {
int a, b;
sp(rt, v - 1, a, b);
int an = sz[a] + 1;
rt = mg(a, b);
return an;
}
int pre(int v) {
int a, b;
sp(rt, v - 1, a, b);
int an = kth(a, sz[a]);
rt = mg(a, b);
return an;
}
int nxt(int v) {
int a, b;
sp(rt, v, a, b);
int an = kth(b, 1);
rt = mg(a, b);
return an;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
while (n--) {
int op, x;
cin >> op >> x;
if (op == 1) ins(x);
else if (op == 2) del(x);
else if (op == 3) cout << rk(x) << "\n";
else if (op == 4) cout << kth(rt, x) << "\n";
else if (op == 5) cout << pre(x) << "\n";
else cout << nxt(x) << "\n";
}
return 0;
}
// Problem: P3391 【模板】文艺平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3391
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// by 1zhio2
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
int n, m, rt, tot;
int ch[N][2], sz[N], va[N], ky[N], tg[N];
mt19937 rnd(71236721);
int nw(int v) {
++tot;
va[tot] = v;
sz[tot] = 1;
ky[tot] = rnd();
return tot;
}
void pu(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
void rv(int x) {
if (!x) return;
swap(ch[x][0], ch[x][1]);
tg[x] ^= 1;
}
void pd(int x) {
if (!tg[x]) return;
rv(ch[x][0]);
rv(ch[x][1]);
tg[x] = 0;
}
void sp(int u, int k, int &x, int &y) {
if (!u) {
x = y = 0;
return;
}
pd(u);
int lz = sz[ch[u][0]];
if (k <= lz) {
y = u;
sp(ch[u][0], k, x, ch[u][0]);
pu(y);
} else {
x = u;
sp(ch[u][1], k - lz - 1, ch[u][1], y);
pu(x);
}
}
int mg(int x, int y) {
if (!x || !y) return x + y;
if (ky[x] < ky[y]) {
pd(x);
ch[x][1] = mg(ch[x][1], y);
pu(x);
return x;
} else {
pd(y);
ch[y][0] = mg(x, ch[y][0]);
pu(y);
return y;
}
}
void dfs(int x) {
if (!x) return;
pd(x);
dfs(ch[x][0]);
cout << va[x] << " ";
dfs(ch[x][1]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) rt = mg(rt, nw(i));
while (m--) {
int l, r;
cin >> l >> r;
int a, b, c, d;
sp(rt, l - 1, a, b);
sp(b, r - l + 1, c, d);
rv(c);
rt = mg(a, mg(c, d));
}
dfs(rt);
return 0;
}
/*
题意：在 5*7 棋盘上进行 n 次横向移动，每次移动后模拟下落与连锁消除，求字典序最小通关方案。
思路：n<=5，直接 DFS。每步按 x、y、方向 1/-1 枚举；移动后反复执行下落和同时消除，并用颜色数量小于 3 的剪枝。
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
int a[5][7], an[6][3];
int mk[5][7];
void fal() {
for(int i=0;i<5;i++) {
int k=0;
for(int j=0;j<7;j++)
if(a[i][j]) a[i][k++]=a[i][j];
while(k<7) a[i][k++]=0;
}
}
bool del() {
memset(mk,0,sizeof(mk));
bool ok=0;
for(int i=0;i<5;i++) {
for(int j=0;j<7;j++) {
if(!a[i][j]) continue;
int c=a[i][j], k=i;
while(k<5&&a[k][j]==c) k++;
if(k-i>=3) {
ok=1;
for(int t=i;t<k;t++) mk[t][j]=1;
}
k=j;
while(k<7&&a[i][k]==c) k++;
if(k-j>=3) {
ok=1;
for(int t=j;t<k;t++) mk[i][t]=1;
}
}
}
if(!ok) return 0;
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(mk[i][j]) a[i][j]=0;
fal();
return 1;
}
void sim() {
fal();
while(del());
}
bool emp() {
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(a[i][j]) return 0;
return 1;
}
bool chk() {
int ct[15]={0};
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(a[i][j]) ct[a[i][j]]++;
for(int i=1;i<=10;i++)
if(ct[i]&&ct[i]<3) return 0;
return 1;
}
void mov(int x,int y,int g) {
int nx=x+g;
if(a[nx][y]) swap(a[x][y],a[nx][y]);
else {
a[nx][y]=a[x][y];
a[x][y]=0;
}
sim();
}
bool dfs(int d) {
if(d==n) return emp();
if(!chk()) return 0;
int b[5][7];
memcpy(b,a,sizeof(a));
for(int x=0;x<5;x++) {
for(int y=0;y<7;y++) {
if(!a[x][y]) continue;
for(int z=0;z<2;z++) {
int g=(z==0?1:-1);
int nx=x+g;
if(nx<0||nx>=5) continue;
if(g==-1&&a[nx][y]) continue;
an[d][0]=x;
an[d][1]=y;
an[d][2]=g;
mov(x,y,g);
if(dfs(d+1)) return 1;
memcpy(a,b,sizeof(a));
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<5;i++) {
int x,j=0;
while(cin>>x&&x) a[i][j++]=x;
}
if(dfs(0)) {
for(int i=0;i<n;i++)
cout<<an[i][0]<<" "<<an[i][1]<<" "<<an[i][2]<<"\n";
} else cout<<-1<<"\n";
return 0;
}
给定 头牛的身高 ，有 次询问。
每次询问给出区间 ，要求输出这个区间内最高牛和最低牛的身高差，也就是：
$$\max(h_l,h_{l+1},\dots,h_r)-\min(h_l,h_{l+1},\dots,h_r) $$样例中身高序列为：
1 7 3 4 2 5
第一次询问 ，区间内的身高为：
1 7 3 4 2
最高为 ，最低为 ，答案为 。
第二次询问 ，区间内的身高为：
4 2 5
最高为 ，最低为 ，答案为 。
第三次询问 ，区间内只有一头牛，最高和最低都是 ，答案为 。
这道题需要多次查询静态区间的最大值和最小值。
如果每次询问都从 扫到 ，一次询问最坏是 ，而 最大为 ，会超时。
这题可以用树状数组处理。
普通树状数组常用来维护前缀和，而这里我们不维护和，而是维护区间最大值和区间最小值。
设 表示 在树状数组中管辖区间的长度，那么节点 管辖的区间是：
例如：
i = 4, lowbit(4) = 4
节点 4 管辖 [1,4]
i = 6, lowbit(6) = 2
节点 6 管辖 [5,6]
i = 7, lowbit(7) = 1
节点 7 管辖 [7,7]
i = 8, lowbit(8) = 8
节点 8 管辖 [1,8]
因此我们可以让：
建树时，把每个位置 的身高加入所有包含它的树状数组节点中。
查询 时，从右端点 开始向左拆区间。
如果当前节点 管辖的整段区间：
完全在 内，就可以直接使用 和 ，然后跳过这一整段。
如果这段区间越过了左边界 ，就不能整段使用，只能单独处理当前位置 ，然后令 减 。
这样就能把一个询问区间拆成若干个树状数组已经维护好的区间，再合并最大值和最小值。
以询问 为例：
[1,5] 可以拆成 [5,5] 和 [1,4]
其中：
节点 5 管辖 [5,5]
节点 4 管辖 [1,4]
所以只需要用这两个节点的信息，就能得到整个区间的最大值和最小值。
这道题没有修改操作，所有身高一开始就确定，所以用树状数组维护静态区间最值是可以的。
#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
const int INF = 1e9;
int n, q;
int a[N], mx[N], mn[N];
int lb(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= n; i += lb(i)) {
mx[i] = max(mx[i], v);
mn[i] = min(mn[i], v);
}
}
int gmx(int l, int r) {
int res = 0;
while (r >= l) {
if (r - lb(r) + 1 >= l) {
res = max(res, mx[r]);
r -= lb(r);
} else {
res = max(res, a[r]);
r--;
}
}
return res;
}
int gmn(int l, int r) {
int res = INF;
while (r >= l) {
if (r - lb(r) + 1 >= l) {
res = min(res, mn[r]);
r -= lb(r);
} else {
res = min(res, a[r]);
r--;
}
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) mn[i] = INF;
for (int i = 1; i <= n; i++) {
cin >> a[i];
add(i, a[i]);
}
while (q--) {
int l, r;
cin >> l >> r;
cout << gmx(l, r) - gmn(l, r) << '\n';
}
return 0;
}
建树时，每个位置会更新 个树状数组节点，所以预处理复杂度为 。
每次询问时，从右端点向左拆成若干个树状数组区间，复杂度为 。
因此总时间复杂度为：
空间复杂度为：
YIZHIYANG初来乍到 2026-5-24 15:09:29
给定一棵 个节点的有根树（根为 1）。每个节点 初始有 个不同的糖果。 有 只松鼠，第 只松鼠需要从以 为根的子树中挑选 个糖果。不同松鼠不能选同一个糖果，不同松鼠选到相同的糖果组合视为不同的分配方案。 求所有满足要求的分配方案数，对 998244353 取模。 输入包含树的边、每个节点的 和 。数据范围：，，。 保留样例 1 进行说明：5 个节点，结构为 1 连 2 和 3，3 连 4 和 5。各节点的 为 1, 2, 1, 2, 3， 为 1, 1, 3, 1, 1。输出为 144。
在样例 1 中，节点 2、4、5 是叶子节点，它们上面的松鼠只能在自身节点拿糖果。 节点 2 有 2 个糖果，需拿 1 个，方案数为 。 节点 4 有 2 个糖果，需拿 1 个，方案数为 。 节点 5 有 3 个糖果，需拿 1 个，方案数为 。 节点 3 的子树包含节点 3、4、5，共有 个糖果。节点 4 和 5 的松鼠各自拿走了 1 个，还剩下 个糖果。松鼠 3 需要拿 3 个，方案数为 。 节点 1 的子树包含整棵树，共有 9 个糖果。其他松鼠共计拿走 6 个，留给松鼠 1 的剩余糖果为 个。松鼠 1 需要拿 1 个，方案数为 。 根据乘法原理，总方案数为 。
题目要求各个松鼠在自己的子树内选糖果，且糖果各不相同。由于子树内的糖果对于子树根节点及以上的祖先节点是完全等价的，可以采用自底向上的方式计算方案数。 优先满足深度较大的节点需求。对于节点 的松鼠，它需要从 的子树中选出 个糖果。当处理到 时，它所有的真后代（子树中除 外的节点）已经从这片区域中预定了它们需要的糖果。 设 的子树中初始总糖果数为 ，而 的所有真后代总共需要拿走 个糖果。真后代的选取限制在它们各自的子树内，只要数量足够，它们挑走特定的 个糖果后，剩下的 个糖果对于松鼠 而言没有任何限制，可以任选。 对每个节点 ，当前可用的糖果总数即为 。松鼠 的局部方案数就是 。遍历整棵树时，如果出现子树总糖果数小于总需求数（即 ），直接输出 0 并结束程序；否则将所有节点的局部方案数相乘即可。 组合数计算需要特别处理。 的累加值可能达到 ，而取模的质数 大于 。根据卢卡斯定理，$\binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \times \binom{n/p}{m/p} \pmod p$。因为 ，所以 ，右侧第二项 。公式直接退化为计算 。将可用糖果数量对 取模，若取模后数值小于 则返回 0，否则在 时间内通过展开分子分母计算组合数。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MX = 200005;
vector<int> adj[MX];
ll c[MX], d[MX], sc[MX], sd[MX];
ll ans = 1;
ll qpw(ll a, ll b) {
ll r = 1;
while (b) {
if (b & 1) r = r * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return r;
}
ll inv(ll a) {
return qpw(a, MOD - 2);
}
ll get(ll n, ll k) {
n %= MOD;
if (n < k) return 0;
ll num = 1, den = 1;
for (ll i = 0; i < k; i++) {
num = num * (n - i) % MOD;
den = den * (i + 1) % MOD;
}
return num * inv(den) % MOD;
}
void dfs(int u) {
sc[u] = c[u];
sd[u] = d[u];
for (int v : adj[u]) {
dfs(v);
sc[u] += sc[v];
sd[u] += sd[v];
}
if (sc[u] < sd[u]) {
cout << 0 << "\n";
exit(0);
}
ll rem = sc[u] - sd[u] + d[u];
ans = ans * get(rem, d[u]) % MOD;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
adj[p].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> d[i];
dfs(1);
cout << ans << "\n";
return 0;
}
时间复杂度：树的后序遍历需要 时间。节点 的组合数计算需要 时间，整棵树累计计算次数为 。整体时间复杂度为 。 空间复杂度：使用邻接表存储树的边，维护每个节点的糖果信息，空间复杂度为 。
YIZHIYANG初来乍到 2026-5-24 13:10:59
| 序号 | 题号 | 题目名称 | 标签 | 难度 |
|---|---|---|---|---|
| 1 | B3941 | [GESP样题 五级] 小杨的锻炼 | 数论 最大公约数 gcd |
普及− |
| 2 | B3951 | [GESP样题 五级] 小杨的队列 | 排序 | |
| 3 | B3871 | [GESP202309 五级] 因数分解 | 数论 | |
| 4 | B3968 | [GESP202403 五级] 成绩排序 | 模拟 排序 结构体 |
|
| 5 | B3969 | [GESP202403 五级] B-smooth 数 | 素数判断 质数 筛法 |
|
| 6 | P10720 | [GESP202406 五级] 小杨的幸运数字 | 数论 | |
| 7 | B4051 | [GESP202409 五级] 小杨的武器 | 贪心 | |
| 8 | P13014 | [GESP202506 五级] 最大公因数 | 数学 | |
| 9 | P14073 | [GESP202509 五级] 数字选取 | 数学 贪心 数论 枚举 素数判断 质数 筛法 |
|
| 10 | P15798 | [GESP202603 五级] 有限不循环小数 | 数论 | |
| 11 | P15799 | [GESP202603 五级] 找数 | 二分 离散化 队列 双指针 two-pointer bitset 哈希表 STL |
|
| 12 | B3872 | [GESP202309 五级] 巧夺大奖 | 贪心 | 普及/提高− |
| 13 | B3929 | [GESP202312 五级] 小杨的幸运数 | 二分 筛法 |
|
| 14 | B3930 | [GESP202312 五级] 烹饪问题 | 贪心 位运算 |
|
| 15 | P10719 | [GESP202406 五级] 黑白格 | 数学 二分 前缀和 |
|
| 16 | B4050 | [GESP202409 五级] 挑战怪物 | 贪心 数论 枚举 |
|
| 17 | B4070 | [GESP202412 五级] 奇妙数字 | 数学 数论 |
|
| 18 | B4071 | [GESP202412 五级] 武器强化 | 贪心 线性数据结构 枚举 排序 数组 |
|
| 19 | P11960 | [GESP202503 五级] 平均分配 | 贪心 排序 |
|
| 20 | P13013 | [GESP202506 五级] 奖品兑换 | 二分 整数规划 |
|
| 21 | P14074 | [GESP202509 五级] 有趣的数字和 | 数学 分治 记忆化搜索 数位 DP 进制 组合数学 前缀和 位运算 |
|
| 22 | P14917 | [GESP202512 五级] 数字移动 | 二分 | |
| 23 | P14918 | [GESP202512 五级] 相等序列 | 贪心 数论 素数判断 质数 筛法 |
|
| 24 | P11961 | [GESP202503 五级] 原根判断 | 原根 数论 |
提高+/省选− |
YIZHIYANG初来乍到 2026-5-24 11:12:13
给定一张 个点、 条边的无向连通图，点 1 代表家。需要挑选 4 个互不相同的景点，依次记为 A、B、C、D。要求在 的 5 段行程中，每段行程经过的最短边数不能超过 。每个景点都有一个固定的分数，求 A、B、C、D 四个景点的分数之和的最大值。 输入包含三个整数 ，各个景点的分数，以及连边的具体信息。其中 ，。
输入样例： 8 8 1 9 7 1 8 2 3 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1
以点 1 为家，每段行程转车不超过 1 次，也就是单次最多跨越 2 条边。 从图的连通情况看，距离点 1 步数在 2 以内的候选点有 2、3、8、7。 如果依次挑选 2、3、5、7 作为行程节点，各段相邻点的图上最短距离均不超过 2，且节点互不相同。它们的分数分别是 9、7、8、3，求和得到 27。穷举验证可知无法找到总分更高的合法组合。
看到 这个条件。如果老老实实写四重循环去枚举 A、B、C、D，时间复杂度高达 ，哪怕剪枝再精细也会超时。要稳过这道题，必须把枚举压到两层循环，也就是 的级别。
要把 4 个变量的枚举变成 2 个，突破口在路径的结构上。 我们要走的路径是 。它是一个首尾相接的对称环。如果在中间切一刀，把 和 当作桥墩确定下来，整个过程就被劈成了左半边 和右半边 。 一旦 被外层循环固定，给它找前驱 的任务只和 与 1 有关；一旦 固定，找后继 的任务只和 与 1 有关。这两半是解耦的，把它们拆开分别处理，这就是折半枚举的核心动机。
于是思路变成了：双重循环枚举 和 。对于每一个可能作为桥墩的节点，提前帮它把所有能作为 或者 的候选点找出来。 为了让总分最大，预处理时可以直接挑分数最大的那个候选点吗？ 题目规定 4 个点必须互不相同，直接贪心选最大的容易翻车。假设预处理时只给每个点记录了分数第一的候选点，当外层循环枚举到具体的 和 时，万一 记录的那个最强 恰好就是 ，或者恰好和 撞了位置，唯一的备选就失效了，这条路直接作废。
算一下具体的排斥情况：给 找 的时候， 需要避让的“竞争者”最多只有三个，分别是当前的 、当前的 、以及 选出来的 。 在最极端的冲突下，分数第一大的备选被 占了，第二大的备选被 占了，那么第三大的备选就一定是个自由身。也就是说，在预处理阶段，只要把满足连通条件的备选点按分数从大到小排个序，只存前 3 个，就足以应付所有位置重合的极端情况。 通过维护前 3 大这个常数级的操作，既完美避开了去重的雷区，又不需要增加多余的循环层数，将复杂度彻底锁在了 。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k;
ll val[2505];
vector<int> g[2505];
int ok[2505][2505];
int dis[2505];
int bst[2505][5];
void bfs(int s) {
for (int i = 1; i <= n; ++i) {
dis[i] = -1;
}
dis[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
if (dis[u] == k + 1) continue;
for (int v : g[u]) {
if (dis[v] == -1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
for (int i = 1; i <= n; ++i) {
if (dis[i] != -1 && dis[i] <= k + 1) {
ok[s][i] = 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for (int i = 2; i <= n; ++i) {
cin >> val[i];
}
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
bfs(i);
}
for (int i = 2; i <= n; ++i) {
vector<int> tmp;
for (int j = 2; j <= n; ++j) {
if (i != j && ok[1][j] && ok[j][i]) {
tmp.push_back(j);
}
}
sort(tmp.begin(), tmp.end(), [&](int x, int y) {
return val[x] > val[y];
});
int sz = tmp.size();
for (int j = 0; j < 3 && j < sz; ++j) {
bst[i][j] = tmp[j];
}
}
ll ans = 0;
for (int i = 2; i <= n; ++i) {
for (int j = 2; j <= n; ++j) {
if (i == j || !ok[i][j]) continue;
for (int x = 0; x < 3; ++x) {
int a = bst[i][x];
if (!a || a == j) continue;
for (int y = 0; y < 3; ++y) {
int d = bst[j][y];
if (!d || d == i || d == a) continue;
ans = max(ans, val[a] + val[i] + val[j] + val[d]);
}
}
}
}
cout << ans << '\n';
return 0;
}
时间复杂度：单次广度优先搜索求全源短路耗时 ，执行 次耗时 。对于每个节点寻找备选集合并排序，单次耗时 ，整理所有节点耗时 。核心的两重循环加内层最多 9 次的组合检测耗时 。综合时间复杂度为 。 空间复杂度：存储全图连通关系的二维矩阵占用 。邻接表占用 ，备选数组占用常数倍的 。整体空间复杂度为 。
[https://www.luogu.com.cn/problem/P8817](https://www.luogu.com.cn/probl
YIZHIYANG初来乍到 2026-5-20 22:10:27
给出 个相对位置固定的非负整数，要求在这些数字之间填入 个乘号和 个加号。你可以通过任意添加括号来改变运算顺序，目标是找到一种运算安排，使得最终计算出的表达式结果最大。 数据保证 ，，给定数字都在 到 之间，最终答案小于 。
1 2 3 4 5，共有 2 个乘号。对于给出的 个数字，我们需要插入 个运算符，其中规定包含 个乘号，剩余 个自然是加号。如果要让整体结果最大，一种直观的策略是让加法服务于乘法。也就是说，把加号放在数值较小的数字之间，先让它们通过加法累积出一个相对可观的基数，然后再用乘号将大块的值相乘。
将 1、2、3 分在一个括号内进行加法，得到 。此时还剩下数字 4 和 5，以及分配好的 个乘号。由于符号数量刚好，余下的部分只能是连乘，最终算式变为 ，计算结果为 。这个顺序比优先乘小数字带来的增益大得多。
任意添加括号来安排运算优先级，实质上是构建一棵表达式树。在这棵树中，每个节点代表一次加法或乘法运算，而它管辖的左右子树对应着原序列中连续的两段数字区间。既然每一段连续区间最终都会合并成一个值，我们就可以把大问题拆解成若干个相邻小区间的合并问题。
题目中的数字都是非负数，且运算符仅有加和乘。在这种情况下，无论外层执行加法还是乘法，最终结果都会随着内部子区间计算结果的增大而单调递增。因此，要求整个式子的最大值，只需求出它左右两部分子式的最大值即可。局部最优能够推导出全局最优，这满足动态规划的最优子结构。
定义状态 dp[l][r][p] 表示在区间 内，准确使用 p 个乘号所能获得的最大结果。
当区间长度大于 时，枚举一个分割点 将当前区间分为 和 。假设左半部分分配了 c 个乘号，那么两部分合并的运算方式有两种可能：
若两段区间由加号连接，那么右半部分需要使用 p - c 个乘号，此时结果为左右部分最大值之和。
若两段区间由乘号连接，那么连接本身消耗了一个乘号，右半部分就只能使用 p - 1 - c 个乘号，此时结果为左右部分最大值的乘积。
在具体实现中，按照区间长度从小到大进行递推。对于长度为 的单个数字，不需要任何运算符，它的最大值就是原数字本身。将所有状态初始化为 来标记无效状态，遇到无效状态直接跳过即可。最后 dp[1][n][k] 即是题解。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[20][20][20];
ll a[20];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
for (int p = 0; p < 20; p++) {
dp[i][j][p] = -1;
}
}
}
for (int i = 1; i <= n; i++) {
dp[i][i][0] = a[i];
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
for (int m = l; m < r; m++) {
for (int p = 0; p <= k && p <= r - l; p++) {
for (int c = 0; c <= p; c++) {
if (dp[l][m][c] != -1 && dp[m + 1][r][p - c] != -1) {
dp[l][r][p] = max(dp[l][r][p], dp[l][m][c] + dp[m + 1][r][p - c]);
}
}
if (p > 0) {
for (int c = 0; c <= p - 1; c++) {
if (dp[l][m][c] != -1 && dp[m + 1][r][p - 1 - c] != -1) {
dp[l][r][p] = max(dp[l][r][p], dp[l][m][c] * dp[m + 1][r][p - 1 - c]);
}
}
}
}
}
}
}
cout << dp[1][n][k] << "\n";
return 0;
}
时间复杂度：状态定义包含区间左端点、右端点和乘号数量三个维度，枚举状态需 。对于每个状态，需要枚举分割点和左区间分配的乘号数，这部分消耗 。综合起来时间复杂度为 。在 的数据范围内，计算次数极少，运行非常高效。 空间复杂度：构建了一个大小固定的三维数组存储中间状态，空间开销为 。
YIZHIYANG初来乍到 2026-5-19 21:24:49
给定 个完全相同的乒乓球和 个不同的盒子。第 个盒子最多只能放入 个乒乓球。求将这 个球全部分配到 个盒子中的合法方案数。由于结果可能很大，输出方案数对 1000000007 取模的结果。 假设本题的数据范围为 ，。输入的第一行为 和 ，第二行为 个整数 。输出一个整数表示取模后的方案数。
输入： 2 3 2 2
输出： 2
解释： 一共有 2 个盒子和 3 个乒乓球。第 1 个盒子最多放 2 个球，第 2 个盒子最多放 2 个球。 合法的分配方案有以下两种：
这是一个求非负整数解个数的问题，需要求满足 且 的解的数量。
可以通过动态规划来求解。定义状态 表示将 个球分配到前 个盒子中的方案数。 对于第 个盒子，我们枚举它放入的球数 ，其中 需要满足 且 。 状态转移方程为：
按照这个方程直接计算，每次转移需要遍历 ，在 的情况下总计算量会达到 ，效率不足。需要对转移过程进行优化。
将上述方程展开观察，求 相当于求上一层状态 中一段连续区间的和。我们写出相邻状态 的表达式：
$$f_{i, j-1} = \sum_{k=0}^{\min(j-1, a_i)} f_{i-1, j-1-k} $$将 和 相减，抵消掉公共部分后得到：
$$f_{i, j} - f_{i, j-1} = f_{i-1, j} - f_{i-1, j-a_i-1} $$移项后即可得到优化后的状态转移方程：
$$f_{i, j} = f_{i, j-1} + f_{i-1, j} - f_{i-1, j-a_i-1} $$当 时，不存在越界项，方程简化为 。 通过这个转化，我们将每次转移的时间复杂度从 降到了 。在计算过程中，注意处理取模操作中的负数情况，确保结果在 范围内。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int a[2005];
ll f[2005][2005];
ll md = 1000000007;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
f[0][0] = 1;
for(int i = 1; i <= n; ++i) {
f[i][0] = f[i-1][0];
for(int j = 1; j <= m; ++j) {
f[i][j] = (f[i][j-1] + f[i-1][j]) % md;
if(j > a[i]) {
f[i][j] = (f[i][j] - f[i-1][j - a[i] - 1] + md) % md;
}
}
}
cout << f[n][m] << "\n";
return 0;
}
时间复杂度：状态总数为 ，经过前缀和差分优化后，每次状态转移的时间为 ，总时间复杂度为 。 空间复杂度：使用了一个二维数组记录所有的动态规划状态，空间复杂度为 。
YIZHIYANG初来乍到 2026-5-18 22:14:41
给定 个队员的实力值，需要将他们分成若干个小组。要求每个小组内的实力值必须是连续的整数，且同一个组内不能出现相同的实力值。每个队员都必须恰好分入一个小组。求在所有合法的分组方案中，人数最少的小组人数的最大值。
输入第一行是一个正整数 ；第二行包含 个整数，代表队员的实力值。 数据范围：，实力值的绝对值不超过 。
输入：
7
4 5 2 3 -4 -3 -5
输出：
3
解释：可以将这 7 个数字分成两组：[-5, -4, -3] 和 [2, 3, 4, 5]。两组内部都是连续且不重复的整数。两组的人数分别为 3 和 4，其中人数较少的是 3。没有更优的分法能让最少人数大于 3。
拿到样例中的 7 个数字：4 5 2 3 -4 -3 -5。
如果把它们从小到大排个序，序列就变成了：-5, -4, -3, 2, 3, 4, 5。
顺着这个顺序看：
前面的 -5, -4, -3 是连在一起的，它们可以刚好组成一组，长度是 3。
接下来的 2 和前面断开了，它只能自己新开一组。后面的 3, 4, 5 可以顺次接在 2 后面，组成 [2, 3, 4, 5] 这一组，长度是 4。
此时所有的数字都分配完毕，一共分成了两组，人数较少的那一组人数就是 3。
要让每个分组的实力值连续且不重复，处理这种具有连续性要求的问题时，将数据从小到大排序是一个自然的切入点。排序后，相近的、连续的数字就会排在一起。
排好序后可以按顺序处理每一个数字。对于当前的数字 ，有两种选择：把它接到某一个现有的、以 结尾的小组后面；或者让它作为开头，自己新成立一个小组。
为了让最终“人数最少的小组人数最大”，在有多个现有小组都以 结尾时，应该优先把 接到当前人数最少的那一组后面。这是因为短板决定了最终的答案，把新数字分配给当前最短的小组，能最有效地拉长这个短板。如果没有以 结尾的小组，说明现有的组都无法容纳 ，此时 只能自己新开一组，初始人数为 1。
为了高效地实现这个挑选过程，需要记录每一个小组的结尾数值以及该小组的当前人数。可以使用一个映射，它的键是小组的结尾数值，对应的值是一个最小堆（优先队列）。最小堆里存放所有以该数值结尾的小组的人数。这样每次处理数字 时，只需看 对应的最小堆是否为空：
把所有数字处理完后，遍历整个结构，找出所有现存小组人数的最小值即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100005];
map<int, priority_queue<int, vector<int>, greater<int>>> mp;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
int x = a[i];
if (mp[x - 1].empty()) {
mp[x].push(1);
} else {
int len = mp[x - 1].top();
mp[x - 1].pop();
mp[x].push(len + 1);
}
}
int ans = 2e9;
for (auto &p : mp) {
if (!p.second.empty()) {
ans = min(ans, p.second.top());
}
}
cout << ans << "\n";
return 0;
}
给定长度为 的序列 ，有 次询问，每次给出 ，要求统计 在区间 中出现了多少次。
对每个数值 ，记录它在序列中出现的所有下标，并保持升序。
对于询问 ，只需要在 的下标数组中二分：
也就是：
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int n, q;
inline void solve() {
cin >> n;
map<int, vector<int> > mp;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
mp[x].push_back(i);
}
cin >> q;
while (q--) {
int l, r, x;
cin >> l >> r >> x;
if (!mp.count(x)) {
printf("0\n");
continue;
}
vector<int> &v = mp[x];
int Ans = upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
printf("%d\n", Ans);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1; cin >> _;
while (_--) solve();
return 0;
}
给定一棵 个点的树，部分城市有传送门。任意两个传送门城市之间可以花费 时间互相传送。每次询问从 到 的最短时间。
从 到 有两种方案：
其中 表示点 到最近传送门的树上距离。
所以答案为：
树上距离用 求，最近传送门距离用多源 求。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, inf = 1e9 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int n, k, q;
vector<int> G[N];
int dep[N], fa[20][N];
int dis[N];
void bfs_dep() {
queue<int> que;
que.push(1);
dep[1] = 1;
fa[0][1] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : G[u]) {
if (v == fa[0][u]) continue;
fa[0][v] = u;
dep[v] = dep[u] + 1;
que.push(v);
}
}
for (int j = 1; j < 20; j++) {
for (int i = 1; i <= n; i++) {
fa[j][i] = fa[j - 1][fa[j - 1][i]];
}
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int j = 19; j >= 0; j--) {
if ((d >> j) & 1) x = fa[j][x];
}
if (x == y) return x;
for (int j = 19; j >= 0; j--) {
if (fa[j][x] != fa[j][y]) {
x = fa[j][x];
y = fa[j][y];
}
}
return fa[0][x];
}
int dist(int x, int y) {
int z = lca(x, y);
return dep[x] + dep[y] - 2 * dep[z];
}
inline void solve() {
cin >> n >> k >> q;
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
bfs_dep();
queue<int> que;
for (int i = 1; i <= n; i++) dis[i] = inf;
for (int i = 1, x; i <= k; i++) {
cin >> x;
dis[x] = 0;
que.push(x);
}
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : G[u]) {
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
que.push(v);
}
}
}
while (q--) {
int u, v;
cin >> u >> v;
int Ans = dist(u
给定一个 的邻接矩阵，表示 个迷宫之间是否可以直接到达。对于指定迷宫 ，要求输出：
注意每个迷宫都可以直接到达自己。
邻接矩阵中：
所以直接统计第 行和第 列中 的个数即可。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int n, m;
int a[N][N];
inline void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
int out = 0, in = 0;
for (int j = 1; j <= n; j++) if (a[m][j]) out++;
for (int i = 1; i <= n; i++) if (a[i][m]) in++;
printf("%d %d %d\n", out, in, out + in);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
while (_--) solve();
return 0;
}
给定一个有向无环图，每个点有一个点权 。对于图中的任意一条路径，可以得到路径上的点权序列。要求在所有路径中，求最长不下降子序列的最大长度。点权满足 。
因为图是 ，可以拓扑排序。
由于点权只有 ，可以对每个点维护一个数组：
表示走到点 时，已经得到的最长不下降子序列中，最后一个被选中的值为 的最大长度。
处理点 时，可以选择把 加入子序列。若 ，则可以从所有 的状态转移过来：
然后把 的状态沿有向边传播给后继点。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int n, m;
int a[N], deg[N];
int dp[N][11];
vector<int> g[N];
inline void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
deg[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (!deg[i]) q.push(i);
}
int Ans = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
int w = a[u], best = 0;
for (int v = 1; v <= w; v++) best = max(best, dp[u][v]);
dp[u][w] = max(dp[u][w], best + 1);
for (int v = 1; v <= 10; v++) Ans = max(Ans, dp[u][v]);
for (int to : g[u]) {
for (int v = 1; v <= 10; v++) {
dp[to][v] = max(dp[to][v], dp[u][v]);
}
deg[to]--;
if (!deg[to]) q.push(to);
}
}
printf("%d\n", Ans);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
while (_--) solve();
return 0;
}
有 种商品，每种商品有价值 。若某个商人支持用商品 换商品 ，则你可以从 变成 。交换时还要支付：
其中 是手续费。现在你初始拥有商品 ，希望得到商品 ，求最少花费；若无法得到，输出 。
一条路径：
总费用为：
$$(v_{p_1}-v_a+1)+(v_{p_2}-v_{p_1}+1)+\cdots+(v_b-v_{last}+1) $$中间价值会全部抵消，得到：
因此只需要求从 到 的最少边数。
用 求最短路边数即可。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int n, m, a, b;
一共有 个台阶，每一步可以走 个、 个或 个台阶。求走完 个台阶共有多少种不同方案。
设 表示走到第 个台阶的方案数。
最后一步可能来自：
因此：
初始化：
表示一个台阶都不走有 种方案。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
LL f[N];
int n;
inline void solve() {
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i++) {
if (i - 1 >= 0) f[i] += f[i - 1];
if (i - 2 >= 0) f[i] += f[i - 2];
if (i - 3 >= 0) f[i] += f[i - 3];
}
printf("%lld\n", f[n]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
while (_--) solve();
return 0;
}
给定一个数字串 和正整数 ，统计 的所有连续子串中，有多少个子串对应的整数是 的倍数。子串允许有前导零，相同内容但位置不同的子串算不同子串。
设 表示当前处理到某个位置之前，所有 以当前位置前一位结尾 的子串中，模 余数为 的个数。
读入新数字 后：
每处理一位，就把当前余数为 的子串数量加入答案。
因为 ，所以每个字符枚举所有余数即可。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int p;
string s;
LL cnt[N], tmp[N];
inline void solve() {
cin >> p >> s;
LL Ans = 0;
for (char ch : s) {
int d = ch - '0';
for (int i = 0; i < p; i++) tmp[i] = 0;
tmp[d % p]++;
for (int r = 0; r < p; r++) {
int nr = (r * 10 + d) % p;
tmp[nr] += cnt[r];
}
Ans += tmp[0];
for (int i = 0; i < p; i++) cnt[i] = tmp[i];
}
printf("%lld\n", Ans);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
while (_--) solve();
return 0;
}
有 种饮料，每种饮料最多买一瓶。第 种饮料价格为 ，容量为 。小杨希望购买的总容量不低于 ，并且花费最少。如果无法满足要求，输出 。
这是一个 背包问题。
设 表示买到总容量为 时的最小花费。因为只关心是否达到 ，所以容量超过 的都压缩成 。
对于每瓶饮料，倒序更新：
$$dp_{\min(L,j+l_i)}=\min(dp_{\min(L,j+l_i)},dp_j+c_i) $$最后如果 仍然是无穷大，说明无解。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
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 - '0'; ch = getchar();}
return x * f;
}
int n, L;
LL dp[N];
inline void solve() {
cin >> n >> L;
for (int i = 0; i <= L; i++) dp[i] = inf;
dp[0] = 0;
for (int i = 1; i <= n; i++) {
LL c, l; cin >> c >> l;
for (int j = L; j >= 0; j--) {
if (dp[j] == inf) continue;
int nj = min((LL)L, j + l);
dp[nj] = min(dp[nj], dp[j] + c);
}
}
if (dp[L] == inf) printf("no solution\n");
else printf("%lld\n", dp[L]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
while (_--) solve();
return 0;
}
有 名同学，学号为 到 。他们按给定顺序进入教室。每位同学进入时，会和已经在教室内且学号小于自己的同学握手。求总握手次数。