区的 CSP 赛前蠕动记录

yxdl1

2026-09-12 22:01:41

发布于：浙江

152阅读

0回复

0点赞

可能更好的阅读体验 link，优先更新这里

受到 AIerqwq and wcqwqk 的启发，打算写个题解记录做过的题。以下题目会先用口胡的形式呈现（注意不保证解法正确），后续可能会加上代码 and 正确思路。也欢迎各位大佬来指正我的口胡思路 awa。

部分题目出自题单：https://www.luogu.com.cn/training/9350

P1095

本来写的是贪心，但这个做法会写成构式大分讨，还是老老实实写 DP 吧。

移动有三个优先级：

直接魔法移动
恢复魔法值后魔法移动
跑步

不难发现，使用跑步的情况，要么是充能时间足够跑出去，要么就是剩余时间不足以进行第二轮充能。

定义 $dp_i$ 为第 $i$ 秒所能移动到的最远距离。先按照上述优先级构建好 $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

诶我咋跑过来做橙题了。

定义 $dp_i$ 为从 $1$ 到 $i$ 的最大字段和，显然转移方程为 $dp_i=\max(dp[i-1]+a[i],a[i])$ 。答案为 $\max(a_1,a_2...a_n)$ 。

代码：

#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。

不怼，这个数据怎么高达 $10^5$ 。

不管了先写部分分。

$50\%$ 部分分

显然为朴素 LCS。定义 $dp_{i,j}$ 为长度分别是 $i,j$ 两串的 LCS。若 $a_i=a_j$ 则 $dp_{i,j}=dp_{i-1,j-1}+1$ 。否则 $dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})$ 。那么代码易得。

代码（我是码风切换大佬 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;
}

诶那你就要问了， $100$ 分咋弄啊。这你就问对人了，我会用最直白，最不绕弯子的方式告诉你，我不会（。至少目前不会，满分做法请参考题解 awa

P1507

诶这不是 01 背包板子吗。

哦不对，要维护体积和质量两个参数。

考虑让 $dp_{j,k}$ 维护质量，体积分别为 $j,k$ 情况下所能取到的最大价值。转移方程为 $dp_{j,k}=\max(dp_{j,k},dp_{j-W[i],k-V[i]}+v[i])$ 。其中 $W,V,v$ 分别为物品的质量，体积与卡路里。

代码：

#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。哦 $k$ 有 $10^9$

那咋办。

转化一下，变成求提升攻击力所需要的最小金币数，只要这个值小于 $k$ 即可直接输出。转移方程变为 $dp_j=\min(dp_j,dp_{j-a_i}+c_i)$ 。然后记得别见祖宗。

代码：

#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;
}

P3431

前情提要：本题视频 link 的一定提示下。

42pts 做法：

显然简单 dp 一下即可，不多讲了，复杂度 $\mathcal{O}(n \times m)$ 。

#include <iostream>
namespace yxdl1{
    #define f(i,l,r) for(int i=l;i<=r;i++)
    #define max(a,b) (a>b?a:b)// 不知道为什么不加括号会爆掉，或许是优先级的问题
    int n,m,k,map[5005][5005],dp[5005][5005];
    void solve(){
        std::cin >> n >> m >> k;
        while(k--){
            int x,y,p;
            std::cin >> x >> y >> p;
            map[x][y]=p;
        }
        f(i,1,n){
            f(j,1,m){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+map[i][j];
            }
        }std::cout << dp[n][m];
    }
}
int main(){
    yxdl1::solve();
    return 0;
}

60pts 做法

不难发现我们原本的转移代码是：

$dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})+w[i]$

由于数组存不下，我们不妨转换下。定义 $dp_i$ 为起点到第 $i$ 个点的最大值。我们发现地图里有很多滚木，所以我们只需要存有人的点即可。不难发现，这个点只能从他“左上方位”的点更新。则方程变为：

若有 $i≠j,x_j \le x_i,y_j \le y_x$ ，则

$dp_i=dp_j+w_i$

其中 $j$ 为符合以上条件的权值最大的点。

那不行啊，还是很难维护，那咋办。

看看能不能降下来一维，可以把 $x$ 升序排序，所有 $y$ 在当 $x$ 相等的情况下升序排列，这样就可以减掉 $x$ 的那个维度，接下来只用维护 $y$ 就可以了。

转移方程变为：

满足 $j<i,y_j \le y_i$ ，则

$dp_i=dp_j+w_j$

一样的， $j$ 为所有满足以上条件的 $dp$ 数组的最大值下标。

