思路

• $Floyd$ 算法的模板题目。

• 是基于动态规划思想，$dp[k,i,j]$ 表示经过前 $k$ 个点从点 $i$ 到点 $j$ 的最短路径，有状态转移方程 $dp[k][i][j]=min(dp[k-1][i][k]+dp[k-1][k][j],dp[k-1][i][j])$ 。可以优化掉第一个维度。

• 时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n^2)$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=210;
int dist[N][N];
int n,m,k;
void floyd(){
    int i1,i2,i3;
    for(i1=1;i1<=n;i1++){
        for(i2=1;i2<=n;i2++){
            for(i3=1;i3<=n;i3++){
                dist[i2][i3]=min(dist[i2][i3],dist[i2][i1]+dist[i1][i3]);
            }
        }
    }
}
int main(void){
    memset(dist,0x3f,sizeof dist);
    scanf("%d%d%d",&n,&m,&k);
    int i,j;
    int x,y,z;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        dist[x][y]=min(z,dist[x][y]);
    }
    for(i=1;i<=n;i++) dist[i][i]=0;
    floyd();
    for(i=1;i<=k;i++){
        scanf("%d%d",&x,&y);
        if(dist[x][y]<INF/2) cout<<dist[x][y]<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}

E. MEX vs DIFF
题意：给定一个数组a[], n个元素，最多能操纵k次，把任何数字变成一个非负整数，使得diff(a) - mex(a)最小, diff(a):为数组中不同元素的个数。
思路：
考虑使得diff(a) - mex(a)减少， 若mex(a) = x,那么[0, x - 1]必出现。 所以可以转化为 >= mex 的不同元素的个数。
可以贪心使得mex尽可能变大，然后在此条件下，尽量用 >= mex的数去填补空缺，同样为了使得ans最优，那么就要优先使用出现次数最小的>=mex的数，因为此值都可拿去填补空缺，那么diff + t - 1, mex + t 最优解会减少1 ,否则diff + t, mex + t, 最优解保持不变。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <unordered_map>

#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eb push_back()
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
ll a[maxn];
map <ll, int> mp;
int main() //O(n) O(nlogn)
{   
    int T;
    scanf("%d", &T);
    while(T --)
    {
        int n, k;
        scanf("%d %d", &n, &k);
        int temp = k;
        mp.clear();
        for(int i = 1 ; i <= n ; i ++)
        {
            scanf("%lld", &a[i]);
            mp[a[i]] ++;
        }
        int mex = 0;
        for(int i = 0 ; i <= n ; i ++)
        {
            if(mp.count(i))
            mex ++; // mex = 1
            else 
            {
                if(k == 0)
                break;
                if(k > 0)
                k --, mex ++; // mex = 2
            }
        }
        vector <int> alls;
        for(auto t : mp)
        {
            if(t.first > mex - 1)
            alls.push_back(t.second);           
        }
        sort(alls.begin(), alls.end());
        int cnt = 0;
        for(int i = 0 ; i < alls.size() ; i ++)
        {
            if(temp >= alls[i])
            {
                temp -= alls[i];
                cnt ++; 
            }   
            else break;
        } 
        printf("%d\n", int(alls.size()) - cnt);
    }
    return 0;
}

长度最小的子数组

长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //通过双指针
        int res=Integer.MAX_VALUE;
        int sum=0;
        for(int i=0,j=0;i<nums.length;i++){
            sum+=nums[i];
            while(sum>=target){
                res=Math.min(res,i-j+1);
                sum-=nums[j++];
            }
        }
        return res==Integer.MAX_VALUE? 0:res;
    }
}

算法

(区间DP) $O(n^3)$

本题本质上和 金字塔 一样
唯一的区别就是 dfs序 的定义不同

由于 dfs序 是连续区间，所以可以将整颗树按嵌套关系做如下划分：

$a, b, c$ 分别对应相应子树的根节点，需要满足 $a \leqslant b \leqslant c$

记 dp[l][r] 表示区间 $[l, r)$ 中满足存在某子树的 dfs序列 是 $\{A_l, \cdots, A_{r-1}\}$ 的树的个数

将 $A_l$ 作为根节点，然后再对 $[l+1, r)$ 做划分

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;

