构造
T1
构造一组不相同的 \(x,y,z\) ，使得对于给定的 \(n\) ，满足 \(\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = \frac{2}{n}\)
=> 自己做的，不知道是不是正解
因为只需要一组，所以我们可以先让 \(z = n\)，那么式子就可以转化成
这个就比较好想了，直接让 \(x = n \times (n + 1)\)，\(y = n + 1\) ，这个时候式子就成立了。只要 \(n \ne 1\) 就可以。1的时候无解。
好好好，老师弄出来的答案也是这个。
（原题CF743C，黄题，注意特判一下1）
int n = fr();
if (n == 1) {
wj;
return 0;
}
cout << n << ' ' << n + 1 << ' ' << n * (n + 1) << endl;
T2
有一个长度为 \(n\) 的序列 \(a[]\)，现在要把他分成四个长度非零的子段，用A，B，C，D表示这四段的和，希望 \(\max(A,B,C,D) - \min(A,B,C,D)\) 尽可能小。
求最小值。
\(solution\)
先考虑枚举中间的端点的位置，于是 \(A + B\) 和 \(C + D\) 的值就确定了，可以发现，让 \(A,B\) 和 \(C,D\) 两组之间互相靠近是不会影响的，那就二分找到中间值再算一下就可以了。
T3
给出 \(N\) 个盒子，每个盒子中有 \(A_i\) 个糖果。每次能进行的操作如下：选定两个盒子，记大的一边为 \(A_x\) 个，小的一边为 \(A_y\) 个，从 \(x\) 中拿出 \(A_y\) 个放到另一个盒子里。
目标是把所有糖果放到两个盒子里。找出一个合法方案或者判定无解。
\(solution\)
通过 \(m\) 次操作一定可以使三个盒子变成两个盒子。
证明：取三个盒子，令盒子从小到大分别为 \(x,y,z\) ，设 \(a_y = k \times a_x + t\)
用二进制表示出 \(k\) ，对于 \(k\) 的第 \(i\) 位进行下列操作：
- 如果 \(k\) 的第 \(i\) 位为 \(0\) ，那么进行一次 \((x,z)\)
- 如果 \(k\) 的第 \(i\) 位为 \(1\) ，那么惊醒一次 \((x,y)\)，则 \(k\) 这一位的 \(1\) 会被当前的 \(2^{i- 1} * a_x 夺去\)
这样，在经过若干次操作之后，\(a_y\) 的值会变成 \(t\) ，我们对 \(x,y,z\) ，重新排序，那么一定有 \(a_x' < a_x\)
经过若干次操作，我们可以让某个盒子里的糖数归零。操作轮数可以用辗转相除法分析
（原题CF341E，还要特判一下一开始盒子里面是零的情况，如样例二和样例三）
练习
三道搜索题，麻了。第一题可以简单切掉，第二题看了 Richard_H 的 Python 做法然后自己写了一个 C++ 的。第三题就没写了，然后晚上写了一个 IDA* ，但是信友队上面过不去，但是洛谷原题可以过，那就这样吧，不管了。
A.九数码游戏
这一题就是比较裸的bfs，直接 \(map\) 存一下就可以过了，然后在洛谷原题那里只要把 \(map\) 改成 \(unordered\) 就可以过了，正解好像是用哈希表存的，但是比较懒，不想写哈希表。
还有就是最后输出的时候要注意一下是怎么输出的，还有一开始的 \(string\) 存储不能直接输入 \(w[i]\)
int n = 9;
string w;
unordered_map<string,pii> dis;
unordered_map<string,string> p;
int ans = inf;
int res[40];
string cz1(string w){
swap(w[0],w[3]),swap(w[3],w[6]);
swap(w[6],w[7]),swap(w[7],w[8]);
swap(w[8],w[5]),swap(w[5],w[2]);
swap(w[2],w[1]);
return w;
}
string cz2(string w) {
swap(w[3],w[5]),swap(w[5],w[4]);
return w;
}
int main(){
for (int i = 0; i < n; i ++) {
w += '0' + fr();
}
string temp = w;
queue<string> q;
dis[w].fi = 1;
q.push(w);
for (int i = 0; i < n; i ++)
w[i] = '0' + i;
while (q.size()) {
auto t = q.front();
q.pop();
string u = cz1(t);
if (!dis[u].fi) {
dis[u] = {dis[t].fi + 1,1};
p[u] = t;
if (u == w) {
ans = dis[t].fi;
break;
}
q.push(u);
}
u = cz2(t);
if (!dis[u].fi) {
dis[u] = {dis[t].fi + 1,2};
p[u] = t;
if (u == w) {
ans = dis[t].fi;
break;
}
q.push(u);
}
}
fw(ans);
ch;
int tt = 0;
while (w != temp) {
res[++ tt]=dis[w].se;
w = p[w];
}
for (int i = 1; i <= 3; i ++) {
for (int j = 1; j <= 3; j ++) {
fw(temp[(i - 1) * 3 + j - 1] - '0');
kg;
}
ch;
}
ch;
while (tt) {
int type = res[tt --];
if (type == 1) temp = cz1(temp);
else temp = cz2(temp);
for (int i = 1; i <= 3; i ++) {
for (int j = 1; j <= 3; j ++) {
fw(temp[(i - 1) * 3 + j - 1] - '0');
kg;
}
ch;
}
ch;
}
return 0;
}
B.N的倍数
这个题就是直接 \(bfs\) 就可以了，然后虽然这个复杂度理论上来说是很大的，但是其实还好，可以直接过。
然后存储的时候可以用一个 \(pair<string,int>\) 来存队列里面的数，然后这里面第一维就是这个数是什么，第二维就是到现在这个数除以 \(n\) 的余数。然后这个取余的话就有点类似于在快读里面取余。然后搜到了直接输出，最后如果长度大于 \(500\) 的话直接跳出结束就可以了。
代码里面有一些我一开始骗分写的代码。
lwl n,m;
bool flag[10];
vector<int> use;
int s[N];
bool check(lwl t) {
while (t) {
if (!flag[t % 10]) return false;
t /= 10;
}
return true;
}
int main(){
n = fr(),m = fr();
queue<pii> q;
for (int i = 1; i <= m; i ++) {
int t = fr();
flag[t] = true;
use.push_back(t);
string s;
s += '0' + t;
if(t) q.push({s,t});
}
for (int i = 1; i <= 1e7; i ++) {
if (check(n * i)) {
fw(n * i);
return 0;
}
}
if (m == 1) {
int mod = use[0];
for (int i = 2; i <= 500; i ++) {
mod = mod * 10 + use[0];
mod %= n;
if (mod == 0) {
for (int j = 1; j <= i; j ++)
fw(use[0]);
return 0;
}
}
puts("0");
}
while (q.size()) {
auto t = q.front();
q.pop();
if (t.fi.length() > 500) {
return 0;
}
for (auto i : use) {
auto u = t;
u.fi += '0' + i;
if ((u.se * 10 + i) % n == 0) {
cout << u.fi;
return 0;
}
u.se = (u.se * 10 + i) % n;
q.push(u);
}
}
return 0;
}
C.操作
这个题其实也是暴力做的，然后这个优化我看题解说的是每一次变化序列最多可以改变三个数的后继，但是没看懂为什么，所以他那里有一个判断 \(return false\) 的条件。
然后这里用到了 \(IDA*\) 的算法，是一种和 \(bfs\) 的 \(A*\) 优化有点类似的算法， 这个算法是用来优化 \(dfs\) 的。
\(IDA*\) 其实就是每一次 \(dfs\) 的时候给他规定一个层数，然后每一次回溯的时候就回溯到上一层。这个样子对于这种不太清楚什么时候可以结束，而且有可能层数很浅就可以结束的题目来说可以优化不少（应该吧。我也不太懂，不怎么用 \(IDA*\)
然后这个代码在洛谷上原题（编辑书稿 Editing a Book）是可以过的，但是信友队上过不了，就这样吧。
int n;
int w[N];
int ans = 0;
int num() {
int cnt = n - 1;
for (int i = 1; i < n; i ++) {
if (w[i] == w[i + 1] - 1)
cnt --;
}
return cnt;
}
bool check() {
for (int i = 1; i <= n; i ++) {
if (w[i] != i)
return false;
}
return true;
}
bool dfs(int u) {
if (check()) return true;
if (num() > 3 * (ans - u)) return false;
if (u > n) return false;
int temp[N],c[N];
memcpy(temp,w,sizeof w);
for (int l = 1; l <= n; l ++) {
for (int r = l; r <= n; r ++) {
int len = 0;
for (int i = 1; i <= n; i ++) {
if (l > i || r < i) c[++ len] = temp[i];
}
for (int cut = 0; cut <= len; cut ++) {
int idx = 0;
for (int i = 1; i <= cut; i ++)
w[++ idx] = c[i];
for (int i = l; i <= r; i ++)
w[++ idx] = temp[i];
for (int i = cut + 1; i <= len; i ++)
w[++ idx] = c[i];
if (dfs(u + 1)) return true;
}
}
}
return false;
}
int main(){
while (1) {
n = fr();
if (n == 0) return 0;
for (int i = 1; i <= n; i ++) {
w[i] = fr();
}
ans = 0;
for (;ans <= 10; ans ++) {
if (dfs(0)){
fw(ans);
ch;
break;
}
}
}
return 0;
}