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$之间的路径上,就可以更新新树上对应的权值了。时空复杂度均和算法六一样,也可以通过全部数据。

关于“鏖战表达式”错误复杂度算法水过现象的看法

2016-02-27 21:42:39 By matthew99

WC2016鏖战表达式一题,松爷(王逸松,鏖战表达式出题人)在WC上讲了复杂度为每次操作$O(k + \log n)$的做法,即所谓的树(套树)$^*$。然而民间流行一种直接用treap维护的,并把优先级比较定为比较运算符,运算符相同则根据子树大小用概率比较的做法,复杂度为$O(k\log n)$,为什么呢,因为我们先加入一堆1,再加入一堆2,一直到一堆k,每一次新加入一堆运算符,不能改变前面运算符的形态,因此复杂度是$O(k \log n)$,直接提交会得到七十到八十的分数,由于此题数据强度不大,因此稍微根据数据进行修改一些实现细节即可水过。

松爷与我曾多次提到过此事,我也认为此事十分不妥,作为一个很好的数据结构题,留下的却是一堆的水过,以及不断的有新人抱着以为这是正确的做法的心态去写,最后却死活过不去而只能跟着水过的事情。幸运的是考场上并没有人水过。

本题作为一道特殊的题,难以像现在大部分UOJ上的题一样支持hack和extra test,甚至考场数据和grader都使用了特殊的方法加密,因此想要阻止这种现象只要两条路,一是通过@vfleaking等管理员来手工添加一些extra tests强行卡掉复杂度错误的算法,二是靠大家的理解和自觉,理解这种算法的不正确性,并自觉不使用这种算法。

这里我提醒一下大家不要再陷入错误做法的泥潭中。

对于那个$O(k \log n)$的做法,本人也进行了一些改进,可以参见http://uoj.ac/submission/50137注意,提交统计里面显示的我的提交是我之前跟着大家水过的程序,并不是这份代码。

我大概是在merge和split的时候进行了一些rotate,具体复杂度无法给出详细证明,但是感觉是$O(k + \log n)$的可能性还是比较大的(当然也有可能是$O(k\log n)$,或者甚至$O(\sqrt{k}\log n)$, $O(k \log k + \log n)$, $O(k \log \log n + \log n)$这些鬼畜的复杂度233,大家还可以继续脑洞),大家可以感受一下我改动的地方。如果觉得我的做法也不靠谱可以学习松爷std程序的做法。如果有谁卡掉了我的做法或者是证明了我的做法的复杂度的确是$O(k + \log n)$,欢迎与我讨论。

分金币问题

2015-10-26 15:56:32 By matthew99

今天的模拟题给了我们一次刻骨铭心的经历。

题目是这样的,n个人分m个金币,每个金币完整不可分。从第一个人开始,每个人提出一个分金币方案,如果投票同意的人超过半数,那么这个方案就通过,否则这个人将被杀掉。

现在假设每个人都很聪明。每个人尽可能的保证生命。如果可以保证生命,那么他希望自己分到的金币最多。如果不能过获得更多金币,就会希望别人死。如果一个人知道自己肯定要死,那么他对别人的方案会投反对票。

假设有6个人,100个金币。

对于一个人,显然分到所有金币。

对于两个人,显然第二个人必死,第一个人分到所有金币。

对于三个人,他会给自己留100个金币,其他人不分,第二个人想,自己不同意就会死,第一个人显然不会同意,而第三个人自己的方案显然会同意,所以有两个人同意,方案通过。第三个人获得100个金币,前两个人都没有金币。

对于四个人,他会给自己98个金币,第一个人和第二个人各1个金币,前两个人想,如果我不同意而给第三个人决定,那么自己就不会有金币了,因此会同意,而第四个人显然会同意,所以有三个人同意,第四个人获得98个金币,前两个人各1个金币,而第三个人得不到金币。

对于五个人,他会给自己97个金币,第三个人1个金币,第一个或者第二个人2个金币,这样第三个人肯定同意,给了2个金币的那个人也会同意,第五个人自己也同意,所以分金方案是第五个人97个金币,第三个人1个金币,第一个或者第二个人2个金币。

