UOJ Logo matthew99的博客

博客

快乐游戏鸡LCT做法

2017-01-26 19:40:17 By matthew99

首先你得看了题和题解至少算法二之前的部分。

题解地址:http://vfleaking.blog.uoj.ac/blog/2292

我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。

接着我们按w从大到小加入点,考虑维护每个点的子树中的最小深度

这个怎么维护呢,考虑一个点肯定是更新它到根的路径,所以我们用类似LCT的access的方法更新,我们可以保证随时每个链的最小深度都相同,如果当前的链的最小深度小于用来更新的值就直接退出,否则的话我们就更新,最后再把这些更新了的链连起来。

复杂度显然是$O((n + m)\log{n})$的,用类似证明LCT复杂度的方法证明即可。

答案也很好算,记录一个后缀和即可,你会发现更新的时候也很好打标记,询问也很好处理。

怎样,是不是只要有模板就好写又好调?而且时间效率还不错呢。

代码:http://uoj.ac/submission/123579

UOJ Easy Round #7 题解

2016-10-15 20:15:21 By matthew99

短路

By matthew99

算法一

直接暴力 dfs,复杂度指数级,期望得分 10 分。

算法二

用最短路算法,复杂度 $O(n ^ 2 \log n)$,根据实现情况可以获得 10 至 30 分。

算法三

猜想只能往右或者往下走,然后做一个 $O(n ^ 2)$ 的 DP,可以获得 30 分。正确性证明参见算法五。

算法四

在算法三的基础上进行对称性优化或者使用滚动数组,可以获得 50 分。

算法五

我们考虑假设我们要从左上角走到从外到内第 $i$ 层任意一个中继器上,那么我们最少需要多少代价呢?显然我们一共最少走 $2i - 2$ 步走到 $(i, i)$ 上。其中,第 $1$ 层到第 $i - 1$ 层每层都必须经过至少一个中继器,除了这 $i - 1$ 步,还要再走恰好 $i - 1$ 步。

我们发现剩下来的 $i - 1$ 步至少要走的是 $1$ 到 $i - 1$ 层的前缀最小值之和,为什么呢?考虑一条走到第 $x$ 层某个给定位置且只到过前 $x$ 层的最短路径,那么该路径的最后一步要么是从第 $x - 1$ 层走下来,要么是在第 $x$ 层又逗留了一次。如果是后者,我们总是可以把这最后一步挪到前面去走,相当于对于某个 $k$ 在第 $k$ 层先走了这一步,然后把这一步之后的路径平移一下而不影响平移的这段路径的总时间,这样代价变化就是第 $x$ 层的 $a$ 与第 $k$ 层的 $a$ 的差值。这样我们就推出,如果第 $x$ 层的 $a$ 不是前缀最小值,那么肯定不是最短路径。因此,最短路径肯定不会在不是前缀最小值的层停留超过 $1$ 次,于是这条最短路就是把所有的前缀最小值所在的层的最左上角的点用 L 型的曲线连起来的路径。

那么假设我们走到的最深的一层是第 $x$ 层,首先第 $x$ 层不是前缀最小值的话那么一定不是最短的。如果是前缀最小值,那么最短路径就是先走到第 $x$ 层左上角,再绕一圈绕到第 $x$ 层右下角,再走出去(代价和走过来是一样的)。

这样,我们暴力枚举 $x$,走到第 $x$ 层的代价可以在线计算,然后每次更新答案即可。

时间复杂度 $O(n)$,期望得分 100 分。

同样的我们也证明了算法三的正确性。

怎样,是不是一个超级送分大水题呢?

天路

By zhj, vfleaking,题解 By vfleaking

什么鬼?

嘿嘿嘿……vfk 又来出题玩玩了。事情是这样的,我和 zhj 发现了一个好玩的 idea,然而我并不知道怎么套个优雅的模型。这时 zhj 拯救了世界,于是就出出来了。

哎说实在的过去的一年给 CCF 出题有点心累,在自家 UOJ 上出题各方面还是爽多了2333……

依稀记得 NOI2016 讲题时我兀自地讲讲讲,台下纠结分数线的梦想们并没有多少热情听。后来当我看到分数线公布以及签约的现场有点百感交集,感觉给 CCF 出一次题的事情多,责任也好重……在 UOJ 上自己随便出出出题至少不会直接影响选手痛失金牌。

但愿我出的萌萌哒题目们都能让大家有所启发吧。

谜之声:怎么近似算法都出到 OI 里啊?这真 NOIP 难度?

咳咳客官别急,往下看。敢承诺这个近似算法非常 NOIP 向,并不是那种数学大不等式乱搞证 bound 型。

算法一

对于 1 号测试点,$n \le 100, a_i \le 100$。

大暴力!

你会使用 for 循环吗?

时间复杂度 $O(nV^2)$,可以获得 10 分。(其中 $V$ 为权值范围)

