杂题选讲

Xor Sum

给出正整数 $N$。

求出整数对 $u$ 和 $v$ $(0 \le u,v \le N)$ 的数目，使得存在两个非负整数 $a$ 和 $b$ 满足 $a\ xor\ b = u$ 和 $a\ +\ b= v$ 。这里，$xor$ 表示按位异或。 要求对答案取模 $10^9 + 7$。

$N \le 10^{18}$

题解 ：

云剪贴板

すぬけ君の塗り絵 2

题意 ：

平面上有一个左下角坐标 $(0,0)$ 右上角坐标 $(W,H)$ 的矩形，起初长方形内部被涂白。

现在给定 $n$ 个点，你每次在以下 $4$ 种操作中选择一种：

  • 将矩形内 $x<x_i$ 的区域涂黑
  • 将矩形内 $x>x_i$ 的区域涂黑
  • 将矩形内 $y<y_i$ 的区域涂黑
  • 将矩形内 $y>y_i$ 的区域涂黑

现在你需要最大化操作后白色矩阵周长。

$1 \le W,H \le 10^8$

$1 \le N \le 3 \times 10^5$

$x_i,y_i$ 取值保证合法，输入都是整数，给定的 $n$ 个点坐标两两不同。

题解 ：

ARC063F すぬけ君の塗り絵 2 | Pozhu's blog

[CERC2016]机棚障碍 Hangar Hurdles

题目描述

你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为 $n$ 行 $n$ 列的网格图，其中每个格子要么是空的，要么有障碍物。行从上到下依次被编号为 $1$ 到 $n$，列从左到右依次被编号为 $1$ 到 $n$。

存放飞机零件的大型集装箱能在飞机仓库的地面上自由移动是很重要的。我们可以将每个集装箱看作一个以某个格子为中心的边平行于坐标轴的正方形。对于一个奇数 $k$，一个尺寸为 $k$ 的集装箱是一个包含 $k$ 行 $k$ 列的正方形。一个集装箱的坐标为其中心格子的坐标。集装箱可以向上下左右移动，但不能碰到障碍物，且不能移出仓库的边界。

给定 $q$ 对格子 $A_k$ 和 $B_k$，对于每对格子，请找到能从 $A_k$ 移动到 $B_k$ 的集装箱的最大尺寸，注意这个尺寸也要是一个奇数。

输入格式

第一行包含一个正整数 $n$（$2\le n \le 1000$），表示仓库的尺寸。

接下来 $n$ 行，每行 $n$ 个字符，描述整个仓库，其中 . 表示空格子，# 表示障碍物。接下来一行包含一个正整数 $q$（$1\le q\le 300000$），表示询问的个数。

接下来 $q$ 行，每行四个正整数 $A_x,A_y,B_x,B_y$（$1\le A_x,A_y,B_x,B_y\le n$），分别表示 $A$ 和 $B$ 的坐标。

输入数据保证 $A$ 和 $B$ 是不同的空格子。

输出格式

输出 $q$ 行，每行一个整数，对于每个询问输出最大尺寸，如果不存在解，那么输出 $0$。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7
.....#.
...#.#.
....#..
....###
....#..
#......
.......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7

样例输出 #1

1
2
3
4
5
1
0
3
1
1

实际上这题很水。

首先想了并查集维护连通块，对每种直径开一个并查集。

大概是假的，空间可能开不下。

然后开始想别的做法。

考虑到每次询问相当于从 $S$ 到 $T$ 走一条路径使得路径上的最小值最大。

自然想到最大生成树。

但是要求最大生成树上的最小值。

自然想到kruskal重构树。

于是先预处理每个点能扩展到的最大直径作为点权，网格图上和相邻点连边，边权是两点点权的较小值（这样才能从一个点走到另一个点）。然后建出重构树，对重构树进行树剖，每次询问先判断是否联通，然后找LCA即可。

或许使用tarjan求LCA可以做到更优的复杂度，但是我不会。

上面的做法是 $O(n2+qlog⁡n)$ 的，足以通过本题。

实现时要注意的细节就是由于原图不保证联通重构树可能是重构森林，树剖是不能直接对着最大的标号树剖。

然后用相同的思想就可以解决这个著名题 ：

Peaks

题目描述

在 Bytemountains 有 $n$ 座山峰，每座山峰有他的高度 $h_i$。有些山峰之间有双向道路相连，共 $m$ 条路径，每条路径有一个困难值，这个值越大表示越难走。

现在有 $q$ 组询问，每组询问询问从点 $v$ 开始只经过困难值小于等于 $x$ 的路径所能到达的山峰中第 $k$ 高的山峰，如果无解输出 $-1$。

输入格式

第一行三个数 $n,m,q$。
第二行 $n$ 个数，第 $i$ 个数为 $h_i$。

接下来 $m$ 行，每行三个整数 $a,b,c$，表示从 $a \to b$ 有一条困难值为 $c$ 的双向路径。
接下来 $q$ 行，每行三个数 $v,x,k$，表示一组询问。

输出格式

对于每组询问，输出一个整数表示能到达的山峰中第 $k$ 高的山峰的高度。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2

