分治

51Nod 1601 完全图的最小生成树计数

Posted on

分治+字典树+MST 综合好题

标题即题意,但是不一样的是边权是点权的异或。

不可能会出什么边权也是给定的完全图最小生成树计数的啦,现在看来,也算是套路题了。
当然点数不能太多…………

不卡常才是一个好题的前提条件。写 Trie 习惯性用了类,虽然慢了一些,但也不至于太慢。

题意:
给你 n 个点的点权,边权为其异或值,要你求出最小生成树,以及最小生成树的个数。

思路:
这道题的核心思想还是分治。
我们对给定区间的点权进行处理,并假设这个区间的前面 k - 1 位全部相同。那么对于第 k 位,我们根据 01 将其划分为两个集合,这时候两个集合的前 k 位分别相同,再对这两个集合分别进行同样的处理。
其正确性不言而喻。

在处理的过程中,我们需要将两个集合之间建边,因为是MST,所以要找最小的边。将其中一个集合插入 字典树,再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值,再更新答案与边数。
最小生成树的个数只要根据乘法原理将边的数量相乘即可。

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;

int n, anscnt, val[maxn], s[maxn], t[maxn];
long long sum;

struct Trie {
    int end[maxn * 30], next[maxn * 30][2];
    int size, root;

    int newNode()
    {
        next[size][0] = next[size][1] = 0;
        end[size++] = 0;
        return size - 1;
    }

    void init()
    {
        size = 0;
        root = newNode();
    }

    void insert(int x)
    {
        int cur = root;
        for (int i = 30, y; i >= 0; i--) {
            y = (x >> i) & 1;
            if (!next[cur][y])
                next[cur][y] = newNode();
            cur = next[cur][y];
        }
        end[cur]++;
    }

    pii search(int x)
    {
        int cur = root, ans = 0;
        for (int i = 30, y; i >= 0; i--) {
            y = (x >> i) & 1;
            if (next[cur][y])
                cur = next[cur][y], ans |= (y << i);
            else
                cur = next[cur][y ^ 1], ans |= ((y ^ 1) << i);
        }
        return make_pair(ans ^ x, end[cur]);
    }
} trie;

inline void read(int& x)
{
    char ch = getchar();
    x = 0;
    while (!(ch >= '0' && ch <= '9'))
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
}

