【泛做】构造题选做 · 2

没啥特别原因,就是底下那篇文章题太多了就分流出一部分。

$1$ UVa1697

给定一排长度为 $4n$ 的格子,编号从 $-2n+1$ 到 $2n$ 每个编号为正的格子中有一个物品,其中每个编号为奇数的格子中有一个 $B$ 类物品,编号为偶数的格子中有一个 $A$ 类物品。

你只能进行一种操作:选择某两个相邻的都有物品的格子,移动到另外两个相邻的空格子中,同时不能改变两个格子的相对位置。

要求进行最少的操作使得所有物品以 AAA…ABBB…B ($n$ 个 $A$ 和 $n$ 个 $B$) 的形式排列在一起 输出一种可行方案

$3\leq n \leq 100$

人类智慧学不来了orz

考虑 $n=3,4,5,6,7$ 的时候都可以人类智慧。那么对于 $n > 7$ 时考虑增量构造,即从 $n$ 构造到 $n+4$。

那么 $n=4$ 时可以这么构造:

__babababa

abbabab__a

abba__bbaa

a__abbbbaa

aaaabbbb__

然后考虑对于 $n+4$,记 $|BA|$ 表示有一堆 bababa 这种东西。

那么考虑 $n+4$ 可以这么玩:

__|BA|

ab|BA|b__a

abba__|BA|bbaa

发现中间那一段和起始状态是一样的,就可以大力递归,回代的时候回代一下即可。

$n=3\sim 7$ 我选择直接从网上抄来别人的人类智慧,毕竟我莫得智慧.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void oo(int x, int y){
cout << x << " to " << y << '\n' ;
}
void work(int L, int R){
int len = R - L + 1 ;
if (len == 3 << 1)
return oo(2, -1), oo(5, 2), oo(3, -3), void() ;
if (len == 4 << 1)
return oo(L + 5, L - 2), oo(L + 2, L + 5), oo(L - 1, L + 2), oo(L + 6, L - 1), void() ;
if (len == 5 << 1)
return oo(L + 7, L - 2), oo(L + 2, L + 7),
oo(L + 5, L + 2), oo(L - 1, L + 5), oo(L + 8, L - 1), void() ;
if (len == 6 << 1)
return oo(L + 9, L - 2), oo(L + 6, L + 9), oo(L + 1, L + 6),
oo(L + 5, L + 1), oo(L - 1, L + 5), oo(L + 10, L - 1), void() ;
if (len == 7 << 1)
return oo(L + 7, L - 2), oo(L + 4, L + 7), oo(L + 11, L + 4),
oo(L + 2, L + 11), oo(L + 8, L + 2), oo(L - 1, L + 8), oo(L + 12, L - 1), void() ;
oo(R - 2, L - 2), oo(L + 2, R - 2), work(L + 4, R - 4), oo(L - 1, R - 5), oo(R - 1, L - 1) ;
}
int main(){
while (cin >> N) work(1, N * 2), puts("") ;
}

$2$ BZOJ4148 Pillars

给定一个 $n\times m$ 的矩形,其中有 $f$ 个 $2\times 2$ 的障碍物,其中任意两个障碍物中心之间的欧几里得距离至少为 $6$,且每个障碍物的中心到边缘的距离至少为 $3$。

请找到一条从左下角 $(1,1)$ 出发经过所有没有障碍物的点各一次的且最后回到左下角的回路。

保证 $n,m$ 均为偶数,且 $1\leq n,m\leq 1000$ .

就是考虑如果没有障碍的走法,由于 $n,m$ 都是偶数,所以可以从 $(1,1)$ 上到 $(1,n)$,然后从 $(1,n)$ 到 $(n,n)$ 再到 $(n,n-1)$ 再到 $(2,n-1)$ 这么蛇形走。

考虑有了障碍,因为每个障碍可以看做是独立的的,所以大概可以这么走:

其中紫色是障碍,黄色是原来的路线,红色是新的。由于 $6$ 的限制,所以可以这么绕。

所以是道细节题233

代码先鸽着,什么时候有心情再写。s

$3$ 【UR #6】 智商锁

构造一个节点数不超过 $100$ 的无向图,使其生成树个数对 $998244353$ 取模的结果为 $k$ 。

$k\leq 10^9$

看题,仔细一想,莫非是什么神秘的 $\boldsymbol{EGF}$ 大力乱搞(警觉)。

结果人傻了……以下是官方做法:

考虑如果两个图只有一个公共点,那么生成树个数为两个图相乘。那么随机 $1000$ 个随机无向图,两两拼凑出 $10^6$ 个无向图,然后对每一个在 map 里找 $k$ 的逆元即可。如果没有就再随机一遍。

发现这样实际上几乎不可能没有解。。。

思考熊

降智打击.jpg

$4$ 【UNR #1】Jakarta Skyscrapers

有一个数集,最初其中只有 $a$ 和 $b$。

你可以进行最多 $400$ 次操作,每次选择集合中满足 $i>j$ 的 $i$ 和 $j$,把 $i-j$ 加入集合中,使得最后 $c$ 在这个集合中。

$a,b,c\leq 10^{18}$

考虑构造中间状态。发现可以用 $a-(a-b-c)$ 构造 $b+c$, 可以用 $a-(a-b-b)$ 构造倍增,于是考虑先辗转相除得到 $1$,然后倍增,然后就没了。注意,如果一开始 $(a,b) \not|~c$ 的话是无解的。那么考虑同除
$(a,b)$ 就可以快乐地更相减损得到 $1$ 了。