CVBB ACM Team

====== 2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest ======

Virtual Participated on May 31, 2020.

VP & Practice available here: [[https://codeforces.com/gym/101142/standings|Codeforces Gym]]


====== Results ======

===== Summary =====

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

===== Virtual Participation =====

<HTML>
<table>
<style>
td, th {text-align: center;}
.cell-accepted {color: #0a0;font-weight: bold;}
.cell-rejected {color: #00a;}
.cell-time {font-size: 1.0rem;display: block;}
.contest-name {font-size: 1.5em;color: #445f9d;}
.successfulChallengeCount {color: green;}
.unsuccessfulChallengeCount {color: gray;}
</style>
<tr>
<th style="width:2em;" class="top left">
#
</th>
<th style="width:2em;" class="top">
=
</th>
<th style="width:4em;" class="top">Penalty</th>
<th style="width:4em;" class="top">
        <a>A</a>
</th>
<th style="width:4em;" class="top">
        <a>B</a>
</th>
<th style="width:4em;" class="top">
        <a>C</a>
</th>
<th style="width:4em;" class="top">
        <a>D</a>
</th>
<th style="width:4em;" class="top">
        <a>E</a>
</th>
<th style="width:4em;" class="top">
        <a>F</a>
</th>
<th style="width:4em;" class="top">
        <a>G</a>
</th>
<th style="width:4em;" class="top">
        <a>H</a>
</th>
<th style="width:4em;" class="top">
        <a>I</a>
</th>
<th style="width:4em;" class="top">
        <a>J</a>
</th>
<th style="width:4em;" class="top right">
        <a>K</a>
</th>
</tr>
<tr participantid="66425385">
<td class="left">
82
</td>
<td>
7
</td>
<td>
            711
    </td>
<td contestid="101142" problemid="77622" title="GNU C++11" acceptedsubmissionid="82017830">
        <span class="cell-accepted">+</span>
        <span class="cell-time">00:06</span>
    </td>
    <td contestid="101142" problemid="77623" title="GNU C++11">
<span class="cell-rejected">-5</span>
    </td>
    <td contestid="101142" problemid="77624" title="GNU C++11" acceptedsubmissionid="82020941">
        <span class="cell-accepted">+</span>
        <span class="cell-time">00:52</span>
    </td>
    <td contestid="101142" problemid="77625">
<span class="cell-rejected">&nbsp;</span>
    </td>
    <td contestid="101142" problemid="77626">
<span class="cell-rejected">&nbsp;</span>
    </td>
    <td contestid="101142" problemid="77627" title="GNU C++11" acceptedsubmissionid="82018971">
        <span class="cell-accepted">+2</span>
        <span class="cell-time">00:23</span>
    </td>
    <td contestid="101142" problemid="77628" title="GNU C++11" acceptedsubmissionid="82029290">
        <span class="cell-accepted">+1</span>
        <span class="cell-time">03:01</span>
    </td>
    <td contestid="101142" problemid="77629">
<span class="cell-rejected">&nbsp;</span>
    </td>
    <td contestid="101142" problemid="77630" title="GNU C++11" acceptedsubmissionid="82029071">
        <span class="cell-accepted">+2</span>
        <span class="cell-time">02:58</span>
    </td>
    <td contestid="101142" problemid="77631" title="GNU C++11" acceptedsubmissionid="82023720">
        <span class="cell-accepted">+1</span>
        <span class="cell-time">01:37</span>
    </td>
    <td contestid="101142" problemid="77632" title="GNU C++11" acceptedsubmissionid="82019743" class="right">
        <span class="cell-accepted">+1</span>
        <span class="cell-time">00:34</span>
    </td>
</tr>
</table>
</HTML>

===== Submit Distribution in Members =====

^    Solved     ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^  G  ^  H  ^  I  ^  J  ^  K  ^
|     Pantw     |  √  |     |     |     |     |  √  |     |     |     |  √  |     |
|  Withinlover  |     |  ○  |     |     |     |     |  √  |     |     |     |  √  |
|     Gary      |     |     |  √  |     |     |     |     |     |  √  |     |     |

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


----

====== Solutions ======

===== A: Anniversary Cake =====

  * Solved by **//Pantw//**

==== 题意 ====

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

==== 解法 ====

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

===== B: Boys and Girls =====

  * 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$ 这样的块缩小范围。其余情况均无解。


===== C: CodeCoder vs TopForces =====

  * Solved by **//Gary//**

==== 题意 ====

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

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

==== 解法 ====

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

===== D: Digital Addition =====

==== 题意 ====

==== 解法 ====

===== E: Easy Reading =====

==== 题意 ====

==== 解法 ====

===== F: Folding =====

  * Solved by **//Pantw//**

==== 题意 ====

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

==== 解法 ====

注意两个方向都要算。

===== G: Gangsters in Central City =====

  * Solved by **//Withinlover//**

==== 题意 ====

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

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

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

==== 解法 ====

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

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


===== H: Hard Cuts =====

==== 题意 ====

==== 解法 ====

===== I: Integral Polygons =====
  * Idea by **//Gary//**, **//Pantw//**
  * Code by **//Gary//**
==== 题意 ====

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

==== 解法 ====

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

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

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

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

<code>
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]++;
</code>
其中$s(nx,ny,x,y)$表示$(nx,ny),(x,y),(0,0)$构成的三角形面积,$S$表示总面积,依次枚举即可

===== J: Java2016 =====

  * Solved by **//Pantw//**

==== 题意 ====

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

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

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

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

==== 解法 ====

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

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

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

一个例子：构造 $255$

<code>
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
</code>

===== K: King’s Heir =====

  * Solved by **//Withinlover//**

==== 题意 ====

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

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

==== 解法 ====

好水啊不说了。

----

====== Timeline ======

^  Time  ^Action  ^
|   0    |Start   |
|  300   |End     |


----

====== Reflections ======
CVBB ACM Team

用户工具

站点工具

页面工具
