A 放羊的贝贝
题意：在规定的草原矩阵中有一个羊圈，羊圈的形状同样也是矩形，在羊圈外有n头羊，贝贝想生成一个围栏将羊圈和
所有的羊，生成一个单位的围栏的话需要消耗1个能量，问：生成符合规定的围栏的最小消耗能量是多少？
思路：可以很简单的看出只要找出最大的上边和右边、最小的左边和下边就可以得到最小的围栏长度，即最小的能量消耗
时间复杂度：O(1)
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inf 0x3f3f3f3f
LL n, m, k;
LL a, b, c, d;
int main() {
cin >> n >> m >> k;
cin >> a >> b >> c >> d;
LL x, y;
for (int i = 1; i <= k; i ++ ) {
cin >> x >> y;
a = min(a, x);
b = min(b, y);
c = max(c, x + 1);
d = max(d, y + 1);
}
cout << (LL)2 * ((c - a) + (d - b)) << "\n";
return 0;
}
B 114514
题意：求对于一个正整数n，在1 ~ n之间有多少个数满足
思路：公式化简最后可以看出对于1 - n之间的所有的数都是满足同余公式的
证明：有质因子分解和费马小定理的应用，具体可见参考视频 https://www.bilibili.com/video/BV1Jd4y1y7y4?share_source=copy_web&vd_source=5cffc433b8c97c69d1df237eb6d74cc6
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int n;
cin >> n;
cout << n << "\n";
return 0;****
}
c 1919810
题意：给予一个字符串，问这个字符串中有多少个字串的增减性和1919810一样，即满足
思路：题目中说的是子串并不是连续子串，所以这个题就是一个明显的dp问题
设字符串为s，状态f[i][j]表示以字符s[i]作为构造子串的第j为出现时的次数，属性是总和
最终答案是f[i][7]的总和
状态转移：
1、当选中s[i]作为子串的第一个位置时，每个字符的结果都是一样的，f[i][1] = 1
2、当选中s[i]作为子串的第2个和第4个位置时，对于其前面j - 1位置上的择选必须是小于s[i] - '0'的，但是要是使用
1 - i的方法时间时间复杂度是O（n * n），是无法通过的，所以这时可以使用一个g[i][j - 1]来记录上一个位置所以状态的情况，这样时间复杂度就变成了O（n）的了，这里可以仔细理解一下,
方程就是f[i][j] += g[k][j - 1] (0 <= k < x)
3、当选中s[i]作为子串的其他位置时，对于其前面的选择必须是大于s[i] - '0'的数，但是又不能超过10，所以此时的方程就是 f[i][j] += g[k][j - 1] (x + 1 <= k <= 9)
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5, mod = 1e9 + 7;
LL f[N][8], g[10][8];//这里记得使用longlong，若空间没有限制可以尽量使用longlong来存储
char str[N];
int main() {
scanf("%s", str + 1);
int len = strlen(str + 1);
LL ans = 0;
for (int i = 1; i <= len; i ++ ) {
int x = str[i] - '0';
for (int j = 1; j <= 7; j ++ ) {
if(j == 1) {
f[i][j] = 1;
}
else if(j == 2 || j == 4) {
for (int k = 0; k < x; k ++ ) {
f[i][j] += g[k][j - 1];
}
}
else {
for (int k = x + 1; k <= 9; k ++ ) {
f[i][j] += g[k][j - 1];
}
}
g[x][j] = (g[x][j] + f[i][j]) % mod;
}
ans += f[i][7];
ans %= mod;
}
cout << ans << endl;
return 0;
}
D 逃亡的贝贝
题意：贝贝要从S城市通过n条路中的一些路到达t安全区，每条路都是双向的并且都具有一定的危险值，贝贝有k个药水，每个药水可以使的一条路的危险值有w变成
每一条路都只可以使用一个药水，问贝贝到达安全区的危险值总和最小是多少
思路：二分 + spfa（deque优化）的最短路模型
时间复杂度：spfa算法一般是O（n），最坏是O（n * m），二分的时间复杂度是O（logn），spfa加了deque优化，时间复杂度在O（n）左右 （spfa在加上deque优化，有所提速），所以是可以过得
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inf 0x3f3f3f3f
const int N = 2e5 + 10;
struct node {
int v, w1, w2;
};
vector<node> G[N];
int n, m, s, k,t;
bool vis[N];
int dis[N];
bool check(int x) {
for (int i = 1; i <= n; i ++ ) vis[i] = false, dis[i] = inf;
deque<int> q;
q.push_back(s), dis[s] = 0;
while (q.size()) {
int u = q.front();
q.pop_front();
if(u == t) return dis[u] <= k;
if(vis[u]) continue;
vis[u] = 1;
if(dis[u] > k) return false;
for (auto [v, w1, w2] : G[u]) {
if(w1 <= x) {
dis[v] = min(dis[v], dis[u]), q.push_front(v);
}
else if(w2 <= x) {
dis[v] = min(dis[v], dis[u] + 1), q.push_back(v);
}
}
}
return false;
}
int main() {
scanf("%d%d%d%d%d", &n, &m, &s, &t, &k);
while (m -- ) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
int w2 = ((LL)w * 114 + 513) / 514;
G[u].push_back({v, w, w2});
G[v].push_back({u, w, w2});
}
int l = 0, r = 1e9 + 1;
while (l < r) {
int mid = l + r >> 1;
if(check(mid)) {
r = mid;
}
else l = mid + 1;
}
if(l == 1e9 + 1) {
puts("I really need TS1's time machine again!");
}
else {
printf("%d\n", l);
}
return 0;
}