UOJ Logo matthew99的博客

博客

《UOIP十合一》解题报告

2016-06-26 19:48:35 By matthew99

题目地址

http://uoj.ac/problem/208

Q&A

羊芳斐、牛芳斐、马芳斐、欧阳芳斐,黄瓜条以及共价大爷是谁?

羊芳斐、牛芳斐、马芳斐、欧阳芳斐,黄瓜条他们都是WC2015小品《时光2》中的角色,黄瓜条当时是由UOJ创始人之一vfleaking扮演的。

共价大爷的ID是zhangzj,是目前雅礼机房的红太阳,神通广大,无所不能,切题如麻,所向披靡。

“中国国家队以7分钟的罚时之差惜败给俄罗斯国家队”是什么典故?

这里影射WF2016上上海交通大学队以7分钟只差败给圣彼得堡州立大学队,作者出此题时WF2016刚结束不久。

每个点的做法

测试点1

容易发现,对于所有$x \rightarrow y$的边,都有$x \le y$,去掉自环后无论怎么选都不会有环,因此答案显然是2的非自环边数次幂。

测试点2

容易发现这张图是由若干个边数很少的连通块组成的,而连通块之间显然是独立的,因此答案就是每个连通块的答案乘起来,而每个连通块的答案显然可以直接暴力算。

测试点3

容易发现这张图每个连通块都只有一个环,而对于一个大小为$x$的环,答案是$2 ^ x - 1$,答案就是所有环的答案乘起来再乘上2的不在环上的点数次幂。

测试点4

容易发现这张图是由很多层组成的,每层最多4个点,且只有相邻两层之间有连边,因此我们直接状压连通性,对于两层之间的转移,可以枚举边的子集之后用Floyd或者是BFS。

测试点5

这个点如果不进行一些猜测,是很难做出来的,我们可以发现这张图每个强连通分量边数都很少,而连接两个属于不同强连通分量的点的边选和不选是没有影响的,因此可以直接将答案乘2,对于每个强连通分量我们直接暴力然后将答案乘起来即可。

什么你不会求强连通分量?因为点数少的令人感动所以直接按定义用Floyd就行了。

测试点6

这个点是一个有向完全图,对于有向完全图,我们考虑枚举最终DAG中入度为0的点是哪一些,令$a_n$表示$n$个点的有向完全图的生成DAG个数,很容易得到递推式:

$a_n = \sum_{k = 1}^{n}{\binom{n}{k}{(-1)}^{k + 1}2^{k(n - k)}a_{n - k}}$。

设$a_0 = 1$,通过递推容易求出答案。

测试点7、测试点8

这个两个点$n$都非常小,且没有重边和自环,同测试点6的思路,设$\mathrm{dp}_S$表示$S$这个子集中的生成DAG个数,那么有递推式。

$\mathrm{dp}_S = \sum_{S\prime \subset S, S\prime \ne S}{{(-1)}^{|S| - |S\prime| + 1}2^{E_{S\prime, S - S\prime}}\mathrm{dp}_{S\prime}}$。

其中$E_{S_1, S_2}(S_1 \bigcap S_2 = \emptyset)$ 表示从$S_1$中某个点连向$S_2$中某个点的边的条数。

设$\mathrm{dp}_{\emptyset} = 1$,通过递推容易求出答案。然而直接做的话时间复杂度是$O(3 ^ n n)$ 的,瓶颈在于$E$的计算。我们考虑倒过来DP,从枚举子集改成枚举超集,也就是我们用$\mathrm{dp}_{S\prime}$来反过来更新$\mathrm{dp}_S$,这样的话对应的$E$的值就很好计算了。时间复杂度降为$O(3 ^ n)$。8号点最多几分钟就可以出解。

如果时间复杂度过高或者剩余时间不够的话,可能只能做出测试点7。

测试点9、测试点10

这两个点的特点是,一开始有一个大小为$k + 1$的竞赛图,接下来所有点都与前面$k$个两两之间存在边(即要么从$a$连向$b$要么从$b$连向$a$)的点连一条方向任意的边(即要么由这个点连去要么由那个点连过来)。

容易发现进行树分解后的树宽度是$k$,且$k$很小(9号点是2,10号点是3)。

我们容易将图树分解成这样:除了根之外,每个点的集合都与父亲之差了一个点。

根据树分解的性质,我们容易设计状压DP,同测试点4,我们状压两两之间的连通性。两个子树之间的合并就是直接合并连通性。对于非根的节点我们枚举那个不在父亲的集合中的点向其他点连的边的子集然后转移,对于根我们直接枚举边的子集转移。这样就可以做出这两个点了。

如果不熟悉图树分解,直接进行一系列的思考也可以想出这两个点的做法。

程序

