2024 CCPC 全国邀请赛山东站

I.Left shifting

题目描述 如果一个字符串的第一个字符与最后一个字符相同，我们就说这个字符串很美。

给定长度为 \(n\) 的字符串 \(S = s_0s_1\cdots s_{n-1}\) ，设 \(f(S, d)\) 是将 \(S\) 向左移动 \(d\) 次得到的字符串。即 \(f(S, d) = s_{(d+0)\bmod n}s_{(d+1)\bmod n}\cdots s_{(d+n-1)\bmod n}\) 。求使 \(f(S, d)\) 美观的最小非负整数 \(d\) 。

输入

有多个测试用例。输入的第一行包含一个整数 \(T\) ，表示测试用例的数量。对于每个测试用例

第一行也是唯一一行包含一个仅由小写英文字母组成的字符串 \(s_0s_1\cdots s_{n-1}\) ( \(1 \le n \le 5 \times 10^5\) )。

保证所有测试用例的 \(n\) 之和不超过 \(5 \times 10^5\) 。

输出

对于每个测试用例，输出一行包含一个整数的数据，指出最小的非负整数 \(d\) ，这样 \(f(S, d)\) 是美丽的。如果不可能找到这样的 \(d\) ，则输出 -1 代替。

题解

简单暴力，枚举所有可能的 \(d\) ，检查 \(f(S, d)\) 是否美丽即可。

AC 代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
  string s;
  cin >> s;
  int n = s.size();
  for (int i = 0; i < n; i++) {
    if (s[i] == s[(i + n - 1) % n]) {
      cout << i << '\n';
      return;
    }
  }
  cout << "-1\n";
}

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

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

A.Printer

题目描述

来自 SUA 程序设计竞赛问题设置团队的评委们正在为即将举行的 2024 年 CCPC 山东邀请赛和 CCPC 山东省大学生程序设计竞赛打印问题集。

打印车间有 \(n\) 台打印机。每 \(t_i\) 秒， \(i\) 台打印机就能打印一份题集。然而，每当第 \(i\) 台打印机打印出 \(l_i\) 份副本后，必须停止 \(w_i\) 秒，以避免过热。也就是说， \(i\) （台）打印机将重复以下工作计划：连续工作 \(t_i \times l_i\) 秒，然后停止 \(w_i\) 秒。

评委将同时使用所有打印机。计算制作至少 \(k\) 份问题集所需的最少秒数。

输入

有多个测试用例。输入的第一行包含一个整数 \(T\) ( \(1 \le T \le 100\) )，表示测试用例的数量。对于每个测试用例

第一行包含两个整数 \(n\) 和 \(k\) （ \(1 \le n \le 100\) , \(k\) , \(k\) , \(n\) ）。( \(1 \le n \le 100\) , \(1 \le k \le 10^9\) )，表示打印机数量和所需副本数量。

对于下面的 \(n\) 行， \(i\) -行包含三个整数 \(t_i\) 、 \(l_i\) 和 \(w_i\) ( \(1 \le t_i, l_i, w_i \le 10^9\) )。它们的含义如上所述。

输出

为每个测试用例输出一行，其中包含一个整数，表示所需的最少秒数。

题解

一眼二分，打字机花费时间越长，打印的题目越多，求最少的打字时间。只需要二分打字时间，然后 \(O(1)\) 检查是否满足条件即可。这里有个细节是 checker 的实现容易爆 long long，我这里开了 ull 才过。

AC 代码

#include <bits/stdc++.h>
using namespace std;

#define int unsigned long long
const int inf = 2e18 + 5;

void solve() {
  int n, k;
  cin >> n >> k;
  int l = 1, r = inf + inf / 10;
  vector<int> t(n), ll(n), h(n);
  for (int i = 0; i < n; i++) {
    cin >> t[i] >> ll[i] >> h[i];
  }

  while (l < r) {
    int num = 0, mid = (l + r) / 2;
    for (int i = 0; i < n; i++) {
      int loop = t[i] * ll[i] + h[i];
      num += (mid / loop) * ll[i];
      num += min((mid % loop) / t[i], ll[i]);
    }
    if (num >= k) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  cout << r << '\n';
}

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

  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
}

K.Matrix

题目描述

构造一个行数为 \(n\) 列数为 \(n\) 的矩阵，满足以下所有约束条件：

矩阵的元素是范围从 \(1\) 到 \(2n\) 的整数（包括这两个整数）。
从 \(1\) 到 \(2n\) （包括首尾两个整数）的每个整数都应在矩阵中至少出现一次。
假设 \(a_{i, j}\) 是 \(i\) （第 3 行）和 \(j\) （第 3 列）上的元素，那么正好存在一个整数四元组 \((x, y, z, w)\) 这样的元素：
\(1 \le x < z \le n\) .
\(1 \le y < w \le n\) .
\(a_{x, y}\) ， \(a_{x, w}\) ， \(a_{z, y}\) ， \(a_{z, w}\) 成对不同。

输入

每个测试文件中只有一个测试用例。

输入的第一行也是唯一一行包含一个整数 \(n\) ( \(2\leq n\leq 50\) )，表示矩阵的大小。

输出

如果可以构造这样一个矩阵，首先在一行中输出 "是"。然后输出 \(n\) 行，其中 \(i\) \th行包含 \(n\) 个整数 \(a_{i, 1}, a_{i, 2}, \cdots, a_{i, n}\) （ \(1 \le a_{i, j} \le 2n\) ），用空格隔开，其中 \(a_{i, j}\) 是 \(i\) \th行和 \(j\) \th列上的元素。如果有多个有效答案，可以输出任意一个。

如果无法构建这样一个矩阵，则只需在一行中输出 "否"。

题解