博客广场/ 潘政勋

文章

8.17 日总

1 Grouping increases{ 1. 题意：有一组数组，规定一个数组中的惩罚值为数组中任意两个构成整个数组的子序列的正序下标：bi<bi+1.求整个数组惩罚值的最小值 2. 思路：对于正序下标的求解我们可以初始化两个最大值，以便于求解剩余的正序对有多少个，如果当前的值小于当前最小值，那么将其赋值，如果不是最小值那么说明我们找到了一对正序下标，an

潘政勋发布于 2026-8-17 16:20:10

综合/学习笔记

1 Grouping increases{

题意：有一组数组，规定一个数组中的惩罚值为数组中任意两个构成整个数组的子序列的正序下标：bi<bi+1.求整个数组惩罚值的最小值
思路：对于正序下标的求解我们可以初始化两个最大值，以便于求解剩余的正序对有多少个，如果当前的值小于当前最小值，那么将其赋值，如果不是最小值那么说明我们找到了一对正序下标，ans++

}

核心代码：

 if(last1<last2) swap(last1,last2);
            if(x<=last2) last2=x;//顺序一定不能反，last1和last2的值已经进行交换了，因此如果x<=last1在前那么x<=last2就一定不会被执行
            else if(x<=last1) last1=x;
            else{
                ans++;
                last2=x;
            }
        }

2 Keshi is throwing a party{

题意：有一群人的钱数按从1到n的顺序排列，第i个人拥有i张美元。现给出第i个人能容忍的比自己富有和比自己穷的人数，求你最终能邀请多少人
思路：像这种求一个可能的最大值的题目就要想到二分答案。如果我们以每个人的钱数为标准遍历数组，每经过一个人时如果当前所邀请的人数不超过能容忍的比自己穷的人数且还未邀请的人数不超过能容忍的比自己富有的人数，那么这个人就是可以被邀请的，最终的判断就是能邀请的人数是否超过二分枚举的人数
算法：二分，贪心

}

核心代码：

check函数：

bool check(int mid){
    int cnt=0;
     for(int i=1;i<=n;i++){
        if(b[i]>=cnt&&a[i]>=mid-cnt-1) cnt++;
     }
     return cnt>=mid;
}

3 Move back at a cost{

题意：给定一个数组，对于其中的每个元素，你都可以将其加1并重新排到数组的末尾，求为了使整个数组变成不降序列所需的最少次数
思路：这题给人的第一反应就是维护一个递增序列，如果其中的元素违背递增原则则直接将其丢入队尾，一直到整个序列满足不降为止。但是这并不一定是我们预料中的最少操作次数。首先就是递增顺序很难确定，再就是如果一个一个的去判断的话时间复杂度会很难接受。因此我们需要标记每个数字出现的顺序，并维护一个最大顺序和一个递减的优先队列。如果当前已被排去队尾的数字顺序小于当前的数字顺序，就说明这个数字的位置是正确的，直接放入答案数组，如果不是则说明前面比当前数更大的数字已经排去队尾，则这个数字也应当派去队尾，并赋予它一个新的更大下标，直到满足顺序为止
算法：优先队列

}

核心代码：

 while(!pq.empty()){
         auto[val,idx] = pq.top(); pq.pop();
         if(idx > needback){//顺序正确
            ans.push_back(val);
            needback = idx;
         }
         else{
            pq.push({val + 1,n + back});//重新放入队尾等待调整
            back++;
         }
      }

4 Bicycles{

题意：有一个人准备骑车从1号城市骑到n号城市，其中有m条边，表示u号城市和v号城市可以直接抵达，边长为w,并给出每个城市中的自行车的速度系数，规定如果当前的自行车为j，那么去往另一个城市所花的时间为w*s[j]，求从1到n的最少时间
思路：这题是普通dijsktra的一个变种，核心是增加第二维当前的最小速度系数。

我们定义dist[u][b]为当前所拥有的最大速度的自行车所花的距离，每次到达一个新的城市后，我们都可以取现在的自行车速度，看是之前的自行车走这条道路更划算还是现在的更划算，更新答案：dist[v][b]=dist[u][newb]*newt;

初始化：dist[0][s[0]]=0只有1号城市的单车，距离为0

最终答案：枚举自行车的所有状态1到1000，ans=min(ans,dist[n-1][i])（n的取值取决于初始化）

此题在原版Dijkstra的基础上添加了vis标记，为了避免重复计算选择某个自行车的状态

算法：最短路

}

最短路学的不好，这里放全部代码方便日后参考：

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
const ll INF=1e18;
using tp = tuple<ll, int, int>; 
using pii = pair<ll, ll>;
int main(){
     int t;
     cin >> t;
     while(t--){
        int n,m;
        cin >> n >> m;
        vector<vector<pii>> g(n);
        vector<int> s(n);
        while(m--){
            int u,v,w;
            cin >> u >> v >> w;
            u--; v--;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }  
        vector<vector<ll>> dist(n,vector<ll>(1001,INF));
        for(int i = 0; i < n; i++) cin >> s[i];
        dist[0][s[0]] = 0;//节点和当前最大速度

     priority_queue<tp,vector<tp>,greater<tp>> pq;
     vector<vector<bool>> vis(n,vector<bool>(1001,false));

     pq.push({0,0,s[0]});
     while(!pq.empty()){
            auto[d,u,b] = pq.top(); pq.pop();
           if(vis[u][b]) continue;
           vis[u][b] = true;

            for(auto[v,w] : g[u]){
                ll newt = d + 1LL*w*b;//花费的新时间
                int newb = min(b,s[v]);//目前的最大速度
                if(dist[v][newb] > newt){
                    dist[v][newb] = newt;
                    pq.push({newt,v,newb});
                }
            }

     }
     ll ans=INF;
     for(int b = 1; b <= 1000; b++){
        ans=min(ans, dist[n-1][b]);
     }
     cout<<ans<<endl;
     }
}

