寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)

寒假程序设计训练2:基础算法与程序设计

T1:最大公约数

备注事项

本题来源于今天洛谷上的一次比赛,还请先报名,否则不能提交。给大家造成不便实属不好意思,但是这题真的不错,以后训练会增加这种风格的题,比如codeforces上,这种题挺多,很有趣。

寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)
寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)
寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)

T1:我的参考程序

#include <cstdio>

const int maxn = 2e3 + 5;
int n, m, x, y, ans, flag;

typedef long long ll;

ll a[maxn][maxn], cur;

ll gcd(const ll& s, const ll& t)
{
	return 0 == t ? s : gcd(t, s % t);
}

ll getValue(const ll& r, const ll& c)
{
	if(r >= 1 && r <= n && c >= 1 && c <= m)
		return a[r][c];
	else
		return 0;
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
			scanf("%lld", &a[i][j]);
	scanf("%d %d", &x, &y);
	for(ans = 0;ans <= n + m;++ans)
	{
		for(int dx = 0, dy = ans;dx <= ans && dy >= 0;++dx, --dy)
		{
			cur = gcd(cur, getValue(x - dx, y - dy));
			cur = gcd(cur, getValue(x - dx, y + dy));
			cur = gcd(cur, getValue(x + dx, y - dy));
			cur = gcd(cur, getValue(x + dx, y + dy));
			if(cur == 1)
			{
				flag = 1;
				break;
			}
		}
		if(flag)
			break;
	}
	if(flag)
		printf("%d\n", ans);
	else
		printf("-1\n");
	return 0;
}

T1:算法分析与设计

这题要求计算需要多少次,通过与上下左右求最大公约数的方法,让元素 a[x][y] 的值变为 1。 如果无法让其变为1,则输出 -1,否则输出需要计算的次数。每次计算是让矩阵的每一个元素都变成与上下左右的最大公约数。首先思考,最多需要多少次计算,能让 a[x][y] 变为1 ??

a[x][y] 第一次变换会等于 (x, y - 1)、(x - 1, y)、(x + 1, y)、(x, y + 1) 分别于它本身的最大公约数。我们知道,如果一个数是 0,则任何数与它的最大公约数都是它本身;如果一个数是 1,则任何数与它的最大公约数都是 1。所以四个方向的计算顺序是无所谓的,这一点也很关键。

在行数为n,列数为m的矩阵里,如果最少计算的次数是 k,则需要对从 (x, y)出发的,曼哈顿距离为 k 的所有点进行计算,如果当前最大曼哈顿距离为 k 的时候,能够让 a[x][y] 变为 1,则这个 k 就是最优解。然后k的所有可能值,就是从起点(1, 1)到最远点(n, m),dis = n + m,所以详情见程序,我先去吃海底捞了!

T2:妖梦拼木棒

寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)
寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)

T2:我的参考程序

#include <cstdio>

const int maxn = 1e5 + 5;
const int maxv = 1e4 + 5;
typedef long long ll;

const ll mod = 1e9 + 7;
ll ans;

int n, a, appear[maxv];

inline int C(int x)
{
	return x * (x - 1) / 2;
}

