最小割

51Nod 1499 图

Posted on

emmmmmmm不错的的最小割吧
唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。

题意:
有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。
两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。

思路:
题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。
而跟二分图相关的只有网络流了,将图分为两半是割的概念,当然只存在最小割,正面去想的话,就是总权值和-最小割。

然后……思路就断了,找不到有效的建图方法。

可以先这么想,我们假定与源点相连的点集为相连增加权值的集合,并称之为,与汇点相连的点集则相反,称之为汇点集。
那么我们先将每个点都与源点相连,其容量为将该点加入源点集所能增加的权值。
再将这个点与汇点相连,其容量为将该点加入汇点集所能增加的权值。

此时直接跑最小割是不对的,因为这些点并不是独立的。

其实只要再将任意两个点都连边就可以了。

啊,顺便发现一个,换一种无向图建边,速度快了一倍,因为边几乎少了一半

AC Code

#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e3 + 5;
const int maxm = 5e6 + 5;
const int inf = 0x3f3f3f3f;

int src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

void addEdge(int u, int v, int c, int rc = 0)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], rc);//无向边建边小技巧
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic(int n)
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= n + 1; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int s, int d)
{
    memset(head, -1, sizeof head);
    idx = 0;
    src = s, des = d;
}

bool g[maxn][maxn];
int s[maxn], t[maxn];

inline void scan_d(int& num)
{
    char in;
    in = getchar();
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
}

int main()
{
    int n, m, u, v, tmp;
    scan_d(n), scan_d(m);
    init(0, n + 1);
    while (m--) {
        scan_d(u), scan_d(v);
        g[u][v] = g[v][u] = true;
    }
    range(i, 1, n) range(j, i + 1, n)
    {
        tmp = j - i;
        if (g[i][j])
            s[i] += tmp, s[j] += tmp;
        else
            t[i] += tmp, t[j] += tmp;
        addEdge(i, j, tmp, tmp);
    }
    int ans = 0;
    range(i, 1, n) addEdge(src, i, s[i]), addEdge(i, des, t[i]);
    range(i, 1, n) ans += (1 + n - i) * (n - i) / 2;
    printf("%d\n", ans - dinic(n) / 2); //因为与源点汇点相连的点增加了一倍权值
    return 0;
}
强联通分量

CodeForces 864F Cities Excursions

Posted on

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。

题意:
给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。

思路:
首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。
但是值得注意的是,点数比较少,只有$3000$个,假如我们固定起点,遍历全图来获得路径,在遍历的同时,对每一个点来记录答案。理想复杂度为$O(N^2)$,时间上满足条件。

一个问题是如何保证字典序最小,emmmm
用vector记录整张图,对于每个点的边进行排序,因为每个点访问一次,解决之。

这题还有一个合理的大坑,如果在遍历的时候,在之前已经出现了一个环,那么之后的所有点就都不会被访问。
当然你不能在找到一个环后,后面的点就不再遍历,这样会使最小字典树发生变化,会导致错误答案。
好题啊。

以上。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e3 + 5;
const int maxq = 4e5 + 5;

struct Item {
    int u, v, q, id;
    bool operator<(const Item& item) const { return u < item.u; }
} items[maxq];

int dfn[maxn], low[maxn], vis[maxn], vtm;
int path[maxn], ans[maxq];
vector<int> G[maxn];
vector<Item> qary[maxn];

void tarjan(int u, int dep, bool cant)
{
    path[dep] = u;
    low[u] = dfn[u] = ++vtm;
    vis[u] = 1;
    int sz = qary[u].size();
    if (!cant)
        each(i, sz)
        {
            Item& item = qary[u][i];
            if (item.q <= dep)
                ans[item.id] = path[item.q];
        }
    sz = G[u].size();
    each(i, sz)
    {
        int v = G[u][i];
        if (!vis[v]) {
            tarjan(v, dep + 1, cant | (low[u] < dfn[u]));
            low[u] = min(low[u], low[v]);
            cant |= (low[v] < dfn[v]);
        } else if (vis[v] == 1)
            low[u] = min(low[u], dfn[v]);
    }
    vis[u] = 2;
}