5 Tree query{

题意：有一棵树，并给出k个点，求树上是否存在一点使得这k个点到1-n的这条路径的距离不超过1
思路：如果一个点到1-n这条链上的距离不超过1，就说明这个点的祖先节点一定在这条链上。因此我们可以将所有节点的DFS序预处理出来

核心思路：

Dfs[u]：每个点的入列顺序

Fa[u]: 每个点的父节点，将所有点按父节点排列

u是v的祖先：dfs[u]<dfs[v]+sz[v]&&dfs[u]>dfs[v]

如果上述条件不满足，那么最终一定不会产生合法的链

但如果我们直接去dfs的话会有爆栈的风险，一旦整棵树退化成一棵链树的话

所以我们需要用栈来模拟dfs过程，类似于bfs的入栈出栈，如果当前节点还未被访问，state==0,记录该节点的顺序并将其赋值为根节点，深度标记为1。如果已被访问那么我们需要更新该节点的深度大小，sz[u]+=sz[v]

最终答案：dfs[u]<dfs[v]+sz[v]&&dfs[u]>dfs[v]？Yes:No

}

核心代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[N],sz[N],dfs[N];
vector<int> g[N];
int order=0;
void dfn(int u){
    stack<pair<int,int>> st;
    st.push({u, 0});
    fa[u] = 0;
    while(!st.empty()){//栈模拟递归过程
        auto[u,state] = st.top(); st.pop();
        if(state==0){//如果还未标记
         dfs[u] = ++order;
         sz[u] = 1;//深度为1
         st.push({u,1});
      for(int v : g[u]){
          if(v == fa[u]) continue;
          fa[v] = u;//赋值为根节点
          st.push({v,0});
      }
        }
        else{
            for(int v : g[u]){
                if(v == fa[u]) continue;
                sz[u] += sz[v];//更新深度
            }
        }
    }
}
bool cmp(int a,int b){
    return dfs[a] < dfs[b];//按dfs序从小到大排列
}
int main(){
      int n,m;
      cin >> n >> m;
      for(int i = 1; i < n; i ++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
      }
      dfn(1);
      while(m--){
            int k;
            cin >> k;
            vector<int> node(k);
            for(int i = 0; i < k; i++){
                 cin >> node[i];
                 if(node[i] != 1) node[i] = fa[node[i]]；
            }
            sort(node.begin(),node.end(),cmp);
            bool ok = true; 
            for(int i = 1; i < k; i++){
                int u = node[i-1],v = node[i];
                 if(!(dfs[u] <= dfs[v] && dfs[v] < dfs[u] + sz[u])){//两两满足前一个是后一个的根节点且u必须包含v
                    ok = false;
                    break;
                 }
                 
            }
            cout<<(ok ? "YES" : "NO") << endl;
      }
}

6 Palindromic characteristics{

1. 题意：给定一个长度为n的字符串，规定一个子串为1级回文串当且仅当这个字符串正着读和倒着读的顺序一样，2级往上的回文串的两边都相等且两边都是自身等级-1的回文串，求一个字符串中的从1到n等级的字符串分别有多少个

2 思路：此题需要对字符串的区间进行划分得答案，且数据范围十分适宜。

状态表示：dp[i][j]，区间i到j内的最高回文串等级

状态转移：

If(ispal[i][j]) dp[i][j]=dp[i][mid]+1

如果当前的字符串为回文串，那么其等级一定和自身的左右部分有关，因此我们取左半部分，则当前区间的回文串等级为左半部分的等级+1

答案统计：cnt[dp[i][j]]++每记录到一个k等回文串就加1

最终计算：for(int i=n-1;i>=1;i--) cnt[i]+cnt[i+1] 一个更高等级的字符串一定属于更低等级的字符串，因此低等字符串个数要加上前面更高等的字符串个数

最终答案：cnt数组

3.算法：区间dp

}

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int dp[N][N],cnt[N];
bool ispain[N][N];
char s[N];
int main(){
     scanf("%s",s + 1);
     int n = strlen(s+1);
     for(int i = 1; i <= n; i++){
        dp[i][i] = 1;
        ispain[i][i] = ispain[i][i-1] = true;
        cnt[1]++;
     }

     for(int len = 2 ; len <= n; len ++){
        for(int i = 1; i + len - 1 <= n; i++){
            int j = i + len - 1;
           if(s[i]==s[j]&&ispain[i+1][j-1]){//是回文才进行计算
            ispain[i][j]=true;
            int half = len/2;
            int mid = i + half - 1;
            dp[i][j] = dp[i][mid] + 1;//等级随左半部分等级递增
            cnt[dp[i][j]]++;//个数
           }
        }
     }

   for(int i = n; i >= 1 ; i--) cnt[i] += cnt[i+1];//更高等级的回文串一定属于更低等级的回文串
   for(int i = 1; i <= n ; i++) printf("%d ",cnt[i]);
}

8.17 日总

1 Grouping increases{

2 Keshi is throwing a party{

3 Move back at a cost{

4 Bicycles{

5 Tree query{

6 Palindromic characteristics{

来日方长

评论

1 Grouping increases{

2 Keshi is throwing a party{

3 Move back at a cost{

4 Bicycles{

5 Tree query{

** 6 **Palindromic characteristics{

来日方长

评论

还没有账户？

登录

6 Palindromic characteristics{