int fastPow(int x, int y)
{
    int res = 1;
    while (y) {
        if (y & 1)
            res = 1LL * res * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return res;
}

void dac(int l, int r, int dep)
{
    if (l >= r)
        return;
    if (dep < 0) {
        if (r - l + 1 >= 2)
            anscnt = 1LL * anscnt * fastPow(r - l + 1, r - l - 1) % mod;
        return;
    }
    int lc = 0, rc = 0, ans = inf, cnt = 0;
    for (int i = l; i <= r; i++) {
        if ((val[i] >> dep) & 1)
            s[lc++] = val[i];
        else
            t[rc++] = val[i];
    }
    trie.init();
    for (int i = 0; i < lc; i++)
        val[l + i] = s[i];
    for (int i = 0; i < rc; i++) {
        val[l + lc + i] = t[i];
        trie.insert(t[i]);
    }
    pii tmp;
    for (int i = 0; i < lc; i++) {
        tmp = trie.search(s[i]);
        if (ans > tmp.first)
            ans = tmp.first, cnt = tmp.second;
        else if (ans == tmp.first)
            cnt += tmp.second;
    }
    if (cnt) {
        sum += ans;
        anscnt = 1LL * cnt * anscnt % mod;
    }
    dac(l, l + lc - 1, dep - 1);
    dac(l + lc, r, dep - 1);
}

int main()
{
    anscnt = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", val + i);
    dac(1, n, 30);
    printf("%lld\n%d\n", sum, anscnt);
    return 0;
}
三元环

HDU 6184 Counting Stars

Posted on

一个三元环计数问题……
当然是转化出来的……

一开始没想到去计数三元环的思路,而是直接搜……
然后发现题目理解错了……

又发现这特么不就跟三元环数量有关么??
巧的是薛昊之前问过我三元环计数,我还特意去看了几眼。不然真的可能卡不出来。

题意:
给你一张无向图,让你计数这样的子图。
V=(A,B,C,D) , E=(AB,BC,CD,DA,AC)

思路:
一开始我以为必须是矩形,然后发现同一点的不同三元环都满足条件。
所以我只要找到这个点的所有三元环数量,任意挑出两个即可。记得去重

个人三元环计数方法如下:
首先枚举每一条遍,再判断两个端点,确定度数较少的点,从这个点进行扩展一条边,再判断这条遍的另一端是否有边与第一条边的另一端点相连。

其中有很多细节值得优化,比如说对于\( sqrt(m) \)为分界进行不同的判定。

AC Code

#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;
const int maxn = 1e5 + 5;

vector<int> G[maxn];
int link[maxn];
bool vis[maxn];

set<ll> key;
int deg[maxn];

int main()
{
    int n, m, u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        key.clear();
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            link[i]=vis[i] = false;
            deg[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            key.insert((ll)u * n + v);
            key.insert((ll)v * n + u);
            deg[u]++, deg[v]++;
        }
        int limit = sqrt(1.0 * m);
        ll ans = 0;
        for (int u = 1; u <= n; u++) {
            vis[u] = true;
            int sz = G[u].size();
            for (int i = 0; i < sz; i++)
                link[G[u][i]] = u;
            for (int i = 0; i < sz; i++) {
                int v = G[u][i];
                if (vis[v])
                    continue;
                ll sum = 0;
                if (deg[v] <= limit) {
                    int vz = G[v].size();
                    for (int j = 0; j < vz; j++) {
                        int k = G[v][j];
                        if (link[k] == u)
                            sum++;
                    }
                } else {
                    for (int j = 0; j < sz; j++) {
                        ll k = G[u][j];
                        ll val = k * n + v;
                        if (key.find(val) != key.end())
                            sum++;
                    }
                }
                ans += sum * (sum - 1) / 2;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}
欧拉图

51Nod 1967 路径定向

Posted on

首先说一下这道题的思路真的是非常巧妙。

但是,出题人脑子进shi了么,难道一定要写法和你一样才能过????

反正卡的特别紧,我到最后还有一个测试点一直超时。
时间限制是 1200s ,明显就是故意的。这种故意卡常在51Nod里巨特么多。搞不懂他们在想什么。
不觉得会在以后碰到类似的题目会故意卡我,因为很多人都是 1000 ~ 1200 的时间卡过的。

题意:
给你一个有向图,让你任意改动边的方向,使得出入度相同的点数最多。
并输出方案。

思路:
一眼看成上下界网络流。实际上这道题就是用上下界网络流改出来的,但就别想了,正解都卡着过,网络流能过?

建图方式和无汇源上下界可行流一致,跑一遍最大流即可。

下面是另一种思路。
有入度相同的特征的图还有一种,就是欧拉图,对于度数为奇数的点(以下简称奇点,反之偶点),必然不可能存在一个方案使得其出入点相同。这是必然的,那么反过来对于偶点,如果欧拉路径存在也就必然存在一个方案使得其出入度相同。
直接将所有奇点,顺序两两相连,跑一遍欧拉路径即可。

这里补充两点

  1. 奇点数量必然为偶数。因为每一条遍贡献的度数为 2 ,所以度数和为偶数。
  2. 奇点相连不会对偶点产生任何影响。

因此,我们可以得出结论,这个方案必然存在!

TLE Code

#include <stdio.h>
#include <string.h>

typedef long long ll;
const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;

namespace fastIO {
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc()
{
    static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
    if (p1 == pend) {
        p1 = buf;
        pend = buf + fread(buf, 1, BUF_SIZE, stdin);
        if (pend == p1) {
            IOerror = 1;
            return -1;
        }
    }
    return *p1++;
}
inline bool blank(char ch)
{
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int& x)
{
    char ch;
    while (blank(ch = nc()))
        ;
    if (IOerror)
        return;
    for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
        ;
}
#undef BUF_SIZE
};
using namespace fastIO;

struct node {
    int to, next;
} edges[maxm << 1];
int head[maxn], idx;

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

int deg[maxn];
char dir[maxn];

bool vis[maxm];

void dfs(int u)
{
    for (int id = head[u]; ~id; id = edges[id].next) {
        if (!vis[id]) {
            dir[id >> 1] = (id & 1) + '0';
            vis[id] = vis[id ^ 1] = true;
            dfs(edges[id].to);
        }
    }
}

int main()
{
    int n, m, u, v;
    read(n), read(m);
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    for (int i = 0; i < m; i++) {
        read(u), read(v);
        addEdge(u, v);
        deg[u]++, deg[v]++;
    }
    int ans = 0, pre = -1;
    for (int i = 1; i <= n; i++) {
        if (deg[i] & 1) {
            if (pre == -1)
                pre = i;
            else {
                addEdge(i, pre);
                pre = -1;
            }
        } else
            ans++;
    }
    for (int i = 1; i <= n; i++)
        if (!dir[i])
            dfs(i);
    printf("%d\n", ans);
    dir[m] = 0;
    puts(dir);
    return 0;
}
Havel

HDU 2454 Degree Sequence of Graph G

Posted on

Havel定理判定简单图

被上下界网络流烦傻了,暂时不想写代码太长的题。

虽然是一道水题,但也是建立在一定理论基础上的。

再科普一下简单图,没有重边没有自环的图就是简单图。区别有向图和无向图,也就是说,有向图的反向边不算重边。

给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化

可图化的判定:

\( \sum_{i=1}^{n}d_{i} mod 2 == 0 \) 。关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。

可简单图化的判定(Havel定理):

把序列排成不增序,即 \( d_1 \geq d_2 \geq \ldots \geq d_n \),则d可简单图化当且仅当
\( d' = \left{ d_2-1 , d_3-1 \ldots d_{d_1+1}-1 , d_{d_1+2} , d_{d_1+3} , \ldots d_n \right} \) 可简单图化。简单的说,把d排序后,找出度最大的点( 设度为\( d_1\) ),把它与度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。

题意:
题目很长……没怎么看,就是给你几个点,再给你每个点的度数,问你能否构成简单图。

思路:
裸题,按照定理模拟一下即可。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;

int deg[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        bool flag = true;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", deg + i);
            sum += deg[i];
            if (deg[i] >= n)
                flag = false;
        }
        if (sum & 1)
            flag = false;
        if (!flag) {
            puts("no");
            continue;
        }
        for (int i = 0; i < n; i++) {
            sort(deg + i, deg + n, greater<int>());
            int d = deg[i];
            if (d < 0 || i + d >= n) {
                flag = false;
                break;
            }
            for (int j = 1; j <= d; j++)
                deg[i + j]--;
        }
        puts(flag ? "yes" : "no");
    }
    return 0;
}
二分图染色

洛谷 1155 双栈排序

Posted on

别多说了,神题。

写不来,看得是大佬的题解
很妙,没想到用二分图染色,但是二分图染色的模型的确很适合这个题目。

不过关键还是那个判定定理。

题意:
给你一个序列,要你用两个栈给它排序,问你这个序列是否能排序成功。

思路:
上面的链接很详细,我这里简单说一蛤。
首先必须注意到判定两个数必须在两个不同的栈的充要条件。

S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

我们首先用\( O( n^2 ) \) 的复杂度预处理出必须在两个栈的位置,并对其连边,再对其染色,对没有限制的优先放在第一个栈中因为要字典序最小

通过染色判定,不能形成二分图则输出0,否则模拟输出序列。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;

int ary[maxn];
int bmin[maxn];
int color[maxn];
int st1[maxn], st2[maxn], t1, t2;

vector<int> G[maxn];

bool dfs(int u, int c)
{
    color[u] = c;
    int sz = G[u].size(), v;
    for (int i = 0; i < sz; i++) {
        v = G[u][i];
        if (!color[v] && !dfs(v, 3 - c))
            return false;
        else if (color[v] == c)
            return false;
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", ary + i);
    bmin[n] = inf;
    for (int i = n - 1; i >= 0; i--)
        bmin[i] = min(bmin[i + 1], ary[i]);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (ary[i] < ary[j] && bmin[j + 1] < ary[i])
                G[i].push_back(j), G[j].push_back(i);
    for (int i = 0; i < n; i++)
        if (!color[i] && !dfs(i, 1)) {
            puts("0");
            return 0;
        }
    int cur = 1;
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) {
            printf("a ");
            st1[++t1] = ary[i];
        } else {
            printf("c ");
            st2[++t2] = ary[i];
        }
        while (st1[t1] == cur || st2[t2] == cur) {
            if (st1[t1] == cur)
                printf("b "), t1--;
            else
                printf("d "), t2--;
            cur++;
        }
    }
    return 0;
}
无汇源上下界可行流

ZOJ 2314 Reactor Cooling

Posted on

无汇源上下界可行流的模板题。
说是模板题,其实想让它除了二分以外加点变化也是有点困难的。

关于上下界网络流的问题,以前偷懒没学,本来打算这几天补上,加上今天薛昊这个催化剂又来问我,于是就今天开始补了。

在这里我非常非常非常非常非常推荐这篇博文
总结的非常详细,写的有十分通俗易懂,全文十分连贯,评论也有人说看完给人一种荡气回肠的感觉。
当我看完无汇源上下界可行流的时候,我马上敲了一蛤这道题,就一 A 了。妙啊!

下面简单说一下无汇源上下界可行流的解法,不详细说明,具体请看上面的链接。
无汇源上下界可行流可用建图+最大流解决,建图方式如下:

  • 对每个给定的边建边,容量为 up - down
  • 记录每个点的 down 流量差,这里设 入流量为正,出流量为负。如果总的流量差大于0,建边 src -> 该点,容量为流量差。否则,建边 该点 -> des 容量为流量差的负值。

没了,再跑一遍最大流,如果能满流就说明有可行流,否则无解。

题意:
无汇源上下界可行流裸题。

思路:
见上。

AC Code

#include <bits/stdc++.h>

using namespace std;

using namespace std;
const int maxn = 204;
const int maxm = 4e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, src, des, idx;
int cur[maxn], level[maxn], head[maxn];
int cap[maxm];

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

queue<int> que;

int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], 0);
    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 ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= des; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

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