测试点1

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int ans = 1;
    REP(i, 0, m)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x != y) (ans <<= 1) %= Mod;
    }
    printf("%d\n", ans);
    return 0;
}

测试点2

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 5;

int n, m;

int main()
{
    scanf("%d%d", &n, &m), n /= 10, m /= 10;
    int ans = 1;
    REP(i, 0, 10)
    {
        vector<pair<int, int> > ed;
        REP(j, 0, m)
        {
            int u, v;
            scanf("%d%d", &u, &v), --u, --v, u -= i * n, v -= i * n;
            if (u != v) ed.pb(mp(u, v));
        }
        int tmp = 0;
        REP(j, 0, 1 << SZ(ed))
        {
            static bool f[maxn + 5][maxn + 5];
            memset(f, 0, sizeof f);
            REP(k, 0, SZ(ed)) if (j >> k & 1) f[ed[k].x][ed[k].y] = 1;
            REP(k, 0, n) REP(i, 0, n) if (f[i][k]) REP(j, 0, n) if (f[k][j]) f[i][j] = 1;
            bool failed = 0;
            REP(i, 0, n) REP(j, 0, i) if (f[i][j] && f[j][i]) { failed = 1; break; }
            if (!failed) ++tmp;
        }
        ans = (LL)ans * tmp % Mod;
    }
    printf("%d\n", ans);
    return 0;
}

测试点3

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 100000;

int n;
int fa[maxn + 5];

int lst[maxn + 5];
int pw[maxn + 5];

int main()
{
    scanf("%d%*d", &n);
    REP(i, 0, n) scanf("%*d%d", fa + i), --fa[i];
    pw[0] = 1;
    REP(i, 0, n) pw[i + 1] = (pw[i] << 1) % Mod;
    memset(lst, -1, sizeof lst);
    int cur = 0;
    int ans = 1;
    int cnt = 0;
    REP(i, 0, n) if (!~lst[i])
    {
        int u = i;
        while (1)
        {
            lst[u] = cur++;
            u = fa[u];
            if (~lst[u])
            {
                if (lst[u] >= lst[i])
                {
                    cnt += cur - lst[u];
                    ans = (LL)ans * (pw[cur - lst[u]] - 1) % Mod;
                }
                break;
            }
        }
    }
    ans = (LL)ans * pw[n - cnt] % Mod;
    printf("%d\n", ans);
    return 0;
}

测试点4

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 1000, maxk = 4;

int n, m, K = maxk;
int dp[maxn + 5][(1 << ((maxk * (maxk - 1)))) + 5];

int main()
{
    scanf("%d%d", &n, &m);
    n /= maxk, m /= n - 1;
    dp[0][0] = 1;
    REP(i, 0, n - 1)
    {
        vector<pair<int, int> > ed;
        REP(j, 0, m)
        {
            int u, v;
            scanf("%d%d", &u, &v), --u, --v;
            u -= i * K;
            v -= i * K;
            ed.pb(mp(u, v));
        }
        REP(j, 0, 1 << (K * (K - 1)))
            if (dp[i][j])
            {
                static bool f[(maxk << 1) + 5][(maxk << 1) + 5];
                REP(k, 0, 1 << SZ(ed))
                {
                    memset(f, 0, sizeof f);
                    int cur = 0;
                    REP(u, 0, K) REP(v, 0, K) if (u != v) f[u][v] = (j >> (cur++) & 1);
                    REP(u, 0, SZ(ed)) if (k >> u & 1) f[ed[u].x][ed[u].y] = 1;
                    REP(w, 0, K << 1) REP(u, 0, K << 1) if (f[u][w]) REP(v, 0, K << 1) if (f[w][v]) f[u][v] = 1;
                    bool failed = 0;
                    REP(u, 0, K << 1) REP(v, 0, u) if (f[u][v] && f[v][u]) { failed = 1; break; }
                    if (failed) continue;
                    int nxt = 0;
                    cur = 0;
                    REP(u, 0, K) REP(v, 0, K) if (u != v) nxt |= f[u + K][v + K] << (cur++);
                    (dp[i + 1][nxt] += dp[i][j]) %= Mod;
                }
            }
    }
    int ans = 0;
    REP(i, 0, 1 << (K * (K - 1))) (ans += dp[n - 1][i]) %= Mod;
    printf("%d\n", ans);
    return 0;
}

测试点5

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 110;

int n, m;

bool f[maxn + 5][maxn + 5];
int ori[maxn + 5][maxn + 5];

int N = 0;
int bel[maxn + 5];

