定义

  • 构造一些操作，使得数据满足操作要求，通常还会有次数限制

方法

此类题目现在遇到过三种做法：

  • 一种是直接操作，不关心部分值，直接对全局操作，使得再让全局满足要求的同时，使得部分也满足要求
  • 另一种是进行操作，最后只改变一个量，每次用多步做一步
    （和魔方有点像？）

例题

1.B. Siga ta Kymata

  • 题目描述：
    给你一个排列 $^{\text{∗}}$ 。从 $1$ 到 $n$ 的每个整数的排列 $p$ 。您还拥有一个大小为 $n$ 的二进制 $^{\text{†}}$ 字符串 $s$ ，其中 $s_i = \mathtt{0}$ 代表所有 $1 \le i \le n$ 。您最多可以执行以下操作 $5$ 次：
    选择任意两个整数 $l$ 和 $r$ ，使得 $1 \le l \le r \le n$ .然后，对于每一个 $i$ 使得 $l< i< q$ 和 $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 同时成立，你将把 $s_i$设为 $\mathtt{1}$ 。
    您还会得到一个大小为 $n$ 的二进制字符串 $x$ 。执行运算后，对于每一个 $1 \le i \le n$ 都必须成立：如果 $x_i = \mathtt{1}$ ，则 $s_i = \mathtt{1}$ 。注意，如果 $x_i = \mathtt{0}$ ，那么 $s_i$ 可以有任意值。
    找出最多5个运算序列，使上述条件得到满足，或者报告不可能做到这一点。请注意，您不必尽量减少操作次数。

解法：

1
2
3
4
5
6
7
8
|----------------|-------------------n------------
|                |                   |           |
|----------------|-------------------|——————————a[n]
|                |                   |           |
a[1]----------------------------------------------
|                |                   |           |
|                |                   |           |
|----------------1--------------------------------

  • 一共画了5个框，也就是5次操作的范围
  • 这里实际上是把所有能改变的全改变了，然后也就满足了要求
  • 所以5次也是合理的，证明了做法的正确

2.西安之泪 - 洛谷

  • 题目描述：
    给定一颗无根树,共有n个顶点。每个顶点 i 都具有一个点权$a_i$，初始所有点权都为0。
    你可以进行如下的操作最多不超过$3n$次：
    指定顶点的编号 r,u (1≤r,u≤n)，使得这棵树暂时以顶点 r 为根，随后对于顶点 u 的子树中的每一个顶点 v，将其点权修改为 av​⊕u。此处的 ⊕ 表示按位异或。

这一题就是尝试操作每一个顶点，分步完成。
让每个顶点的邻居给这个顶点发一次，那么最终剩下的节点就被⊕了出度数-1次。如果是偶数，不变；但是奇数时，为了保持不变，那么我们在自己给自己发一次就行了。