2018 - 2019 SEERC 题解

比赛发出来太新了,网上根本就搜不到题解,补题补的太难受了.
在这里分享一篇我自己写的题解,也方便别人补题.

题目链接

http://codeforces.com/gym/101964/attachments/download/7814/seerc-2018.pdf

---

A.Numbers

留坑.

---

B.Broken Watch

题解

先考虑三个针长度各不一样的情况.

注意到需要对$n$n分奇偶性进行讨论.

1. $n$n为偶数的时候,固定$1$1号针的位置,枚举$2$2号针的位置,那么$3$3号针的位置必然在$1,2$1,2号针的反向延长线形成的扇形区域内(可与边界重合).
   并注意到当$1,2$1,2号针反向的时候,$3$3号针有$n-2$n−2种取法.
   可以得到公式$n(1+2+...+\frac{n}{2} + n-2)$n(1+2+...+2n​+n−2).
2. $n$n为奇数的时候,固定$1$1号针的位置枚举$2$2号针的位置,那么$3$3号针的位置必然在$1,2$1,2号针反向延长线之间(不能与边界重合).
   可以得到公式$n(1+2+...+\lfloor \frac{n}{2} \rfloor)$n(1+2+...+⌊2n​⌋)

而当三根针有两根相同时,需要对答案除以$2!$2!,当三根全都相同时,需要对答案除以$3!$3!,这题就结束了.不明白为什么这个题比$C$C题过得人少?

---

C.Tree

题解

训练的时候想了一种树dp的做法,不太好调,幸好最后还是A掉了.赛后翻比别人代码发现还有一种很巧妙地方法,即枚举树的直径.两种方法我都简略说一下.

方法一.树dp

二分最大距离$M$M,然后树$dp$dp来$check$check可行性.

定义$dp[i][j]$dp[i][j]表示以$i$i为根的子树,选出来的黑点中距$i$i节点距离不会超过$j$j,所能选出最多的黑点个数.
并记$lim = MIN\{M-1-j,j-1\}$lim=MIN{M−1−j,j−1}
那么转移就是:
假设$v_1,v_2,...,v_m$v1​,v2​,...,vm​是$i$i的儿子节点.

1. $MIN_{1\le p \le m}\{dp[v_p][j-1] + \sum_{q != p}dp[v_q][lim]\} \rightarrow dp[i][j]$MIN1≤p≤m​{dp[vp​][j−1]+∑q!=p​dp[vq​][lim]}→dp[i][j]

2. $dp[i][j-1] \rightarrow dp[i][j]$dp[i][j−1]→dp[i][j]

最后只要看$dp[1][M] \ge k$dp[1][M]≥k.

时间复杂度?
$O(n^3log(n))$O(n3log(n))

方法二.枚举树的直径

先预处理出树上两点之间的距离(使用Floyd算法即可).

注意到将黑点取出之后会形成一颗虚树,并且两两之间最长的距离就是

然后我们考虑枚举这颗虚树的直径,假设是$(i,j)$(i,j),然后再枚举黑点,黑点进到虚树中一定不能使直径边长.所以就要要求$dis[i][k] \le dis[i][j] \&\& dis[k][j] \le dis[i][j]$dis[i][k]≤dis[i][j]&&dis[k][j]≤dis[i][j].

时间复杂度$O(n^3)$O(n3)

这个方法简单多了.

注意:不需要建虚树,说虚树主要是好描述.

---

D.Space Station

题解

一道很神奇的题,需要先猜出结论,然后再进行树上背包.思路弄清楚了实现起来很简单.

简述一下题意:一颗$n$n个结点的带权树,要求从$1$1号点出发,遍历所有的边,然后回到$1$1号点.途中可以最多使用$m$m次技能,技能花费时间为$k$k,功能是在任意两点中穿越.求最小代价.

我们先来发现一些规律性的东西.

1. 注意到一颗子树如果子树中包含的技能出发点和技能到达点共$p$p个,如果$p$p是偶数的时候,那么这颗子树根节点的父亲边一定要走两次(可以画图帮助理解一下)
2. 而如果$p$p是奇数的话,那么子树根节点的父亲边只需要走一次就好了.(画图帮助理解)

这就很简单了.

定义$dp[i][j]$dp[i][j]表示以$i$i为根的子树,其子树中奇点个数为$j$j,从$i$i点出发遍历完$i$i的子树再回到$i$i点,所需要的最小代价.

那么转移方程就是

$\sum_{p_1+p_2+...+p_m=j}(dp[v_i][p_i]+(![p_i\&1]+1)*c_i) \rightarrow dp[u][j]$∑p1​+p2​+...+pm​=j​(dp[vi​][pi​]+(![pi​&1]+1)∗ci​)→dp[u][j]

$\sum_{p_1+p_2+...+p_m=j}(dp[v_i][p_i]+(![p_i\&1]+1)*c_i) \rightarrow dp[u][j+1]$∑p1​+p2​+...+pm​=j​(dp[vi​][pi​]+(![pi​&1]+1)∗ci​)→dp[u][j+1]

---

E.Fisherman

题解

不是我写的,后面补充

---

F.Min Max Convert

题解

大致的题意是给你两个长为$n$n的数列$A,B$A,B,然后你每次可以选择一段区间将区间覆盖成它的最大值或者是覆盖成它的最小值.要求输出一个长不超过$2n$2n的方案,将$A$A数列变成$B$B数列.

很明显的构造题.

我们首先要找一下规律以发现一些结论.

