2017 NEERC

Problem A. Archery Tournament

题目描述：在二维平面上，会陆续出现一些圆，以及一些询问，询问点是否在圆内，如果是，则输出那个圆，并把那个圆删掉，否则输出\(-1\)。注意：这些圆均与\(x\)轴相切，并且这些圆不会相交。

solution

因为这些圆都与\(x\)轴相切，所以经过直线\(x=x'\)的圆不会超过\(log\)个。所以只要找出询问点的左右\(log\)个圆逐一判断即可。

时间复杂度：\(O(nlog10^9)\)

Problem B. Box

题目描述：用一张\(n \times m\)的网格纸，折出\(a \times b \times c\)的长方体。输出是否可解。注意：折痕只能是网格线。

solution

题解：答案只有两种情况：

\(3b+a+c \leq w\)且\(a+c \leq h\)。
\(2a+2c \leq w\)且\(a+2c \leq h\)。

\(a, b, c, w, h\)全部组合一下。

时间复杂度：\(O(1)\)

Problem C. Connections

题目描述：给出一个顶点数为\(n\)的有向图，删掉一些边，使得只剩下\(2n\)条边，且任意两点能互相到达。

solution

从\(1\)开始搜索，搜到的边为留下的边。然后将边的方向全部相反，从\(1\)开始搜索，搜到的边也是留下的边。这样就有至多\(2n-2\)条边，剩下的随便补足\(2n\)条就好了。

时间复杂度：\(O(n)\)

Problem D. Designing the Toy

题目描述：给出一个由\(1 \times 1 \times 1\)方块组成的立体图形的正视图、侧视图、俯视图的面积，问是否存在一种堆积方式，满足题目所给的数据。

solution

假设面积分别是\(a, b, c, c \geq max(a, b)\)，将面积为\(a\)的面变成\(a \times q\)，面积为\(b\)的面变成\(b \times 1\)，然后就相当于在一个\(n \times m\)的网格中填\(c\)个格子，所以如果\(c>ab\)，则无解；否则先填满对角线，剩下的随便填就好了。之所以把面变成\(a \times 1\)和\(b \times 1\)，是因为这样子能填的方块最多，即\(ab\)。

时间复杂度：\(O(c)\)

Problem E. Easy Quest

题目描述：有\(n\)个关卡，每个关卡为一个数字\(a_i\)。如果\(a_i>0\)，则是武器，如果\(a_i<0\)，则是怪兽，只能用值为\(-a_i\)的武器杀死，如果\(a_i=0\)，则可以生成一个任意值的武器。问是否能通关，若能，则每个\(a_i=0\)应该生成什么武器。

solution

贪心，尽量先用已有的武器，再用能生成任意值的武器。

时间复杂度：\(O(n)\)

Problem F. The Final Level

题目描述：用长度为\(n\)的\(L\)型方块摆在二维网格平面上，仅通过方块从\((0, 0)\)走到\((a, b)\)。输出方案。

solution

为了方便，可以先将\((a, b)\)映射到第一象限。然后贪心构造方案。可以逆着构造，zhe这样对于边界的判断会方便一些。

时间复杂度：\(O(n)\)，\(n\)为方块数

Problem G. The Great Wall

题目描述：现要建一堵长度为\(n\)的墙。第\(i\)段墙有三个属性值\(a_i, b_i, c_i\)。现给定一个值\(r\)。自行选定两个值\(x, y\)，形成两个区间\([x, x+r-1], [y, y+r-1]\)，这两个区间必须包含于\([1, n]\)。\(x, y\)对应的墙的值为\(\sum v_i\)，当\(i\)不属于任一区间时，\(v_i=a_i\)；当\(i\)只属于一个区间时，\(v_i=b_i\)；当\(i\)属于两个区间时，\(v_i=c_i\)。求出第\(k\)小的墙的值。

solution

先将\(b_i-=a_i, c_i-=a_i, a_i=0\)。

二分答案\(value\)，判断有多少个数对\((x, y)\)小于等于\(value\)。

先处理区间不相交的情况。预处理\(h_i=\sum_{j=0}^{r-1} b_{i+j}\)，枚举\(i\)，假设\(y=i\)，然后用\(multiset\)之类的数据结构，计算出有多少对\((x, y)\)小于等于\(value\)。

接着就是构造两个函数。

\[g_i=\sum_{j=1}^{i-1} c_j-2b_j + \sum_{j=i}^{i+r-1} c_j-b_j
\]

\[f_i=\sum_{j=1}^{i-1} 2b_j-c_j + \sum_{j=i}^{i+r-1} b_j
\]

这样，数对\((x, y)\)的相交区间的值为\(g_x+f_y\)。这样就可以用与上面一样的方法来求出有多少对\((x, y)\)小于等于\(value\)。

时间复杂度：\(O(nlogn)\)

Problem H. Hack

题目描述：

1 modPow(a, d, n) {

2   r = 1;

3   for (i = 0; i < 60; ++i) {

4     if ((d & (1 << i)) != 0) {

5       r = r * a % n;

6     }

7     a = a * a % n;

8   }

9 }

其中只有第\(5, 7\)行耗时间，若表达式为\(x*y%n\)，则时间为\((bits(x)+1)(bits(y)+1)\)，\(bits(x)\)为二进制位数。已知\(n, d\)是这样生成的：首先随机找两个二进制位数为\(30\)的质数\(p, q\)，其中\(n=pq\)，而\(d\)由\(1\)~\(\phi(m)-1\)随机选取，且与\(m\)互质。现给出\(n\)，每次可向系统输出一个\(a\)，系统返回所需的时间。最后确定\(d\)。

solution

待解决。

Problem I. Interactive Sort

题目描述：随机生成一个\(n\)排列，将奇数按顺序设为\(o\)数组，将偶数按顺序设为\(e\)数组。每次向系统输出一个数对\((x, y)\)，系统返回\(o[x]\)与\(e[y]\)的大小关系，最后确定\(o, e\)数组。

solution

判断\(o[1]\)与\(e\)的所有数的大小关系，从而确定\(o[1]\)，也同时将\(e\)分成小于\(o[1]\)和大于\(o[1]\)两部分，以此类推，会将\(e\)分成\(i+1\)份，在以后的判断中，只要从\(i+1\)份中每份选一个数与\(o[i]\)比较，即可将\(o[i]\)的大小范围缩小到两份，再与这两份中每一个数相比较即可。

时间复杂度：\(O(nlogn)\)

Problem J. Journey from Petersburg to Moscow

题目描述：有一个有边权的无向图，一条从\(1\)到\(n\)的路径的长度为路径中最长的\(k\)条边的和，如果路径中不足\(k\)条边，则为全部边的和。问\(1\)到\(n\)的最短距离。

solution

待解决。

Problem K. Knapsack Cryptosystem

题目描述：有一个数列\(a_i\)，且满足\(a_i>\sum_{j=1}^{i-1} a_j\)，设\(q=2^{64}, r\)与\(q\)互质，且为一个正数。令\(b_i=(a_i \cdot r) mod q\)。现生成一个数\(num\)，将\(num\)的二进制中为\(1\)的位\(i\)找出，令\(s=\sum b_i mod q\)。现给出\(s\)，求\(num\)。

solution

假如\(n \leq \frac{2}{3}logq\)，则可以将\(n\)分成两半，然后爆搜出两半分别能构成的和，再枚举其中一半的和，另一半能单调枚举。

假如\(n > \frac{2}{3}logq\), 因为\(a_i>\sum_{j=1}^{i-1} a_j\)，所以\(a_1 < \frac{q}{2^n}=t\)，所以可以枚举\(a_1\)，又因\(r\)为奇数，\(q=2^{64}\)，所以\(a_i\)与\(b_i\)最低位\(0\)的个数相同，设个数为\(z\)，所以只需要枚举\(\frac{t}{2^z}\)。

其次可以根据\(a_1\)与\(b_1\)，算出\(r\)，但\(r\)的最高\(z\)位是不确定（因为被模了），所以可以枚举最高位\(2^z\)。然后逐一算出\(a_i\)，看\(a_i\)是不是指数增长，若是，则找到了对的\(r\)，然后从大到小贪心分解\(s\)，得到答案。

时间复杂度：\(O(\sqrt[3]{q})\)

Problem L. Laminar Family

题目描述：给出一棵树，用很多数对\((x, y)\)的路径覆盖树，如果路径有相交部分（包括点相交，但不算互相包含），则输出\(No\)，否则输出\(Yes\)。

solution

树链剖分。将数对按路径长度从长到短排序，然后对每个数对随机生成一个数值\(key\)，将路径上的每个点都异或这个值，判断时只要判断路径上每个点的值是否都相同。

时间复杂度：\(O(nlogn)\)

巴特西

2017 NEERC

2017 NEERC

Problem A. Archery Tournament

Problem B. Box

Problem C. Connections

Problem D. Designing the Toy

Problem E. Easy Quest

Problem F. The Final Level

Problem G. The Great Wall

Problem H. Hack

Problem I. Interactive Sort

Problem J. Journey from Petersburg to Moscow

Problem K. Knapsack Cryptosystem

Problem L. Laminar Family

最新文章

热门文章