0%

ICPCCamp 2015 构造专题

发表于 更新于 分类于 阅读次数： 评论数：

这两天看了 Camp 2015 的构造题选讲，在这写几道题。

CF 468C: Hack it!

求一个区间 [$l$, $r$] 使得区间中的数的数位之和模 $a$ 为 $0$。

$l, r \leq 10^{200} \quad a \leq 10^{18}$

题解：
令 $l=1$，$r=10^{19}$，这样对应着一个和 $s$。由于 $r$ 很大，当每次把区间右移 $k$ 时 $s$ 会增加 $k$。所以把 $l$，$r$ 右移 $a - s \bmod a$ 即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

typedef BigInteger Int;

int main()
{
    Int a;
    cin >> a;
    Int l = 1, r = 1e18;
    r *= 10;
    Int s = r / 10 * 45 * 19 + 1;
    Int x = s % a;
    l += a - x, r += a - x;
    cout << l << " " << r << endl;
    return 0;
}

Andrew Stankevich Contest 44: H. Huffman Codes

给出 $n\leq 100$ 个哈夫曼编码当中的 $0/1$ 个数，问是否存在可能的哈夫曼编码。

CF 209C: Trails and Glades

有一张无向图 $\leq 10^6$，加最少的边使之有欧拉回路。

ZOJ 3823: Excavator Contest

在 $n \times n$ 的网格上，由边界某个格子出发四连通经过所有格子一次且仅一次再次回到边界上，要求拐弯的数量至少有 $n \times (n-1)-1$ 次。

Latvia U Contest 14: G. Mosaic

有三种颜色的珠子各 $a$, $b$, $c \leq 2^{31}$ 个，给出方案铺满若干层的三角形，且每层颜色必须相同。