代码如诗

有 $T$ 组数据，每组数据有一个长度为 $n$ 的 $\tt 01$ 字符串，求构造一个 $n$ 个结点的树满足每个结点的度数的奇偶性符合 $\tt 01$ 串 $s$，且将这些点依次排列到一个环上，任意两条边不在非端点处相交。

现在有一个正整数序列 $a$ , 你可以选择一个位置 $i$ ，进行一次操作：将 $a_i$ 减去 $2$ ，将 $a_{i-1}$（如果存在）减去 $1$ ，将 $a_{i+1}$（如果存在）减去 $1$，问至少要多少次操作可以使数列中至少出现两个非正整数。

Translated by CmsMartin

题目描述

我们定义“魔法网格”为一个满足以下两个条件的大小为 $n \times n$ 的整数方阵：

$1.$ 从 $0$ 到 $n^2-1$ 的所有整数都在矩阵中出现过恰好一次。

$2.$ 矩阵中的每行元素的按位异或和与每列元素的按位异或和都相等。

按位异或，即 $C/C++$ 中的 $\wedge$ 运算符或 $Pascal$ 中的 $xor$ 运算符。

现在给你一个 $n$ ，保证 $n$ 是 $4$ 的倍数。请构造一个“魔法网格”。

输入仅包含一行，为一个整数 $n$ ，保证 $n$ 是 $4$ 的倍数。

输出 $n$ 行，每行 $n$ 个整数，每个整数之间用一个空格隔开，第 $i$ 行第 $j$ 列输出的数表示“魔法网格”的第 $i$ 行第 $j$ 列的数。

如果有多个答案，请输入任意一个。保证每组数据至少有一个合法解。

给出一个 $n\times m$ 的矩阵 $a$（$1\le n,m\le 100$），其中 $1\le a_{i,j}\le 10^9$。

定义一个矩阵是合法的当且仅当没有任何两个相邻的元素是相等的（上下左右为相邻）。

你可以将矩阵中若干个元素加一，使其合法，输出最终矩阵。

形式化地，对于每个 $(i,j)$，$b_{i,j}=a_{i,j}$ 或者 $b_{i,j}=a_{i,j}+1$，输出合法的 $b$ 矩阵。

$t$ 组数据（$t\le 10$）。

给定长度为n（n为偶数）的数列x的偶数项，求出数列x的奇数项，使得对于任意t∈[1,n]，x1+x2+...+xt为平方数，若无解输出No，否则先输出一行Yes，再输出x1,x2,x3,...,xn，若有多解输出任意一组解。

$x$ 数组奇数项不超过 ${10}^{13}$，偶数项不超过 $2 \times {10}^5$，$n \le 10^5$。

在一棵树上删去一些边，使得形成的几个连通块，都有且仅有 $3$ 个结点。

第一行是数据组数，接下来：

对于每组数据：

• 第一行一个正整数 $n$，表示结点数量。

• 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u,v$ 间有一条边。

对于每组数据：

• 若不存在任何一种删边方式满足条件，则输出：-1。

• 若存在满足条件的删边方式：

• 第一行，一个正整数，删掉的边数。

• 第二行，所有删掉的边的编号，若不用删除任何边，则输出一个空行。

by @gty314159

Treeland包含n个城市和n-1条道路。每条道路都是双向的，连接两个不同的城市。从任何一个城市你都可以通过公路到达任何其他城市。是的，你是对的——这个国家的拓扑结构是一棵没有方向的树。

在Treeland有一些私人道路公司。政府决定向这些公司出售道路。每条路都属于一家公司，一家公司可以拥有多条道路。

政府害怕看上去不公平。他们认为，如果有一家公司拥有两条或两条以上的进入这个城市的道路，那么这个城市里的人就会认为这是不公平的。政府希望这样不公平的城市数量不超过k，那么最少需要多少个不同的公司来参与投资？

选择公司的数量r，这样就可以将每条道路分配给某家公司，这样一家公司拥有两条或两条以上到达同一个城市道路的城市数量最多为k。（译者注：这里是有一点费脑子，大家多想想）换句话说，如果对一个城市来说，所有的到达这座城市的道路都属于不同的公司，那么这个城市就是好的。你的任务是找到最小的r，然后分配所有道路，使得不太好的城市的数量不超过k。

图为第一个例子(n=6，k=2)。答案r=2。边上的数字表示边的编号。边的颜色表示公司：红色为第一个公司，蓝色为第二个公司。灰色顶点(3号)不好。这类顶点的数目(只有一个)不超过k（k=2）。如果有一家公司，在分配合理的情况下，不可能有2个不好的城市。