GDNOJ – DAY 10

Posted on By 张, 高畅 GDNOJ – DAY 10无评论

将碎石一块叠一块 如此堆砌起来
饱受风吹雨打的心 如同晚霞
总有一天会找到 仍然坚信能找到
如此纯洁 天真 又淡然
— Azari,D/N/A

原题移步题单，以简介页更新为准。

[T1]

DP 是不可能 DP 的，这辈子都不可能。

好吧这题真的是DP。

首先从贪心上思考，一定是倒着做而不是正着做，原因是倒着做能够将要往前调的字符先取出来不塞回去，等到匹配到相同字符的时候塞回的那位，这样能够保证总步数最少。

然后发现直接吊着一直不放回去是不行的，考虑 DP。

以下我们设原串为 S, 答案串是 T。

设 f_{i,j} 表示 对于 S 串已经拿出或匹配上了 i 到 n 位 且 T 串已经匹配上了 j 到 n 位的情况下所需要的最小步数。

初始条件好写，就是 T 串都没匹配上的情况，即 \forall i \in [1, n + 1], f_{i, n + 1} = n – i + 1。

接下来考虑转移，分三种情况。

  • $S_i = T_j$ 情况下直接匹配，即 $f_{i,j} \leftarrow f_{i + 1, j + 1}$。
  • $S_{[i,n]}$ 的 $T_j$ 个数 大于等于 $T_{[j, n]}$ 的 $T_j$ 个数，换言之之前拿出来的 $T_j$ 比之前匹配的多，判断这点用前缀和 $O(1)$ 判断就行，有 $f_{i, j} \leftarrow f_{i,j + 1}$。
  • 把 S_i 拿出去，步数增加，即 f_{i, j} \leftarrow f_{i + 1, j} + 1。

把以上三者取 \min，O(n^2) DP，答案显然是 f_{1, 1}。

方案的记录，直接记录 DP 的前驱，正如无数次看到的最短路路径记录方法一样，把拿出来的 S_i 记录下来。

至于方案的输出，由于可以 O(n ^ 2)，直接从前往后做，碰到字符不相等的时候，查找当前位置之后 被记录下来的 且与当前字符相等的换过去，直接 O(n) 暴力换就行。

具体实现见代码，但是代码与上述 f_{i, j} 两维是反的

