题山采玉：Day2
嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！
我的博客：yuanManGan
我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记 闲言碎语小记坊 题山采玉 领略算法真谛
P1948 [USACO08JAN] Telephone Lines S - 洛谷
P4942 小凯的数字 - 洛谷
P7912 [CSP-J 2021] 小熊的果篮 - 洛谷
P4057 [Code+#1] 晨跑 - 洛谷
P4057 [Code+#1] 晨跑
这道题就很简单了，题目搞这么长浪费时间，就直接求这三个数的lcm就可以了。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{return b ? gcd(b, a % b) : a;
}
LL lcm(LL a, LL b)
{return a * b / gcd(a, b);
}
int main()
{LL a, b, c; cin >> a >> b >> c;cout << lcm(lcm(a, b), c) << endl;return 0;
}
P4942 小凯的数字
题目要求从l到r构成一个数字，然后这个数字mod9的结果，我们注意到l和r的数据范围是1e12，很明显，我们至少要采用O(logn)的时间复杂度，能做到O(1)更好。
当 l和 r都是个位数时，比如l为3，r为6
我们得到的数是3456
我们用秦九韶算法把这个数拆开就是
（（（（3 *10+ 4）*10） + 5）*10）+6我们对这个结果去模9就成了
（（（（（3 *10%9+ 4）*10%9） + 5）*10%9）+6）%9
我们发现结果就是（3 + 4 + 5 + 6）% 9
我们仅仅需要对这个区间的和取模就可以，用前n项和公式即可，那当我们r为两位或者更多位的时候还成立吗，答案依旧成立。
这里还有一个细节要处理，我们的前n项和公式是(a1 + an)/2 * n
也就是 (r + l)(l - r + 1)/2 %9,这里要除以2再取模那我们是不是要用乘法逆元呢，其实不用，r + l 和l - r + 1必定有一个数是2的倍数。
#include <iostream>using namespace std;
typedef long long LL;int main()
{int q; cin >> q;while (q--){LL l, r; cin >> l >> r;LL x = l + r, y = r - l + 1;LL ret;if (x % 2 == 0) ret = x / 2 % 9 * y % 9;else ret = y / 2 % 9 * x % 9;cout << ret << endl;}return 0;
}P7912 [CSP-J 2021] 小熊的果篮
这道题的思路很好想但实现起来有点困难，我们这里用set来实现一下吧，我们定义两个set一个存储值为0的下标，另一个存储值为1 的下标。我们先判断一下两个set里面谁的第一个元素小也就是下标最小的，因为set是默认按照升序排序的，这里找到谁更小就代表那个元素要先出来，比如第一个set里面有最小的他代表的是0，我们就要去另一个set找最小的，但这个最小的要比我们刚刚找的要大，重复操作直到找不到。
按照这个模拟即可。
#include <iostream>
#include <set>using namespace std;set<int> s[2];
int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){int x; cin >> x;s[x].insert(i);}while (s[0].size() || s[1].size()){int p;if (s[1].empty() || (s[0].size() && *s[0].begin() < *s[1].begin()))p = 0;else p = 1;int x = 0;while (1){auto t = s[p].upper_bound(x);if (t == s[p].end()) break;x = *t;cout << *t << " ";s[p].erase(t);p = !p;}cout << endl;}return 0;
}P1948 [USACO08JAN] Telephone Lines S
我们仅需连同1节点和n号节点即可，我们可以免费连接k个路线，多出来的路线按照最大的付钱，
我们可以将大于x的边的边权为1，小于的定义为0，这时我们就可以采用01bfs来解决，01bfs的时间复杂度为n，二分的时间复杂度为logn，时间复杂度为n*logn刚刚好，我们就来解决一下吧。
#include<iostream>
#include<cstring>
#include<deque>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int n, p, k;
const int N = 1e3 + 10;
vector<PII>edges[N];
int dist[N];
bool st[N];
bool check(int x)
{memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);deque<int> q;q.push_back(1);dist[1] = 0;while (q.size()){int a = q.front(); q.pop_front();if (st[a]) continue;st[a] = true;for (auto t : edges[a]){int b = t.first, c = t.second > x ? 1 : 0;if (dist[a] + c < dist[b]){dist[b] = dist[a] + c;if (c) q.push_back(b); else q.push_front(b);}}}return dist[n] <= k;
}
int main()
{cin >> n >> p >> k;for (int i = 1; i <= p; i++){int a, b, c; cin >> a >> b >> c;edges[a].push_back({ b,c });edges[b].push_back({ a,c });}int l = 0, r = 1e6;while (l < r){int mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid + 1;}if (dist[n] == 0x3f3f3f3f) cout << -1 << endl;else cout << l << endl;return 0;
}