嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！
我的博客：yuanManGan
从今天开始每天写四道题的题解，望大佬监督！
Day1
P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题 - 洛谷
P1514 [NOIP 2010 提高组] 引水入城 - 洛谷
P6033 [NOIP 2004 提高组] 合并果子 加强版 - 洛谷
P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题
我们之前了解到lcm(x,y) * gcd(x,y) = x * y
lcm和gcd我们都知道了，我们仅需枚举x推导出y即可，但x * y 为1e10时间开销太大了，我们枚举的时候 比如案例中3，60我们枚举了3，60自然会想出60和3，我们仅仅需要枚举到x*y开根号，我们还得处理一下特殊情况，两个因数相同的时候就只加一
代码：
#include <iostream>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
LL x, y; cin >> x >> y;
LL t = x * y;
LL cnt = 0;
for(LL p = 1; p <= t/ p; p++)
{
if(t % p) continue;
LL q = t / p;
if(gcd(p, q) == x)
{
cnt += 2;
if(p == q) cnt--;
}
}
cout << cnt << endl;
return 0;
}P1195 口袋的天空
题目要求把每个单独的棉花糖连城k个连通块，就是经典的最小生成树问题，只不过我们不连同完即可。 并查集加kk算法，如果cnt < n-k说明连同不了k个。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int n, m, k;
const int M = 1e4 + 10, N = 1e3 + 10;
struct node
{
int a, b, c;
}e[M];
int fa[N];
bool cmp(node& x, node& y)
{
return x.c < y.c;
}
int find(int x)
{
return fa[x] == x ? x : find(fa[x]);
}
void kk()
{
sort(e + 1, e + 1 + m, cmp);
for (int i = 1; i <= n; i++) fa[i] = i;
LL ret = 0;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
int x = e[i].a, y = e[i].b, l = e[i].c;
int fx = find(x), fy = find(y);
if (fx == fy) continue;
cnt++;
ret += l;
fa[fx] = fy;
if (cnt == n - k) break;
}
if (cnt == n - k) cout << ret << endl;
else cout << "No Answer" << endl;
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
cin >> e[i].a >> e[i].b >> e[i].c;
kk();
return 0;
}P6033 [NOIP 2004 提高组] 合并果子 加强版
这道题，只是加强了一下数据范围，我们之前解决这道题用的是堆加贪心的思路，这里简单回顾一下，我们建个小堆，然后每次拿出最小的两个数据然后合并，合并后放会堆中，进行改操作需要用n*logn的时间复杂度，1e8会超时，我们就得采取其他的方法。
由于我们每次选了两个数合并之后的数会一次比一次大，这里就存在单调性，我们会先拿走先进来的数，这不就是我们的队列数据结构吗？我们用一个队列来放我们合并后的数据，一个我们用队列来放按照降序排完序的数据，然后我们每次比较两个队列，每次拿出最小的，然后需要进行n-1次操作，我们排序如果用快排的化时间复杂度也是n*logn，还是会超时，这里我们看到数据范围是
我们可以采用计数排序，我们还得使用快速读写，不然也会超时。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int cnt[N]; // 计数排序
LL tmp[3]; // 标记需要合并的两个果⼦
queue<LL> q[3]; // q[1] q[2]
int read()
{
int ret = 0;
char ch = getchar();
while (ch > '9' || ch < '0') ch = getchar();
while (ch <= '9' && ch >= '0')
{
ret = 10 * ret + ch - '0';
ch = getchar();
}
return ret;
}
int main()
{
int n = read();
for (int i = 1; i <= n; i++)
{
int x = read();
cnt[x]++;
}
for (int i = 1; i < N; i++)
while (cnt[i]--)
q[1].push(i);
LL ret = 0;
for (int i = 1; i < n; i++)
{
for (int j = 1; j <= 2; j++)
{
if (q[2].empty() || (q[1].size() && q[2].front() > q[1].front()))
{
tmp[j] = q[1].front();
q[1].pop();
}
else
{
tmp[j] = q[2].front();
q[2].pop();
}
}
ret += tmp[1] + tmp[2];
q[2].push(tmp[1] + tmp[2]);
}
printf("%lld\n", ret);
return 0;
}P1514 [NOIP 2010 提高组] 引水入城
我们先来考虑一下最简单的情况，不能填满时：
我们对第一行进行dfs然后遍历最后一行，最后一行如果有st为false时就代表该格子没有被遍历到，让ret++，经典的floodfill问题。
有解的情况：
反证法：如果红色的填缺口的话，那为什么不走紫色的路呢？
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
const int N = 510;
bool st[N][N];
int l[N][N];
int r[N][N];
int a[N][N];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
void dfs(int i, int j)
{
st[i][j] = true;
for (int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > m || a[x][y] >= a[i][j]) continue;
if (!st[x][y]) dfs(x, y);
l[i][j] = min(l[i][j], l[x][y]);
r[i][j] = max(r[i][j], r[x][y]);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
memset(l, 0x3f, sizeof l);
for (int j = 1; j <= m; j++)
l[n][j] = r[n][j] = j;
for (int j = 1; j <= m; j++)
if (!st[1][j]) dfs(1, j);
int cnt = 0;
for (int j = 1; j <= m; j++)
if (!st[n][j]) cnt++;
if (cnt)
{
cout << 0 << endl << cnt << endl;
return 0;
}
int x = 1;
while (x <= m)
{
int right = 0;
for (int i = 1; i <= m; i++)
if (l[1][i] <= x)
right = max(right, r[1][i]);
cnt++;
x = right + 1;
}
cout << 1 << endl << cnt << endl;
return 0;
}