mint dp[505][505];

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    rep(i, n+1) dp[i][i] = 1;

    for (int w = 1; w <= n; ++w) {
        rep(l, n) {
            int r = l+w;
            if (r > n) break;
            dp[l][r] = dp[l+1][r];
            for (int k = l+2; k < r; ++k) {
                if (a[l+1] < a[k]) {
                    dp[l][r] += dp[l+1][k]*dp[k-1][r];
                }
            }
        }
    }

    cout << dp[0][n].val() << '\n';

    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int s[N];//先用来存储a[i],再变为前缀和
int f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];
    //len=1不需要了，因为f[i][i]==0,这已经在全局变量f[N][N]里了
    for(int len=2;len<=n;len++)//先枚举长度，因为后面枚举k时，要用到前面已经求得的长度更小的f[l][k]+f[k+1][r];
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int l=i,r=i+len-1;
            f[l][r]=1e8;//先初始化一个较大的数
            for(int k=l;k<r;k++)//枚举分界线
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

直接裸的堆优化dijkstra

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
#define L 0x3f
int e[N],ne[N],w[N],h[N],idx;
int dis[N];
int st[N];
int n,m;
typedef pair<int,int> PII;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
    memset(dis,L,sizeof dis);
    dis[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int ver=t.second;
        if(st[ver]) continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[ver]+w[i])
            {
                dis[j]=dis[ver]+w[i];
                q.push({dis[j],j});
            }
        }
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d %d",&n,&m);
    while(m--)
    {
        int a,b,c;
         scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra();
    printf("%d",dis[n]);
    return 0;
}

高精度加法

• 高精度存储：先存低位，再存高位。下标为0对应个位，下标为1对应十位，以此类推。
• 进位：(A[i] + B[i] + t) / 10 (实际上是0或者1，不会出现其它值，因为进位从一开始就是0或者1，接下来每一位的A[i] + B[i] + t最大是9 + 9 + 1 = 19，进位也是1)
• 本位留下：(A[i] + B[i] + t) % 10

代码

#include<iostream>
#include<vector>
using namespace std;

vector<int> add(const vector<int> &a, const vector<int> &b) {
    vector<int> c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}


int main() {
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');

    vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i --) cout << C[i];

    return 0;
}

思路

• $SPFA$ 的简单变形题目。
• 因为问题是找是否存在负环，那么每个点都可能是负环中的一个起点，所以 $dist[i]$ 表示从任意点到 $i$ 所需的最短路径，同时用 $cnt[i]$ 表示到点 $i$ 经过的最短路径上边的数目。
• 当 $dist[x]>dist[y]+w$ 时，我们进行更新：$dist[x]=dist[y]+w , cnt[x]=cnt[y]+1$ 。
• 当每次对 $cnt[i]$ 进行更新后，进行判断 $cnt[i]>=n$ ，如果满足，由鸽笼定理知一定有负环。
• 时间复杂度为 $O(n+m)$ ，空间复杂度为 $O(n+m)$ 。

AC代码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=2010;
vector<PII> v[N];
int dist[N],cnt[N];
bool st[N];
int n,m;
bool spfa(){
    int i;
    queue<int> q;
    for(i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }
    while(!q.empty()){
        int t=q.front();
        st[t]=false;
        q.pop();
        for(i=0;i<v[t].size();i++){
            int t1=v[t][i].x,t2=v[t][i].y;
            if(dist[t1]>dist[t]+t2){
                dist[t1]=dist[t]+t2;
                cnt[t1]=cnt[t]+1;
                if(cnt[t1]>=n) return true;
                if(!st[t1]){
                    st[t1]=true;
                    q.push(t1);
                }
            }
        }
    }
    return false;
}
int main(void){
    int i,j;
    scanf("%d%d",&n,&m);

    int x,y,z;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
    }
    bool ans=spfa();
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 2010;
PII a[N],b[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int x,y;
        cin >> x >> y;
        a[i] = {x,y};
    }
    for (int i = 1; i <= n; i ++ )
    {
        int x,y;
        cin >> x >> y;
        b[i] = {x,y};
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int i = 1,j = 1;
    int ans = 0;
    while(i <= n && j <= n)
    {
        int a1 = a[i].first,a2 = a[i].second;
        int b1 = b[j].first,b2 = b[j].second;
        if(a2 >= b1 && b2 >= a1)
        {
            ans += (min(a2,b2) - max(a1,b1));
        }
        if(b2 < a2) j++;
        else i++;
    }
    cout << ans << endl;
    return 0;

}