Try and Cry

我们肯定是尽可能的让前 \((n - 1)\) 个多拿,但是有可能这个有一些一样的,所以向上取整即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 5;

int t, n;

void Solve() {
  cin >> n;
  int tmp = ((n * (n - 1) / 2) - (n - 1) - (n - 2) - (n - 3));
  cout << (tmp + n - 4) / (n - 3) << "\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  while (t--) {
    Solve();
  }
  return 0;
}

Trick or Treat

我们可以设 \(dp_{l, r, 0/1}\) 表示将区间 \([l, r]\) 的人家全部要过躺了,在区间的左端点或者端点

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e3 + 5, INF = 1e18;

int t, n, k, a[N], dp[N][N][2];

void Solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dp[i][j][0] = dp[i][j][1] = INF;
    }
  }
  dp[k][k][0] = dp[k][k][1] = 0;
  for (int len = 2; len <= n; len++) {
    for (int l = 1, r = len; r <= n; l++, r++) {
      if (l < n) {
        if (dp[l + 1][r][0] + 1 < a[l]) dp[l][r][0] = min(dp[l][r][0], dp[l + 1][r][0] + 1);
        if (dp[l + 1][r][1] + r - l < a[l]) dp[l][r][0] = min(dp[l][r][0], dp[l + 1][r][1] + r - l);
      }
      if (r > 1) {
        if (dp[l][r - 1][0] + r - l < a[r]) dp[l][r][1] = min(dp[l][r][1], dp[l][r - 1][0] + r - l);
        if (dp[l][r - 1][1] + 1 < a[r]) dp[l][r][1] = min(dp[l][r][1], dp[l][r - 1][1] + 1);
      }
    }
  }
  int tmp = min(dp[1][n][0], dp[1][n][1]);
  if (tmp == INF) {
    cout << "-1\n";
  }
  else cout << tmp << "\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  t = 1;
  while (t--) {
    Solve();
  }
  return 0;
}

Phantom Poker

矩乘板子题,我们可以用 \(dp_{i, 0-13, 0-13}\) 那么我们可以得到如下题目

for (int i = 0; i < 13; i++) {
    for (int j = 0; j < 13; j++) {
        tmp.mat[(i * j) % 13] += x.mat[i] * y.mat[j];
        tmp.mat[(i * j) % 13] %= mod;
    }
}

那么我们可以用线段树维护矩阵

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e4 + 5, mod = 1e9 + 7;

struct node {
  int mat[13];
}tr[N * 4], INF;

int n, q, a[N];

node Merge(node x, node y) {
  node tmp;
  for (int i = 0; i < 13; i++) {
    tmp.mat[i] = 0;
  }
  for (int i = 0; i < 13; i++) {
    for (int j = 0; j < 13; j++) {
      tmp.mat[(i * j) % 13] += x.mat[i] * y.mat[j];
      tmp.mat[(i * j) % 13] %= mod;
    }
  }
  return tmp;
}

void build(int i, int l, int r) {
  if (l == r) {
    for (int j = 0; j < 13; j++) {
      tr[i].mat[j] = 0;
    }
    tr[i].mat[1]++;
    tr[i].mat[a[l] % 13]++;
    return ;
  }
  int mid = (l + r) >> 1;
  build(i * 2, l, mid);
  build(i * 2 + 1, mid + 1, r);
  tr[i] = Merge(tr[i * 2], tr[i * 2 + 1]);
}

void modify(int i, int l, int r, int p, int x) {
  if (l == r) {
    tr[i].mat[a[p]]--;
    tr[i].mat[x]++;
    return ;
  }
  int mid = (l + r) >> 1;
  if (mid >= p) modify(i * 2, l, mid, p, x);
  else modify(i * 2 + 1, mid + 1, r, p, x);
  tr[i] = Merge(tr[i * 2], tr[i * 2 + 1]);
}

node query(int i, int l, int r, int x, int y) {
  if (l > y || r < x) {
    return INF;
  }
  if (l >= x && r <= y) {
    return tr[i];
  }
  int mid = (l + r) >> 1;
  return Merge(query(i * 2, l, mid, x, y), query(i * 2 + 1, mid + 1, r, x, y));
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	INF.mat[1] = 1;
	cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= 4 * n; i++) {
    for (int j = 0; j < 13; j++) {
      tr[i].mat[j] = 0;
    }
  }
  build(1, 1, n);
  while (q--) {
    int op, x, y;
    cin >> op >> x >> y;
    if (op == 1) {
      modify(1, 1, n, x, y);
      a[x] = y;
    }
    else {
      cout << query(1, 1, n, x, y).mat[5] << "\n";
    }
  }
	return 0;
}