T1：最大公约数
备注事项
本题来源于今天洛谷上的一次比赛，还请先报名，否则不能提交。给大家造成不便实属不好意思，但是这题真的不错，以后训练会增加这种风格的题，比如codeforces上，这种题挺多，很有趣。
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：妖梦拼木棒
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：攀爬者
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：加密通信
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)，然后记录此位置，前后递推即可得到答案！
总结与展望
今天吃了顿海底捞，撑得慌，做题时间有点少，先四道题作为今天的题单，明天继续！希望有志于此的同学一起努力，完成题单的训练，欢迎交流！
感谢阅读~