CSP 前加训记录
2026-08-24 07:39:05
发布于：浙江
67阅读
0回复
0点赞
可能更好的阅读体验 link，优先更新这里
受到 AIerqwq and wcqwqk 的启发，打算写个题解记录做过的题。以下题目会先用口胡的形式呈现（注意不保证解法正确），后续可能会加上代码 and 正确思路。也欢迎各位大佬来指正我的口胡思路 awa。
部分题目出自题单：https://www.luogu.com.cn/training/9350
P1095
本来写的是贪心，但这个做法会写成构式大分讨，还是老老实实写 DP 吧。
移动有三个优先级：
- 直接魔法移动
- 恢复魔法值后魔法移动
- 跑步
不难发现，使用跑步的情况，要么是充能时间足够跑出去，要么就是剩余时间不足以进行第二轮充能。
定义 为第 秒所能移动到的最远距离。先按照上述优先级构建好 数组。第二轮我们考虑可以在恢复魔法值时间内里开的情况，把所有休息替换成奔跑。如果到了终点直接输出即可。
代码(排班有点小问题，不用在意)：
#include <iostream>
namespace yxdl1{
int dp[1000005]={},m,s,t;
void solve(){
std::cin >> m >> s >> t;
for(int i=1;i<=t;i++){
if(m>=10){//魔法值足够我们直接魔法移动
m-=10;
dp[i]=dp[i-1]+60;
}else{//否则恢复
m+=4;
dp[i]=dp[i-1];
}
}for(int i=1;i<=t;i++){
if(dp[i]<dp[i-1]+17)dp[i]=dp[i-1]+17;//可以理解为把所有休息时间替换成跑步移动，这里注意不会影响魔法移动，理由可以自行思考。
if(dp[i]>=s){
std::cout << "Yes\n" << i;
return ;
}
}std::cout << "No\n" << dp[t];
}
}
int main(){
yxdl1::solve();
return 0;
}
P1462
开始是不会做的，看了下 tag 有一丢丢思路了。
发现题目要求经过城市单次交费最大值的最小值，考虑二分答案。其中的 check 函数就是最短路，如果可以跑完，那就往大了跑，否则就往小了跑。
代码：
咕咕咕
B4133
诶我咋跑过来做橙题了。
定义 为从 到 的最大字段和，显然转移方程为 。答案为 。
代码：
#include <iostream>
namespace yxdl1{
#define int long long
int n,a[10000005]={},dp[10000005]={},ans=-100000000;
int max(int a,int b){return a>b?a:b;}
void solve(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> n;
for(int i=1;i<=n;i++){
std::cin >> a[i];
}dp[0]=0;
for(int i=1;i<=n;i++){
dp[i]=max(dp[i-1]+a[i],a[i]);
ans=max(ans,dp[i]);
}std::cout << ans;
}
}
signed main(){
yxdl1::solve();
return 0;
}
P1439
乍一看 LCS，仔细一看确实 LCS。居然是绿题 /yiw。
不怼，这个数据怎么高达 。
不管了先写部分分。
部分分
显然为朴素 LCS。定义 为长度分别是 两串的 LCS。若 则 。否则 。那么代码易得。
代码（我是码风切换大佬 awa）：
#include <iostream>
namespace yxdl1{
#define max(a,b) a>b?a:b
#define f(i,l,r) for(int i=l;i<=r;i++)
int n,a[100005]={},b[100005]={},dp[5005][5005]={},ans=0;
void solve(){
std::cin >> n;
f(i,1,n){
std::cin >> a[i];
dp[0][i]=0,dp[i][0]=0;
}f(i,1,n)std::cin >> b[i];
dp[0][0]=0;
f(i,1,n){
f(j,1,n){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
ans=max(ans,dp[i][j]);
}
}std::cout << ans;
}
}
int main(){
yxdl1::solve();
return 0;
}
诶那你就要问了， 分咋弄啊。这你就问对人了，我会用最直白，最不绕弯子的方式告诉你，我不会（。至少目前不会，满分做法请参考题解 awa
P1507
诶这不是 01 背包板子吗。
哦不对，要维护体积和质量两个参数。
考虑让 维护质量，体积分别为 情况下所能取到的最大价值。转移方程为 。其中 分别为物品的质量，体积与卡路里。
代码：
#include <iostream>
namespace yxdl1{
#define max(a,b) a>b?a:b;
#define f(i,l,r) for(int i=l;i<=r;i++)
#define ff(i,l,r) for(int i=l;i>=r;i--)
int h,t,n,V[405]={},W[405]={},v[405]={},dp[405][405];
void solve(){
std::cin >> h >> t >> n;
f(i,1,n)std::cin >> V[i] >> W[i] >> v[i];
f(i,1,n){
ff(j,t,W[i]){
ff(k,h,V[i]){
dp[j][k]=max(dp[j][k],dp[j-W[i]][k-V[i]]+v[i]);
}
}
}std::cout << dp[t][h];
}
}
int main(){
yxdl1::solve();
return 0;
}
P3379
学的是 Tarjan 求 LCA。板子就不多讲了。
#include <iostream>
#include <vector>
const int N=1e6;
namespace yxdl1{// Tarjan 离线 LCA
#define f(i,l,r) for(int i=l;i<=r;i++)
int n,m,s,fa[N],ans[N],vis[N];
std::vector<int> tree[N];//树
std::vector<std::pair<int,int>> ask[N];//离线查询
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}void merge(int x,int y){
fa[find(x)]=find(y);
}void init(){
f(i,1,n)fa[i]=i;
}
void read(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m >> s;
f(i,1,n-1){
int x,y;
std::cin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}f(i,1,m){
int x,y;
std::cin >> x >> y;
if(x==y)ans[i]=x;
ask[x].push_back({y,i});
ask[y].push_back({x,i});
}
}void Tarjan(int u){
vis[u]=1;
for(auto i:tree[u]){
if(!vis[i]){
Tarjan(i);
merge(i,u);
}
}for(auto i:ask[u]){
if(vis[i.first])ans[i.second]=find(i.first);
}
}void print(){
f(i,1,m)std::cout << ans[i] << std::endl;
}void solve(){
read();
init();
Tarjan(s);
print();
}
}
int main(){
yxdl1::solve();
return 0;
}
（雷霆码风
B3694
离散板子，但我为啥没做。
#include <bits/stdc++.h>
namespace yxdl1{
#define f(i,l,r) for(int i=l;i<=r;i++)
void solve(){
int n,a[1000005]={},copy[1000005]={};
std::cin >> n;
f(i,1,n){std::cin >> a[i];copy[i]=a[i];}
std::sort(copy+1,copy+1+n);
int cnt=std::unique(copy+1,copy+1+n)-copy-1;
f(i,1,n)a[i]=std::lower_bound(copy+1,copy+1+cnt,a[i])-copy;
f(i,1,n)std::cout << a[i] << " ";
std::cout << "\n";
}
}
int main(){
int t;
std::cin >> t;
while(t--){
yxdl1::solve();
}
return 0;
}
P14920
啥意思啊，这都是黄吗。
诶不是咋只有 60 pts。哦 有
那咋办。
转化一下，变成求提升攻击力所需要的最小金币数，只要这个值小于 即可直接输出。转移方程变为 。然后记得别见祖宗。
代码：
#include <iostream>
namespace yxdl1{
#define int long long
#define min(a,b) a<b?a:b
#define f(i,l,r) for(int i=l;i<=r;i++)
#define ff(i,l,r) for(int i=l;i>=r;i--)
int n,k,w[100005]={},v[100005]={},dp[10000005]={},cnt=0;
void solve(){
std::cin >> n >> k;
f(i,1,n){
std::cin >> v[i] >> w[i];
cnt+=v[i];
}f(i,1,cnt)dp[i]=1e9;
f(i,1,n){
ff(j,cnt,v[i]){
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}ff(i,cnt,0){//注意要取到 0
if(dp[i]<=k){
std::cout << i;
return ;
}
}
}
}
signed main(){
yxdl1::solve();
return 0;
}
有帮助，赞一个