博客广场/ 潘政勋

文章

8.16 日总

今天的题目主要涉及到最短路，区间DP，字符串哈希等多种算法 1 Hyperset{ 1. 题意：有n个卡牌，每个卡牌对应的信息有k种，其中包含”S”,””T”,”E”三种信息。我们规定，如果每三种卡牌中的信息都不相同或全都相同，那么这三张卡牌组成的集合为好集合，求最多有多少个好集合 2. 思路：Meta-set的解法与这题类似。我们可以枚举好集合中的任意两张

潘政勋发布于 2026-8-16 15:56:15

综合/学习笔记

今天的题目主要涉及到最短路，区间DP，字符串哈希等多种算法

1 Hyperset{

题意：有n个卡牌，每个卡牌对应的信息有k种，其中包含”S”,””T”,”E”三种信息。我们规定，如果每三种卡牌中的信息都不相同或全都相同，那么这三张卡牌组成的集合为好集合，求最多有多少个好集合
思路：Meta-set的解法与这题类似。我们可以枚举好集合中的任意两张卡牌，利用这两张卡牌中的信息求出第三张卡牌，如果第三张卡牌存在那么cntgood++,这里选择将题目中的三种状态替换成掩码，方便我们找到第三张卡牌：

算法：哈希hashing

}

核心代码：

掩码计算：

long long enth(const string& s){
      long long c=0;
      for(char t:s){
        c=c*3+(t=='S'?0:(t=='E'?1:2));
      }
      return c;
}
long long get(long long a,long long b,int k){
    long long t=0;
    vector<int> digit(k);
    for(int i=k-1;i>=0;i--){
        int x=a%3,y=b%3,z;
        a/=3;
        b/=3;
        if(x==y) z=x;
        else z=3-x-y;
        digit[i]=z;
    }
    for(int i=0;i<k;i++){
        t=t*3+digit[i];
    }
    return t;
}

题意：有一群人互不相识，现给出k组要求，要求第u个人和第v个人直接认识或经过自己认识的人间接认识，求对于每组要求，某个人最多能认识多少人
思路：我们可以将每个人看做图中的节点，互相直接或间接认识就是相当于他们在同一个连通块中，因此问题就转化为了如果两个人在同一个连通块，那么我们将会获得一次合并任意一个最大点数的连通块的机会，如果不在同一个连通块中那么直接合并，求最终点数最多的连通块的点数-1

连通块的点数可以将两个连通块的大小相加得到，而我们最终求得的点数是所有小连通块合并在一起后的大连通块，所以我们要对我们在合并过程中求得的连通块大小进行排序，最终的答案就是排序后的答案数组

算法：并查集

}

核心代码：

 if(find(u)==find(v)){
            exr++;
        }
       else uni(u,v);
       vector<int> size;
     for(int i=1;i<=n;i++){
        if(find(i)==i) size.push_back(sz[i]);
     }
     sort(size.rbegin(),size.rend());//按从大到小排序
     int res=0;
     for(int i=0;i<=exr&&i<size.size();i++){
            res+=size[i];//最终大小
     }

3 Greg and Graph{

题意：给定一组点与点之间的权值，并给定删除点的顺序，求每删除一个点后点与点之间的权值和最小值
思路：（由于我一开始没自学Floyd,只能遗憾卡着这道题）这里还是普及一下Floyd最短路的概念吧：

Floyd 全源最短路：

N<=500的题直接秒，唯一的不分图的最短路算法，核心思想是枚举点作为其他点的中转站，查看如果直接走i到j和从i到mid再从mid到j是否更划算

核心代码：

 for(int mid = 1; mid <= n; mid++)
    for(int i = 1; i <= n; i++)
       for(int j = 1; j <= n; j++)
         dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j]);

了解完算法以后我们再回过头来看这道题。由于一个一个删点可能导致一些原本属于连通块中的点无法到达，因此过于麻烦。但是如果我们把原本的图看成空图再一个一个加点就会很轻松。因此我们将原本题目中给的删点顺序逆序存储起来，之后用Floyd计算路径最小值，最后更新答案

算法：Floyd最短路

}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
ll dist[N][N],ans[N];
int order[N];
bool active[N];
int main(){  
        int n ;
        cin >> n;
        for(int i = 1; i <= n; i++){
               for(int j = 1; j <= n; j++){
                 cin >> dist[i][j];
               }
        }
        for(int i = 1; i <= n; i++) cin >> order[i];
        for(int step = n; step >= 1; step--){
            int mid = order[step];
            active[mid] = true;
            for(int i = 1; i <= n ; i++){
                for(int j = 1; j <= n ; j++){
                   dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j]);
                 } 
            }
            ll sum=0;
           for(int i = 1; i <= n; i++){
            if(!active[i]) continue;
            for(int j = 1; j <= n; j++){
                   if(!active[j]) continue;
                   sum += dist[i][j];
            }
           }
             ans[step] = sum;
        }
        for(int i = 1;i <= n; i++) cout << ans[i] <<' ';
}

