“钉耙编程”2025春季联赛（2）题解（更新中）

// Problem: 学历史导致的
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1151&pid=1002
// Memory Limit: 524288 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
// #define int long long
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int, int>;

const int N = 1e5 + 5;

string a[10] = {"jia", "yi",   "bing", "ding", "wu",
                "ji",  "geng", "xin",  "ren",  "gui"};
string b[12] = {"zi", "chou", "yin",  "mao", "chen", "si",
                "wu", "wei",  "shen", "you", "xu",   "hai"};
vector<string> s(200);
void solve() {
  string c;
  cin >> c;
  for (int i = 0; i < 120; i++) {
    if (s[i] == c) {
      cout << i + 1984 << endl;
      return;
    }
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t;
  cin >> t;
  int cnt = 0;
  for (int i = 0, j = 0; cnt < 200; j++, i++) {
    s[cnt++] = a[i % 10] + b[j % 12];
  }

  while (t--) {
    solve();
  }

  return 0;
}

/*
 *                        _oo0oo_
 *                       o8888888o
 *                       88" . "88
 *                       (| -_- |)
 *                       0\  =  /0
 *                     ___/`---'\___
 *                   .' \\|     |// '.
 *                  / \\|||  :  |||// \
 *                 / _||||| -:- |||||- \
 *                |   | \\\  - /// |   |
 *                | \_|  ''\---/''  |_/ |
 *                \  .-\__  '-'  ___/-. /
 *              ___'. .'  /--.--\  `. .'___
 *           ."" '<  `.___\_<|>_/___.' >' "".
 *          | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *          \  \ `_.   \_ __\ /__ _/   .-` /  /
 *      =====`-.____`.___ \_____/___.-`___.-'=====
 *                        `=---='
 *
 *
 *      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *            佛祖保佑       永不宕机     永无BUG
 */

 签到题吗？我是菜鸡

我的想法是，找每个数第一次出现的位置和每个位置后面不同数的个数，考虑0的位置

跑一遍数组，记录 i 之前最近的0的位置

a[i]第一次出现在0之前，现在出现在0之后，就在ans上加上i位置后面不同数的个数

感觉题目说的有点别扭

p,q是一对数，p用过之后就不用了，否则会重复，所以记录ans之后把a[i]第一次出现的位置设成非法的

就是p前面有0有p，就加上q，答案记得开i64

// Problem: 学数数导致的
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1151&pid=1003
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
// #define int long long
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int, int>;

const int N = 1e6 + 5;
int fira[N], q[N];

void solve() {
  fill(fira, fira + N, 0);
  fill(q, q + N, 0);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {  // 从1开始，默认是0不要和默认一样
    cin >> a[i];
  }
  for (int i = n; i > 0; i--) {  // 倒着跑真好啊
    if (a[i] == 0) {
      q[i] = q[i + 1];
      continue;
    }
    q[i] = q[i + 1] + (fira[a[i]] == 0);  // 没出现过，新种类++
    fira[a[i]] = i;                       // 倒着跑就是最前的位置
  }
  i64 zero = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0)
      zero = i;
    else {
      if (fira[a[i]] < zero) {
        ans += q[i + 1];
        fira[a[i]] = 0x3f3f3f3f;
      }
    }
  }
  cout << ans << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    solve();
  }

  return 0;
}

/*
 *                        _oo0oo_
 *                       o8888888o
 *                       88" . "88
 *                       (| -_- |)
 *                       0\  =  /0
 *                     ___/`---'\___
 *                   .' \\|     |// '.
 *                  / \\|||  :  |||// \
 *                 / _||||| -:- |||||- \
 *                |   | \\\  - /// |   |
 *                | \_|  ''\---/''  |_/ |
 *                \  .-\__  '-'  ___/-. /
 *              ___'. .'  /--.--\  `. .'___
 *           ."" '<  `.___\_<|>_/___.' >' "".
 *          | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *          \  \ `_.   \_ __\ /__ _/   .-` /  /
 *      =====`-.____`.___ \_____/___.-`___.-'=====
 *                        `=---='
 *
 *
 *      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *            佛祖保佑       永不宕机     永无BUG
 */

 最长上升子序列

但是k太大了，所以超过26次就覆盖所有字母了

比如 z...a

这样排26次就能a..z了

 写的时候有点愚蠢啊，s重复26次不要在自身上加，那样是2的26次了

// Problem: 学 DP 导致的
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/contest/problem?cid=1151&pid=1004
// Memory Limit: 65536 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
// #define int long long
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int, int>;

const int N = 1e5 + 5;

void solve() {
  string s, ss = "";
  cin >> s;
  string k;
  cin >> k;
  int a;
  if (k.size() < 3) {
    a = stoi(k);
    if (a < 26) {
    } else
      a = 26;
  } else
    a = 26;

  for (int i = 0; i < a; i++) {
    ss += s;
  }

  int n = ss.size();
  vector<int> dp(n, 1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (ss[i] > ss[j]) {
        dp[i] = max(dp[i], dp[j] + 1);
      }
    }
  }

  cout << *max_element(dp.begin(), dp.end()) << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    solve();
  }

  return 0;
}

/*
 *                        _oo0oo_
 *                       o8888888o
 *                       88" . "88
 *                       (| -_- |)
 *                       0\  =  /0
 *                     ___/`---'\___
 *                   .' \\|     |// '.
 *                  / \\|||  :  |||// \
 *                 / _||||| -:- |||||- \
 *                |   | \\\  - /// |   |
 *                | \_|  ''\---/''  |_/ |
 *                \  .-\__  '-'  ___/-. /
 *              ___'. .'  /--.--\  `. .'___
 *           ."" '<  `.___\_<|>_/___.' >' "".
 *          | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *          \  \ `_.   \_ __\ /__ _/   .-` /  /
 *      =====`-.____`.___ \_____/___.-`___.-'=====
 *                        `=---='
 *
 *
 *      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *            佛祖保佑       永不宕机     永无BUG
 */

180/k*x=90

x=k/2

k为奇数转多少次都不垂直

 有x组相互垂直的

n%x组有n/k+1条

x-(n%x)组有n/k条