桌游制造

我们可以对于每种图案记录拥有这种图案的有那些圆片,然后我们枚举每一个圆片,枚举这个圆片上面的图案,枚举拥有这种图案的圆片还有哪些,然后分别打上标记,如果有一个圆片明明已经有标记了,然而又要被打一次标记,那么我们可以直接输出 \(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 long

const 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;
}