A - Automatic Judge
题意
\(n\)个问题，\(m\)条记录，每条记录有题号、时间、状态，第一次\(AC\)的时候计入罚时，其他没发罚\(20\)分钟。求队伍过题数和罚时。
思路
模拟。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long longvoid solve()
{int n, m;cin >> n >> m;map<string, int> mp;int cnt = 0, ans = 0;for (int i = 0; i < m; i++){string r, s, t;cin >> r >> s >> t;if (mp[r] == -1){continue;}if (t == "AC"){cnt++;ans += mp[r] * 20 + (s[1] - '0') * 60 + (s[3] - '0') * 10 + s[4] - '0';mp[r] = -1;}else{mp[r]++;}}cout << cnt << ' ' << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T--){solve();}return 0;
}B - Building Shops
题意
\(n\)个教室，在教室中建超市，在第\(i\)个教室建花费\(c_i\)，没建的教室花费为其坐标与其左边最近超市坐标之差。求最少花费。
思路
\(n\)很小，一眼\(dp\)。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long longconst int mxn = 3e3 + 5;struct node
{int x, c;bool operator < (const node& a) const{return x < a.x;}
};int dp[mxn][mxn]; // dp[i][j]表示在[1,i]的教室中最后一个建超市的地方是第j个教室的最小花费void solve()
{int n;while (cin >> n){vector<node> v(n + 1);for (int i = 1; i <= n; i++){cin >> v[i].x >> v[i].c;}sort(v.begin() + 1, v.end());for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){dp[i][j] = 1e18;}}dp[1][1] = v[1].c;for (int i = 2; i <= n; i++){for (int j = 1; j <= i; j++){dp[i][j] = min(dp[i][j], dp[i - 1][j] + v[i].x - v[j].x); // 不建 dp[i][i] = min(dp[i][i], dp[i - 1][j] + v[i].c); // 在i建}}int ans = LLONG_MAX;for (int i = 1; i <= n; i++){ans = min(ans, dp[n][i]);}cout << ans << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;//cin >> T;while (T--){solve();}return 0;
}C - Coprime Sequence
题意
给定长度为\(n\)的互质序列(所有数的GCD是\(1\))，删一个数使得剩下数的GCD最大。求删数后的最大GCD。
思路
假设答案是\(x\)，那\(x\)必须要整除\(n-1\)个数，即有\(n-1\)个数都\(\ge x\)，那\(x\)最大就是排序后的第二个数(不一定是第二小)，让后往下找到\(1\)即可。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long longvoid solve()
{int n;cin >> n;vector<int> v(n);for (int i = 0; i < n; i++){cin >> v[i];}sort(v.begin(), v.end());for (int i = v[1]; i >= 1; i--){int sum = 0;for (int j = 0; j < n; j++){if (v[j] % i == 0){sum++;}if (sum >= n - 1){cout << i << endl;return;}}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T--){solve();}return 0;
}D - Deleting Edges
题意
思路
代码
点击查看代码
E - Easy Summation
题意
给定\(n\)和\(k\)，以及函数\(f(i) = i^k\)。求\(\sum_{i=1}^n f(i)\)。
思路
快速幂，模拟。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long longconst int mod = 1e9 + 7;int qp(int base, int x)
{int res = 1;while (x){if (x & 1){res *= base;res %= mod;}x >>= 1;base *= base;base %= mod;}return res;
}void solve()
{int n, k;cin >> n >> k;int ans = 0;for (int i = 1; i <= n; i++){ans += qp(i, k);ans %= mod;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T--){solve();}return 0;
}G - Graph Theory
题意
思路
代码
点击查看代码
H - Happy Necklace
题意
思路
代码
点击查看代码
I - Innumerable Ancestors
题意
思路
代码
点击查看代码