1. 一个区间最多通过两次操作可以将区间覆盖为区间中任意一个数.
   当$v$v在区间边界上时,例如$v = a[l]$v=a[l],将$[l,r]$[l,r]覆盖为$v$v的方法是:判断$a[l]$a[l]和$a[l+1]$a[l+1]的大小关系,如果$a[l] > a[l+1]$a[l]>a[l+1],那么就将$[l+1,r]$[l+1,r]取最小值,再将$[l,r]$[l,r]取最大值.
   当$v$v在$[l,r]$[l,r]中间时,可以将区间分成两段,分别操作.

2. 对于$B$B数列的每个数,在$A$A数列中都应该有一个数与它对应.并且这些对应关系不交叉.
   比如:
   $A:5,3,1,2,2,4,7,6,8,6$A:5,3,1,2,2,4,7,6,8,6
   $B:1,1,2,4,4,7,7,8,8,8$B:1,1,2,4,4,7,7,8,8,8
   那么对应关系是这样的:

好难讲,直接看我代码吧.

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define pr(x) std::cout << #x << ':' << x << std::endl
#define rep(i,a,b) for(int i = a;i <= b;++i)

const int N = 100007;
int A[N],B[N],Loc[N];
char C[N<<1];int L[N<<1],R[N<<1];
int tot;
struct E{
	int b,e,x;
}es[N];
int etot = 0;
int n;
void Do(char c,int l,int r) {
	C[tot] = c;L[tot] = l;R[tot] = r;
	++tot;
}
int main() {
	scanf("%d",&n);
	rep(i,1,n) 
		scanf("%d",&A[i]);
	rep(i,1,n) 
		scanf("%d",&B[i]);
	int pos = 1;
	rep(i,1,n) {
		while(pos <= n && A[pos] != B[i]) pos ++;
		if(pos == n+1) return 0*puts("-1");
		Loc[i] = pos;	
	}
	int p = 1;
	rep(i,1,n) {
		if(Loc[i] != Loc[i+1]) {
			es[etot++] = (E){p,i,Loc[i]};
			p = i+1;
		}
	}
	for(int i = etot-1;i >= 0;--i) {
		if(es[i].x < es[i].b) {
			if(A[es[i].x] >= A[es[i].x+1]) {
				Do('m',es[i].x+1,es[i].e);
				Do('M',es[i].x,es[i].e);
			}
			if(A[es[i].x] < A[es[i].x+1]) {
				Do('M',es[i].x+1,es[i].e);
				Do('m',es[i].x,es[i].e);
			}
		}
	}
	rep(i,0,etot-1) {
		if(es[i].x > es[i].e) {
			if(A[es[i].x] <= A[es[i].x-1]) {
				Do('M',es[i].b,es[i].x-1);
				Do('m',es[i].b,es[i].x);
			}	
			if(A[es[i].x] > A[es[i].x-1]) {
				Do('m',es[i].b,es[i].x-1);
				Do('M',es[i].b,es[i].x);
			}
		}
	}
	rep(i,0,etot-1) {
		if(es[i].b <= es[i].x && es[i].x <= es[i].e) {
			if(es[i].x > es[i].b && A[es[i].x] >= A[es[i].x-1]) {
				Do('m',es[i].b,es[i].x-1);
				Do('M',es[i].b,es[i].x);
			}
			if(es[i].x > es[i].b && A[es[i].x] < A[es[i].x-1]) {
				Do('M',es[i].b,es[i].x-1);
				Do('m',es[i].b,es[i].x);
			}
			if(es[i].x < es[i].e && A[es[i].x] >= A[es[i].x+1]) {
				Do('m',es[i].x+1,es[i].e);
				Do('M',es[i].x,es[i].e);
			}
			if(es[i].x < es[i].e && A[es[i].x] < A[es[i].x+1]) {
				Do('M',es[i].x+1,es[i].e);
				Do('m',es[i].x,es[i].e);
			}
		}
	}
	std::cout << tot << std::endl;
	rep(i,0,tot-1) {
		printf("%c %d %d\n",C[i],L[i],R[i]);
	}
	return 0;
}

---

G.Matrix Queries

题解

不是我写的,后面补充

---

H.Modern Djinn

题解

留坑.

---

I.Inversion

题解

第一步,根据图恢原来的排列.

在得到原来的排列以后,我们从排列中挑选一些位置$(p_1,p_2,...p_m)$(p1​,p2​,...pm​)组成一个独立支配集.必然有$a[p_1] &lt; a[p_2] &lt;... &lt; a[p_m]$a[p1​]<a[p2​]<...<a[pm​],只有这样,集合里的点之间才没有边相连,并且还要满足条件即$[p_i,p_{i+1}]$[pi​,pi+1​]之间的数要么大于$a[p_{i+1}]$a[pi+1​],要么小于$a[i]$a[i].

并且在排列中不可能存在$p_0 &lt; p_1并且a[p_0] &lt; a[p_1 ]$p0​<p1​并且a[p0​]<a[p1​],否则的话,它也应该存在于集合当中,应为它与集合中的所有点都无边相连.同理,不存在$p_{m+1} &gt; p_m$pm+1​>pm​,使得$a[p_{m+1}] &gt; a[p_m]$a[pm+1​]>a[pm​].

如果$p&lt;q且a[p] &lt; a[q]且a[p,q]$p<q且a[p]<a[q]且a[p,q]之间的数不会存在介于$a[p]$a[p]与$a[q]$a[q]之间的数,就从$p$p向$q$q连边.

答案就是从入度为$0$0的点,跑到出度为$0$0的点的路径数之和.

拓扑序dp一下结束.

---

J.Rabbit vs Turtle

题解

留坑

---

K.Points and Rectangles

题解

留坑