int deg[maxn], down[maxm];

int main()
{
    int T, u, v, up;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        init(0, n + 1);
        memset(deg, 0, sizeof deg);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d", &u, &v, &down[i], &up);
            addEdge(u, v, up - down[i]);
            deg[u] -= down[i], deg[v] += down[i];
        }
        int sum = 0;
        for (int i = 1; i <= n; i++)
            if (deg[i] > 0) {
                addEdge(src, i, deg[i]);
                sum += deg[i];
            } else
                addEdge(i, des, -deg[i]);
        if (dinic() < sum) {
            puts("NO");
        } else {
            puts("YES");
            for (int i = 0; i < m; i++)
                printf("%d\n", edges[i << 1 | 1].cap + down[i]);
        }
    }
    return 0;
}
AC自动机

ZOJ 3228 Searching the String

Posted on

AC自动机吼题

虽然是很常规的模式串与匹配串的匹配计数问题,但它稍微给了一个新花样和一些坑。
写完这题,我当时就很感慨,如果我能在多校之前写过这题就好了……

题意:
先给你一个匹配串,再给你很多模式串,模式串前都有标号。标号为 0 表示计数可重叠,标号为 1 表示计数不可重叠。

思路:
写不来呀…………
看了题解,kuangbin只说了一句,加一个数组维护一下就好了…………这特么怎么维护…………