int main()
{
    int n, m, q, u, v;
    scanf("%d %d %d", &n, &m, &q);
    each(i, m)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    range(i, 1, n) sort(G[i].begin(), G[i].end());
    each(i, q)
    {
        Item& item = items[i];
        scanf("%d %d %d", &item.u, &item.v, &item.q);
        item.id = i;
    }
    sort(items, items + q);
    fill(ans, -1);
    each(i, q)
    {
        Item& item = items[i];
        qary[item.v].push_back(item);
        if (i == q - 1 || item.u != items[i + 1].u) {
            vtm = 0, fill(vis, 0);
            tarjan(item.u, 1, false);
            range(j, 1, n) qary[j].clear();
        }
    }
    each(i, q) printf("%d\n", ans[i]);
    return 0;
}
树形DP

CodeForces 19E Fairy

Posted on

一道二分图性质的应用 + 树形DP ?

看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些

题意:
给你一个图,让你删除一条边,使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路:
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写,最后无奈去看题解了……

先整理一下判断思路:

  1. 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件
  2. 覆盖了所有的奇环,并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环,这个我还真没想到,但是在纸上画一画就是很显然的了,同时覆盖奇环和偶环的边删去后,两个环会变成一个新的环,偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现,随便生成一棵生成树,用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ,那么非树边必定不可能是满足条件的,因为非树边最多只能覆盖一个环,两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑,如果该非树边覆盖了奇环,则删之。
而对于树边,判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

void addEdge(int u, int v)
{
    edges[idx] = make_pair(v, head[u]);
    head[u] = idx++;
    edges[idx] = make_pair(u, head[v]);
    head[v] = idx++;
}

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}
后缀数组

POJ 3415 Common Substrings

Posted on

后缀数组 + 单调栈好题
网络赛时的后缀数组可以用这个思路解,但是我并不是很会,今天补上。

题意:
给你两个串,问你长度不小于 k 的重复子串的数量。

思路:
若只是对于一个字符串,问它长度不小于 k 的重复子串数量,那么考虑对height根据 k 分组,然后记录一下就可以了,将 height 去重后,每个 height 的贡献为 \( max ( 0, height - k +1 ) \) 个人猜测,后果不计

但这题是两个字符串,我们可以将两个字符串用一个特殊字符连接,并将后缀通过第一个字符串长度区分开来,对于同一个 height 组中,当前的 height 只能跟另一个 height 组相比求 lcp 。
一个可行的方法是,将组内不同的height都记录下来,再对于每一个当前height,我把它跟另一个height组一一求贡献。但是这个复杂度为 \( O ( n^2 ) \),显然是不行的。

最后学到的优化就是单调栈优化了,用 st[i][0]表示栈中第 i 号元素记录时候的height值,st[i][1]表示在这个height值上覆盖了st[i][1]个子串,在栈内维护height递增,实现\( O( 1 ) \) 求贡献。

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 5;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        DA(len + 1, 130);
        getHeight(len);
    }

    int st[maxn][2];
    void solve(int key, int limit)
    {
        ll tot = 0, top = 0, sum = 0;
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] < key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] > key)
                sum += tot;
        }
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] > key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] < key)
                sum += tot;
        }
        printf("%lld\n", sum);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int k;
    while (scanf("%d", &k) != EOF && k > 0) {
        scanf("%s", buf);
        int len = strlen(buf);
        buf[len] = '$';
        scanf("%s", buf + len + 1);
        suffix_array.input(buf);
        suffix_array.solve(len, k);
    }
    return 0;
}
思维

HDU 5486 Difference of Clustering

Posted on

这种题目就是专门针对我的……
思路简单,所需注意细节多。

题意:
给你每个元素所在集合,问你有多少个,分割,聚集,映射关系。