如果这题知道用 DP 做，其实就赢了一半人，因为大部分都死在贪心的路上。

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
typedef pair<int, int> PII;
#define x first
#define y second
//1 -> 0
int n, cnt[2][30][N], flag[N];
int f[N][N];//0从n匹配到i, 1从n拿出到 j 两者得到最小代价 
PII pre[N][N];
char str[2][N];
void work()
{
    memset(f, 0x3f, sizeof f); 
    scanf("%s%s", str[0] + 1, str[1] + 1);
    n = strlen(str[0] + 1);
    for (int op = 0; op < 2; op ++)
    {
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 0; j < 26; j ++)cnt[op][j][i] = cnt[op][j][i - 1];
            cnt[op][str[op][i] - &#039;a&#039;][i] ++;
        }
    }
    for (int i = 1; i <= n + 1; i ++)
    {
        f[n + 1][i] = n - i + 1;
        flag[i] = 0;
    }
    for (int i = n; i; i --)
    {
        for (int j = i; j; j --)
        {
            if (str[0][i] == str[1][j] && f[i][j] > f[i + 1][j + 1])
            {
                f[i][j] = f[i + 1][j + 1];
                pre[i][j] = {i + 1, j + 1};
            }
            if (cnt[0][str[0][i] - &#039;a&#039;][n] - cnt[0][str[0][i] - &#039;a&#039;][i - 1] <= cnt[1][str[0][i] - &#039;a&#039;][n] - cnt[1][str[0][i] - &#039;a&#039;][j - 1] && f[i][j] > f[i + 1][j])
            {
                f[i][j] = f[i + 1][j]; 
                pre[i][j] = {i + 1, j};
            }
            if (f[i][j] > f[i][j + 1] + 1)
            {
                f[i][j] = f[i][j + 1] + 1;
                pre[i][j] = {i, j + 1};
            }
        }
    }
    printf("%d\n", f[1][1]);
    PII cur = {1, 1};
    while (cur.x <= n && cur.y <= n)
    {
        PII nxt = pre[cur.x][cur.y];
        if (cur.x == nxt.x && cur.y + 1 == nxt.y)flag[cur.y] = 1;
        cur = nxt;
    }
    for (int i = cur.y; i <= n; i ++)flag[i] = 1;
    for (int i = 1; i <= n; i ++)
    {
        if (str[0][i] != str[1][i])
        {
            int pos = i + 1; 
            for (int j = i + 1; j <= n; j ++)
            {
                if (flag[j] && str[0][i] == str[1][j])
                {
                    pos = j;
                    break;
                }
            }
            for (int j = pos; j > i; j --)
            {
                swap(str[1][j - 1], str[1][j]);
                swap(flag[j - 1], flag[j]);
            }
            printf("%d %d\n", pos, i);
        }   
    }
}
int main()
{
    freopen("chinese.in", "r", stdin);
    freopen("chinese.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T --)work();
    return 0;
}

[T3]

谁家提高组模拟赛放费用流。

首先考虑贪心/反悔贪心，然后发现没有策略是正确的。

然后考虑是不是 DP，然后发现限制太多，没办法做。

然后就不知道为什么想到了费用流，甚至还是一个非常离谱的构图方案。

我们将第 i 天的决策放到 i 到 i + 1 这一条边上。

先介绍构图方案，后面介绍为什么这样做。

  1. 源点 S 向 1 连一条边，流量 \infty，费用为 0。
  2. $n + 1$ 向汇点 $T$ 连一条边，流量 $\infty$，费用 $0$。
  3. $\forall i \in [1, n]$ 连接 $(i, i + 1)$， 流量 $\infty – a_i$，费用 $0$。
  4. $\forall i \in [1, m]$ 连接 $(s_i, t_i + 1)$， 流量 $\infty$，费用 $w_i$。

第一条和第二条很好理解。

对于第三条和第四条，首先我们可以看出，这个图的最大流一定是 \infty。

而要在这个前提下费用最少，首先一定是走第三条所构造的边。

但是我们发现第三条所构造的边流量往往是达不到 \infty 的，因此不得不走第四条所构造的边来补全流量到 \infty。

然后上一个最小费用最大流的板子就完成了，但是网络流是NOI级里的 8 级考点，理论上不属于提高组内容。

代码和最小费用最大流基本一样，除了人类智慧的建图。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5005, M = 100005;
const LL INF = 1e14;
int n, m, S, T;
int h[N], e[M], ne[M], idx;
LL f[M], d[N], w[M], incf[N];
int q[N], pre[N], st[N];
void add(int a,int b, LL c, LL d)
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0,w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
int spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while(hh != tt)
    {
        int u = q[hh++];
        if(hh == N)hh = 0;
        st[u] = 0;
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(f[i] && d[j] > d[u] + w[i])
            {
                d[j] = d[u] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[u]);
                if(!st[j])
                {
                    q[tt ++] = j;
                    if (tt == N) tt = 0;
                    st[j] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
void EK(LL &flow, LL &cost)
{
    flow = cost=0;
    while (spfa())
    {
        LL t = incf[T];
        flow += t;
        cost += t * d[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    S = 0, T = n + 2;
    add(S, 1, INF, 0);
    add(n + 1, T, INF, 0);
    for (int i = 1; i <= n; i ++)
    {
        LL x;
        scanf("%lld", &x);
        add(i, i + 1, INF - x, 0);
    }
    for (int i = 1; i <= m; i ++)
    {
        int l, r;
        LL w;
        scanf("%d%d%lld", &l, &r, &w);
        add(l, r + 1, INF, w);
    }
    LL flow, cost;
    EK(flow, cost);
    printf("%lld", cost);
    return 0;
}

[T2]

不会DP不会DP不会DP。

你这DP怎么还带优化。

首先一看就是最短路，然后开开心心最短路之后发现得到了 73 pts。

原因是显然的，因为有太多边了，最高能够达到 m ^ 2 条。

考虑第一问仍然最短路，但是把边拆的细一点。

接下来重点是第二问。

我们建立出最短路树，然后将最短路树上连续的线路拆下来维护。

（可以这么理解，就是如果最短路树用了同一段线路上不同的两段，我们视为它们是不同的线路，分别维护）

我们设 f_u 表示目前到 u 情况下答案最大是多少。

朴素地，我们可以暴力枚举和 u 在 同一条线路上 且在 u 前序的节点 v，有 f_u = \max(f_v + (dist_u – dist_v) ^ 2)。

直接枚举转移是 O(n ^ 2) 的，太暴力了。

考虑斜率优化，如果 i 处转移优于 j，那么有：

$$f_i + dist_u ^ 2 + dist_i^2 – 2 \cdot dist_u dist_i – f_j – dist_u ^ 2 – dist_j^2 + 2 \cdot dist_u dist_j \geq 0$$

化成斜率优化的形式：

$$\frac{(f_i + dist_i^2) – (f_j + dist_j^2)}{dist_i – dist_j} \geq 2 \cdot dist_u$$

这个东西用单调栈维护就行了。

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e6 + 5;
typedef long long LL;
const LL INF = 1e14;
typedef pair<LL, int> PLI;
typedef long double LD;
int n, m, st[N], pos[N];
LL dist[N], f[N];
struct node
{
    int u, v;
    LL w;
};
vector<node> tr[N], ntr[N];
vector<PLI> G[N];
vector<int> id[N], stk[N];
int cmp(int a, int b){return dist[a] < dist[b];}
inline LL X(int x){return dist[x];}
inline LL Y(int x){return f[x] + (dist[x] * dist[x]);}
LD get_slope(int a, int b){return 1.0 * (Y(b) - Y(a)) / (X(b) - X(a));}
void dijkstra()
{
    priority_queue<PLI, vector<PLI>, greater<PLI> > q;
    for (int i = 1; i <= n; i ++)
    {
        dist[i] = INF;
        pos[i] = i;
    }
    q.push({dist[1] = 0, 1});
    while (q.size())
    {
        PLI u = q.top();
        q.pop();
        int ver = u.second;
        if (st[ver])continue;
        st[ver] = 1;
        for (PLI t : G[ver])
        {
            if (dist[t.y] > dist[ver] + t.x)q.push({dist[t.y] = dist[ver] + t.x, t.y});
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++)
    {
        int cnt, last;
        scanf("%d%d", &cnt, &last);
        for (int j = 1; j <= cnt; j ++)
        {
            int w, cur;
            scanf("%d%d", &w, &cur);
            tr[i].push_back({last, cur, w});
            G[last].push_back({w, cur}); 
            last = cur;
        }
    }
    dijkstra();
    int cnt = 0;
    for (int i = 1; i <= m; i ++)
    {
        for (auto item : tr[i])
        {
            if (dist[item.v] == dist[item.u] + item.w)ntr[cnt].push_back(item); 
            else if (ntr[cnt].size())cnt ++;
        }
        if (ntr[cnt].size())cnt ++;
        tr[i].clear();
    }
    for (int i = 0; i < cnt; i ++)
    {
        if (ntr[i].size())
        {
            id[ntr[i][0].u].push_back(i);
            for (auto j : ntr[i])id[j.v].push_back(i);
        }
    }
    sort(pos + 1, pos + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
    {
        int cur = pos[i];
        if (dist[cur] == INF)continue;
        for (int j : id[cur])
        {
            while (stk[j].size() > 1 && get_slope(stk[j][stk[j].size() - 2], stk[j].back()) < 2.0 * dist[cur])stk[j].pop_back();
            if (stk[j].size())f[cur] = max(f[cur], f[stk[j].back()] + (dist[cur] - dist[stk[j].back()]) * (dist[cur] - dist[stk[j].back()]));
        }
        for (int j : id[cur])
        {
            while (stk[j].size() > 1 && get_slope(stk[j][stk[j].size() - 2], stk[j].back()) < get_slope(stk[j].back(), cur))stk[j].pop_back();
            stk[j].push_back(cur); 
        }
    }
    printf("%lld %lld\n", dist[n], f[n]);
    return 0;
}
训练日志

发表回复