算法

(区间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;

}

思路

• 二分
  • 二分范围：[-100, 100]
  • 浮点数二分

易错点

• 对于一个数n，其立方根不一定在区间[0, n]内，比如0.001的立方根是0.1。这里容易想当然地用[0, n]作为二分范围，就会出错

代码

#include<iostream>
using namespace std;

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

    double l = -100, r = 100;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid > n) r = mid;
        else l = mid;
    }
    printf("%.6lf", l);

    return 0;
}

我们考虑分层图。

分层图，顾名思义就是将图分层。而对应到当前这道题，就是在层之间正常连边（不免费），每一层与下一层之间连单向且边权为 $0$ 的边（免费），总共的层数为 $k + 1$（最多免费 $k$ 次），如在样例的基础上建出的图就是：（从洛谷里抄的图片）

随后，循环可能的免费航线数量（循环范围 $0 \sim k$，循环变量为 $i$），求出从 $s$ 节点到 $t + n \times i$ 的最短距离的最小值，公式化的来说就是：答案是：$\min\limits _ {i = 0} ^ k \lbrace \text{dis}(s, t + n \times i) \rbrace$（$\text{dis}$ 函数代表求两个节点之间的距离）

此处还有一个优化点：可以用Dijkstra+堆优化算法一次性求出 $s$ 点到所有点的最短距离，求答案的时候直接调用 $dis$ 数组即可

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
#include <queue>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, INF_BIT = 0x3f;

const int N = 1.1e5 + 10, M = 2.5e6 + 10;

int n, m, k;
int st, ed;
int u, v, w;

struct Node{
    int from, to, len, next;
};
Node a[M];
int ind;
int pre[N];
void add(int u, int v, int w){
    ind++;
    a[ind].from = u;
    a[ind].to = v;
    a[ind].len = w;
    a[ind].next = pre[u];
    pre[u] = ind;
}

int dis[N];
bool vis[N];
priority_queue<PII, vector<PII>, greater<PII> > q;
void dijk(){
    memset(dis, INF_BIT, sizeof(dis));
    dis[st] = 0;
    memset(vis, false, sizeof(vis));
    q.push({dis[st], st});
    while(!q.empty()){
        int x = q.top().second, d = q.top().first;
        q.pop();
        vis[x] = true;
        for(int i = pre[x];i;i = a[i].next){
            int to = a[i].to;
            if(!vis[to] && dis[to] > d + a[i].len){
                dis[to] = d + a[i].len;
                q.push({dis[to], to});
            }
        }
    }
}

int ans = INF;

int main(){
    scanf("%d%d%d", &n, &m, &k);
    scanf("%d%d", &st, &ed);

    st++, ed++;

    for(int i = 1;i <= m;i++){
        scanf("%d%d%d", &u, &v, &w);

        u++, v++;

        for(int j = 0;j <= k;j++){
            add(u + n * j, v + n * j, w);
            add(v + n * j, u + n * j, w);
        }
        for(int j = 0;j < k;j++){
            add(u + n * j, v + n * (j + 1), 0);
            add(v + n * j, u + n * (j + 1), 0);
        }
    }

    dijk();

    for(int i = 0;i <= k;i++){
        ans = min(ans, dis[ed + i * n]);
    }

    printf("%d\n", ans);
    return 0;
}

思路

• 二分
  • 首先定好二分区间，即确定好l和r
  • 能够二分的区间：左半部分满足一个性质，右半部分满足另外一个性质。因此在二分时需要想好性质，其实等价于想好check函数怎么写
  • r = mid l = mid + 1 mid = l + r >> 1
  • l = mid r = mid - 1 mid = l + r + 1 >> 1
  • 最后得到的答案是满足check条件的边界值。
• 本题思路
  • 二分区间：[0, n - 1]
  • check函数
    • $\geq x$的边界值，即$\geq x$的最小值：a[mid] >= k
    • $\leq x$的边界值，即$\leq x$的最大值：a[mid] <= k
  • 最后得到的答案
    • a[mid] >= k ：大于等于k的边界值，即大于等于k的最小值
    • a[mid] <= k ：小于等于k的边界值，即小于等于k的最大值

代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N];

int find_st(int a[], int l, int r, int k) {
    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] >= k) r = mid;
        else l = mid + 1;
    }
    if (a[l] != k) return -1;
    return l;
}

int find_ed(int a[], int l, int r, int k) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= k) l = mid;
        else r = mid - 1;
    }
    if (a[l] != k) return -1;
    return l;
}


int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    while (q --) {
        int k;
        scanf("%d", &k);
        printf("%d %d\n", find_st(a, 0, n - 1, k), find_ed(a, 0, n - 1, k));
    }
    return 0;
}