Virtual Participated on May 31, 2020.

VP & Practice available here: Codeforces Gym

• Solved 7 out of 11 problems
• Rank 13/107 in official records
• Solved 8 out of 11 afterwards

(√ for solved during VP, ○ for after VP, - for tried but not solved)

• Solved by Pantw

$h\times w$ 的格点上有两个不同的染色点，要求选取边界上的两个格点将这堆格点分为两侧，且一侧各有一个染色点。

因为 $x$ 坐标和 $y$ 坐标中有一组不一样，直接这两个坐标对应的线上选相对的端点即可。简单题不多解释。

• Code By Withinlover
• Debug by Pantw

$n$ 个同学站成一个环，其中 $x$ 个人与男生相邻， $y$ 个人与女生相邻。询问是否存在合法的站位，如果存在，输出任意方案。

利用鸡兔同笼的思想（大雾

先算出，有多少人的周围既有男生又有女生：$A = x + y - n$

然后求解有多少人周围只有男生：$B = x - A$，周围只有女生： $C = y - A$

不难发现，若有解 $A$ 必定是偶数，按 $A$ 的取值分类讨论， $A = 0$ 和 $A = 2$ 的时候大力出奇迹， $A >= 4$ 的部分可以通过添加 $BBGG$ 这样的块缩小范围。其余情况均无解。

• Solved by Gary

给出n个人在两个网站上的排名(排名各不相同)，求每个人可能战胜多少个人。

x可能战胜y的条件，x至少在一个网站的排名大于y。

对两个网站的排名分别排序后连边$rank_i\to rank_{i+1}$,之后会得到n点2(n-1)边的有向图，缩点后用拓扑序就各点的子树大小即为可能战胜的人数

• Solved by Pantw

给一个 $H\times W$ 的纸片，折痕只能平行于边界，问将其折成 $h\times w$ 的纸片至少要多少次。

注意两个方向都要算。

• Solved by Withinlover

一棵树， 叶子节点被黑白染色，初始时均为白色，要求所有被染成黑色的节点，其到根节点的路径上也必须有一条边被染色。

点的染色是动态的，你需要随时计算边的染色数量最少的染色方案，同时，使得白色的点到根的路径尽可能的不被染色。

输出每一时刻，最少的染边数量，以及此条件最少有多少白色节点受影响。

把根节点去掉，变成 $m$ 颗森林， 对于第一问，显然森林中每棵树对答案的贡献至多为1。考虑到第二问，染色的边越深越好。贪心的选择树中所有黑色节点的 $lca$ 进行染色即可。

由于每次只会涉及一个点的修改，每一次询问均记录差值。便可以做到 $O(q\log n)$ 的复杂度了。对所有黑色节点求 $lca$ 的操作可以利用 $DFS$ 序优化为两点的 $lca$，比较简单就不提了。

• Idea by Gary, Pantw
• Code by Gary

给定一个凸包，其上的点都横纵坐标都是整数，现在让你连接凸包上两点，把凸包变为两个多边形，满足两个多边形的面积都是整数

结合了一下场上的代码和网站的题解，对于一个点是原点的三角形，其面积为到原点的两条边的叉积/2，故我们在统计面积时不除2，通过面积和的奇偶性就可以判断是否为整数

可以发现只统计奇偶时，加法等价于异或，乘法等价于与

$f[S][x][y]$表示面积奇偶性为S，最后一条边的横坐标奇偶性为x,纵坐标奇偶性为y的个数

从某一条边开始枚举，对于每个边

for(int nx=0;nx<2;nx++) 
    for(int ny=0;ny<2;ny++) 
        ans+=f[(S^s(nx,ny,x,y))&1][nx][ny];
f[S&1][x[i]&1][y[i]&1]++;

其中$s(nx,ny,x,y)$表示$(nx,ny),(x,y),(0,0)$构成的三角形面积,$S$表示总面积,依次枚举即可

• Solved by Pantw

编程语言 Java2016 中没有字常量，只有一个变量 ?，在 $0$ 到 $255$ 之间随机取。

语言支持 +，-，*，/，max，min，以及括号。

可以定义宏，宏在编译时直接展开，宏名只能是一个小写英文字母。

给一个 $0$ 到 $255$ 之间的整数 $c$，要求构造一个 Java2016 中的表达式，使得这个表达式至少有 $1/2$ 的概率求值结果为 $c$。

可以看到样例给的 $1$ 的答案是

a = ? max ?
(a max a) / a

简单思考一下，我构造很多个 ? 求 max 的表达式，那么这个表达式取 $255$ 的概率就很大，然后我拿它自己除以自己，那么求值得到 $1$ 的概率也很大。

然后我拿这个近似的 $1$ 就可以直接倍增构造出所有所需整数。

一个例子：构造 $255$

a = ? max ?
b = a max a
c = b max b
d = c max c
e = d max d
f = e max e
g = f max f
h = g max g
i = h max h
j = i max i
k = j max j
l = k max k
m = l max l
n = (m max m) / m
o = n + n
p = o + o
q = p + p
r = q + q
s = r + r
t = s + s
t + t + t + s + r + q + p + o + n

• Solved by Withinlover

国王有一堆儿子，国王死了。

在他所有满18岁的儿子里面，选一个最年轻的继承王位。

好水啊不说了。