int main()
{
    scanf("%d%d", &n, &m);
    REP(i, 0, m)
    {
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        f[u][v] = 1;
        ++ori[u][v];
    }
    REP(i, 0, n) f[i][i] = 1;
    REP(k, 0, n) REP(i, 0, n) if (f[i][k]) REP(j, 0, n) if (f[k][j]) f[i][j] = 1;
    int ans = 1;
    memset(bel, -1, sizeof bel);
    REP(i, 0, n) if (!~bel[i])
    {
        vector<int> all;
        REP(j, 0, n) if (f[j][i] && f[i][j]) all.pb(j), bel[j] = N;
        ++N;
        vector<pair<int, int> > ed;
        for (auto x : all) for (auto y : all) if (x != y) REP(j, 0, ori[x][y]) ed.pb(mp(x, y));
        int tmp = 0;
        REP(j, 0, 1 << SZ(ed))
        {
            static bool g[maxn + 5][maxn + 5];
            memset(g, 0, sizeof g);
            REP(k, 0, SZ(ed)) if (j >> k & 1) g[ed[k].x][ed[k].y] = 1;
            for (auto w : all) for (auto u : all) if (g[u][w]) for (auto v : all) if (g[w][v]) g[u][v] = 1;
            bool failed = 0;
            for (auto u : all) for (auto v : all) if (u != v && g[u][v] && g[v][u]) { failed = 1; break; }
            if (!failed) ++tmp;
        }
        ans = (LL)ans * tmp % Mod;
    }
    REP(i, 0, n) REP(j, 0, n) if (bel[i] != bel[j]) REP(k, 0, ori[i][j]) (ans <<= 1) %= Mod;
    printf("%d\n", ans);
    return 0;
}

测试点6

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 110;

int n;

int C[maxn + 5][maxn + 5];
int pw[maxn * maxn + 5];

int a[maxn + 5];

int ans;

int main()
{
    REP(i, 0, maxn + 1)
    {
        C[i][0] = 1;
        REP(j, 1, i + 1) (C[i][j] = C[i - 1][j - 1] + C[i - 1][j]) %= Mod;
    }
    pw[0] = 1;
    REP(i, 0, maxn * maxn) pw[i + 1] = (pw[i] << 1) % Mod;
    a[0] = 1;
    REP(i, 1, maxn + 1)
    {
        a[i] = 0;
        REP(j, 1, i + 1)
        {
            int tmp = (LL)a[i - j] * pw[j * (i - j)] % Mod * C[i][j] % Mod;
            if (j & 1) (a[i] += tmp) %= Mod;
            else (a[i] -= tmp) %= Mod;
        }
    }
    scanf("%d", &n);
    ans = (a[n] + Mod) % Mod;
    printf("%d\n", ans);
    return 0;
}

测试点7、测试点8

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

#define clz __builtin_clz
#define ctz __builtin_ctz
#define bcnt __builtin_popcount
#define bpar __builtin_parity  

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 20;

int n, m;
int from[maxn + 5], to[maxn + 5];
int dp[(1 << maxn) + 5];

int ans = 0;

int nxt[maxn + 5];

int bc[(1 << maxn) + 5];

int oriS;

void dfs(int x, int S, int mul)
{
    if (x == n)
    {
        if (S != oriS) (dp[S] += mul) %= Mod;
        return;
    }
    dfs(nxt[x], S, mul);
    dfs(nxt[x], S | (1 << x), ((LL)-mul << (bc[to[x] & oriS])) % Mod);
}

int main()
{
    scanf("%d%d", &n, &m);
    REP(i, 0, 1 << n) bc[i] = bcnt(i);
    REP(i, 0, m)
    {
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        from[u] |= 1 << v;
        to[v] |= 1 << u;
    }
    dp[0] = 1;
    REP(i, 0, 1 << n) if (dp[i])
    {
        oriS = i;
        int now = n;
        for (int j = n - 1; j >= 0; --j) 
        {
            nxt[j] = now;
            if (~i >> j & 1) now = j;
        }
        dfs(now, i, -dp[i]);
    }
    ans = dp[(1 << n) - 1];
    (ans += Mod) %= Mod;
    printf("%d\n", ans);
    return 0;
}

测试点9、测试点10

以下是测试点10的程序,测试点9的程序和测试点10的程序的区别参见代码注释。

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 1100;

const int per = 3;//测试点9中per = 2
const int maxmask = 1 << (per * (per + 1));

int n, m;
int N;

vector<int> chd[maxn + 5];

vector<int> belong[maxn + 5];

int fa[maxn + 5];
map<int, int> rk[maxn + 5];
vector<int> what[maxn + 5];
int w[maxn + 5];

int dp[maxn + 5][maxmask + 5];
int tr[maxmask + 5];
bool ok[maxmask + 5];

vector<pair<int, int> > rt_ed;

int id[per + 5][per + 5];

