Practice.
A. Number Replacement
题意
给定一个序列，一个字母可以映射到任意一个数字，但要求一个字母只能映射到一个数字，一个数字可以映射到多个字母。输出是否合法。
思路
简单，我们用哈希即可。用 \(map\) 即可解决本题。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
string s;
cin >> s;
map<int, char> mp;
bool f = true;
for(int i=0;i<n;i++){
if(mp[a[i]] > 0 && mp[a[i]] != s[i]) f = false;
mp[a[i]] = s[i];
}
cout << (f ? "YES\n" : "NO\n");
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//init();
int t;
cin >> t;
while(t --) solve();
}水.jpg
B. Even-Odd Increments
题意
给定一个序列，含有奇数和偶数，定义操作如下：
\(0\ x\) 表示将 \(x\) 添加到所有偶数上；
\(1\ x\) 表示将 \(x\) 添加到所有奇数上。
在每次操作后，输出总和。前面的操作会影响后面的值。
思路
显然，我们只需统计当前序列有多少偶数即可。
设偶数的个数为 \(cnt\)，那么第一个操作即为将 \(sum\) 加上 \(even \times x\)，第二个操作即为将 \(sum\) 加上 \((n - even) \times x\)。
显然，我们不需要在每次操作后遍历找偶数个数，而是考虑下面的规律：
偶数加奇数为奇数；
奇数加奇数为偶数。
因而，若出现将奇数加在奇数上的情况，那么 \(even = n\)，若出现将奇数加在偶数上的情况，那么 \(even = 0\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n); //注意一下偶数和奇数的相加即可
int even = 0, sum = 0;
for(int i=0;i<n;i++){
cin >> a[i];
sum += a[i];
if(a[i] % 2 == 0) even ++;
}
while(q --){
int t, v;
cin >> t >> v;
if(t % 2 == 0){ //加到偶数上
sum += even * v;
cout << sum << '\n';
if(v % 2 == 1) even = 0; //偶加奇
}else{ //加到奇数上
sum += (n - even) * v;
cout << sum << '\n';
if(v % 2 == 1) even = n; //奇加奇
}
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//init();
int t;
cin >> t;
while(t --) solve();
}偏模拟的思维题
C. Traffic Light
题意
定义三种交通信号灯：\(R,H,G\)，只有位于 \(G\) 的时间下才可过马路。交通信号灯的切换具有周期性，因而给定一个周期的信号灯切换情况 \(s\)，如 \(s = RBRGG\)，那么在执行五秒后，将会重新执行一次，构成 \(RBRGGRBRGGRB...\)。给定当前的信号灯种类 \(c\)，输出遇到下一个 \(G\) 所间隔的最长时间。
思路
如上，我们只需遍历所有 \(c\)，找出其和下一个 \(G\) 的距离即可。
至于距离，数据范围貌似可以允许我们暴力往后搜，但后缀数组会出手。
我们维护后缀数组，\(suf_i\) 表示 \(i\) 及以后第一个出现的 \(G\) 的位置。
那么，查询的复杂度即为 \(O(1)\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve() {
int n;
char c;
cin >> n >> c;
string s;
cin >> s;
s = " " + s + s;
n *= 2;
vector<int> suf(n + 1);
suf[n] = -1;
for(int i=n - 1;i>=1;i--){
if(s[i] == 'g') suf[i] = i;
else suf[i] = suf[i + 1];
}
int mx = 0;
for(int i=0;i<n;i++){
if(s[i] == c) mx = max(mx, suf[i] - i);
}
cout << mx << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//init();
int t;
cin >> t;
while(t --) solve();
}可能就真的能暴力（（
D. Divisibility by 2^n
题意
给定一个长度为 \(n\) 的序列，定义一次操作为选取一个 \(a_i\) 并将其改为 \(a_i \times i\)。输出最少的操作数，使最后的序列的乘积为 \(2 ^ n\) 的倍数。
思路
首先，乘上奇数绝对没什么用，所以我们只需考虑偶数。
观察偶数的递推性以及二进制下的规律，我们不难发现所有的偶数都是一个 \(2 ^ t\) 乘上一个奇数得到的。
上述没必要乘上偶数，毕竟那就是 \(2 ^ {t + 1}\) 的事情了，为何要考虑重复呢。
因而，我们自然希望我们能在一次操作中乘上尽可能多的 \(2\)，也就是让 \(t\) 尽可能大。
这个 \(t_{\max}\) 是很容易求的，我们只需循环乘二直到不超过 \(n\) 的最大值即可。
那么，我们不妨去枚举 \(2 ^ t\) 的奇数倍，然后在超过 \(n\) 后将 \(t\) 递减，这样即可满足条件。
在加之前，我们判断一下当前能除多少个 \(2\)，和 \(n\) 比较即可。
时间复杂度：\(O(nt)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void solve() {
int n;
cin >> n;
int cnt = 0;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
while(cur % 2 == 0){
cur /= 2;
cnt ++;
}
}
int mx = 1, cur = 2;
while(true){
if(cur * 2 > n) break;
mx ++;
cur *= 2;
}
int ans = 0;
for(int i=mx;i>=1;i--){
for(int j=1;pow(2, i)*j<=n;j+=2){ //奇数倍
if(cnt >= n) break;
cnt += i;
ans ++;
}
if(cnt >= n) break;
}
cout << (cnt >= n ? ans : -1) << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//init();
int t;
cin >> t;
while(t --) solve();
}奇怪的清晰思路增加了
E1. Divisible Numbers (easy version)
详见E2，区别是本题的数据范围小
E2. Divisible Numbers (hard version)
题意
给定 \(4\) 个整数 \(a, b, c, d\)，找出一对 \(x, y\)，满足 \(x \in (a, c], y \in (b, d], xy\) 可以被 \(ab\) 整除。
思路
首先，我们不难发现，\(y = k \times \frac{ab}{gcd(ab, x)}\)，其中 \(k\) 为常数，那么，我们可以很简单的用 \(O(1)\) 的复杂度算出 \(y\)。
那么我们来考虑 \(x\)。显然，\(x \neq 1\)，所以 \(x\) 就是 \(gcd(ab, x)\) 的倍数，或者说，是 \(ab\) 的因数的倍数。
那么，我们只需枚举所有的因数，然后，我们也可以用 \(O(1)\) 的方法算出 \(x\)，和求 \(y\) 的方法类似。
但是，枚举 \(ab\) 的因数是不现实的，因为 \(\sqrt{ab}\) 太大了。但是，既然我们可以将这个数分解为 \(a, b\)，那么它的所有因数就是 \(a\) 的所有因数和 \(b\) 的所有因数配对相乘。
因而，\(\sqrt a\) 可以减到 \(1e5\) 的复杂度，足以。
时间复杂度：\(O(\sqrt a + \sqrt b + t ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
vector<int> fact(int x) {
vector<int> facts;
int sq = (int) sqrt(x);
for (int i = 1; i < sqrt(x); i++) {
if (x % i == 0) facts.emplace_back(i), facts.emplace_back(x / i);
}
if (sq * sq == x) facts.emplace_back(sq);
return facts;
}
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
vector<int> factA = fact(a), factB = fact(b);
bool f = false;
for (int i: factA) {
for (int j: factB) {
int bx = i * j, by = a * b / (i * j);
int x = ((int) ceil((double) a / (double) bx) + (a % bx == 0 ? 1 : 0)) * bx,
y = ((int) ceil((double) b / (double) by) + (b % by == 0 ? 1 : 0)) * by;
if (x <= c && y <= d) {
cout << x << ' ' << y << '\n';
f = true;
break;
}
}
if (f) break;
}
if (!f) cout << -1 << ' ' << -1 << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
//init();
int t;
cin >> t;
while (t --) solve();
}一开始还想着贪心，似也做不出来，淦