思路:
首先很直接的思路就是把每个集合的元素都表示出来,进一步的说hash一下,但集合元素多,集合数量也不少,hash有点困难。
考虑将不同集合的所有相同元素用一个元素表示 (这个只要排序去重即可)
那么对于两个存在这个相同元素的集合 A, B,有如下四种讨论情况:

  1. A有若干个元素而B没有 ----> 聚集
  2. B有若干个元素而A没有 ----> 分割
  3. A,B各自存在不同元素是另一个集合不存在的 -----> 不参与讨论
  4. 不存在相异的元素 ----> 映射

顺便提示一下集合编号在 int 范围内, 要离散化……

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
const int maxn = 2e6 + 6;

int head[maxn];
struct node {
    int to, next;
} edges[maxn];

int idx;
int deg[maxn];
pii nodes[maxn];
map<int, int> uid, vid;

bool cmp(const pii& a, const pii& b)
{
    return a.first == b.first ? a.second < b.second : a.first < b.first;
}

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

void init()
{
    memset(head, -1, sizeof head);
    memset(deg, 0, sizeof deg);
    uid.clear(), vid.clear();
    idx = 0;
}

int main()
{
    int T, n, cas = 0, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        int ui = 0, vi = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &u, &v);
            if (uid.count(u) == 0)
                uid[u] = ++ui;
            if (vid.count(v) == 0)
                vid[v] = ++vi;
            u = uid[u], v = vid[v];
            nodes[i] = make_pair(u, v);
        }
        sort(nodes, nodes + n, cmp);
        for (int i = 0; i < n; i++)
            if (i == n - 1 || nodes[i].first != nodes[i + 1].first || nodes[i].second != nodes[i + 1].second) {
                int old = nodes[i].first, now = nodes[i].second + n;
                addEdge(old, now);
                addEdge(now, old);
                deg[old]++, deg[now]++;
            }
        int ans1 = 0, ans2 = 0, ans3 = 0;
        for (int u = 1; u <= ui; u++) {
            if (deg[u] > 1) {
                bool flag = true;
                for (int id = head[u]; ~id; id = edges[id].next) {
                    if (deg[edges[id].to] != 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans1++;
            } else if (deg[u] == 1) {
                if (deg[edges[head[u]].to] == 1)
                    ans3++;
            }
        }
        for (int u = 1; u <= vi; u++) {
            if (deg[u + n] > 1) {
                bool flag = true;
                for (int id = head[u + n]; ~id; id = edges[id].next) {
                    if (deg[edges[id].to] != 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans2++;
            }
        }
        printf("Case #%d: %d %d %d\n", ++cas, ans1, ans2, ans3);
    }
    return 0;
}
后缀数组

HDU 6194 string string string

Posted on

一眼以为KMP能解,上去就是一WA……

但是我还不知道KMP的错误点……可惜看不了提交的代码了……
这道题因为我在比赛的时候被一道煞笔树形DP卡到了,因为图没清空,所以没什么时间去看,虽然最后还是有一个小时给我,但我还是没有做出来。

比赛的时候天海的解法用到了单调栈,但我看了题解还有另一个非常巧妙的做法。

题意:
给你一个字符串,问你刚好出现 k 次的子串数量。

思路:
看了大佬的题解,只给了一个方程。枚举区间为 k - 1 的 height 数组,也就是 k 的 sa,贡献为

$ max(0, lcp( i , i + k - 1 ) - max(height[ i ], height[ i + k ]) $

一开始听蒙蔽的,略加思考就察觉到了方程的正确性,对于每个区间的 LCP ,如果跟区间外的后缀一旦有重复的,那么这个公共部分就不能算及在内。因为这个部分就不是刚好出现 k 次的子串了。于是把区间 LCP 将它减去即可。

注意 k == 1 的时候需要特判。

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int mmin[maxn][17], s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len - 1) s[i] = str[i] - 'a' + 1;
        s[len] = 0;
        DA(len + 1, 28);
        getHeight(len);
    }

    void initRMQ()
    {
        for (int i = 1; i <= len; i++)
            mmin[i][0] = height[i];
        for (int j = 1; (1 << j) <= len; j++)
            for (int i = 1; i + (1 << j) - 1 <= len; i++)
                mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r)
    {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);
    }

    void work(int k)
    {
        height[len + 1] = 0;
        int ans = 0;
        for (int i = 1; i <= len - k + 1; i++)
            ans += max(0, query(i, k) - max(height[i], height[i + k]));
        printf("%d\n", ans);
    }

    int query(int id, int k)
    {
        return k == 1 ? len - sa[id] : RMQ(id + 1, id + k - 1);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %s", &n, buf);
        suffix_array.input(buf);
        suffix_array.initRMQ();
        suffix_array.work(n);
    }
    return 0;
}
思维