复杂度相较以前有了很大改善，为 $\mathcal{O}(k^2)$ 。

正解

你知道的，这题是数据结构优化 DP。

看看用什么优化。

发现对于更新 $dp_i$ ， $dp_{1...i-1}$ 肯定都被更新过了。转化一下，我们需要一个数据结构来维护 $1$ 到 $i-1$ 最大的值，也就是维护 $y$ 。区间查询单点修改，显然 BIT 码量与常数最小，可以胜任。那么在原代码基础上加上 BIT 维护即可。记得离散化。

代码：

#include <iostream>
#include <algorithm>
namespace yxdl1{
    #define int long long
    #define f(i,l,r) for(int i=l;i<=r;i++)
    #define max(a,b) (a>b?a:b)// 不知道为什么不加括号会爆掉，或许是优先级的问题
    #define lowbit(x) (x&(-x))
    struct node{
        int x,y,p;
    }a[1000005];
    int n,m,k,map[5005][5005],dp[1000005],ans=0,bit[1000005],y[1000005],_k;
    int init(){//离散化，顺便更新 k
        std::sort(y+1,y+1+k);
        int cnt=std::unique(y+1,y+k+1)-y-1;
        f(i,1,k){
            a[i].y=std::lower_bound(y+1,y+cnt+1,a[i].y)-y;
        }return cnt;
    }
    void update(int idx,int v){
        while(idx<=_k){
            bit[idx]=max(bit[idx],v);
            idx+=lowbit(idx);
        }
    }int query(int idx){
        int mx=0;
        while(idx>0){
            mx=max(mx,bit[idx]);
            idx-=lowbit(idx);
        }return mx;
    }bool cmp(node x,node y){
        if(x.x==y.x)return x.y<y.y;
        return x.x<y.x;
    }
    void solve(){
        std::cin >> n >> m >> k;
        f(i,1,k){
            std::cin >> a[i].x >> a[i].y >> a[i].p;
            y[i]=a[i].y;
        }_k=init();
        std::sort(a+1,a+k+1,cmp);
        f(i,1,k){
            int mx=query(a[i].y);
            dp[i]=mx+a[i].p;
            ans=max(dp[i],ans);
            update(a[i].y,dp[i]);
        }std::cout << ans;
    }
}
signed main(){
    yxdl1::solve();
    return 0;
}

时间复杂度 $\mathcal{O}(k \log k)$ 。

这道题或许可以算是我独立做的，看视频发现这道题，之后开始打部分分。 $40pts$ 的代码做完之后有事走了。路上一直在想方法，想到了 $60pts$ 的做法。吃饭的时候想到了 $100pts$ 的做法。在做之前看了一部分的视频，但我没看懂你信吗（

这个题大概率是我收获最大的题了，学会了排序降纬这个 trick，第一个数据结构优化 DP，第一次独立思考出青 DP。

P3908

我不更你们 P 什么。

口胡的，先说结论。

对于一个正整数 $k$ ，令 $1 \oplus 2 \oplus 3... \oplus k$ 的值为 $f(k)$ ，则有：

$f(k) = \begin{cases} k, & k \equiv 0 \pmod{4} \\ 1, & k \equiv 1 \pmod{4} \\ k+1, & k \equiv 2 \pmod{4} \\ 0, & k \equiv 3 \pmod{4} \end{cases}$

然后没了。

::::info[至于我是怎么想到的]
搓一个打表代码：

namespace yxdl1{
    #define f(i,l,r) for(int i=l;i<=r;i++)
    void hyw(){
        int num=0;
        f(i,1,10){
            num^=i;
            std::cout << num << "\n";
        }
    }
}

然后观察输出，发现每隔三个输出就会出现一个 $0$ ，那么不难想到与 $4$ 有关。

具体证明还是看题解吧，我太区了不会证明。
::::

Leetcode No.80

这不是随便做吗。

哦不对要原地去重。

发现遍历之后之前的值都没用了，所以考虑把去完重后的数组扔到先前已经遍历过的空间中。所以思路很简单了。

显然，因为数组是升序的，所以重复元素必然相连。题目要求我们保留两个数，只需要判断新数组倒数第二个元素是否与当前元素相等即可。如果相等则跳过，否则加入新数组。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len=0;
        for(int i=0;i<nums.size();i++){
            if(len<2 or nums[len-2]!=nums[i])nums[len++]=nums[i];
        }return len;
    }
};

ABC475 D

$|S| \le 7$

直接射！

解法 1