算法二

对于 1,2,3 号测试点,$n \le 100$。

权值范围好大啊……

不要慌,你可以先枚举 $k$,然后枚举 Nokia1050 是在哪一段时间连续拦截了 $k$ 次攻击嘛……该区间中高度的最小值和最大值作为高度区间。

你会使用 for 循环吗?

时间复杂度 $O(n^3)$,可以获得 30 分。

算法三

对于 4,5 号测试点,$n \le 1000$。

在算法二基础上,把每次扫一遍求最小值最大值改为 for 的时候乱维护维护就行了……

(而且 $O(n^3)$ 常数好就过了呢)

(感觉在 CCF 系列比赛这样送分会被选手喷的……hhh)

时间复杂度 $O(n^2)$,可以获得 50 分。

算法四

对于 6,7 号测试点,$n \le 10^5$。

诶数据随机?

同学们你想到了什么!随机数据的前缀最小值只会变化 $O(\log n)$ 次对吧!

所以当我们固定左端点移动右端点时,区间内最大值与最小值至多只会变化 $O(\log n)$ 次。

拿个单调栈维护一下……每次给对应的长度区间更新答案。

脑抽选手可以使用线段树,但其实由于答案单调,所以可以变成给一个长度的后缀更新更新,于是就能 $O(n \log n)$ 的复杂度了。

可以获得 70 分。

算法五

还是数据随机的情况,观察数据我们注意到如果区间长度够长,那么答案就非常接近$10 ^ 6$。

所以我们设一个几百左右的值 $l$,然后处理小于 $l$ 时的答案,剩下来的输出 $10 ^ 6$ 即可。

同样可以获得 70 分。

算法六

好了好了所以之前的部分分跟近似算法都没什么关系……

这题应该怎么近似呢?你想,要是直接把权值除以一个大常数,做完之后再乘回来,看上去好像很近似!但是冷静冷静就会发现这样做出来是个绝对误差的,如果碰到 \begin{equation} 233333 - 233332 = 1 \end{equation} 这种就 GG 了。

所以……相对误差,看上去很没头绪。

来来来先把近似算法扔进垃圾桶,来想想如果要你求出准确解,你可以怎么做。

一个思路是,我们应该是枚举一个 $k$ 然后某种方式维护一下,但这个看上去就很没办法改造为近似算法。

诶,那如果告诉你一个常数 $c$,我们来把答案 $c_k$ 划一划范围好像很兹瓷啊……那 $c_k \ge c$ 可做吗?

……好像是可做的诶,因为最终的答案肯定是单调递增的,所以范围肯定是一段连续的 $k$。我们可以两个指针再开两个栈乱扫扫,左端点往后挪一挪,右端点也往后挪一挪……就能把 $k$ 的范围求出来了。

嗯很好,于是我们就可以每次找找 $c$,划分 $k$ 的范围。当范围足够小的时候,就可以把这一段的 $k$ 都用同一个数近似了。

事实上,你只需要取: \begin{equation} 1.05^0, 1.05^1, 1.05^2, 1.05^3, \dots \end{equation} 就可以啦!每一段里面随便找个数当答案一定不会超过相对误差的容许范围。

现在还差一个想题时的直觉 —— 就是需要划分的段很少……只要注意到其实段数是 $O(\log V)$ 级别的……23333333……别看人家 $1.05$ 小,但人家也是个指数函数。

中间找到 $k$ 的范围只需要 $O(n)$ 时间乱扫,所以总时间复杂度是 $O(n \log V)$。如果把 $5\%$ 当做变量 $\epsilon$,那么时间复杂度就可以写为 \begin{equation} O(n \log_{1+\epsilon} V) = O(n \log V / \log(1 + \epsilon)) = O(\epsilon^{-1} n \log V). \end{equation}

这个算法其实说明,所有 $f(i)$ 随 $i$ 递增且有个算法告诉我 $f(i) \ge k$ 的第一个 $i$ 在哪里的话,都可以套这个近似算法!(然并卵)

噔噔!这题就做完了!相信比赛时很多选手都轻松 AC 啦~

(为什么一道水题的题解我能写这么长)

套路

By matthew99

算法一

枚举区间,再枚举区间内两个数统计这个区间的答案,再求出整个问题的答案。时间复杂度 $O(n ^ 4)$,期望得分 7 分。

算法二

用 $\mathrm{ans}[l, r]$ 表示区间 $[l, r]$ 的答案,很容易发现 $\mathrm{ans}$ 可以由如下递推式算出: \begin{equation} \mathrm{ans}[l, r] = \begin{cases} |a_l - a_{l + 1}| & \qquad r - l = 1, \\ \min\{\lvert a_l - a_r \rvert, \mathrm{ans}[l + 1, r]\,, \mathrm{ans}[l, r - 1]\} & \qquad r - l > 1. \end{cases} \end{equation}

