Location>code7788 >text

10.9 Summary

Popularity:948 ℃/2024-10-12 09:02:28

T1

It was okay, the exam room AC'd.

The main idea is to start from the first column, for the last column of each of the same number of intervals to sort, and finally test the line, pay attention to the correspondence.

#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

const int kMaxN = 305;

ifstream cin("");
ofstream cout("");

int t, n, m, b[kMaxN], a[kMaxN][kMaxN], l[kMaxN];

int main() {
  ios::sync_with_stdio(0), (0);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      l[i] = i;
      for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
      }
    }
    vector<pair<int, int>> v;
    v.push_back({1, n});
    for (int i = 1; i <= m; i++) {
      vector<pair<int, int>> o = v;
      ();
      for (auto p : o) {
        int L = , R = ;
        for (int j = L; j <= R; j++) {
          b[l[j]] = a[l[j]][i];
        }
        sort(l + L, l + R + 1, [](int x, int y) {
          return b[x] < b[y];
        });
        int u = L;
        for (int j = L; j <= R; j++) {
          if (b[l[j]] != b[l[u]]) {
            if (j - u >= 2) {
              v.push_back({u, j - 1});
            }
            u = j;
          }
        }
        if (R - u + 1 >= 2) {
          v.push_back({u, R});
        }
      }
    }
    bool f = 1;
    for (int i = 1; i <= m; i++) {
      for (int j = 2; j <= n; j++) {
        f &= a[l[j]][i] >= a[l[j - 1]][i];
      }
    }
    cout << (f ? "YES\n" : "NO\n");
  }
  return 0;
}

T2

Based on the wide-eye observation method, we setA because of\(0\)B because of\(1\)C because of\(2\), then let the two neighbors of this layer be\(x_1, x_2\)The answer to the upper level then is\(-(x_1 + x_2) \bmod 3\), and then based on the wide-eyed observation method, you can see that it is in the form of a combinatorial number, then you AC this question.

The tournament didn't think about the number of combinations of grooves :(

Not a buddy? You don't know how to count? The combinatorial number formula $C_{m}^{n} = \dfrac{m!}{n!(m-n)!} $, except I didn't want to write it that way.
#include <fstream>

using namespace std;
using ll = long long;

const int kMod = 3, kMaxN = 2e5 + 1;

ifstream cin("");
ofstream cout("");

int t, n, jie[kMaxN];
string s;

void Init() {
  for (int i = 1; i <= 1e5 + 1; i++) {
    jie[i] = jie[i - 1] * i % kMod;
  }
}

ll fpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    (b & 1) && (res = res * a % kMod);
    b >>= 1;
    a = a * a % kMod;
  }
  return res;
}


ll Gt(ll n, ll m) {
  if (n < m) {
    return 0;
  }
  ll res = 1;
  for (ll i = n - m + 1; i <= n; i++) {
    res *= i;
  }
  for (ll i = 1; i <= m; i++) {
    res /= i;
  }
  return res % 3;
}

ll C(ll n, ll m) {
  return (n < m ? 0 : (n <= 10 ? Gt(n, m) : C(n / 3, m / 3) * Gt(n % 3, m % 3) % 3));
}

ll Get(char c) {
  return c == 'A' ? 0 : (c == 'B' ? 1 : 2);
}

char To(ll x) {
  return (x == 1 ? 'B' : x == 0 ? 'A' : 'C');
}

int main() {
  Init();
  for (cin >> t; t; t--) {
    cin >> n >> s;
    ll ans = 0, f = n & 1 ? 1 : -1;
    for (int i = 0; i < n; i++) {
      ans = (ans + Get(s[i]) * C(n - 1, i) % kMod);
    }
    ans *= f;
    cout << To((ans % kMod + kMod) % kMod) << '\n';
  }
  return 0;
}