✏️ 复习规划说明
因为 08.28 之后会有两天多的假期时间，因此特意制定此复习表，本贴用于存放之前做过的题目的讲解，以规划今后的复习：
📌 题目清单
考虑到计划的界面不太直观，这项内容放在帖子里。
本 oj 题目
任务题目
1729, 3418, 9040, 1617, 1768, 10492, 7244, 9310, 10344, 10343, 9306, 10123, 9301, 7177, 10449, 9476, 10543 .
比赛题目
10442, 10398, 10312, 10399, 10313, 10418, 10417, 9697, 9699, 9649, 9650, 9891, 10387, 10388, 9505, 10141, 10228, 10229, 10230, 10142, 10100, 9822, 10101, 9973, 9410, 1536, 1868, 9165, 10554
这些题目后期回放一些讲解，以供复习。
规划在 08.31 内写完。
🧩 题目讲解
2026.08.27 复习内容
任务题目
gmoj/1729
思路 ：先按边权从大到小排序，再遍历，如果连接这条边不会使得敌人连接，则连接，否则拆除。
#include <iostream>
using namespace std;
int n;
struct edge
{
int u,v,w;
//起终点, 边权
}e[55];
bool cmp(edge a,edge b) { return a.w>b.w; }
void qs(int st,int ed)
{
if(st>=ed)
{
return ;
}
edge mid=e[(st+ed)>>1];
int lf=st,rt=ed;
while(lf<=rt)
{
while(cmp(e[lf],mid)) lf++;
while(cmp(mid,e[rt])) rt--;
if(lf<=rt)
{
swap(e[lf],e[rt]);
lf++,rt--;
}
}
qs(st,rt);
qs(lf,ed);
}
int fa[55];
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void merge(int x,int y)
{
fa[find(x)]=find(y);
}
int p[55],pcnt=0;
int ans=0;
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
cin>>e[i].u>>e[i].v>>e[i].w;
e[i].u++,e[i].v++;
fa[i]=i;
}
fa[n]=n;
qs(1,n-1);
while(cin>>p[++pcnt]) { p[pcnt]++; }
pcnt--;
for(int i=1;i<n;i++)
{
if(find(e[i].u)==find(e[i].v))
{
continue;
}
bool hu=false,hv=false;
for(int j=1;j<=pcnt;j++)
{
if(find(p[j])==find(e[i].u))
{
hu=true;
break;
}
}
for(int j=1;j<=pcnt;j++)
{
if(find(p[j])==find(e[i].v))
{
hv=true;
break;
}
}
if(hu&&hv)
{
ans+=e[i].w;
}
else
{
merge(e[i].u,e[i].v);
}
}
cout<<ans;
return 0;
}gmoj/3418
对于任何 dp，都有一种方法：
- 设状态
- 看操作
- 寻上一步
- 找联系
可以记成“设, 看, 寻, 找”。
那我们可以根据这四步来解这道题：
- 设状态
树形 dp 里，一般第一维是当前点的编号，那我们可以就可以先设之。
题目中说过：选择的课程个数必须为 n，那么我们就将这个因素设为状态的第二维。
那么 dp[ i ][ j ]的意思就是：当前课程为根节点 i ，子树选择了 j 门课程的最大学分。 - 看操作
题目中既然说了要选择课程，那么操作就是“选”或“不选”了。
但是因为我们设定的状态是“选几个”，所以我们在进行计算的时候，操作应该是“选几个”地去选。 - 寻上一步
树形 dp 里，上一步的状态经常是子节点，这道题也不例外。 - 找联系
因为树形 dp 中当前节点的子树与子节点的子树重叠，子节点的子树选了 x 个，那么当前的这棵树一定包括这 x 个。所以当前节点选择了 y 个，子状态选了 x 个的话，它就可以分解为“当前选了 y-x 个”和“子节点选了 x 个”，这样这两个子状态加起来，就可以用来转移了。
于是这四步做完之后，剩下的也不怎么难了。
首先根据第四步，我们很简单就能列出：dp[u][y]=max(dp[u][y−x]+dp[v][x])
为了防止子树二次选择，我们遍历选择个数的时候需要倒序，因为如果是正序的话，在计算dp[u][y]的时候，dp[u][y−x]有可能会包括之前选择过的子树，反过来的话，dp[u][y−x]要么还没算过，要么就是上一个子树算出来的结果，所以不会重复。
还有输出选择课程的情况，我们在取dp[u][y]的时候，记录一下我们v和x，这样我们递归的时候，就能通过这两个数找到之前的子状态了。
因为我们还需要知道当前点还选择了哪些子树，所以dp[u][y−x]也要去递归。
#include <iostream>
using namespace std;
int dp[1005][1005],s[1005];
int mem1[1005][1005],mem2[1005][1005];
int h[1005],v[1005],nxt[1005],cnt;
void add(int U,int V)
{
cnt++;
v[cnt]=V;
nxt[cnt]=h[U];
h[U]=cnt;
}
int n,m,x;
void dfs(int u)
{
dp[u][1]=s[u];
for(int i=h[u];i;i=nxt[i])
{
dfs(v[i]);
for(int j=n;j>=1;j--)
{
for(int k=1;k<j;k++)
{
if(dp[u][j]<dp[u][j-k]+dp[v[i]][k])
{
dp[u][j]=dp[u][j-k]+dp[v[i]][k];
mem1[u][j]=v[i];
mem2[u][j]=k;
}
}
}
}
}
bool vis[105];
void dg(int x,int y)
{
vis[x]=true;
if(mem1[x][y]==0)
{
return ;
}
dg(mem1[x][y],mem2[x][y]);
dg(x,y-mem2[x][y]);
}
int main()
{
cin>>m>>n;
n++;
for(int i=1;i<=m;i++)
{
cin>>x>>s[i];
add(x,i);
}
dfs(0);
cout<<dp[0][n]<<'\n';
if(m<100)
{
dg(0,n);
for(int i=1;i<=m;i++)
{
if(vis[i])
{
cout<<i<<'\n';
}
}
}
return 0;
}这里我们可以借着“没有先修课就是 0”的特性，用 0 节点将每个课程的最先修的课程给串起来。
gmoj/9040
最长路径的两个端点如果不在同一条线上，那么这两个点一定是叶子节点，否则它的子节点到另一个点的路径会比当前节点还要长。
最长路径可以表示成 最底下的点 -> 转折点 -> 最底下的点 ，但是这两个点互为祖先的话，那又该如何判断呢？我们不看点，看边的话，发现如果是刚刚那种情况的话，只会有一段路径，反之则有两段。
如果是一段的话就说明转折点只有一个子树，为什么以及两段的情况自行思考。
所以路径可以写成：最高子树高度 + 次高字数高度。因为如果只有一个子树的话，那么后者将会是 0。
#include <iostream>
using namespace std;
int n;
int h[100005],v[200005],nxt[200005],cnt;
void add(int U,int V)
{
cnt++;
v[cnt]=V;
nxt[cnt]=h[U];
h[U]=cnt;
}
int dp[100005][2];
bool vis[100005];
void dfs(int u)
{
vis[u]=true;
int mx1=-1,mx2=-1;
for(int i=h[u];i;i=nxt[i])
{
if(vis[v[i]]) continue;
dfs(v[i]);
if(mx1<=dp[v[i]][0])
{
mx2=mx1,mx1=dp[v[i]][0];
}
else if(mx2<dp[v[i]][0])
{
mx2=dp[v[i]][0];
}
}
dp[u][0]=mx1+1;
dp[u][1]=mx2+1;
}
int ans;
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
dfs(1);
for(int i=1;i<=n;i++)
{
ans=max(ans,dp[i][0]+dp[i][1]);
}
cout<<ans;
return 0;
}dp[ i ][ 0 ]，dp[ i ][ 1 ]表示的是“ i 为转折点时的最高次高子树”，注意从子节点到当前节点的长度也要算进去。mx1 和 mx2 设为-1 是为了保证在没有子树的情况下 +1 后得到 0。
gmoj/1617
还记得前面说到的“四部曲”吗？
- 设状态
- 看操作
- 寻上一步
- 找联系
这道题同样可以用这四步解决。
- 设
题目很明显是一个状态 dp，于是我们设一维状态，紧接着是行，最后因为要求只能放置 k 个皇后，所以我们必须要再加一维表示放置皇后的数量。最后合在一起就是dp[i][j][k]，表示的是当第 i 行的状态为 j 时，一共放置了 k 个皇后的方案数。 - 看
也就是放不放置，这里的状态维度的 0 和 1 已经表示了。 - 寻
上一步就是上一行，“看”这个部分讲过了。 - 找
只需要看是否合法就行，对于当前行，两个棋子不能相邻，对于上下行，因为现在又多了四个角，所以上一行的每个棋子的左右两边都不能在下一行放置了，这个请自行思考。
#include <iostream>
using namespace std;
long long dp[10][(1<<9)][90];
long long cnt[(1<<9)+5];
long long g[(1<<9)+5],gcnt;
long long n,k;
int main()
{
cin>>n>>k;
for(long long i=0;i<(1<<n);i++)
{
cnt[i]=cnt[(i>>1)]+(i&1);
if(!((i>>1)&i))
{
g[++gcnt]=i;
dp[1][i][cnt[i]]=1;
}
}
for(long long i=2;i<=n;i++)
{
for(long long j=0;j<=k;j++)
{
for(long long q=1;q<=gcnt;q++) //dq
{
if(cnt[g[q]]>j) continue;
for(long long p=1;p<=gcnt;p++) //sh
{
if(g[p]&g[q]||((g[p]>>1)&g[q])||((g[p]<<1)&g[q]))
{
continue;
}
dp[i][g[q]][j]+=dp[i-1][g[p]][j-cnt[g[q]]];
}
}
}
}
long long ans=0;
for(long long i=1;i<=gcnt;i++)
{
ans+=dp[n][g[i]][k];
}
cout<<ans;
return 0;
}gmoj/1768
- 设
首先第一维是行，我们发现，这道题需要考虑到上一行和上上一行的情况，所以应该开两维，专门存储当前行和上一行的状态（因为转移的时候第 i 行只需要考虑 i-1 行状态中的两行） - 看
“选不选择”这个策略已经在状态中表示了。 - 寻
也就是看上一行状态中的上一行和上上一行，来得出当前行。 - 找
首先我们知道，对于当前一行以及前面两行，都不能上下相邻，所以我们为了加快代码运行的速度，可以先预处理出行内不相邻的状态，再利用这个状态算出两行上下不相邻的状态，这时候可以将这两行放在两个数组里。
这样的话，当前行就可以遍历行内不相邻的状态，前两行就可以遍历上下不相邻的情况了，最后只需要判断当前行和前两行重不重复即可。
因为题目问的是放置的数量，所以我们可以用到前一题写的 cnt 数组来快速获得 1 的数量。
#include <iostream>
using namespace std;
int n,m;
int g[65],gcnt;
int g1[3005],g2[3005],agcnt;
int cnt[1200],dp[105][1200][1200],d[105];
char c;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c;
d[i]<<=1;
if(c=='P')
{
d[i]|=1;
}
}
}
for(int i=0;i<(1<<m);i++)
{
cnt[i]=cnt[(i>>1)]+(i&1);
if((i&(i>>1))==0&&(i&(i>>2))==0)
{
g[++gcnt]=i;
dp[1][i][0]=cnt[i];
}
}
if(n==1)
{
int ans=0;
for(int i=1;i<=gcnt;i++)
{
ans=max(ans,dp[1][g[i]][0]);
}
cout<<ans;
return 0;
}
for(int i=1;i<=gcnt;i++)
{
for(int j=1;j<=gcnt;j++)
{
if((g[i]&g[j])==0)
{
g1[++agcnt]=g[i],g2[agcnt]=g[j];
if(((g[i]&d[2])==g[i])&&((g[j]&d[1])==g[j]))
{
dp[2][g[i]][g[j]]=cnt[g[i]]+cnt[g[j]];
}
}
}
}
for(int i=3;i<=n;i++)
{
for(int j=1;j<=gcnt;j++) //dq
{
if((g[j]&d[i])!=g[j])
{
continue;
}
for(int k=1;k<=agcnt;k++) //sl
{
if(((g[j]&g1[k])==0)&&((g[j]&g2[k])==0))
{
dp[i][g[j]][g1[k]]=max(dp[i][g[j]][g1[k]],dp[i-1][g1[k]][g2[k]]+cnt[g[j]]);
}
}
}
}
int ans=0;
for(int i=1;i<=agcnt;i++)
{
ans=max(ans,dp[n][g1[i]][g2[i]]);
}
cout<<ans;
return 0;
}gmoj/10492
- 设
因为题目说要分组，那么就是“选不选”了，所以可以直接设 dp[i] 为选择状态为 i 时的最短时间。 - 看
“选不选择”这个策略已经在状态中表示了。 - 寻
因为我们是一组一组的选，所以如果我们需要先预处理出所有选择情况的时间和重量，因为m<=16，所以状态数是 216，内存并不会超限。
如果我们要选择的组的状态是 j ，而当前一共选择的状态是 i ，那我们选择前的状态应该就是 i xor j。 - 找
因为题目规定每组的重量不得超过 W，所以对于当前选择的 i 本身的重量就不超过 W 情况下，可以先取它的时间（它并不一定是最优的）
接着遍历状态 i 的子集 j ，我们前面也写过了，状态 i 可以分为 j 和 i xor j ，那么很容易就能得出，在我们选择的组的重量不超过 W 的情况下，我们就可以这样转移：
dp[i]=min(dp[j]+time[i xor j])
#include <iostream>
#include <cstring>
using namespace std;
int W,n;
int t,w;
int wt[(1<<16)+5],tt[(1<<16)+5];
int dp[(1<<16)+5];
int main()
{
cin>>W>>n;
for(int i=1;i<=n;i++)
{
cin>>t>>w;
for(int j=1;j<(1<<n);j++)
{
if((j>>(i-1))&1)
{
tt[j]=max(tt[j],t);
wt[j]+=w;
}
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<(1<<n);i++)
{
if(wt[i]<=W)
{
dp[i]=tt[i];
}
for(int j=i;j;j=(j-1)&i)
{
if(wt[(i^j)]<=W)
{
dp[i]=min(dp[i],dp[j]+tt[(i^j)]);
}
}
}
cout<<dp[(1<<n)-1];
return 0;
}遍历子集 ：详情看二进制集合操作 - Oi Wiki
⚡ 2026.08.28 复习内容
比赛题目
gmoj/10442
因为对于第 ai 个武器，要出现 ai 次才能获得，那么当种类数是 x 时，最少也有 x2+x 个武器，又因为 n 最大只是 105，所以 x 最大也不会超过 500(5002+500=250500>105)，我们设一个 p 数组来存放可能符合条件的武器，后面枚举这些数，再搞前缀和，最后比较就可以了。
执行次数 << 500n(5∗107)。完全足够
#include <iostream>
using namespace std;
const int N=1e5+5;
int n;
struct node
{
int nx,x,id;
}a[N];
int m,l[N],r[N],k[N];
int cnt[N],y[N],s[N],ans[N];
int p[505],pcnt;
bool f=true;
bool cmp(node a,node b)
{
if(f) return a.nx<b.nx;
return a.id<b.id;
}
void qs(int s,int e)
{
if(s>=e) return ;
node mid=a[(s+e)>>1];
int l=s,r=e;
while(l<=r)
{
while(cmp(a[l],mid)) l++;
while(cmp(mid,a[r])) r--;
if(l<=r)
{
swap(a[l],a[r]);
l++,r--;
}
}
qs(s,r);
qs(l,e);
}
long long C[405][405];
int main()
{
freopen("weapon.in","r",stdin);
freopen("weapon.out","w",stdout);
cin>>n;
C[0][1]=1;
for(int i=1;i<=400;i++)
{
for(int j=1;j<=i;j++)
{
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
for(int i=1;i<=n;i++)
{
cin>>a[i].nx; //原值
a[i].id=i;
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>l[i]>>r[i]>>k[i];
}
f=true,qs(1,n); //元素
a[1].x=1;
y[a[1].x]=a[1].nx;
cnt[a[1].x]++;
for(int i=2;i<=n;i++)
{
if(a[i].nx==a[i-1].nx) a[i].x=a[i-1].x;
else a[i].x=a[i-1].x+1;
y[a[i].x]=a[i].nx;
cnt[a[i].x]++;
}
int q=a[n].x;
f=false,qs(1,n); //前后
for(int i=1;i<=q;i++)
{
if(cnt[i]>=y[i])
{
p[++pcnt]=i;
}
}
for(int i=1;i<=pcnt;i++)
{
/*
当前数字 => p[i]
前缀和 => s[i]
原数字 => y[p[i]]
*/
for(int j=1;j<=n;j++)
{
s[j]=s[j-1];
if(a[j].x==p[i])
{
s[j]++;
}
}
for(int j=1;j<=m;j++)
{
if(s[r[j]]-s[l[j]-1]>=y[p[i]])
{
ans[j]++;
}
}
}
for(int i=1;i<=m;i++)
{
cout<<C[ans[i]+1][k[i]+1]<<'\n';
}
return 0;
}这里的排列组合涉及到了一个公式：
Cij = Ci−1j−1 + Ci−1j
📐 2026.08.29 复习内容
比赛题目
gmoj/10443
这道题目的数据限制十分吓人，是1010000，所以很显然需要使用到高精度。
首先通过举例子等方法能看出来答案均为⌊n/(k−1)⌋。
接着就需要处理如何快速地得出最高位 10000−1 位的答案。
很显然，如果用试除法时，每次减去数字都是 O(n)，枚举每位也是 O(n)（ n 表示的是位数），那么时间复杂度就是 O(10000∗9)，不会超时。
我们解决这种位数非常大的高精度时，得先做出这东西。
将高精度压位，以剩下时间和内存。
然后大概也就这些了。
不过这里还是要说明一下压位高精（因为这两个东西我都没有学过）
压位高精度
原生的高精度每一个 int 变量 都只存储一位，这样用很浪费 int 2∗109 的存储能力，为了更好地计算，也为了剩下内存，我们让每个 int 变量 存储多位，这样就会更好。
我们当前设每个 int 变量 存储五位。
struct BigInt
{
int num[2005],size;
};其中，num 可以存的位数是 2000∗5，size 是当前使用到压缩后的第几位。
（注：为了节省时间防止内存复制，后面的参数均为 const BigInt& ，简写为 cb）
赋值：
（原来还有六级标题）
我们使用 string 来赋值，分 5 位存储到各个位数，也就是对于原来的第 i 位在压缩后变成了 第 ⌊i/5⌋+1 位（ 0 是首位 ）。
但是高精度是倒序存储，所以我们得先让第 i 位转换成倒数的，那么就是倒数 ∣S∣−i−1 位了。( 0 首 )
void operator=(string s)
{
int t=s.size();
for(int i=0;i<t;i++)
{
num[i/5+1]=(num[i/5+1]<<1)+(num[i/5+1]<<3)+(s[i]^48);
}
size=(t-1)/5+1;
}顺便把构造函数搞定了
BigInt(string s="0"){ *this=s; }比较：
其实和原生的别无二致。
bool operator<(cb other)
{
if(size!=other.size) return size<other.size;
else
for(int i=1;i<=size;i++)
if(num[i]!=other.num[i])
return num[i]<other.num[i];
return false;
}
bool operator==(cb other)
{
if(size!=other.size) return false;
else
for(int i=1;i<=size;i++)
if(num[i]!=other.num[i])
return false;
return true;
}
bool operator>(cb other)
{
return !((*this==other)||(*this<other));
}
bool operator<=(cb other)
{
return !(*this>other);
}
bool operator>=(cb other)
{
return !(*this<other);
}四则运算
接下来就是重头戏了。
加法：我们要处理进位的情况，这时候，我们设定一下数位的进制，因为最多只能存五位，所以是 105。
const int base=1e5;如果当前同位数的和大于这个值，就进位。
BigInt operator+(cb other)
{
BigInt ret;
ret.size=max(size,other.size)+1;
for(int i=1;i<=ret.size;i++)
{
ret.num[i]+=num[i]+other.num[i];
if(ret.num[i]>=base)
{
ret.num[i+1]+=ret.num[i]/base;
ret.num[i]%=base;
}
}
while(ret.num[ret.size]==0)
{
ret.size--;
}
return ret;
}减法：没什么区别。
BigInt operator-(cb other)
{
BigInt ret;
if(*this<other)
{
return ret;
}
ret.size=max(size,other.size);
for(int i=1;i<=ret.size;i++)
{
ret.num[i]+=num[i]-other.num[i];
if(ret.num[i]<0)
{
ret.num[i+1]--;
ret.num[i]+=base;
}
}
while(ret.num[ret.size]==0)
{
ret.size--;
}
return ret;
}乘法：没区
（其实有更快的，不过它跟题目没什么关系）
BigInt operator*(cb other)
{
BigInt ret;
ret.size=this->size+other.size-1;
for(int i=1;i<=this->size;i++)
{
for(int j=1;j<=other.size;j++)
{
ret.num[i+j-1]+=this->num[i]*other.num[j];
int p=i+j-1;
while(ret.num[p]>=base)
{
ret.num[p+1]+=ret.num[p]/base;
ret.num[p]%=base;
p++;
}
}
}
while(ret.num[ret.size]==0)
{
ret.size--;
}
return ret;
}除法：
试商法：除数高位对齐被除数，能减就减并记录，减完到下一位。
不过这道题的 k 用 int 存就可以了，所以直接用高精除以低精的方法就行了。
BigInt operator/(BigInt a,long long b)
{
BigInt ret;
ret.size=a.size;
long long yu=0;
for(int i=a.size;i>=1;i--)
{
yu=(yu<<1)+(yu<<3)+(a.num[i]^48);//模拟竖式除法中的落位
ret.num[i]=yu/b;
yu%=b;
}
while(ret.num[ret.size]==0)
{
ret.size--;
}
return ret;
}📅 2026.09.02 21:54 复习规划修改通知
之后复习的题目根据优先级会放在前面：
10666, 10444, 9230, 10313, 10399, 10141, 10387。
以后的时间安排：
周一三四 ：20:20 ~ 22:00
周五 ：19:00 ~ 22:00
周六 ：全天
有空余时间的话刷一下 CSP-JS 的题。
经验积累：
dp 中遍历顺序也有为重要，可以根据上一步来设定顺序。
题目一般有什么限制，都能算一个维度。（不过记得保证不会超内存或者超时间）
🧬 2026.09.03 复习内容
gmoj/10666
上周看了解析才知道树形 dp 怎么做。
设每一层括号：当前这层为父节点，被当前括号包住的上一层括号是子节点，同层括号互为兄弟节点。
不过为了更好地计算，我们再设一个虚拟父节点，也就是在最外面多加一层括号。
那么我们输入完，处理完字符串后，后面就是一个递归建树了。
建树
设数组 id[l][r] 为区间 l ~ r 所属的子节点编号，每次遍历到一层，都可以先创建与其对应的节点。
不难看出，每一个上一层的括号一定会相邻，有能知道第一个上一层的括号的左括号一定是当前层的左括号下一位，所以我们可以在递归前先用栈预处理出每个右括号对应的左括号。那么在递归时设上一个左括号为 l + 1，当找到匹配的右括号，那么下一个同层的括号的左括号就是当前右括号的下一位了。
void create(int l,int r)
{
tot++;
id[l][r]=tot;
int lst=l+1;
for(int i=l+1;i<r;i++)
{
if(L[i]==lst)
{
create(L[i],i);
add(id[l][r],id[L[i]][i]);
lst=i+1;
}
}
}好，那我们再看如何进行树形 dp。
树形 dp
很明显能看出这些：
- 第一个和最后一个子节点不能与当前节点的颜色相同。
- 相邻两个兄弟节点不能相同。
那么我们在进行树形 dp 的时候，可以设两个数组。
- 设 dp[u][c] 为给 u 子树的节点 u 上色 c 的最大花费。
- 设 f[c1][c2] 为当前子节点中第一个的颜色为 c1 ，最后一个颜色为 c2 的最大价值，用于辅助 dp 计算。
这两个数组其实也可以用“题目限制什么或有什么就开一维设。”的方法得出。
那么过程大概是这样的：
- 如果 u 是叶子结点，于是它的上色没有限制，直接 dp[u][c]=cost[c]。
- 反之，因为计算节点 u 的 dp 时还要考虑子节点的 dp，所以先递归子节点。
- 对于第一个节点的情况 f[c][c]=dp[v][c]。也就是首尾都是取决于第一个节点，因为子树不仅要考虑子节点，所以这里要使用 dp[v][c] 而不是 cost[c]。
- 对于其他的节点，为了防止上色叠加，我们需要先临时储存一下 f ，也就是复制一份到另一个数组，接着我们就可以使用 dp 四部曲来看看如何写 f 的转移方程：
设，已经解决了。
看，给当前子节点 i 上颜色。
寻，上一步是还没有给子节点 i 上色的状态。
找，当给当前子节点 i 上颜色 nc ，那么如果原状态是 f[fc][lc] 时，那么在上色后产生的效益应该是 dp[i][nc] （不仅要考虑子节点），最后的状态就是 dp[fc][nc]。
那么根据刚刚的四步，得出转移方程 new f [fc][nc]=f[fc][lc]+dp[i][nc]。（注意 nc 不能等于 lc，不然就违反了第二条限制了） - 最终计算完所有子树后，则 dp[u][c]=max(cost[c]+f[lc][nc]) ，不过需要注意c!=lc,c!=nc，不然就会违反第一条限制。
#include <iostream>
#include <cstring>
using namespace std;
int n,cost[3];
struct stk_
{
int num[1005],tp;
stk_(){ memset(num,0,sizeof(num));tp=0; }
void push(int x){ num[++tp]=x; }
void pop(){ tp--; }
int top(){ return num[tp]; }
} stk;
int L[1005];
int id[1005][1005],tot;
string s;
int sL;
int h[505],v[505],nxt[505],cnt;
void add(int U,int V)
{
cnt++;
v[cnt]=V;
nxt[cnt]=h[U];
h[U]=cnt;
}
void create(int l,int r)
{
tot++;
id[l][r]=tot;
int lst=l+1;
for(int i=l+1;i<r;i++)
{
if(L[i]==lst)
{
create(L[i],i);
add(id[l][r],id[L[i]][i]);
lst=i+1;
}
}
}
int dp[505][3],f[3][3];
int new_f[3][3];
void dfs(int u)
{
if(h[u]==0)
{
for(int c=0;c<=2;c++)
{
dp[u][c]=cost[c];
}
return ;
}
for(int i=h[u];i;i=nxt[i])
{
dfs(v[i]);
}
memset(f,0,sizeof(f));
for(int c=0;c<=2;c++)
{
f[c][c]=dp[v[h[u]]][c];
}
for(int i=nxt[h[u]];i;i=nxt[i])
{
memcpy(new_f,f,sizeof(f));
for(int fc=0;fc<=2;fc++)
{
for(int lc=0;lc<=2;lc++)
{
for(int nc=0;nc<=2;nc++)
{
if(nc==lc) continue;
new_f[fc][nc]=max(new_f[fc][nc],f[fc][lc]+dp[v[i]][nc]);
}
}
}
memcpy(f,new_f,sizeof(f));
}
for(int c=0;c<=2;c++)
{
for(int lc=0;lc<=2;lc++)
{
for(int nc=0;nc<=2;nc++)
{
if(lc!=c&&nc!=c)
{
dp[u][c]=max(dp[u][c],cost[c]+f[lc][nc]);
}
}
}
}
}
int main()
{
freopen("parenthesis.in","r",stdin);
freopen("parenthesis.out","w",stdout);
cin>>n>>cost[1]>>cost[2];
cin>>s;
s="("+s+")",sL=s.size(),s=" "+s;
for(int i=1;i<=sL;i++)
{
if(s[i]=='(')
{
stk.push(i);
}
else
{
L[i]=stk.top();
stk.pop();
}
}
create(1,sL);
dfs(1);
int ans=0;
for(int c=0;c<=2;c++)
{
ans=max(ans,dp[1][c]-cost[c]);
}
cout<<ans;
return 0;
}gmoj/10444
这道题同时考验了线段树和堆，研究起来很有意义。
首先我们先整理一下题目的重要信息：
- 假设第 x 个单位时间开始手术，则第 x+bi−1 个单位时间结束手术，医生在第 x+bi 个单位时间及以后才能接待别的患者。
- 如果一个患者发现医院里有一个病情严重度比自己轻微的患者正在手术而自己还没有进行手术，则他会开始医闹。
- 问第 k 个单位时间结束后能收获金币的最大值。
- 保证 pi 两两不同
由于第四条性质，我们可以使用线段树来维护在当前病症严重情况的区间为 l ~ r 时，所对应的最短时间。如果这个病人已经治好，那么直接将时间设为最大值，防止后面不小心选择到。
堆可以根据第二条性质，在堆顶存储当前时间内还没治好的病人中病症最严重的那个人的下标，不过注意在进行操作时不要下标和下标间比较，而是根据 p 来比较。
由于病人来的顺序是根据时间的先后的，所以计算前需要将病人来的时间排序。
由于时间有序并不代表病情有序，所以在进行建树的时候，要将病症情况与时间做一个映射，这样在找到一段单区间时，就可以调用映射数组来找到时间，用代码实现就是seg[p]=ys[p](ys[p]=t)。
由于线段树只会取最小的时间，所以初始化的时候其实就可以直接将所有病人的时间存储进去，时间大的也可以存，毕竟也不会影响到最小时间。
那么其实注意这些就差不多了，那么总过程就是：
- 输入，排序，建树等基本操作。
- 设时间为 cur，如果没有等待病人且后面也不会再来等待病人了，那么就结束（反过来就是循环条件）。
- 将当前时间下的所有病人加入。
- 判断一下如果加入后还是没有病人，那么就有两种情况：
如果后面还有病人，那么就直接将时间跳到那个病人的时间。
否则就直接结束循环。 - 取堆顶，有线段树取一下比当前病人病情更严重的时间的最小值，如果这个值在病人手术的范围内，那么就会产生医闹，于是又有两种情况：
如果那么更严重的病人来到的时间已经大于 k，那么就没有必要调到那个时间了（毕竟已经超出范围了），直接结束循环。
否则就跳到那个更严重的病人来到的时间。
（解释：因为最严重的那个都手术不了，更别说其他的了，所以只能等） - 如果这个人手术后的时间也大于 k，那么也手术不了了，也结束循环。
- 最后如果经历了层层的判断都没有成立，那么让这个病人手术，并加上这个人的利益。
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const ll INF=4e18;
struct ps
{
int p;
ll t,a,b;
}a[MAXN];
int n;
ll k;
int heap[MAXN],hl;
ll ys[MAXN];
ll seg[MAXN*4];
bool cmp(const ps &x,const ps &y)
{
return x.t<y.t;
}
void qs(int s,int e)
{
if(s>=e) return;
ps mid=a[(s+e)>>1];
int l=s,r=e;
while(l<=r)
{
while(cmp(a[l],mid)) l++;
while(cmp(mid,a[r])) r--;
if(l<=r)
{
swap(a[l],a[r]);
l++,r--;
}
}
qs(s,r);
qs(l,e);
}
void build(int node,int l,int r)
{
if(l==r)
{
seg[node]=ys[l];
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
seg[node]=min(seg[node<<1],seg[node<<1|1]);
}
void update(int node,int l,int r,int pos,ll val)
{
if(l==r)
{
seg[node]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) update(node<<1,l,mid,pos,val);
else update(node<<1|1,mid+1,r,pos,val);
seg[node]=min(seg[node<<1],seg[node<<1|1]);
}
ll query(int node,int l,int r,int ql,int qr)
{
if(ql>r||qr<l)
{
return INF;
}
if(ql<=l&&r<=qr)
{
return seg[node];
}
int mid=(l+r)>>1;
return min(query(node<<1,l,mid,ql,qr),query(node<<1|1,mid+1,r,ql,qr));
}
void push(int x)
{
hl++;
heap[hl]=x;
int idx=hl;
while(a[heap[(idx>>1)]].p>a[heap[idx]].p)
{
swap(heap[(idx>>1)],heap[idx]);
idx>>=1;
}
}
void pop()
{
swap(heap[1],heap[hl]);
hl--;
int idx=1;
while(true)
{
int mini=idx;
int lft=(idx<<1);
int rgt=lft+1;
if(lft<=hl&&a[heap[lft]].p<a[heap[mini]].p) mini=lft;
if(rgt<=hl&&a[heap[rgt]].p<a[heap[mini]].p) mini=rgt;
if(mini==idx) break;
swap(heap[idx],heap[mini]);
idx=mini;
}
}
int top()
{
return heap[1];
}
int main()
{
freopen("operation.in","r",stdin);
freopen("operation.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;++i) cin>>a[i].p;
for(int i=1;i<=n;++i) cin>>a[i].t;
for(int i=1;i<=n;++i) cin>>a[i].a;
for(int i=1;i<=n;++i) cin>>a[i].b;
for(int i=1;i<=n;++i)
{
ys[a[i].p]=a[i].t;
}
qs(1,n);
build(1,1,n);
ll cur=1;
int ptr=1;
ll ans=0;
int cnt=0;
while(ptr<=n||hl>0)
{
while(ptr<=n && a[ptr].t<=cur)
{
int p=a[ptr].p;
update(1,1,n,p,INF);
push(ptr);
ptr++;
}
if(hl==0)
{
if(ptr>n) break;
cur=a[ptr].t;
continue;
}
int x=top();
int px=a[x].p;
ll bx=a[x].b;
ll mn=INF;
if(px>1)
{
mn=query(1,1,n,1,px-1);
}
if(mn<cur+bx)
{
if(mn>k) break;
cur=mn;
continue;
}
if(cur+bx-1>k)
{
break;
}
ans+=a[x].a;
cur+=bx;
pop();
cnt++;
}
cout<<ans;
return 0;
}小结
人类的创造性真是无穷无尽，以后多了解这种思维的题，想必也能提升能力吧。
不过也不用那么操之过急，一步一步来，总能成功。
（成功这个词真的可以不分场合地讨论吗？）
📎 关于复习计划题单的扩展
atcoderABC473 A~E
🌐 2026.09.05 复习内容
AtcoderABC473 题目
A~C
A 循环结构问题，B 循环结构 + 数组问题，C 同上
D
dfs，不过有一个优化的点：最后一个数其实已经在选择完倒数第二个数的时候决定了，所以最后一个数不用搜索，只需要算出剩下的数是否为 n 的倍数就行了。
#include <iostream>
using namespace std;
int n,k,a[15];
void dfs(int pos,int sum)
{
if(pos==n)
{
if((k-sum)%n==0) //优化在这里！
{
for(int i=1;i<pos;i++)
{
cout<<a[i]<<' ';
}cout<<(k-sum)/n<<'\n';
}
return ;
}
for(int i=0;sum+i*pos<=k;++i)
{
a[pos]=i;
dfs(pos+1,sum+i*pos);
}
}
int main()
{
cin>>n>>k;
dfs(1,0);
return 0;
}E
设 dp[i] 为从 1 ~ i 内的数字能组成 k 的倍数的子序列数量的最大值，那么不难看出操作是选或不选，对应的转移方程就是 dp[i]=max(dp[i−1],dp[j]+1) ，其中 s[i]−s[j] mod k==0，但是因为元素值的范围很大，所以可以转化为 s[i] mod k==s[j] mod k，于是每求一次前缀和就多取模 k。
因为 dp 数组有一种单调性，所以我们的 j 可以只看上一个同余的 j，就不用再看之前的了。
所以我们可以用哈希的方法来找到上一个同余的 j ，但是余数的范围也很大，怎么解决呢？
我们可以看到，虽然余数的范围很大，但是种数却只有 2∗105，我们可以利用这点，将所有得到的余数做离散化，后面就根据上面的思路写就可以了。
（这道题我在使用离散化的方法之前一直在处理哈希冲突，改了十几次模数才发现可以用离散化）
#include <iostream>
using namespace std;
long long n,k,a[200005];
struct node{ int x,id; } s[200005];
int f[200005],dp[200005];
bool flag;
bool cmp(node a,node b)
{
if(flag) return a.x<b.x;
return a.id<b.id;
}
void qs(int st,int e)
{
if(st>=e) return;
node mid=s[(st+e)>>1];
int l=st,r=e;
while(l<=r)
{
while(cmp(s[l],mid)) l++;
while(cmp(mid,s[r])) r--;
if(l<=r)
{
swap(s[l],s[r]);
l++,r--;
}
}
qs(st,r);
qs(l,e);
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i].x=(s[i-1].x+a[i])%k;
s[i].id=i;
}
flag=true,qs(1,n);
int pre=s[1].x;
if(pre==0) f[1]=0;
else f[1]=-1;
s[1].x=1;
for(int i=2;i<=n;i++)
{
if(s[i].x==pre) s[i].x=s[i-1].x;
else
{
pre=s[i].x;
s[i].x=s[i-1].x+1;
}
}
flag=false,qs(1,n);
for(int i=2;i<=n;i++) f[i]=-1;
for(int i=1;i<=n;i++)
{
dp[i]=max(dp[i-1],f[s[i].x]+1);
f[s[i].x]=max(f[s[i].x],dp[i]);
}
cout<<dp[n];
return 0;
}F
我们先看看什么字符串才能用 "AB" "A" 插入组成：
当我们只看 AB 时，可以很明显地看出来这很像括号，例如 ABAB，AABB 等。
那也就说明，这里所有的括号层级一定会大于等于 0 （因为到最后一个右括号的时候层级 -1 ，变成了 0）
如果我们增加了插入 A 的情况时，那么层级可能回更大，括号层级仍然大于等于 0。
而对于不合法的情况，例如 "ABBA"，那么在到第二个 B 时，括号层级已经变成了 -1 ，那么就不符合了。
但是查询区间不一定是开头的，例如 "AABBAA" 中查询 2 ~ 5，那么层级也就不能为 <0 不合法，而是 < 左端点上一位的层数(1) 不合法。（取最小值）
修改的话，如果不变那就不动，变的话那就区间增加减少就可以了。
说到区间修改和区间查询都很快的数据结构，想必目前能写的也只有线段树了吧。
📚 2026.09.06 复习内容
为了以后能加快打 ABC 以及以后的 ARC 的时间，我在 Atcoder 上搜集了一些高频词汇，用于积累。
单词
- Determine —— 判断
- Whether —— 是否
- Exists —— 存在
- Sequence —— 序列
- Satisfying —— 满足
- Following —— 接下来的
- Conditions —— 条件
- Construct —— 构建
- Such —— 这样的
- Respectively —— 分别
- Certain —— 某个