先筛出来所有质数，然后离散下原字符串。生成对于长度为 $10$ 包含字符 $0$ 到 $9$ 的排列，根据事先离散的数组取前 $|S|$ 个数，转化为整数之后判断是否为质数，是的话直接输出。

解法 2

我怎么这都没想到，直接打表所有 $P$ 就行了，我是啥比！！！

有帮助，赞一个

去预览

0/2000

全部评论 12

yxdl1
置顶
哦不，折叠筐又炸了

2026-09-05 来自浙江
0
- yxdl1
  回复
  yxdl1
  ACGO 啥时候弄个折叠框
  
  2026-09-05 来自浙江
  0
Suger_zhy🤔
湖北J组大概多少分过初赛？

2026-08-30 来自云南
1
- yxdl1
  回复
  Suger_zhy🤔
  反正可以用脚过
  
  2026-08-30 来自浙江
  0
- Suger_zhy🤔
  回复
  yxdl1
  60分行吗
  
  2026-08-30 来自云南
  0
- yxdl1
  回复
  Suger_zhy🤔
  感觉很低
  
  2026-08-30 来自浙江
  0
yxdl1
首青 DP 纪念 awa

2026-08-26 来自浙江
1
- Suger_zhy🤔
  回复
  yxdl1
  可以做打砖块
  
  2026-08-30 来自云南
  0
- prediction
  回复
  yxdl1
  建议做涂色
  
  2026-09-06 来自浙江
  0
yxdl1
笑点解析：短时间内码风大变，如果去做比赛直接被判 AIer

2026-08-25 来自浙江
1
- wcqk🦐
  回复
  yxdl1
  对啊为什么马蜂大便呢？
  
  2026-08-26 来自湖北
  0
- yxdl1
  回复
  wcqk🦐
  不知道啊学习先进技术（
  
  2026-08-26 来自浙江
  0
- yxdl1
  回复
  wcqk🦐
  骗你的如果我去 Atcoder 直接被当人机爆头了
  
  2026-08-26 来自浙江
  0
𝓈𝓎𝓃𝒸
大佬，您今年考S组吗？我如果想在江苏J组初赛过并且复赛一等奖，有什么建议吗？求

2026-09-12 来自江苏
0
- yxdl1
  回复
  𝓈𝓎𝓃𝒸
  你现在水平多少
  
  2026-09-13 来自浙江
  1
- 𝓈𝓎𝓃𝒸
  回复
  yxdl1
  才学到Meet_in_the_middle
  
  2026-09-13 来自江苏
  0
- 𝓈𝓎𝓃𝒸
  回复
  yxdl1
  我太菜了，初赛感觉过不了，江苏分太高了，主要是DP不太熟
  
  2026-09-13 来自江苏
  0
TanorWhileBai
还是那句话，这玩意我弄懂了地球将进入十级文明

2026-09-09 来自浙江
0
TanorWhileBai
e为什么我7年纪就要考了啊，我还不会

2026-09-05 来自浙江
0
- yxdl1
  回复
  TanorWhileBai
  多背背 DP 基本 J 组没啥大问题了
  
  2026-09-06 来自浙江
  0
- TanorWhileBai
  回复
  yxdl1
  nonono背的东西太多了
  
  2026-09-06 来自浙江
  0
- yxdl1
  回复
  TanorWhileBai
  代码都挺短的啊，J 组的。
  
  2026-09-06 来自浙江
  0
cjdst
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊大撒大撒大撒伟大撒旦撒旦撒

2026-09-05 来自广东
0
- yxdl1
  回复
  cjdst
  大撒旦
  
  2026-09-12 来自浙江
  1
- cjdst
  回复
  yxdl1
  看这名字还以为是谁呢，怎么这么能串
  
  2026-09-13 来自广东
  0
- yxdl1
  回复
  cjdst
  对
  
  2026-09-13 来自浙江
  0
Xylophone
太牛了

2026-09-05 来自广东
0
🥥
巧了P3431我也做了，也是因为看的这个视频（

2026-08-27 来自上海
0
- yxdl1
  回复
  🥥
  orz
  
  2026-08-27 来自浙江
  0
- 🥥
  回复
  yxdl1
  您比我强，我完全不是独立切的
  
  2026-08-27 来自上海
  0
- 🥥
  回复
  🥥
  虽然是4个月前做的（
  
  2026-08-27 来自上海
  0
cchu
虽然但是为什么发两遍？

2026-08-25 来自江西
0
- yxdl1
  回复
  cchu
  我说过要转移到小号的
  
  2026-08-25 来自浙江
  0
yxdl1
d

2026-08-24 来自浙江
0