对于第六个人,矛盾就出现了。

考虑给自己留97个金币,第四个人1个金币,第一个和第二个人各1个金币。 自己和第四个人肯定会同意,而第一个和第二个人会不会同意呢。

第一个人和第二个人的想法是,如果自己不同意,那么自己可能一分钱没有,也可能会得到两块钱,如果他们都想保全这一块钱,那么就都会同意,反之如果有人想奋力一搏,觉得还不如不同意,说不定有两块钱,那么大家都不会同意,出现了矛盾。

如果第一个人和第二个人都清楚第五个人的选择,比如第一个人和第五个人关系特别好,他知道第五个人肯定会给他,而第二个人也清楚这一点,那么,如果是上面这样分,只会有第一个人同意,第六个人就会被杀死。

这个时候正确方案应该是自己留96,第二个人留1,第四个人留1,第三个人留2。 如果第六个人想:“唉我还这么年轻,真的不想死啊,钱是身外之物我不想要了!”,那么他就会做出这样的决策:

自己留94,第四个人留1,第三个人留3,第二个人或者第一个人留3,这样给3个金币的人肯定会同意,另外三个也会同意,自己肯定死不了。

五个人的情况似乎是小学奥数的经典内容?因为五个人的情况是没有争议的。

事实上,我考场上实现的,包括出题人的数据,都是第二个想法,就是大家都是先知,都可以预测别人的想法。然而也有相当一部分人写的是第一种想法,而第三种没听说有人写过。

实际上题面也什么也没说清楚,所以才会导致这么大的撕逼。

如果是CF或者TC遇到这种情况当然unrated咯。

但实际上大家为此撕逼了一中午和一下午233333333333333333333。各抒己见,感觉还是很好玩很刺激。

实际上如果大家都可以预测别人的想法,那两个人玩起石头剪刀布,究竟会怎么出呢,估计两个人的大脑都栈溢出咯......

事实上撕逼这种问题也不是第一次,CTSC day2的前夕和吉丽、松爷、猪猪侠和DZY也为此撕逼过。详见http://jiruyi910387714.is-programmer.com/posts/94162.html

公平分配中的争议还真是多。

app管理器的乱搞经历

2015-08-11 09:06:46 By matthew99

