A 智乃与瞩目狸猫、幸运水母、月宫龙虾
第一个字母在忽略大小写相同输出 yes 否则
no
1 | if (tolower(s[0]) == tolower(t[0])) { |
B 智乃的数字手串
有一个手串 (第 \(N\) 个数字与第一个数字相邻)
两人轮流进行操作：
- 当且仅当某两个相邻数字的和为偶数时，可以拿走这两个相邻数字中的任意一个，取数后将剩下的数字按照它们之前的相对顺序重新紧凑排列
- 选择两个数字交换他们的值 (可以不交换)
如果最后手串只剩下一个了，则可以直接取走并赢得胜利。
若玩家不能进行取数操作，则该玩家失败输掉游戏。
现在 qcjj
先手取数，若两个人都采取最优策略，谁将获胜？
考虑游戏最终的结果，无论是谁不能取数，最终剩下的数字一定按照\([奇, 偶, 奇, 偶,..., 奇, 偶]\)排列，即长度为偶数。所以无论数字的内容是什么，两人的决策是什么，都不影响起始回合到终局回合的奇偶性。
1 | if (n % 2) { |
D/E/F chino's bubble sort and maximum subarray sum (easy)(hard)(very hard)
现在智乃有一个长度大小为 \(N\) 的数组，数组中元素的值有正有负。她想要先进行恰好 \(K\) 次相邻元素的交换操作，再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大，请你帮助智乃算出她最终可能的最大子段和有多大。
easy: \(2\leq n\leq 10^3,0\leq k\leq 1\)hard: \(2\leq n\leq 10^3,0\leq k\leq 100\)very hard: \(2\leq n\leq 10^3,0\leq k\leq 1000\)
当 \(k=0\) 时，则求的是数组的最大字段和，
1 | for (int l = 1;l <= n;l++) { |
当 \(k=1\) 时，则在可以交换一次的前提下，数组的最大字段和。(PS：交换后记得还原)
1 | for (int i = 2; i <= n; ++i) { |
1 | void solve() { |
L/M 智乃的 36 倍数 (easy)(normal)
定义运算 \(f\)，表示将两个正整数按照字面值从左到右拼接
智乃现在有一个大小为 \(N\) 的正整数数组 \(a\)，第 \(i\) 个元素为 \(a_i\)，现在他想选出两个正整数进行前后拼接，使得它们拼接后是一个 \(36\) 的倍数，问智乃有多少种可行的方案。
她想要知道有多少对有序数对 \((i, j)(i≠j)\) 满足 \(f (a_i, a_j)\) 是一个 \(36\) 的倍数。
easy: \(1\leq N\leq 1000,1\leq a_{i}\leq 10\)normal: \(1\leq N\leq 10^5,1\leq a_{i}\leq 10^{18}\)
\(\text{easy:}\)
法一：暴力枚举
stoi: 即 string to int 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0;i < n;i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (i != j) {
string s = to_string(a[i]) + to_string(a[j]);
int num = stoi(s);
if (num % 36 == 0) {
cnt++;
}
}
}
}
cout << cnt << '\n';
}
法二：只需要统计 36 72 108 即可。 1
2
3
4
5
6
7
8
9
10void solve() {
int n, x;
cin >> n;
vector<int> a(11);
for (int i = 1;i <= n;++i) {
cin >> x;
a[x]++;
}
cout << a[3] * a[6] + a[7] * a[2] + a[10] * a[8] << '\n';
}
\(\text{normal:}\)
法一：可以考虑 36 实际上就是 4 的倍数和 9 的倍数
- 4 的倍数只要后两位可以被 4 整除即可。
- 9 的倍数只要所有数位和可以被 9 整除即可。
(待更 \(\dots\))
法二：根据模的性质，两个数字求和模 36 实际上就是每一部分分别模 36 求和后再模 36
即 \((a+b)\%36=(a\%36+b\%36)\%36\)，
所以可以直接开桶统计每个数字模 36 后是几，然后 36 还有个特殊性质， \(10^k\ \%36=28(k\geq 2)\) 所以只需要知道它是不是 10 位数即可。
\(f(j,i)=j\times10^k+i\) (\(k\) 为 \(i\) 的位数)
如果 \(k\geq 2(i\geq 10),j\times10^k\%36=j\times28\) 如果 \(k=1(i<10),j\times10^k\%36=j\times10\)
\(f(j,i)\) 即
(j * (i < 10LL ? 10LL : 28LL) + i) \(j\) 是 a[i] 中的元素 \(\text{mod 36}\) 的结果， \(i\) 是 a[i]，\(sum[i]\) 是代表 \(a[i]\%36\) 结果相同的数量(证明这些数相差 36
的倍数，对结果不影响，在 \(f(j,i)\%36\)
时会消掉，这些数就可以一起加上降低复杂度)
对于 a[i] 中的每个元素，遍历 \(f(j,a[i])\),若被 36 整除加上
1 | void solve() { |
代码没有怎么看懂，我主要是想预处理 \(sum[i]\) 数组，然后在两层循环中两层循环所对应的下标不能相同 (即不能和自己拼接)，这样就不用翻转数组再来一次了
给予实现
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n;
ll ans = 0;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<ll> sum(36, 0);
for (auto i : a) {
sum[i % 36]++;
}
for (auto i : a) {
--sum[i % 36];
for (int j = 0; j < 36; ++j) {
if ((j * (i < 10LL ? 10LL : 28LL) + i) % 36 == 0) {
ans += sum[j];
}
}
++sum[i % 36];
}
cout << ans << '\n';
}
G/H 智乃的比较函数 (easy)(normal)
\(cmp(x,y)\) :
- \(x<y,cmp (x, y)=1\)
- \(x\geq y,cmp(x,y)=0\)
有 \(a_{1},a_{2},a_{3}\) 整型变量，给出 \(N\) 组 \(cmp(a_{x},a_{y})\) 的值，问是否产生了矛盾。
easy: \(1\leq N\leq 2\)normal: \(1\leq N\leq 50\)
\(\text{easy:}\)
1 | void solve() { |
\(\text{normal:}\)
枚举 \(a_{1},a_{2},a_{3}(1,2,3)\) 如果有满足 \(z=1\&\&a[x]\geq a[y]\mid\mid z=0\&\&a[x]<a[y]\),则产生了矛盾。
只要找到符合条件的情况，则存在
感觉代码很简单，只是自己没有想到。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33int i, j, k, n, m, t, a[1005];
vector<tuple<int, int, int> > v;
bool fuck() {
for (auto [x, y, w] : v) {
if (w == 1) {
if (a[x] < a[y])continue;
else return 0;
} else {
if (a[x] >= a[y])continue;
else return 0;
}
}
return 1;
}
void solve() {
int n;
cin >> n;
while (n--) {
cin >> i >> j >> k;
v.push_back({ i,j,k });
}
int res = 0;
for (i = 1;i <= 3;i++)
for (j = 1;j <= 3;j++)
for (k = 1;k <= 3;k++) {
a[1] = i; a[2] = j; a[3] = k;
int ans = 0;
res |= fuck();
}
if (res)cout << "Yes\n";
else cout << "No\n";
v.clear();
}
(待更 \(\dots\))可以先暂时不补了，后面的都比较有难度，还是先去系统学习算法再来。