T1--4519. 正方形数组的数目
给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。
两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i]≠A2[i]。
输入格式
第一行包含一个整数 n，表示数组 A 的长度。
第二行包含 n 个整数 A[i]。
输出格式
一个整数，表示 A 的正方形排列的数目。
数据范围
1≤n≤12,
0≤A[i]≤10^9。
输入样例：
3
1 17 8
输出样例：
2
样例解释
[1,8,17] 和 [17,8,1] 都是有效的排列。
有重复元素的无重复全排列。
开始想尝试 next_permutation，不好处理，还是直接DFS。
参考题解： https://www.acwing.com/solution/content/126342/。
#include <bits/stdc++.h>
using namespace std;
const int N =15;
int n,q[N],ans;
bool st[N];
bool check(int x){ // 判断完全平方数
int t = sqrt(x);
return t*t == x;
}
void dfs(int u,int last){ // u表示搜索层数，last表示上次枚举的数
if (u >= n){ // 把 n 个数枚举完就能得到一个答案序列
ans ++; // 和蓝桥杯模板题的排列枚举略有不同，那题u = 1时开始枚举第一个数
// 本题u = 1时第一个数已经确定
return;
}
for (int i = 0;i < n;i ++){
if (st[i]) continue; // 判重，用过的数字不能再用
//举例[3 3 5 6], 如果当前6是元素，那么第二层会是3 3 5其中一个
//然后我们如果第二层连续两次使用这个相同的3，就会使得搜到的结果是一样的
//[6 3(第一个3) 5 3(第二个三)] === [6 3(第二个3) 5 3(第一个三)]
//所以需要跳过，只需要搜其中一个就行
// 然后为什么要判断这个呢 (!st[i - 1]) 因为前面一个数肯定是回溯之后，
//恢复现场了，st肯定是false,
//如果是被标记的，说明是相同元素而已，dfs的不同层数
if (i && !st[i-1] && q[i] == q[i-1]) continue; // 排除重复排列
if (check(last + q[i])){
st[i] = true;
dfs(u+1,q[i]);
st[i] = false;
}
}
}
int main(){
cin >> n;
for (int i = 0;i < n;i ++) cin >> q[i];
sort(q,q + n);
for (int i = 0;i < n;i ++){
// 限定枚举的第一个数字不能重复
if (i && q[i] == q[i-1]) continue;
st[i] = true; // 判重
dfs(1,q[i]);
st[i] = false;
}
cout << ans << '\n';
return 0;
}
T2--3432. 二叉树
1
/ \
2 3
/ \ / \
4 5 6 7
/\ /\ /\ /\
... ...
如上图所示，由正整数 1,2,3,… 组成了一棵无限大的（满）二叉树。
从任意一个结点到根结点（编号是 1 的结点）都有一条唯一的路径，比如从 5 到根结点的路径是 (5,2,1)，从 4 到根结点的路径是 (4,2,1)，从根结点 1 到根结点的路径上只包含一个结点 1，因此路径就是 (1)。
对于两个结点 x 和 y，假设他们到根结点的路径分别是 (x1,x2,…,1) 和 (y1,y2,…,1)，那么必然存在两个正整数 i 和 j，使得从 xi 和 yj 开始，有 xi=yj,xi+1=yj+1,xi+2=yj+2,…
现在的问题就是，给定 x 和 y，要求他们的公共父节点，即 xi（也就是 yj）。
输入格式
1≤x,y≤2^31−1
输入样例：
10 4
输出样例：
2
参考题解： https://www.acwing.com/solution/content/126489/。
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
while (a != b){
if (a > b) a /= 2;
if (b > a) b /= 2;
}
cout << a << '\n';
return 0;
}
T3--3559. 围圈报数
N 个人围成一圈顺序编号，从 1 号开始按 1、2、3 顺序报数，报 3 者退出圈外，其余的人再从 1、2、3 开始报数，报 3 的人再退出圈外，依次类推。
请按退出顺序输出每个退出人的原序号。
要求使用环行链表编程。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据一行，一个整数 N。
输出格式
每组数据输出一行，一个结果，包含每个退出人的原序号，用空格隔开。
数据范围
1≤T≤5,
1≤N≤50
输入样例：
1
4
输出样例：
3 2 4 1
数组模拟循环链表，画个图方便理解。
优质题解： https://www.acwing.com/solution/content/126684/。
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int m,n,e[N],ne[N],idx;
int main(){
cin >> m;
while (m --){
cin >> n;
idx = 0; // 记得重置！
for (int i = 1;i < n;i ++){
e[++idx] = i,ne[idx] = i + 1;
}
e[n] = n,ne[n] = 1;
int st = 1;
while (ne[st] != st){
int t = ne[st];
cout << e[ne[t]] << ' ';
ne[t] = ne[ne[t]];
st = ne[t];
}
cout << st << '\n';
}
return 0;
}
T4--3588. 排列与二进制
在组合数学中，我们学过排列数。
从 n 个不同元素中取出 m（m<=n）个元素的所有排列的个数，叫做从 n 中取 m 的排列数，记为 p(n,m)。
具体计算方法为 p(n,m)=n(n−1)(n−2)……(n−m+1)=n!/(n−m)!（规定 0!=1）。
当 n 和 m 不是很小时，这个排列数是比较大的数值，比如 p(10,5)=30240。
如果用二进制表示为 p(10,5)=30240=(111011000100000)b，也就是说，最后面有 5 个零。
我们的问题就是，给定一个排列数，算出其二进制表示的后面有多少个连续的零。
输入格式
输入包含多组测试数据。
每组数据占一行，包含两个整数 n,m。
最后一行为 0 0，表示输入结束，无需处理。
输出格式
每组数据输出一行，一个结果，表示排列数 p(n,m) 的二进制表示后面有多少个连续的零。
数据范围
1≤m≤n≤10000,
输入最多包含 100 组数据。
输入样例：
10 5
6 1
0 0
输出样例：
5
1
组合数问题，不会，参考y总。
二进制末尾连续的0的数量等于这个数字包含因子2的数量。
根据公式，n!中有质因子p的个数为（\(\frac n p + \frac n {p^2} + \frac n {p^3} + ...\))，时间复杂度为:O(logn)
举例：当n=12,p=2时：
\(\frac n p\) 表示1~12中有6个数是2的倍数，即2,4,6,8,10,12
\(\frac n {p^2}\) 表示1~12中有3个数是4的倍数，即4,8,12，它们能在提供2的基础上多提供一个2
\(\frac n {p^3}\) 表示1~12中有1个数是8的倍数，即8，它能在提供两个2的基础上又多提供一个2
所以答案为6+3+1=10
y氏证明：
#include <bits/stdc++.h>
using namespace std;
int n,m;
int f(int x,int p){ // f(x,p)求x!中质因子p的指数，即x!中含有多少个质因子p
int res = 0; // f(x,p) = x/p + x/p^2 + ... + x/p^i
while (x) x /= p,res += x;
return res;
}
int main(){
while (cin >> n >> m && m){
cout << f(n,2) - f(n-m,2) << '\n';
}
return 0;
}
T5--3555. 二叉树
给定一个 n 个结点（编号 1∼n）构成的二叉树，其根结点为 1 号点。
进行 m 次询问，每次询问两个结点之间的最短路径长度。
树中所有边长均为 1。
输入格式
第一行包含一个整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,m。
接下来 n 行，每行包含两个整数，其中第 i 行的整数表示结点 i 的子结点编号。如果没有子结点则输出 −1。
接下来 m 行，每行包含两个整数，表示要询问的两个结点的编号。
输出格式
每组测试数据输出 m 行，代表查询的两个结点之间的最短路径长度。
数据范围
1≤T≤10,
1≤n,m≤1000
输入样例：
1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1
输出样例：
2
4
2
4
树的LCA问题，不会。
对于树上两点的最短路问题，可以转化为图上两点的最短路问题，树上两点的路径是唯一的，可以直接DFS或BFS。
或者可以结合DFS和LCA算法，然后用倍增法或Tarjan算法求解LCA，还可以用朴素版的LCA算法。
Tarjan算法求解LCA是离线算法，倍增法求解LCA是在线算法。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int l[N],r[N],p[N],dist[N],m,n;
void dfs(int u,int d){ // 计算每个结点到根结点的距离dist
dist[u] = d;
if (l[u] != -1) dfs(l[u],d+1);
if (r[u] != -1) dfs(r[u],d+1);
}
int get_lca(int x,int y){ // 求解结点x与y的LCA编号
// 朴素版LCA算法求解流程
// 1.将深度更大的结点向上走到和另一结点同一层的深度
// 2.然后两结点同时向上走，直到两结点走到同一点，即为LCA
if (dist[x] < dist[y]) return get_lca(y,x); // dist值相等表示在同一层
while (dist[x] != dist[y]) x = p[x];
while (x != y) x = p[x],y = p[y];
return x;
}
int main(){
int t;
cin >> t;
while (t --){
cin >> n >> m;
int x,y;
for (int i = 1;i <= n;i ++){
cin >> x >> y;
l[i] = x,r[i] = y;
if (x != -1) p[x] = i;
if (y != -1) p[y] = i;
}
dfs(1,0);
int a,b;
while (m --){ // 处理询问
cin >> a >> b;
int c = get_lca(a,b);
cout << (dist[a] + dist[b] - 2*dist[c]) << '\n';
}
}
return 0;
}
T6--4520. 质数
给定一个正整数 X，请你在 X 后面添加若干位数字（至少添加一位数字；添加的数不能有前导0），使得结果为质数，在这个前提下所得的结果应尽量小。
输入格式
第一行包含一个整数 T，表示共有 T 组测试数据。
每组数据占一行，包含一个整数 X。
输出格式
每组数据输出一行结果，一个整数，表示所得的满足条件的最小质数。
数据范围
1≤T≤100,
1≤X≤100。
输入样例：
1
1
输出样例：
11
不会，参考y总。
题目数据范围有限，直接枚举要添加的数即可。
#include <bits/stdc++.h>
using namespace std;
bool check(int a){
if (a < 2) return false;
for (int i = 2;i*i <= a;i ++){
if (a % i == 0) return false;
}
return true;
}
int main(){
int t,x;
cin >> t;
while (t --){
cin >> x;
for (int i = 1;;i ++){
string str = to_string(x) + to_string(i);
int a = stoi(str);
if (check(a)){
cout << a << '\n';break;
}
}
}
return 0;
}