样例输出 #1

1
2
3
4
6
1
-1
8

数据规模与约定

对于 $100\%$ 的数据，$n \le 10^5$，$0 \le m,q \le 5\times 10^5$，$h_i,c,x \le 10^9$。

不写题解了，应该不难。

放俩构造

[IOI2014]game 游戏

题目描述

健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 $n$ 个城市（编号为 $0,\cdots,n−1$），其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。

梅玉问健佳，是否任意两个城市之间都可以坐飞机互达（直接或间接），健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问”城市 $u$ 和 $v$ 之间有直接航线吗？”，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 $r = \frac{n (n−1)}{2}$ 个问题。如果由前 $i$（$i<r$）个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接），梅玉就获胜。否则意味着她需要知道全部 $r$ 个回答，此时健佳获胜。

为了让游戏更好玩，他们俩同意，健佳可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就是根据梅玉此前的提问来决定此后如何作答。你的任务是，通过决定健佳如何回答，来帮助他赢得游戏。

输入格式

  • 第 $1$ 行：一个正整数 $n$，代表城市数量。
  • 余下 $r$ 行：每行包含两个整数 $u$ 和 $v$，表示对城市 $u$ 和 $v$ 的提问。

输出格式

  • 共 $r$ 行，对于每次梅玉的提问，你必须回答在城市 $v$ 和 $u$ 之间是否有直接航线。具体而言，返回值 $1$ 表示有，$0$ 表示没有。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
4
0 3
1 0
0 2
3 1
1 2
2 3

样例输出 #1

1
2
3
4
5
6
0
1
0
1
0
1

提示

子任务及数据规模

子任务 分值 $n$
$1$ $15$ $n=4$
$2$ $27$ $4 \le n \le 80$
$3$ $58$ $4 \le n \le 1500$

题目并不困难。

首先这题可以离线，于是问题变得容易。

发现询问是完全图的所有边。

考虑每次询问回答联通则合并了两个连通块。

于是我们容易构造出一种方案，使得整张图最后只有一个连通块。

方法是构建一颗生成树，保证最后一次询问是一条树边的话，则一定要问完所有询问才能确定树的形态。

实现起来可以先合并最后一次询问的两个端点，再对于每次询问如果两点在同一连通块内输出 $0$，否则输出 $1$ 并合并这两个连通块。

注意钦定最后一次询问的返回值为 $1$。

所以这题做完了，看来是构造入门题。

HonestOrUnkind

题面翻译

现在有 $n$ 个人，编号从 $0\sim n-1$。这些人中有 $a$ 个人是诚实的，剩下的 $b$ 个人是不友好的。这 $n$ 个人都知道各自的身份，但是你只知道有 $a$ 个诚实的人和 $b$ 个不友好的人，你现在试图通过询问来得知他们的身份。

你可以进行询问，询问格式类似于 ? x y，表示向 $x$ 询问 $y$ 是否是诚实的。返回答案按照如下规则：

  • 如果 $x$ 是诚实的人，那么他会按照事实返回答案，也就是说如果 $y$ 是诚实的，返回答案就为 $\rm Y$，否则返回 $\rm N$。
  • 如果$x$是不友好的人，那么他会任意选择 $\rm Y$ 和 $\rm N$ 来回答。也就是说 $x$ 是可以按照某种策略来回答你的问题的。

现在请你在 $2n$ 次询问以内确定 $n$ 个人的身份，如果不可能，请输出 Impossible，否则请按照 ! S0S1S2...Sn-1 的格式输出（其中 $0,1,2,\ldots,n-1$ 都为下标，$S_i$ 表示 $i$ 的身份，如果第 $i$ 个人是诚实的，请输出 $1$，否则输出 $0$，身份之间没有空格）。

如下是一个成功的询问的示例：

1
void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);}

上面这个交互函数中的 $s$ 为字符串变量，用来读入返回的答案。

制約

  • $ 1 \le A,B \le 2000 $

这题可以体现出一些构造题的妙处来，这题属于看题解前冥思苦想看完题解觉得很简单的题型吧。

CF1182F Maximum Sine

一道CF *2700，然而其原题解思想并不很难。

这题有一些值得深入思考的地方，于是单独写了题解。

[ARC061F] 3人でカードゲーム

应该讲不到这题吧（

三人 $a,b,c$ 面前分别有 $N,M,K$ 张牌, 每张牌上写了 $a,b,c$ 中的一个, 规则如下：

第一回合是 $a$ 的回合,若轮到某个玩家行动时他面前没牌了,该玩家获胜

否则拿出牌堆中的一张牌，丢掉它，并进入该牌上写着的玩家的回合 游戏开始前牌的所有情况共 $3^{n+m+k}$种。

求 $a$ 获胜的情况数，对 $1e9+7$ 取模。

$1 \le N,M,K \le 3 \times 10^5$

题解 ：

我们重设一下原题面的数 ：

把 $N,M,K$ 换成 $n_1,n_2,n_3$。

总牌数为 $n = n_1 + n_2 + n_3$。

把 $a,b,c$ 换成 $1,2,3$。

于是变量名舒服多了。

考虑