桌游制造
我们可以对于每种图案记录拥有这种图案的有那些圆片,然后我们枚举每一个圆片,枚举这个圆片上面的图案,枚举拥有这种图案的圆片还有哪些,然后分别打上标记,如果有一个圆片明明已经有标记了,然而又要被打一次标记,那么我们可以直接输出 \(NO\) 如果标记都已经打完了,可还是有节点没被打到也是 \(NO\)。乍一看是 \(O(n ^ 2 \times m)\) 的,但是对于每一个圆片来说每次只会被打一次标记,所以实际时间复杂度为 \(O(n ^ 2)\)
#include <bits/stdc++.h>using namespace std;const int N = 6e3 + 5;int t, n, m, k, p[N][N];bool vis[N];vector<int> v[N];void Solve() {cin >> n >> m >> k;bool flag = true;for (int i = 1; i <= k; i++) {v[i].clear();}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> p[i][j];if (!v[p[i][j]].empty() && v[p[i][j]].back() == i) {flag = false;}v[p[i][j]].push_back(i);}}if (!flag) {cout << "NO\n";return ;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {vis[j] = false;}for (int j = 1; j <= m; j++) {for (auto cur : v[p[i][j]]) {if (cur != i && vis[cur]) {cout << "NO\n";return ;}vis[cur] = 1;}}for (int j = 1; j <= n; j++) {if (!vis[j]) {cout << "NO\n";return ;}}}cout << "YES\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0);freopen("boardgame.in", "r", stdin);freopen("boardgame.out", "w", stdout);cin >> t;while (t--) {Solve();}return 0;
}
车轮站
我们可以发动人类智慧,我们思考到 \(2\) 操作只会做 \(80\) 次,因为如果要做第 \(81\) 次的话那就需要再攻击 \(80\) 下才能回本,但是再做 \(80\) 次的战力就已经到 \(80 \times 81\)了,战力已经远超 \(5000\) 了,所以我们没必要做。我们即使先做 \(80\) 次\(2\)操作将法力升级到 \(80\) 以上,然后再做 \(80\) 次 \(1\)操作的战力到了 \(80 \times 80\) ,所以我们最多只会失败不到 \(60\) 次。我们设 \(dp_{i, j, k}\) 表示当前打到了那个怪兽,法力是多少,失败了几次的最高战力,那么我们只要找出第一个\(k\) 最小的合法状态,即 \(dp_{i, j, k} >= 0\) ,就可以直接输出 \(n - k\)
#include <bits/stdc++.h>using namespace std;const int N = 5e3 + 5, INF = 1e18;int t, n, s, x, dp[N][80][160];void Solve() {cin >> n >> s >> x;for (int i = 0; i <= n; i++) {for (int j = 0; j <= min(75, i + 1); j++) {for (int k = 0; k <= min(n, 150); k++) {dp[i][j][k] = -INF;}}}dp[0][0][0] = s;for (int i = 1, a; i <= n; i++) {cin >> a;for (int j = 0; j <= min(75, i); j++) {for (int k = 0; k <= min(n, 150); k++) {if (dp[i - 1][j][k] < 0) {continue;}dp[i][j + 1][k + (dp[i - 1][j][k] < a)] = max(dp[i][j + 1][k + (dp[i - 1][j][k] < a)], dp[i - 1][j][k]);dp[i][j][k + (dp[i - 1][j][k] + j + x < a)] = max(dp[i][j][k + (dp[i - 1][j][k] + j + x < a)], dp[i - 1][j][k] + j + x);}}}for (int i = 0; i <= min(n, 150); i++) {for (int j = 0; j <= min(n, 75); j++) {if (dp[n][j][i] >= 0) {cout << n - i << "\n";return ;}}}
}int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("battle.in", "r", stdin);
freopen("battle.out", "w", stdout);cin >> t;while (t--) {Solve();}return 0;
}
兵力调配
我们可以看看有那些情况,无非就是列列列,行行行,列列行,行行列,我们可以枚举当前是哪一行或者那一列,然后选两个相同的即可(即行行,或列列)
#include <bits/stdc++.h>using namespace std;using Pii = pair<long long, long long>;#define int long longconst int N = 5e4 + 5;int t, n, m, k, x[N], y[N], val[N], c[N], p[N], cnt, sumx[N], sumy[N], ans;multiset<Pii, greater<Pii>> sx, sy;vector<Pii> vx[N], vy[N];int get_ans(int op, int len) {int tot = 0;if (!op) {if (sx.size() >= 1) tot += (*sx.begin()).first;if (sx.size() >= 2) tot += (*next(sx.begin())).first;if (sx.size() >= 3 && len >= 3) tot += (*next(next(sx.begin()))).first;}else {if (sy.size() >= 1) tot += (*sy.begin()).first;if (sy.size() >= 2) tot += (*next(sy.begin())).first;if (sy.size() >= 3 && len >= 3) tot += (*next(next(sy.begin()))).first;}return tot;
}void Solve() {cin >> n >> m >> k;for (int i = 1; i <= k; i++) {cin >> x[i] >> y[i] >> val[i];c[i] = x[i];}cnt = 0;sort(c + 1, c + k + 1);for (int i = 1; i <= k; i++) {if (c[i] != c[i - 1]) p[++cnt] = c[i];}n = cnt;for (int i = 1; i <= k; i++) {x[i] = lower_bound(p + 1, p + cnt + 1, x[i]) - p;}cnt = 0;for (int i = 1; i <= k; i++) {c[i] = y[i];}sort(c + 1, c + k + 1);for (int i = 1; i <= k; i++) {if (c[i] != c[i - 1]) p[++cnt] = c[i];}m = cnt;for (int i = 1; i <= k; i++) {y[i] = lower_bound(p + 1, p + cnt + 1, y[i]) - p;}for (int i = 1; i <= k; i++) {sumx[x[i]] += val[i];sumy[y[i]] += val[i];vx[x[i]].push_back({y[i], val[i]});vy[y[i]].push_back({x[i], val[i]});}for (int i = 1; i <= n; i++) {sx.insert({sumx[i], i});}for (int i = 1; i <= m; i++) {sy.insert({sumy[i], i});}ans = 0;ans = max(ans, get_ans(0, 3));ans = max(ans, get_ans(1, 3));for (int i = 1; i <= n; i++) {for (auto cur : vx[i]) {sy.erase(sy.find({sumy[cur.first], cur.first}));sumy[cur.first] -= cur.second;sy.insert({sumy[cur.first], cur.first});}ans = max(ans, get_ans(1, 2) + sumx[i]);for (auto cur : vx[i]) {sy.erase(sy.find({sumy[cur.first], cur.first}));sumy[cur.first] += cur.second;sy.insert({sumy[cur.first], cur.first});}}for (int i = 1; i <= m; i++) {for (auto cur : vy[i]) {sx.erase(sx.find({sumx[cur.first], cur.first}));sumx[cur.first] -= cur.second;sx.insert({sumx[cur.first], cur.first});}ans = max(ans, get_ans(0, 2) + sumy[i]);for (auto cur : vy[i]) {sx.erase(sx.find({sumx[cur.first], cur.first}));sumx[cur.first] += cur.second;sx.insert({sumx[cur.first], cur.first});}}cout << ans << "\n";for (int i = 1; i <= n; i++) {sumx[i] = 0, vx[i].clear();}for (int i = 1; i <= m; i++) {sumy[i] = 0, vy[i].clear();}sx.clear(), sy.clear();
}signed main() {freopen("floor.in", "r", stdin);freopen("floor.out", "w", stdout);cin >> t;while (t--) {Solve();}return 0;
}