inline void deal(int *f)
{
    REP(w, 0, per + 1) REP(u, 0, per + 1) if (f[u] >> w & 1) f[u] |= f[w];
}

inline void masktoa(int x, int *f)
{
    REP(u, 0, per + 1) f[u] = 0;
    REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v && (x >> id[u][v] & 1)) f[u] |= 1 << v;
}

inline int atomask(int *f)
{
    int ret = 0;
    REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v && (f[u] >> v & 1)) ret |= 1 << id[u][v];
    return ret;
}

void dfs(int x)
{
    memset(dp[x], 0, sizeof dp[x]);
    dp[x][0] = 1;
    for (auto y : chd[x]) dfs(y);
    static int sum[maxmask + 5];
    memset(sum, 0, sizeof sum);
    if (~fa[x])
    {
        REP(i, 0, maxmask) if (dp[x][i])
        {
            REP(j, 0, 1 << per)
            {
                static int f[per + 5];
                masktoa(i, f);
                REP(u, 0, per) if (j >> u & 1)
                {
                    if (w[x] >> u & 1) f[per] |= 1 << u;
                    else f[u] |= 1 << per;
                }
                deal(f);
                if (!ok[atomask(f)]) continue;
                int mask = 0;
                REP(u, 0, per) REP(v, 0, per) if (u != v && (f[u] >> v & 1)) mask |= 1 << id[what[x][u]][what[x][v]];
                if (ok[mask]) (sum[mask] += dp[x][i]) %= Mod;
            }
        }
        static int nxt[maxmask + 5];
        memset(nxt, 0, sizeof nxt);
        REP(i, 0, maxmask) if (dp[fa[x]][i]) REP(j, 0, maxmask) if (sum[j] && ok[tr[i | j]]) (nxt[tr[i | j]] += (LL)dp[fa[x]][i] * sum[j] % Mod) %= Mod;
        memcpy(dp[fa[x]], nxt, sizeof dp[fa[x]]);
    }
    else
    {
        REP(i, 0, maxmask) if (dp[x][i])
        {
            REP(j, 0, 1 << SZ(rt_ed))
            {
                static int f[per + 5];
                masktoa(i, f);
                REP(k, 0, SZ(rt_ed)) if (j >> k & 1) f[rt_ed[k].x] |= 1 << rt_ed[k].y;
                int mask = atomask(f);
                mask = tr[mask];
                if (ok[mask]) (sum[mask] += dp[x][i]) %= Mod;
            }
        }
        memcpy(dp[x], sum, sizeof dp[x]);
    }
}

int main()
{
    int cnt = 0;
    REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v) id[u][v] = cnt++;
    REP(i, 0, maxmask)
    {
        ok[i] = 1;
        REP(u, 0, per + 1) REP(v, 0, u) if ((i >> id[u][v] & 1) && (i >> id[v][u] & 1)) ok[i] = 0;
        static int f[per + 5];
        masktoa(i, f);
        deal(f);
        tr[i] = atomask(f);
    }
    scanf("%d%d", &n, &m);
    memset(dp, 0, sizeof dp);
    REP(i, 0, per * (per + 1) >> 1)
    {
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        rt_ed.pb(mp(u, v));
    }
    REP(i, 0, per + 1) belong[i].pb(0), rk[i][0] = i;
    fa[0] = -1;
    N = 1;
    REP(i, per + 1, n)
    {
        w[N] = 0;
        what[N].clear();
        REP(j, 0, per)
        {
            int u, v;
            scanf("%d%d", &u, &v), --u, --v;
            if (u == i) w[N] |= 1 << j, what[N].pb(v);
            else what[N].pb(u);
        }
        vector<int> &all(what[N]);
        assert(!all.empty());
        vector<int> now(belong[all[0]]);
        REP(j, 1, SZ(all))
        {
            vector<int> nxt;
            set_intersection(ALL(now), ALL(belong[all[j]]), back_inserter(nxt));
            now = nxt;
        }
        assert(!now.empty());
        fa[N] = *now.begin();
        chd[fa[N]].pb(N);
        belong[i].pb(N);
        rk[i][N] = SZ(all);
        REP(j, 0, SZ(all)) 
        {
            int &u = all[j];
            belong[u].pb(N);
            rk[u][N] = j;
            u = rk[u][fa[N]];
        }
        ++N;
    }
    dfs(0);
    int ans = 0;
    REP(i, 0, maxmask) (ans += dp[0][i]) %= Mod;
    (ans += Mod) %= Mod;
    printf("%d\n", ans);
    return 0;
}

评论

absi2011
我认识欧阳芳菲 @lqybzx
Menci
前排膜
PbTfcLx
前排膜,感觉不是某个场上十个人的比赛中现在中国队的水平就好了Q(AQ)*

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。