CodeForces 853 B Jury Meeting

Posted on

思维题,老实说我并没有想出来,应该说是我想歪了……

看了一个大佬的代码,真的是超整洁,这是我目前见过最整洁的代码。值得借鉴。

题意:
每个点距源点有几条单项路径,路径有个花费和另一个时间。要你买构造来回路径使得中间间隔时间不小于 k 。

思路:
首先按照日期排序,菜鸡第一想到的是按照花费权值排序
在相同日期的路径中找出所有花费权值最小的加入集合并维护其最小。如果集合已满就记录当前日期的花费。
一个道理在正向前往目的地来一次,反向返回来一次。
就得到了当前日期正向的的最小值,当前日期反向返回的最小值。
再正向找出当前日期之前的最小值,当前日期之后返回的最小值,使得中间区间尽可能大,越往中间花费越小。

再枚举间隔区间,将往返花费相加找出最小值就是答案。

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxd = 1e6 + 5;
const int maxn = 1e5 + 5;

int n, m, k;
int fIn[maxn], fOut[maxn];
ll minInCost[maxd], minOutCost[maxd];
ll prefix[maxd], suffix[maxd];

struct Item {
    int d, f, t, c;
    bool operator<(const Item& item) const { return d < item.d; }
} items[maxn];

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        Item& item = items[i];
        scanf("%d %d %d %d", &item.d, &item.f, &item.t, &item.c);
    }

    sort(items, items + m);

    ll total = 0;
    int cnt = 0;
    for (int i = 0; i < m;) {
        int d = items[i].d;
        for (; i < m; i++) {
            Item& item = items[i];
            if (item.d != d)
                break;
            if (item.f == 0)
                continue;
            if (!fIn[item.f]) {
                cnt++;
                fIn[item.f] = item.c;
                total += item.c;
            } else if (item.c < fIn[item.f]) {
                total -= fIn[item.f] - item.c;
                fIn[item.f] = item.c;
            }
        }
        if (cnt == n)
            minInCost[d] = total;
    }

    cnt = total = 0;
    for (int i = m - 1; i >= 0;) {
        int d = items[i].d;
        for (; i >= 0; i--) {
            Item& item = items[i];
            if (item.d != d)
                break;
            if (item.t == 0)
                continue;
            if (!fOut[item.t]) {
                cnt++;
                fOut[item.t] = item.c;
                total += item.c;
            } else if (item.c < fOut[item.t]) {
                total -= fOut[item.t] - item.c;
                fOut[item.t] = item.c;
            }
        }
        if (cnt == n)
            minOutCost[d] = total;
    }

    int D = items[m - 1].d;

    for (int i = 1; i <= D; i++) {
        prefix[i] = prefix[i - 1];
        if (minInCost[i])
            prefix[i] = prefix[i] ? min(prefix[i], minInCost[i]) : minInCost[i];
    }

    for (int i = D; i > 0; i--) {
        suffix[i] = suffix[i + 1];
        if (minOutCost[i])
            suffix[i] = suffix[i] ? min(suffix[i], minOutCost[i]) : minOutCost[i];
    }

    ll ans = -1;
    for (int i = 1; i + k + 1 <= D; i++) {
        if (prefix[i] && suffix[i + k + 1]) {
            ll res = prefix[i] + suffix[i + k + 1];
            ans = ans != -1 ? min(ans, res) : res;
        }
    }
    printf("%lld\n", ans);
    return 0;
}