A.谁来自智算学部
模拟
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
int ans[5];
void solve() {
int n; cin >> n;
while (n--) {
string str; cin >> str;
if (str.substr(4, 3) == "244") {
ans[1]++;
if (str[0] == '3') ans[2]++;
else if (str[0] == '2') ans[3]++;
else ans[4]++;
}
}
for (int i = 1; i <= 4; i++)
cout << ans[i] << " ";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
B.加密呼叫
模拟矩阵乘法
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
void solve() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[1][i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> b[i][j];
for (int i = 1; i <= m; i++) {
int ans = 0;
for (int j = 1; j <= n; j++)
ans += a[1][j] * b[j][i];
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
C.小J打大金
每遇到9看最近一局是否1-8都有出现
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
void solve() {
string str;
cin >> str;
int ans = 0;
int x = 0;
int lst = -1;
for (auto ch : str) {
if (ch - '0' <= lst) x = 0;
lst = ch - '0';
x |= 1 << (ch - '0');
if (ch == '9') {
if (__builtin_popcount(x) == 9) {
ans += 10;
} else ans += 4;
x = 0;
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
D.图不灵测试
进制转换，特判负数负号
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int trans(char ch) {
if (isdigit(ch)) return ch - '0';
else {
return 10 + ch - 'a';
}
}
char trans2(int x) {
if (x <= 9) return '0' + x;
else return 'a' + x - 10;
}
void solve() {
string a, b; cin >> a >> b;
int aa = 0, bb = 0;
for (auto ch : a) {
aa = aa * 16 + trans(ch);
}
for (auto ch : b) {
bb = bb * 16 + trans(ch);
}
int ans = aa - bb;
int pos = ans >= 0;
ans = abs(ans);
if (pos == 0) cout << '-';
string res;
while (ans) {
res.push_back(trans2(ans % 16));
ans /= 16;
}
reverse(res.begin(), res.end());
cout << res << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
E.小A的口算题卡
枚举进制，边遍历边取余，看余数是否为0
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
string str;
int trans(char ch) {
if (isdigit(ch)) return ch - '0';
return 10 + ch - 'A';
}
int ck(int x) {
int res = 0;
for (auto ch : str) {
res = (res * x + trans(ch)) % (x - 1);
}
return res == 0;
}
void solve() {
cin >> str;
int mx = 1;
for (auto ch : str) {
mx = max(mx, trans(ch) + 1);
}
for (int i = mx; i <= 36; i++) {
if (ck(i)) {
cout << i << "\n";
return;
}
}
cout << "No Solution\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
F.贴纸导购
结论，题目等价于求差分数组的区间平均值最大值，即为差分数组的区间最大值，答案一定是相邻的两天买入卖出，遍历取最大值即可。
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int arr[maxn];
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
db ans = 0;
for (int i = 2; i <= n; i++)
ans = max(ans, (db)arr[i] - arr[i - 1]);
printf("%.5f\n", ans);
}
signed main() {
// ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
G.谁是非酋
交互题，随机选10个位置问是否是众数，可有不低于 \(1 - \frac{1}{2^{10}}\) 概率正确，关闭同步流的话注意用endl刷新缓冲区。
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int query1(int x) {
cout << "? 1 " << x << endl;
int res; cin >> res; return res;
}
int query2(int x) {
cout << "? 2 " << x << endl;
int res; cin >> res; return res;
}
void solve() {
int n; cin >> n;
srand(time(0));
for (int i = 1; i <= 10; i++) {
int pos = rand() % n + 1;
int tem = query1(pos);
if (query2(tem)) {
cout << "! " << tem << endl;
return;
}
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
H.矩阵判断器
方法1 生成 \(1 \times n\) 的行向量 \(X\) 判断 \(X \times A \times B\) 是否等于 \(X \times C\) , 复杂度 \(O(n^2)\)
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e3 + 10;
const int mod = 998244353;
struct mat {
vector<vector<int>> arr;
};
mat operator* (mat a, mat b) {
int n = a.arr.size(), m = b.arr[0].size();
vector<vector<int>> res(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
for (int k = 0; k < a.arr[0].size(); k++)
res[i][j] += a.arr[i][k] * b.arr[k][j];
}
return mat{res};
}
bool operator==(mat a, mat b) {
return a.arr == b.arr;
}
void solve() {
int n; cin >> n;
mat A, B, C;
A.arr.resize(n);
for (int i = 0; i < n; i++) {
A.arr[i].resize(n);
for (int j = 0; j < n; j++)
cin >> A.arr[i][j];
}
B.arr.resize(n);
for (int i = 0; i < n; i++) {
B.arr[i].resize(n);
for (int j = 0; j < n; j++)
cin >> B.arr[i][j];
}
C.arr.resize(n);
for (int i = 0; i < n; i++) {
C.arr[i].resize(n);
for (int j = 0; j < n; j++)
cin >> C.arr[i][j];
}
int flag = 1;
srand(time(0));
for (int i = 0; i < 2; i++) {
vector<int> tem;
for (int j = 0; j < n; j++)
tem.push_back(rand() % 1000);
mat tem2;
tem2.arr.clear();
tem2.arr.push_back(tem);
flag &= (tem2 * A * B) == (tem2 * C);
if (!flag) break;
}
cout << (flag ? "Yes" : "No") << "\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
方法2 对于 \(C\) 的每一行求和，利用前缀和，快速算出 \(A \times B\) 对应的一行和，判断是否相等，对每一行计算，复杂度 \(O(n^2)\)
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e3 + 10;
const int mod = 998244353;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int sumb[maxn];
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++)
sumb[i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cin >> b[i][j], sumb[i] += b[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> c[i][j];
for (int i = 1; i <= n; i++) {
ll sumc = 0;
for (int j = 1; j <= n; j++)
sumc = (sumc + 1ll * c[i][j] + mod) % mod;
ll sum = 0;
for (int j = 1; j <= n; j++)
sum = (sum + 1ll * a[i][j] * sumb[j] % mod + mod) % mod;
if (sum != sumc) {
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
I.树织
预处理每一行的合法染色方案，爆搜枚举每一行的染色结果，最后判断列是否合法。
// 一眼鉴定为张老板出的题
#include<bits/stdc++.h>
#define int long long
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int n;
vector<int> vec[10];
vector<int> col[10];
int arr[10][10];
int ck() {
for (int j = 0; j < n; j++) {
vector<int> tem;
for (int i = 0; i < n; i++) {
if (arr[i][j] == 0) continue;
int cnt = 0;
while (i < n && arr[i][j] == 1) cnt++, i++;
tem.push_back(cnt);
}
if (col[j] != tem) return 0;
}
return 1;
}
void dfs(int num, string str) {
if (num == n - 1) {
// if (str == "10220") {
// for (int i = 0; i < n; i++)
// for (int j = 0; j < n; j++)
// cout << arr[i][j] << " \n"[j == n - 1];
// }
if (ck()) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cout << arr[i][j] << " \n"[j == n - 1];
exit(0);
}
return;
}
for (int i = 0; i < vec[num + 1].size(); i++) {
for (int k = (n - 1); k >= 0; k--)
arr[num + 1][n - 1 - k] = vec[num + 1][i] >> k & 1;
dfs(num + 1, str + (char)('0' + i));
}
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
int cnt; cin >> cnt;
vector<int> tem;
while (cnt--) {
int x; cin >> x;
tem.push_back(x);
}
for (int j = 0; j < (1 << n); j++) {
vector<int> tem2;
for (int k = (n - 1); k >= 0; k--) {
if (!(j >> k & 1)) continue;
int len = 0;
while (k >= 0 && (j >> k & 1)) len++, k--;
tem2.push_back(len);
}
if (tem2 == tem) {
vec[i].push_back(j);
// cout << i << " " << j << "\n";
}
}
}
for (int i = 0; i < n; i++) {
int cnt; cin >> cnt;
while (cnt--) {
int x; cin >> x;
col[i].push_back(x);
}
}
for (int i = 0; i < vec[0].size(); i++) {
for (int k = (n - 1); k >= 0; k--)
arr[0][n - 1 - k] = vec[0][i] >> k & 1;
dfs(0, to_string(i));
}
cout << "No solution.\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
J.小L的游戏
图论建模, 对于 \(x - y\) 看作一个节点, 每个操作看作一条移动 \(a - b\) 或 \(b - a\) 的长度为 \(c\) 的边, 跑最短路。建边时注意先去重取最短的边，再跑迪杰斯特拉，负数下标整体偏移 \(2\times 10^3\)。
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
vector<pii> G[maxn];
int vis[maxn], dis[maxn];
map<int, int> mp;
const int base = 2e3;
void solve() {
int x, y; cin >> x >> y;
int L, R; cin >> L >> R;
int n, m; cin >> n >> m;
if (x - y < L || x - y > R) {
cout << 2147483647 << "\n";
return;
}
L += base, R += base;
int s = x - y + base;
for (int i = 1; i <= n; i++) {
int a, b, c; cin >> a >> b >> c;
for (auto it : {a - b, b - a}) {
if (!mp.count(it)) {
mp[it] = c;
} else mp[it] = min(mp[it], c);
}
}
for (int i = L; i <= R; i++) {
for (auto [u, v] : mp) {
if (L <= i + u && i + u <= R) {
G[i].emplace_back(i + u, v);
}
}
}
priority_queue<pii, vector<pii>, greater<pii>> q;
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
q.push(pii{0, s});
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : G[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(pii{dis[v], v});
}
}
}
int ans = 2e18;
for (auto t : {m + base, -m + base}) {
if (L <= t && t <= R) {
ans = min(ans, dis[t]);
}
}
if (ans > 1e18) {
cout << "2147483647\n";
} else cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
K.DTOOTD
发现答案为YES等价于可以将字符串划为两个非回文串, 考虑预处理数组 \(pre[i]\) 和 \(suf[i]\) 表示每个前缀和后缀是否是回文串, 可以使用哈希、马拉车，PAM。
哈希做法对正串和反串处理哈希值, 每次 \(O(1)\) 判断子串是否是回文串。
#include<bits/stdc++.h>
#define int long long
#define ll __int128_t
#define pii piar<int, int>
#define db double
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e18 + 121, base = 131;
int mi[maxn];
int h[maxn], h2[maxn];
void init(string& str) {
mi[0] = 1;
int n = str.length();
for (int i = 1; i <= n; i++)
mi[i] = (ll)mi[i - 1] * base % mod;
for (int i = 1; i <= n; i++) {
h[i] = ((ll)h[i - 1] * base + str[i - 1]) % mod;
h2[i] = ((ll)h2[i - 1] * base + str[n - i]) % mod;
}
}
int query(int l, int r, int h1[]) {
return (h1[r] - (ll)h1[l - 1] * mi[r - l + 1] % mod + mod) % mod;
}
int n;
int ishuiwen(int l, int r) {
// cout << query(l, r, h) << "\n";
// cout << query(n - r + 1, n - l + 1, h2) << "\n";
return query(l, r, h) == query(n - r + 1, n - l + 1, h2);
}
void solve() {
string str; cin >> str;
init(str);
set<char> s;
for (auto ch : str) {
s.insert(ch);
}
if (s.size() == 1) {
cout << "NO\n";
return;
}
n = str.length();
int flag = ishuiwen(1, n);
if (!flag) {
cout << "YES\n1\n" << str << "\n";
return;
}
for (int i = 2; i <= n; i++) {
if (!ishuiwen(1, i - 1) && !ishuiwen(i, n)) {
cout << "YES\n2\n";
cout << str.substr(0, i - 1) << " " << str.substr(i - 1) << "\n";
return;
}
}
cout << "NO\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
马拉车做法枚举每个前缀，看中心的最长回文半径是否覆盖到端点，代码略。
PAM做法，边插入字符，边判断前缀的最长回文后缀是否覆盖到端点。插入后对于终点，不断跳fail指针，得到每个后缀是否是回文串。
#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
vector<pii> vec;
struct PAM {
int tot, last, fail[maxn], c[maxn][26], len[maxn];
char s[maxn]; // 下标从1开始的字符串
PAM() {
tot = last = fail[0] = 1, len[1] = -1, len[0] = 0;
}
void clear() {
for (auto it : vec) {
c[it.first][it.second] = 0;
}
vec.clear();
tot = last = fail[0] = 1, len[1] = -1, len[0] = 0;
}
int getfail(int x, int i) {
while (s[i - len[x] - 1] != s[i])
x = fail[x];
return x;
}
void extend(char ch, int i) { // 插入位置 i 的字符 ch
s[i] = ch;
int x = getfail(last, i), v = ch - 'a';
if (!c[x][v]) {
len[++tot] = len[x] + 2;
int tem = getfail(fail[x], i);
fail[tot] = c[tem][v];
c[x][v] = tot; // 必须放最后
vec.emplace_back(x, v);
}
last = c[x][v];
}
} pam;
int pre[maxn], suf[maxn];
void solve() {
pam.clear();
string str; cin >> str;
int n = str.length();
for (int i = 1; i <= n; i++) pre[i] = suf[i] = 0;
for (int i = 1; i <= n; i++) {
pam.extend(str[i - 1], i);
if (pam.len[pam.last] == i) pre[i] = 1;
}
int x = pam.last;
while (x > 1) {
suf[n - pam.len[x] + 1] = 1;
x = pam.fail[x];
}
if (!pre[n]) {
cout << "YES\n1\n" << str << "\n";
return;
}
for (int i = 1; i < n; i++)
if (!pre[i] && !suf[i + 1]) {
cout << "YES\n2\n" << str.substr(0, i) << " " << str.substr(i, n - i + 1) << "\n";
return;
}
cout << "NO\n";
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}