时间复杂度降为$O(n ^ 2)$,期望得分20分。

算法三:

注意到如果 $m \le 1000$,那么根据鸽巢原理,长度超过 $m$ 的区间肯定有两个相同特征值相同的跳蚤,因此答案是 $0$,所以我们处理长度小于 $m$ 的区间即可。

时间复杂度为 $O(nm)$,期望得分 27 分,结合算法二可以获得 40 分。

算法四:

使用任何一种时间复杂度为 $O(n \sqrt{m + n} (\log m + \log n))$ 的算法(请注意大O符号的意思),即可获得至少 $70$ 分。由于这些算法过于复杂且与标算没有太大关系(或者是标算强行多写了一个 $\log$),故不再赘述。

算法五:

我们考虑如果区间长度是 $x$,那么最小差不超过 $\frac{m}{x - 1}$。

设一个常数 $S$。

如果 $x \le S$,则用类似算法三的方法,可以做到 $O(nS)$。

如果 $x > S$,那么最小差不会超过 $\frac{m}{S - 1}$。我们扫描一遍序列,考虑当前位置作为右端点,用 $r_x$ 表示权值为 $x$ 的数最后出现的位置,然后每次新加入一个数 $z$ 之后,对于所有 $\lvert z - y \rvert \le \frac{m}{S - 1}$,利用 $r_y$ 进行计算更新答案,然后 $r_z$ 即可。时间复杂度为 $O(n\frac{m}{S})$。

设 $S = O(\sqrt{m})$,则总时间复杂度为 $O(n\sqrt{m})$,可以获得 100 分。

这是不是 UOJ 历史上最水的C呢,相信大家 AK 得非常的爽,作为出题人之一看到大家 AK 我也感到非常荣幸。

UPD:好像打脸了。

《UOIP十合一》标程已经放出

2016-07-07 16:14:38 By 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;
}

《共价大爷游长沙》解题报告

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

题目地址

http://uoj.ac/problem/207

Q&A

题目名称怎么来的?

本题题名是跟风另外两道题目的,另外两道题目的题目名见题面第一句话。

共价大爷和小L是谁?

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

小L的ID是luoyuchu,他是共价大爷的忠实粉丝。

长沙市真的总是在不断的施工吗?

的确是的,比如说从雅礼到我现在住的地方就有多处施工点。雅礼操场目前在施工,已经挖出了多座古墓,甚至曾经被以为是太守坟。

算法一

直接上暴力,每次对于所有路径将它经过的边边权加一,然后看看询问的路径边权是否为$|S|$,时间复杂度$O(n ^ 2m)$,期望得分10分。

算法二

如果没有加边删边操作和删除点对操作,那么我们可以维护当前的可行路径,每次可以用$O(\log n)$或者$O(1)$时间进行树上路径求交以及判断一条边是否在路径上,如果使用倍增,则时间复杂度为$O((n + m)\log n)$,期望得分20分,结合算法一可以获得30分。

算法三

如果没有加边删边操作,那么我们可以用动态树或者树链剖分等支持链修改单点询问的结构,维护每个点被路径经过的次数,每次看看询问边的两个端点是否都被经过了$|S|$次。如果使用LCT那么时间复杂度$为O((n + m) \log n)$,期望得分40分,结合算法一可以获得50分。

算法四

对于没有加边删边操作的数据,我们还有一种做法,我们对所有点对建一棵线段树,每个节点存子树中所有路径的交,每次操作的时候都很容易在线段树上update解决,如果用ett序或者dfs序加ST表,那么每次可以在$O(1)$的时间内update,总时间复杂度为$O(n \log n + m \log m)$,期望得分40分,结合算法一可以获得50分。

算法五

对于$|S| \le 10$的数据,我们可以每次询问的时候进行和算法三类似的操作,每次暴力加入所有路径维护每个点被经过的次数再用同样的方法询问,期望得分20分,结合前面的算法可以获得70分。

算法六

我们注意到,一条$x$到$y$路径被所有路径经过,当前仅当以$x$为根时,所有路径的端点都恰好有一个在$y$的子树中。这样,我们对每一个路径随机一个权值,然后每次加入删除路径时,将两个段点的点权异或上这个权值,然后用动态树维护子树权值异或和,每次询问对应子树内的权值异或和是否是当前所有路径的权值异或和,权值如果设为$10 ^ 9$级别,就基本不可能出错了。时间复杂度$O((n + m) \log n)$,空间复杂度$O(n)$,可以通过全部数据。

算法七

这题罗哲正同学提出了另外一种做法,我们可以将权值异或在一条链上,新加入一条边的时候,新形成的环上必然有一条边会被删除,假设这条边是$u$和$v$之间的边。我们发现,将这条被删除的边的权值异或到删除这条边后$u$和$v$之间的路径上,就可以更新新树上对应的权值了。时空复杂度均和算法六一样,也可以通过全部数据。

matthew99 Avatar