int main()
{
	scanf("%d", &n);
	for(int i = 0;i < n;++i)
	{
		scanf("%d", &a);
		appear[a]++;
	}
	for(int i = 1;i < maxv;++i)
	{
		for(int j = i;j < maxv;++j)
		{
			if(i != j && appear[i] && appear[j] && appear[i + j] >= 2)
			{
				ans = (ans + ((ll)appear[i] * appear[j] % mod) * (ll)C(appear[i + j]) % mod) % mod;
			}
			else if(i == j && appear[i] && appear[i + j] >= 2)
			{
				ans = (ans + (ll)C(appear[i]) * C(appear[i + j]) % mod) % mod;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

T3:算法设计与分析

吃完海底捞回来了!

这题也比较有意思其实,首先很重要的破题点:四根木棍拼出一个正三角形!如何才能四个木棍?由于组合原理,可以知道,必然有一条边是两根木棍,并且这两根木棍的长度之和要等于另外两条木棍。然后再看数据范围,木棍的长度范围是5 * 10^3,这说明我们可以枚举木棍的长度,然后判断:

1、当前木棍 i 和木棍 j 是否在n个木棍中出现
2、两个木棍的长度和 i + j 是否在 n 个木棍中有两个或两个以上

然后进行计算,这里需要分类讨论:

1、如果 i != j ,则计算 i 的数量(用标记数组)乘以 j 的数量,再乘以 i + j 中选两个的数量(组合数、乘法原理)

2、如果 i = j ,则计算 i 的数量中选两个的个数乘以 i + j 中选两个的个数(同理)

最后详情见程序。

T3:攀爬者

寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)
寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)

T3:我的参考程序

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int maxn = 50007;

struct Point
{
	int x, y, z;
}p[maxn];

bool cmp(const Point& p1, const Point& p2)
{
	return p1.z < p2.z;
}

double dis(const Point& p1, const Point& p2)
{
	return sqrt((p1.x - p2.x) * (p1.x - p2.x)
				+ (p1.y - p2.y) * (p1.y - p2.y)
				+ (p1.z - p2.z) * (p1.z - p2.z));
}

int main()
{
	int n;
	double ans = 0.0;
	cin >> n;
	for(int i = 0;i < n;++i)
		cin >> p[i].x >> p[i].y >> p[i].z;
	sort(p, p + n, cmp);
	for(int i = 1;i < n;++i)
	{
		ans += dis(p[i], p[i - 1]);
	}
	printf("%.3lf\n", ans);
	return 0;
}

T3:算法分析与设计

这题的难度标号就离谱,选的难度是《普及/提高-》,但是真实难度也太普及了……所以就不解释了!

T4:加密通信

寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)
寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)

T4:我的参考程序

#include <cstdio>
#include <cstring>

const int maxn = 1e5 + 5;
int T, n;

typedef long long ll;
ll M, a[maxn], res[maxn];

ll gcd(const ll& x, const ll& y)
{
	return 0 == y ? x : gcd(y, x % y);
}

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %lld", &n, &M);
		bool flag = true;
		ll pos = -1;
		for(int i = 0;i < n - 1;++i)
		{
			scanf("%lld", &a[i]);
			if(i >= 1 && a[i] != a[i - 1])
			{
				res[i] = gcd(a[i], a[i - 1]);
				pos = i;
			}	
		}
		if(-1 == pos)
			flag = false;
		if(flag)
		{
			for(int j = pos - 1;j >= 0;--j)
				res[j] = a[j] / res[j + 1];
			for(int j = pos + 1;j < n;++j)
				res[j] = a[j - 1] / res[j - 1];
			for(int i = 0;i < n;++i)
			{
				if(res[i] > M)
				{
					flag = false;
					break;
				}
			}
		}
		if(flag)
		{
			for(int i = 0;i < n;++i)
				printf("%lld ", res[i]);
			printf("\n");
		}
		else
			printf("-1\n");
		memset(res, 0, sizeof(res));
	}
	return 0;
}

T4:算法分析与设计

本题要求输出任意符合条件的密文,然后要求密钥与明文的关系是:B(i) * B(i + 1) = A(i)

由此可以推出:

B(i) = A(i) / B(i + 1)

B(i) = A(i - 1) / B(i - 1)

上述两个式子,然后很明显,如若知道任意一个B(i),就可以递推计算出所有的B(i),通过上面两个式子。并且题目说明了,必然有两个A(i) 和 A(j) 是不相等的,既然有上面的式子的约束,又有此条件,说明存在A(i) 和 A(i + 1)不相等,否则所有的A(i) 都将是相同的。所以一次遍历即可找到这么一对不相等的数对,然后他们的最大公约数,必然是B(i + 1),因为:

A(i) = B(i) * B(i + 1)

A(i + 1) = B(i + 1) * B(i + 2)

所以最大公约数是B(i + 1),然后记录此位置,前后递推即可得到答案!

总结与展望

今天吃了顿海底捞,撑得慌,做题时间有点少,先四道题作为今天的题单,明天继续!希望有志于此的同学一起努力,完成题单的训练,欢迎交流!

感谢阅读~

上一篇:mdadm: md device /dev/md0 does not appear to be active.


下一篇:442. Find All Duplicates in an Array