看了代码大致能理解,开了一个 last 数组记录每个位置上一次被匹配时的位置。
如果匹配串的位置与AC自动机上的相应位置的上一匹配位置差距为这个模式串的长度以上,说明可以匹配。
特别想要详细说,但又觉得没有什么好说的,所谓大道至简,原理真的很简单。

AC Code

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

using namespace std;

const int max_n = 6e5 + 10;
const int max_c = 26;
int mp[max_n / 6], sel[max_n / 6];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int dep[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
        dep[root] = 0;
    }

    int insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i] - 'a';
            if (!next[now][c]) {
                next[now][c] = newNode();
                dep[next[now][c]] = dep[now] + 1;
            }
            now = next[now][c];
        }
        end[now] = true;
        return now;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int ans[max_n][2];
    int last[max_n];
    void query(char str[], int n)
    {
        memset(ans, 0, sizeof ans);
        memset(last, -1, sizeof last);
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            now = next[now][str[i] - 'a'];
            int cur = now;
            while (cur != root) {
                if (end[cur]) {
                    ans[cur][0]++;
                    if (i - last[cur] >= dep[cur]) {
                        last[cur] = i;
                        ans[cur][1]++;
                    }
                }
                cur = fail[cur];
            }
        }
        for (int i = 0; i < n; i++)
            printf("%d\n", ans[mp[i]][sel[i]]);
        puts("");
    }
} aho;

char str[max_n], buf[10];

int main()
{
    int n, cas = 0;
    while (scanf("%s", str) != EOF) {
        scanf("%d", &n);
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%d %s", sel + i, buf);
            mp[i] = aho.insert(buf);
        }
        aho.build();
        printf("Case %d\n", ++cas);
        aho.query(str, n);
    }
    return 0;
}