昨天下午改完app管理器之后发现dwjshift的程序特别快,然而是个乱搞,便造了个数据hack了。之后觉得他的思路很有趣,便新建了一个dwjshift_fan的账号优化他的算法,代码风格都是我自己的然而并没有多少人认出那是我(大雾。

最后137ms过了那道题,我的hack数据也跑得很快,自己试了试好像也没能hack。算法大概就是每次用dfs实现的SPFA暴力找环然后确定方向之后缩起来,注意重边的处理。加了很多优化之后才跑到137ms。欢迎有兴趣的同学前来hack:http://uoj.ac/submission/24834

...妈妈我终于会做动态仙人掌IV了

2015-05-16 23:10:45 By matthew99

妈妈我终于会做动态仙人掌IV了!!

鼓掌熊

由于mx此时刚好正在滚粗搞文化课,为了战这道题,可谓历尽辛酸(大雾)。迟到缺交作业忘搞卫生已经把我罚得在班上没脸做人了。

傻逼mx还因为手算算错答案怀疑标程正确性制造了两个恶意hack。看来要被封号了QAQ

不能作为除出题人之外第一个AC的人真是太遗憾了,膜CHXER!

UPD:出了点奇怪的事情。

mx的仙人掌 题解

2015-03-27 11:59:14 By matthew99

题目地址

http://uoj.ac/problem/87

算法一

估计大家应该不会被仙人掌吓到而直接$\mathrm{gg}$了,至少先会考虑任意图的情况。

妈妈我不会处理图的问题怎么办?

有$5\%$的数据$n \le 7, \mathrm{tot} \le 7$,可以用各种方法(如枚举所有路径)水过去。

算法二

有$10\%$的数据$n, \mathrm{tot} \le 5000$。

最短路算法

由于时限和数据都很令人感动,这些数据其实用$\mathrm{dijkstra}$甚至$\mathrm{SPFA}$(我多良心没有卡哦!(大雾))都能跑得过去......

更好的做法

考虑仙人掌图的$\mathrm{dfs}$遍历树,有很多条前向边,每条前向边$x \rightarrow y$对应一个环,不妨设这个环的根为$y$,每当我们找到一条前向边$x \rightarrow y$时,通过从$x$不断回到$\mathrm{dfs}$树上的父亲直到到达$y$,我们可以取出这个环上所有点,并且容易得出环的长度,对所有点除了$y$以外的点都标记一下它所在的环编号。

$\mathrm{dfs}$完以后,对每个点考虑他到根的距离,如果他没有环标记那么距离就是父亲到根的距离加上自己到父亲的边的长度。否则就是他到环的根$y$的两条路径长度(一个是$\mathrm{dfs}$树上的距离(这个用两个点离根的距离减一减就求出来了),另一个是环的长度减去树上距离)中的较小值加上$y$到根的距离。

对每个询问的每个询问点,我们都遍历一遍,时间复杂度为$O(n\times \mathrm{tot})$。

算法三

有$10\%$的数据$Q \le 10$。我们考虑对每一次询问直接$\mathrm{dfs}$一遍求得答案。

用$\mathrm{maxlen}_x$表示从$x$出发到以$x$为根的子仙人掌(即在原图中删去$x$之后不与根相连的点和$x$的导出子图)的某个询问点的最短路的最大值(如果没有询问点可以设为-∞),对于$x$的某个$\mathrm{dfs}$树上的孩子$y$,如果从$x \rightarrow y$的边$e$是割边那么就直接用$\mathrm{maxlen}_y + w_e$更新$\mathrm{maxlen}_x$,$w_e$表示$e$的权值,否则如果$x$成为了边$e$所在环的根那么我们要把环取出来,直接枚举换上的点然后用他的$\mathrm{maxlen}$加上他到$x$的两条路径长度的最小值更新$\mathrm{maxlen}$即可。

考虑更新答案,所有询问点的$\mathrm{maxlen}$显然可以用来更新答案,对一个点的两个不同的子仙人掌(即在原图中删去$x$之后不与根相连的点的一个连通块和$x$的导出子图),他们的$\mathrm{maxlen}$之和加显然也可以用来更新答案(求出一个子仙人掌$y$的$\mathrm{maxlen}_y$之后,先用$\mathrm{maxlen}_y + \mathrm{maxlen}_x$更新答案,再用$\mathrm{maxlen}_y$更新$\mathrm{maxlen}_x$即可)。现在还需要考虑经过一个环的路径的情况。

经过一个环的最短路径一定是由两条环以外的路径(可以长度为0)和一条环上的路径组成,我们按顺序取出环上的边,并且复制一份接在后面,形成一条链。对于链上的点$i$,记$mathrm{len}_i$为链的头部到它的路径的长度,$\mathrm{val}_i$为它对应的点的$\mathrm{maxlen}$,那么经过这个环的最长的最短路径即为$\mathrm{max}\{\mathrm{val}_i + \mathrm{val}_j + \mathrm{len}_i - \mathrm{len}_j\}(0 \le \mathrm{len}_i - \mathrm{len}_j \le \frac{\mathrm{cirlen}}{2})$,其中$cirlen$表示该环的长度,容易用单调队列维护,时间复杂度为$O(Qn)$,如果用线段树时间复杂度为$O(Qn\log n)$。

算法四

对于树的情况,可以使用虚树。

虚树的建立方法之一是,对询问点按$\mathrm{dfs}$序排序,然后取出他们相邻节点间的$\mathrm{lca}$,接着再按$\mathrm{dfs}$序排序,接着扫一遍,维护一个栈,如果当前栈顶的节点是当前节点的祖先那么就连一条边,边权为它们之间的距离,否则将栈顶的节点弹出栈。这只是一种建立方法。

然后在虚树上$\mathrm{DP}$即可。

时空复杂度均为$O(n\log n)$(今后视tot = $O(n)$)

此外时间复杂度可以通过更大的代码复杂度降为$O(n\alpha(n))$或者$O(n)$,具体不再赘述,我多良心没有要求大家写这些算法哦!(大雾)。

算法五

对于树的情况,还可以用树分治解决。

一种较方便的树分治的做法是,先建立好树分治结构,然后对每一个询问,先将点去重。接着对于每一个树分治结构中的节点(对应一棵子树$T$),我们只考虑该询问中所有在$T$中的点。直接用两个属于不同子树的点到根的距离和的最大值更新答案即可(要注意判一下询问点是根的情况)。接着对于它的每一个孩子节点,递归处理下去,注意我们只要保留该询问中在这个孩子节点中的点。

但是这个做法由于要预先存储结构,时间空间常数都比较大。

还有一种做法是,询问和树一起分治,这个很好理解,无非就是把两个过程合并了,每一次要处理的是一棵子树和一个询问序列,这个序列只保留所有存在询问点在该子树中的询问,并且每个询问只保留在该子树中的询问点,然后处理询问的方法如同前面所述。

时空复杂度均为$O(n\log n)$。

UPD:树上迭代两次求最远点即可,最远点可以直接枚举然后$\mathrm{lca}$,呜呜呜我出题的时候怎么就脑抽了,30分送大家吧,前面的算法就当做口胡......

算法六

对于树的情况,如果你只会虚树或者树分治,对于仙人掌你肯定也只能这么做了。

如果我们能建立“虚仙人掌”,肯定可以解决这个问题。思考熊

我们想一想就能想清楚虚仙人掌的一种最笨但是也绝对正确并且可以通过这题的建立方法,先按$\mathrm{dfs}$序排序,再求出相邻节点间的$\mathrm{lca}$(注意这里$\mathrm{dfs}$序和$\mathrm{lca}$都是在它的$\mathrm{dfs}$遍历树上做,后面的深度也是),接着我们取出每一个点所在环的根和环上最深的点,再排序并取一遍相邻节点$\mathrm{lca}$,然后建出$\mathrm{dfs}$树上的虚树,接着再每个环的最浅的点和最深的点之间连边,边权为它们原先连的边的权值(它们原先显然一定连了边),由于我们要求的是最短路径,其实这里连它们之间在环上走的两条路径的较小值也没有关系,不会对任何最短路径造成影响,这一个画一画图就知道了。

根据上述结论,连虚树上的边时,可以将虚仙人掌上的环边和树边一视同仁,统统连它们两个端点在原仙人掌上的最短路径长度。但是这个最短路径长度和树上不同,树上可以直接用离根的距离减一减,仙人掌上就不是这么简单了,离根的最短路长度不具有可减性。是,我们可以用动态仙人掌。但是这样代码复杂度太高。我们考虑一下,如果树上有一个值也不具有可减性,比如路径边权最小值,你会怎么弄?一种方法就是倍增。对仙人掌也这么弄,考虑动态仙人掌维护生成树法的思想,我们记录每个点到它第$2 ^ i$级祖先的最短路长度,同时如果有一个环不完全包含这条路径,且包含第$2 ^ i$级祖先的父亲(显然这个祖先如果是根就不可能存在满足条件的环),那么我们就记录一下这条路径上深度最大的在这个环上的点,合并的时候就根据这个环是走树边还是走非树边来求出最短路,非常简单。

UPD:好像可以记录到根的距离,然后用特殊的方法处理一下就可以直接减了。总之实现上有各种技巧优化时间复杂度和代码复杂度,感觉标程就是个逗比啊TAT......

实际上,std的方法和上述方法有细节上的差异,如果$x$本身连了一条非树边,包含了整个路径及$2 ^ i$级祖先的父亲,那么他也将被记录,但是这样合并的时候将会多出一些小麻烦,因为一个环可能会更新一条路径两次,用后一次更新覆盖掉前一次更新即可。但是如果不用这个方法,$\mathrm{dfs}$树的叶子节点连接的非树边也要特判。不过这些东西都是一些细节问题,稍微处理一下即可。

总之这个算法可以非常愉悦的跑出100分, 时空复杂度均为$O(n\log n)。$鼓掌熊

提交记录在这里

算法七

对于树分治,我们显然也可以想办法把它搞到仙人掌上,也就是用仙人掌分治来解决问题,实现细节和树分治大同小异,每一次去掉一个点时,先把它弄成仙人掌的根,然后断开它连的所有割边,以及所有它所在环的环边,每一次选一个进行上述操作后,剩下来的子仙人掌中大小最大的最小的点来分治即可(其实为了方便我写的程序不一定能取出最小,但绝对剩下来的子仙人掌中大小最大的不超过$\frac{n}{2}$)。

处理每个询问时,根可能连着不少的环。对一个点(除了根),如果在某一个环$C$上或者某一个在$C$上的点(除了根)的子仙人掌,那么称这个点属于环$C$。,直接用两个属于不同子仙人掌或者环的点到根的距离和的最大值更新答案即可(同样要注意判一下询问点是根的情况)。但是我们还要注意属于同一个环但不是环上同一个点的子仙人掌的点,他们两两之间也要更新答案,这个用单调队列很好解决。

时空复杂度均为$O(n\log n)$。鼓掌熊

我用算法七写的程序,比算法六的程序常数大了很多。我估计树分治应该常数也会比虚树大很多(大雾)。但鉴于我是个常数渣,我的程序的运行时间仅供参考。

UPD:$\mathrm{extra\ test}$把这个程序卡掉了,卡常数中T_T......大家可以争取比我先卡过去然后尽情地来婊出题人的常数吧!

UPD:卡过去了,提交记录在这里,从不到8K卡到9K多,感觉有点爽。

解法八

松爷给出了另外一种解法,详见http://wangyisong1996.is-programmer.com/user_files/wangyisong1996/File/zjoi2015/cactus-slides/wys-cactus-slides.html#/6

AC代码:

http://uoj.ac/submission/13387

http://uoj.ac/submission/13388

第一份的空间复杂度是$O(n\log n)$,比第二份多一个$O(\log n)$,但代码量更小。

此外,仙人掌分治和虚仙人掌都可以在线,前者在线情况应该会TLE甚至可能MLE(至少我的写法如此= =b),后者本身就可以在线。这种做法就没什么简单办法做到在线了= =b。

解法九

waltz给出了另外一种解法:http://uoj.ac/submission/13649

时间空间代码量都完虐我啊orz......

这个做法是对每个环,新建一个点,向环上每个点连长度为它到环的根的最短路径长度的边,如果对新树dfs,那么每个点到它的任意非新建祖先的最短路径长度就是它们之间在树上的距离,对于lca不是新建点的两个点最短路长度就是它们之间在树上的距离,是新建点的话,在树上的距离也不会小于真实距离,但我们可以单独取出环再单调队列来解决环的问题。这道题成功降级为符合人民大众胃口的既无思考难度也无代码难度的傻逼题。跪烂waltz!

基于这个思路,也许很多仙人掌上问题可能会有更简单的做法?思考熊

乱搞

我们发现对于树的情况,直径就是任取一个点$a$,求出他的最远点$x$,再求出最远点$y$,$x$到$y$的距离,应用到仙人掌上是不正确的。因为一个大环连上一条小边,只有$a$取到$O(1)$个点时才能求出答案,对于其他点就算不断找最远点迭代∞次答案也不正确。(想知道这个算法能拿多少分吗?写写就知道!坏笑熊)

另外我们还可以多次枚举点做根,然后设法求得经过根的最长路径,由于答案路径可能很长,一旦取到了一个答案路径上的点做根就可以求出正确答案。但是一旦答案路径比较短,这个算法就不靠谱了。并且这个算法没法较好的判断是否已经是当前答案已经正确。

如果你通过各种方法乱搞过了,你就可以好好感受一下$\mathrm{extra\ test}$和$\mathrm{hack}$的威力了。坏笑熊

后记

其实这个题如果出成每对点的最短距离和的话,是可以避免乱搞的,而且不难实现,但是由于奇怪的原因,我没有把它改成这样。

在出题人想出一个原始的算法之后,算法又其他人不断被改进,长江后浪推前浪。感觉我从这道题的出题经历中感受到了科技的进步。捂脸熊

5s的时限真是太良心了233,主要是为了欢迎各种奇葩做法。

共 14 篇博客