本周学习总结22.4.4-4.10：两种搜索、比赛

本周看的博客大部分都是与搜索有关的，也有一些是其他方面的，看的博客大多是在做题中遇到一些不会的思路和内容时，专门看如何解决遇到的问题的博客，阅读的篇目比较多，具体数量我忘记统计了，收获如下：

能够更加熟练地运用递归函数来写深度优先搜索的函数，并且在此基础上ac了不少的题，根据题意中不同的情况，将递归函数中一个或几个数据修改，减少程序的运算时间，我在周六晚上的比赛中的第二题就用到了这样的思路

Suppose you have an integer vv. In one operation, you can:

• either set v=(v+1)mod32768v=(v+1)mod32768
• or set v=(2⋅v)mod32768v=(2⋅v)mod32768.

You are given nn integers a1,a2,…,ana1,a2,…,an. What is the minimum number of operations you need to make each aiai equal to 00?

Input

The first line contains the single integer nn (1≤n≤327681≤n≤32768) — the number of integers.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai<327680≤ai<32768).

Output

Print nn integers. The ii-th integer should be equal to the minimum number of operations required to make aiai equal to 00.

 这个题目的意思是，输入一个数字v，这个数字v可以*2或者+1，求这个数一直到能够被32768整除的最小步骤，这个题我的思路是这样的：由于32768是偶数，同时也是2的10次方，所以当v是奇数的时候，先+1变成偶数，再进行接下来的计算。

后面，当v小于32768的一半时，先让它×2，大于一半时，同时进行两个递归函数，每运行一次递归函数计数器就＋1，直至能被32768整除时返回计数器。

我这样写的程序运行是正确的，但是由于超时总是有一个测试点过不去。

#include
#include
int a;
int dfs(int a,int m) {
	if (a == 32767 || a == 16384) {
		return m;
	}
	else if (a % 2 != 0) {
		dfs(a + 1, m + 1);
	}
	else if(32768-a>16384){
		dfs(a * 2, m + 1);
	}
	else if (32768-a < 16384) {
		if(double(a/2.5)==int(a/2.5))dfs(a / 2.5, m + 1);
		else dfs(a + 1, m + 1);
	}
}
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	for (int u = 1; u <= t; u++) {
		cin >> a;
		cout << dfs(a,1);
		if (u != t)cout << " ";
	}
}

 这是周六codeforces的情况，再一个就是周五晚上的一个比赛题，题目的大致意思是：a+b+c+d=n,a&b的最大公约数==c&d的最小公倍数，输入n求a,b,c,d。

这个题我本来也打算使用搜索，到最后用搜索也做出来了，但是这个题目的要求和之前做的题目似乎有点不同，这个题的输出还是比较自由的，有很多答案，所以这个题误导了我很长时间，最后我还是用搜索“搜索”到了思路，最后用的for函数与减法运算做出了这个题。

代码如下：

#include
#include
using namespace std;
int r, t, y, u, h;
int gcd(int a, int b) {
	int maxx;
	if (a >= b)maxx = a;
	else maxx = b;
	for (int i = maxx; i >= 1; i--) {
		if (a % i == 0 && b % i == 0)return i;
	}
}
int lcm(int a, int b) {
	int maxx;
	if (a >= b)maxx = a;
	else maxx = b;
	for (int i = maxx;; i++) {
		if (maxx % a == 0 && maxx % b == 0)return i;
	}
}
	if (gcd(a, b) == lcm(c, d) && a + b + c + d == h) {
		cout << a << " " << b << " " << c << " " << d << endl;
		goto fuck;;
	}
	if (b != h && a + b + c + d <= h) {
		look(a, b + 1, c, d);
	}
	if (a != h && a + b + c + d <= h) {
		look(a + 1, b, c, d);
	}
	if (c != h && a + b + c + d <= h) {
		look(a, b, c + 1, d);
	}
	if (d != h && a + b + c + d <= h) {
		look(a, b, c, d + 1);
	}
fuck:
	h = 0;
}
int main() {
	int n,c=0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h;
		look(1, 1, 1, 1);
	}
}

最后其实就几行就做出来了

#include
using namespace std;
int main() {
	int n , a;cin >> n;
	for (int i = 1; i <= n; i++) {cin >> a;cout << "1 " << a - 3 << " 1 1" << endl;}}

思路也很简单，让他最小公倍数和最大公约数都变成1就好了。

已知 n 个整数 x_1,x_2,...,x_n​，以及 1 个整数 k（k

从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。

例如当 n=4，k=3，4 个整数分别为 3,7,12,19 时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

 这个题我感觉是一个很经典的深度优先搜索题，我是写了两个函数，一个是判断素数的函数，这个函数之前写过无数次了不再重复了，再有一个是深度优先搜索的函数，也是用到了递归。

#include
#include
#include
#include
#include
#include