2020牛客暑期多校训练营(第九场)
A.Groundhog and 2-Power Representation
题意:
要求计算给定的式子的值
题解:
将式子中的"("替换成"**("用python的eval()
函数即可
print(eval(input().replace('(','**(')))
B.Groundhog and Apple Tree
题意:
现在有一棵树,你要从开始跳一遍所有的点并且每条边只能走两次,再回到,每条边都有一个边权,你走过这条边会先消耗点HP,每个点都有一个果子,吃掉这个果子会上升点HP,你在任何时候的HP不能小于.并且你如果休息一秒钟会恢复点HP。问你最少要休息多少时间才能走完这棵树。
题解:
观察题目意思,我们发现遍历整棵树其实就是从根节点出发遍历每一个子树,最后回到根节点,对于根节点的每个子树其实是一样的,没有后效性,就可以用动态规划来做
- 优先走能加HP的节点
- 在都能加HP的节点中优先去能加HP多的节点
- 在要消耗HP的节点总优先去T(最短时间)+HP大的节点
- 再去减HP的节点
所以我们只要排一下序再按以上策略跑树形dp 表示节点及其子树所需的HP,表示节点及其子树所能增加的HP
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const int maxn = 1e6 + 5; pll dp[maxn]; bool cmp(pll x, pll y) { if (x.second >= x.first) { if (y.second < y.first) return true; return x.first < y.first; } else { if (y.second >= y.first) return false; return x.second > y.second; } } vector<pll> G[maxn]; int a[maxn], n; void dfs(int u, int fa) { vector<pll> tor; for (auto i : G[u]) { ll v = i.first, dis = i.second; if (v == fa) continue; dfs(v, u); dp[v] = {dp[v].first + dis, dp[v].second - dis}; if (dp[v].second < 0) dp[v] = {dp[v].first - dp[v].second, 0}; tor.push_back(dp[v]); } sort(tor.begin(), tor.end(), cmp); ll mn = a[u], now = a[u]; for (int i = 0; i < tor.size(); i++) { pair<ll, ll> v = tor[i]; mn = min(mn, now - v.first); now += v.second - v.first; } if (mn >= 0) dp[u] = {0, now}; else dp[u] = {-mn, now - mn}; } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); G[i].clear(); } for (int i = 1; i < n; i++) { ll u, v, dis; scanf("%lld%lld%lld", &u, &v, &dis); G[u].push_back(make_pair(v, dis)); G[v].push_back(make_pair(u, dis)); } dfs(1, -1); printf("%lld\n", dp[1].first); } }
E.Groundhog Chasing Death
题意:
求
题解:
将和分解质因数,可以发现最终对答案有贡献的就是那些公共的质因子,因此枚举每种公共的质因子。计算肯定不可能一一枚举,但是可以发现对于固定的是可求的
- 当时,即的均为
- 当时,即的均为
- 当时,即的为,的为
要注意的是这题有点卡常,因此对每个质因子求一次快速幂,而不是对每个质因子的每个求,因此对于的贡献累加可能会超long long,需要用到费马小定理对每次的结果
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; const ll mod = 998244353; map<ll, ll> num1; map<ll, ll> num2; ll ksm(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } ll get(ll x, ll y) { return (x + y) * (y - x + 1) / 2; } int main() { ll a, b, c, d, x, y; scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &x, &y); for (ll i = 2; i * i <= x; i++) if (x % i == 0) while (x % i == 0) { num1[i]++; x /= i; } if (x > 1) num1[x]++; for (int i = 2; i * i <= y; i++) if (y % i == 0) while (y % i == 0) { num2[i]++; y /= i; } if (y > 1) num2[y]++; ll res = 1; for (auto i : num1) { if (num2.count(i.first) != 0) { ll k = i.first, k1 = i.second, k2 = num2[i.first]; ll sum = 0; for (ll j = a; j <= b; j++) { if (j * k1 < c * k2) sum += (d - c + 1) * j * k1; else if (j * k1 > d * k2) sum += get(c, d) * k2; else sum += get(c, j * k1 / k2) * k2 + j * k1 * (d - j * k1 / k2); sum %= (mod - 1); } res = res * ksm(k, sum, mod) % mod; } } printf("%lld\n", res); }
F.Groundhog Looking Dowdy
题意:
给定天,每天有件衣服,每件衣服都有个值,现在要求从这天中选出天,每一天都选出一件衣服,询问这件衣服最大值减最小值的差最小
题解:
将所有的衣服按值从小到大进行排序,用尺取的方法计算每个有种不同天衣服的极差,更新极差的最小值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e6 + 5; vector<pair<int, int>> vec; unordered_map<int, int> mp; int main() { int n, m; scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) { int k; scanf("%lld", &k); for (int j = 1; j <= k; j++) { int x; scanf("%d", &x); vec.push_back({x, i}); } } sort(vec.begin(), vec.end()); int num = 0; int ans = 0x3f3f3f3f; int head = 0; for (auto i : vec) { if (!mp[i.second]) num++; mp[i.second]++; while (num == m) { ans = min(ans, i.first - vec[head].first); mp[vec[head].second]--; if (!mp[vec[head].second]) num--; head++; } } printf("%d\n", ans); return 0; }
I.The Crime-solving Plan of Groundhog
题意:
给定个的数,将它们组合成两个数,使得这两个数的乘积最小,要求不能有前导
题解:
稍微试几个数可以发现,当用一个最小的正整数乘上剩下的数组成的最小的数乘积是最小的,因此可以统计出最小的两个正整数,一个作为一个乘数,另一个作为另一个乘数的最高位,剩余的数从小到大接到后面即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 4e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; unordered_map<int, int> mp; string BigNumMultiply(string str1, string str2) { int size1 = str1.size(), size2 = str2.size(); string str(size1 + size2, '0'); for (int i = size2 - 1; i >= 0; --i) { int mulflag = 0, addflag = 0; for (int j = size1 - 1; j >= 0; --j) { int temp1 = (str2[i] - '0') * (str1[j] - '0') + mulflag; mulflag = temp1 / 10; temp1 = temp1 % 10; int temp2 = str[i + j + 1] - '0' + temp1 + addflag; str[i + j + 1] = temp2 % 10 + 48; addflag = temp2 / 10; } str[i] += mulflag + addflag; } if (str[0] == '0') str = str.substr(1, str.size()); return str; } void solve() { int n; cin >> n; mp.clear(); for (int i = 0; i < n; i++) { int x; cin >> x; mp[x]++; } int f1 = 0, f2 = 0; for (int i = 1; i <= 9; i++) { if (f1 == 0 && mp[i] != 0) { f1 = i; mp[i]--; } if (f2 == 0 && mp[i] != 0) { f2 = i; mp[i]--; break; } } string s1, s2; s1.push_back(f1 + '0'); s2.push_back(f2 + '0'); for (int i = 0; i <= 9; i++) s2.insert(s2.size(), mp[i], i + '0'); cout << BigNumMultiply(s1, s2) << endl; } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
K.The Flee Plan of Groundhog
题意:
给定一棵个节点的树,一个人从节点出发,每向节点走,然后另一个人从节点以开始追,询问最长多少时间会被追到
题解:
可以先算出后这个人的位置,然后以这个节点为根节点dfs求出到所有节点的距离,判断两人的距离差和最远距离的大小
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; typedef long long ll; int to[maxn << 1], nex[maxn << 1], head[maxn], dep[maxn], cnt, mx, rt, dp; int n, t; void init() { cnt = 0; mx = 0; rt = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { to[cnt] = v; nex[cnt] = head[u]; head[u] = cnt++; } bool dfs(int u, int fa) { if (u == n) { dp = dep[n]; if (dep[u] <= t) { rt = n; return false; } return true; } for (int i = head[u]; ~i; i = nex[i]) { int v = to[i]; if (v == fa) continue; dep[v] = dep[u] + 1; if (dfs(v, u)) { if (dep[v] - dep[1] == t) rt = v, dp -= dep[v]; if (!rt) dep[v] = -1; return true; } } return false; } void DFS(int u, int fa) { for (int i = head[u]; ~i; i = nex[i]) { int v = to[i]; if (v == fa) continue; if (dep[u] == -1 || dep[v] == -1) dep[v] = -1; else dep[v] = dep[u] + 1; if (v != n) DFS(v, u); } mx = max(mx, dep[u]); } int main() { init(); scanf("%d%d", &n, &t); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } dfs(1, 0); if (rt == n) { puts("0"); return 0; } dep[rt] = 0; DFS(rt, 0); if (mx >= dp) printf("%d\n", dp); else printf("%d\n", (mx + dp + 1) / 2); return 0; }