2014-2015 ACM-ICPC, NEERC, Central Subregional Contest

代码和题目链接: https://github.com/zimpha/acm-icpc/tree/master/archived/2014-NEERC-Central

提交地址: http://atpp.vstu.edu.ru/cgi-bin/arh_problems.pl?id_tm=10048

Problem A. Balloons

给出$n$个点$(x_i,y_i)$, 问能否搭出一个台阶, 使得任意两个台阶高度差不超过1, 并且可以从$(0,0)$遍历每个点.

数据规模: $1 \le n \le 10^4, 1 \le x_i, y_i \le 10^4$

应该都会做.

Problem B. Intellect Ltd

给出长度为$n+1$的数字串, 你要删掉一个数字使得剩下的数字可以被11整除, 问方案数.

数据规模: $1 \le n \le 10^5$

能被11整除的数满足奇数位置和偶数位置数字和只差是11的倍数.

Problem C. Race condition

给出$n$个线程, 第$i$个线程有$m_i$个指令, 问指令的运行方案数.

数据规模: $1 \le n \le 10, \sum m_i \le 20$

Problem D. Ingress

给出平面上$n$个点$(x_i,y_i)$, 任意三点不共线. 要求找出一个平面图包含最多的三角形.

数据规模: $3 \le n \le 10^4, -300000 \le x_i, y_i \le 300000$

假设凸包上有$m$个点, 那么答案就是$3n - 2m - 2$.

可以这么考虑, 先搞出一个凸包, 然后每往凸包内加一个点都会新增3个三角形.

Problem E. 4x4

给出一个$5 \times 5$的棋盘(具体见题面), 给定初始局面, 要求输出一个不超过$10000$步的解.

首先一定是有解得, 我们可以先通过一系列操作使得棋盘只有4个角的位置可能是不同的.

如果固定R在(1,1)这个位置, 然后这样只有6中可能(顺时针方向): RYBG, RGYB, RGBY, RYGB, RBGY, RBYG.

分别对这6种情况手动构造解就好了.

Problem F. Sages

有一个方程$\frac{1}{k_1}+\frac{1}{k_2}+\dots+\frac{1}{k_n}=1, k_i \ne k_j, i \ne j$, 告诉你$n$找出$k$的一组解.

数据规模: $1 \le n \le 20, 1 \le k_i \le 100$

$n$比较小的是可以爆搜的, 然后利用这两个性质可以扩展答案的长度$\frac{1}{n} = \frac{1}{n+1}+\frac{1}{n(n+1)}$, $\frac{1}{n}=\frac{1}{2n}+\frac{1}{3n}+\frac{1}{6n}$.

貌似也可以直接手动从$\frac{1}{2}$构造出全部答案.

Problem G. Bus Conductor

如果一个6位数的前三个数字的和与后三个数组和相同, 那么就称之为lucky. 然后给出一些连续数字的情况, 找出最早出现的起点.

数据规模: $1 \le n \le 1000$

直接上kmp就好了.

Problem H. Cryptography

给出$n$个数字$a_1,a_2,\dots,a_n$, 已知$a_1 \oplus k \le a_2 \oplus k \le \dots \le a_n \oplus k$. 问$k$是否唯一, 如果唯一输出这个值.

数据规模: $1 \le n \le 10^5$

从高到低考虑$k$的每一位, 如果这一位0和1均可行, 那么$k$不唯一, 否则可以把序列划分成两部分单独考虑.

Problem I. Belt Drive

给出一个传送带的长度$l$以及两个圆的半径$r_1,r_2$, 求出圆心的间距.

数据规模: $1 \le r_1, r_2 \le 1000, 2 \pi (r_1+r_2) \le l \le 10^4$

二分间距即可.

Problem J. Dominoes

给出$n$个多米诺骨牌, 两段分别写着0~6的数字, 问能否找到一个排列方式使得相邻两个骨牌连接处的数字相同.

数据规模: $1 \le n \le 1000$

就是欧拉路的判断.

Problem K. Embroidery

给出一个$1 \times n$个格子, 对角线也有边, 问从左下角开始的哈密尔顿路的数目.

数据规模: $1 \le n \le 30$

逐列dp, 只需要考虑这一列两个点的联通性就好了, 然后暴力转移到下一列.

• Relative Posts