4 The Sports Festival{

题意：有一组运动员参加跑步，现规定一个数组中的元素di=max(a1,a2,...ai)-min(a1,a2,...,ai)，求d1+d2+...+dn的最小值
思路：此题如果对区间DP不熟的话很难看出是区间DP（虽然我也不熟，但我做过）。首先看到这样的从1一直到i计算最大值和最小值的信息差我们就能想到区间划分，那为什么这题适用于区间DP呢？

首先是时间复杂度适宜。区间DP的题目时间复杂度一般都是O(n^2)或O(n^3)（这题就是O(n^3)，因为要枚举分割区间并遍历），而此题的数组长度n小于5000。此题同样涉及区间分割（因为要算某一个区间内的max(ai)-min(ai)）

为了方便当前区间di最小值的计算，我么选择对a数组进行排序

状态表示：dp[i][j]:区间i到j之间的di最大值

状态转移：dp[i][j]=min(dp[i+1][j],dp[i][j-1])+a[j]-a[i]

整个i到j的区间中属性为di的最小值，而对于前面一个区间传递过来的最小值我们需要在两个端点之间取di最小值，加上当前的最大值减最小值就是当前区间的di最小值

详情见代码：

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
ll dp[N][N];
int main(){
      int n;
      cin >> n;
      vector<ll> a(n+1);
      for(int i=1;i<=n;i++) cin >> a[i];
      sort(a.begin(),a.end());//方便快速查找最大最小值
      for(int len=2;len<=n;len++){
         for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i+1][j],dp[i][j-1])+a[j]-a[i];//当前添加要么是最大值，要么是最小值
            }
         }
      }
      cout<<dp[1][n];
}

算法：区间DP

}

5 Dijkstra?{

题意：给定一张无环图，求一个权值和最小的路径，并输出其中经过的节点标号
思路：此题是一道裸的dijkstra求最短路的问题，与普通模版的唯一区别就是需要对我们取到的最短路径的节点进行存储
算法：dijkstra最短路

}

给个模版，方便记忆：

void dj(int st,int n){
    for(int i=1;i<=n;i++){
         pre[i]=-1;
         dist[i]=INF;
    }
      priority_queue<pll,vector<pll>,greater<pll>> pq;
      dist[st]=0;
      pq.push({0,st});
      while(!pq.empty()){
           auto[d,u]=pq.top(); pq.pop();
           if(d!=dist[u]) continue;
          for(auto [v,w]:g[u]){
                if(dist[v]>dist[u]+w){//最短路径
                    dist[v]=dist[u]+w;
                    pre[v]=u;//前驱节点
                    pq.push({dist[v],v});
                }
          }
      }
}
vector<int> getpath(int st,int end){
       vector<int> path;
       if(dist[end]==INF) return path;//没有路径返回空
       for(int v=end;v!=-1;v=pre[v]){
          path.push_back(v);
          if(v==st) break;
       }
       reverse(path.begin(),path.end());
       return path;
}

6 Zuma{

题意：给定一组宝石的编号，如果其中有组成回文串的区间那么可以对其进行消除，求将整个区间消除所需的最小操作次数
思路：对于这种区间判断问题我们又可以拿出区间DP.我们知道，如果一个区间内的数可以组成回文串，那么其内部也一定是回文串，由此可以得出如果一个回文串的最小删除次数要么等于1，要么等于其内部的回文串个数，及dp[i][j]=(len==2?1:dp[i+1][j-1])

状态表示：dp[i][j]:区间i到j内的最小删除次数

状态转移：dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])区间内的最小删除次数等于其内部分段后的最小删除次数

算法：区间DP

}

核心代码：

  for(int i=1;i<=n;i++){
        dp[i][i]=1;//单个数字及是回文串
     }
     for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
           if(juw[i]==juw[j]) dp[i][j]=(len==2)?1:dp[i+1][j-1];//端点相同，要么次数为1，要么次数为内部的回文串次数
            for(int k=i;k<=j;k++){//枚举分割点
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
     }

今天的题目主要涉及到最短路，区间DP，字符串哈希等多种算法

1 Hyperset{

2 Social Network{

3 Greg and Graph{

4 The Sports Festival{

5 Dijkstra?{

6 Zuma{

评论

还没有账户？

登录