Contestant^. Rank 154. Rating +119 (+469 -350).不知道有没有可能在有生之年打到 cf 第1000场（
A. How Much Does Daytona Cost?
题意
给定一个序列 \(a\)，以及一个整数 \(k\)，判断 \(k\) 是否是 \(a\) 的任意子串中出现次数最多的字符。
思路
只要子串长度是 \(1\)，那么该字符就是出现次数最多的字符。
那么，问题就转化为判断 \(k\) 是否在 \(a\) 中出现了。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k;
cin >> n >> k;
bool ok = false;
for(int i=1;i<=n;i++){
int x;
cin >> x;
if(x == k) ok = true;
}
cout << (ok ? "YES\n" : "NO\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}签到
B. Aleksa and Stack
题意
给定一个正整数 \(n\)，构造一个长为 \(n\) 的严格递增序列，满足 \(3 \cdot a_{i + 2}\) 不被 \(a_i + a_{i + 1}\) 整除。
思路1
我们可以构造递增的 \(3\) 的倍数，并加上一定值，来让条件不成立。
具体来说，我们可以构造下面的序列：
\(4, 7, 8, 13, 16, 17, \ldots\)
给出如下证明：
\(a_{3k + 1} + a_{3k + 2} = (9k + 4) + (9k + 7) = 18k + 11\)，\(a_{3k + 3} = 9k + 8\)；\(3 \cdot a_{3k + 3} = 27k + 24\)； \(lcm(18, 27) = 54\)，\((18k + 11) \cdot \frac{lcm(18, 27)}{18} = 54k + 33, (27k + 24) \cdot \frac{lcm(18, 27)}{27} = 54k + 48\)； \(33 \neq 48\)，从而无法整除。
\(a_{3k + 2} + a_{3k + 3} = (9k + 7) + (9k + 8) = 18k + 15, a_{3k + 4} = 9k + 13\)；\(3 \cdot a_{3k + 4} = 27k + 36\)； \(lcm(18, 27) = 54\)，\((18k + 15) \cdot \frac{lcm(18, 27)}{18} = 54k + 45, (27k + 36) \cdot \frac{lcm(18, 27)}{27} = 54k + 72\)； \(45 \neq 72\)，从而无法整除。
\(a_{3k + 3} + a_{3k + 4} = (9k + 8) + (9k + 13) = 18k + 21, a_{3k + 5} = 9k + 16\)；\(3 \cdot a_{3k + 4} = 27k + 48\)； \(lcm(18, 27) = 54\)，\((18k + 21) \cdot \frac{lcm(18, 27)}{18} = 54k + 63, (27k + 48) \cdot \frac{lcm(18, 27)}{27} = 54k + 96\)； \(63 \neq 96\)，从而无法整除。
从而，可得构造合法。
思路2
我们可以按顺序输出所有奇数，即：
\(1, 3, 5, 7, 9, \ldots\)
可以发现，\(3a_{i + 2}\) 为奇数，\(a_i + a_{i + 1}\) 是偶数，从而一定不满足整除条件。
时间复杂度：\(O(n)\)
对应AC代码1
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
for(int i=1;i<=n;i++) {
cout << i * 3 + 1 - (i % 3 == 0) << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}对应AC代码2
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
for(int i=1;i<=n;i++) {
cout << i * 2 - 1 << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}难绷，也是写出了很神奇的构造（
C. Vasilije in Cacak
题意
给定三个正整数 \(n, k, x\)，判断是否可以在 \([1, n]\) 中选择不同的 \(k\) 个数，使总和为 \(x\)。
思路
通过观察，我们可以发现，总和在 \([\) 前 \(k\) 小的数之和 \(,\) 前 \(k\) 大的数之和 \(]\) 之间，且可以取任意值。
那么，我们只要计算一下区间的左右端点，然后判断 \(x\) 是否在区间内即可。
注意特殊情况的边界判断。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k, x;
cin >> n >> k >> x;
if((k + 1) * k / 2 > x || (n + n - k + 1) * k / 2 < x) cout << "NO\n";
else cout << "YES\n";
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}差点没想到这个结论（x
D. Reverse Madness
题意
给定一个字符串，并将字符串分割为 \(k\) 段，给定这 \(k\) 段的左右端点。
现在，给定 \(q\) 次修改，每次修改给定一个正整数 \(x\)，将 \([\min(x, r + l - x), \max(x, r + l - x)]\) 内的字符串翻转。
输出最后一次修改后的字符串。
思路
首先，既然我们只要知道最后一次修改后的字符串，那么我们只需知道每一个位置被修改了几次即可。
考虑到区间修改，我们可以使用差分数组，最后判断每个位置的值的奇偶性即可。
至于判断当前位于哪个区间，我们可以二分。
时间复杂度：\(O(n + q)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = " " + s;
vector<int> l(k + 1), r(k + 1);
for(int i=1;i<=k;i++) cin >> l[i];
for(int i=1;i<=k;i++) cin >> r[i];
int q;
cin >> q;
vector<int> d(n + 2);
while(q --){
int x;
cin >> x;
int ind = lower_bound(all(r), x) - r.begin();
int a = min(x, r[ind] + l[ind] - x), b = max(x, r[ind] + l[ind] - x);
d[b + 1] ^= 1;
d[a] ^= 1;
}
for(int i=1;i<=n;i++) d[i] ^= d[i - 1];
for(int i=1;i<=k;i++){
for(int j = l[i];j <= (l[i] + r[i]) / 2;j++){
if(d[j]) swap(s[j],s[r[i] - (j - l[i])]);
}
}
for(int i=1;i<=n;i++) cout << s[i];
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}不然就用树状数组（x
E. Iva & Pav
题意
给定一个序列 \(a\)，定义 \(f(l, r) = a_l~\&~a_{l + 1}~\& \ldots \&~a_r\)。
给定 \(q\) 次询问，每次询问给定两个整数 \(k, l\)，输出最大的 \(r\)，使 \(f(l, r) \geq k\)。
思路
显然，在左端点确定的情况下，右端点越大，\(f(l, r)\) 越小。
所以我们只需二分即可。
具体来说，我们预处理前缀与，然后二分处理每个询问。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<vector<int>> a(n + 1, vector<int>(32));
vector<int> x(n + 1);
for(int i=1;i<=n;i++){
cin >> x[i];
bitset<32> bs(x[i]);
for(int j=0;j<=30;j++){
a[i][j] = a[i - 1][j];
if(bs[j]) a[i][j] ++;
}
}
auto check = [&](int l, int k, int x){
int cur = 0;
for(int i=0;i<=30;i++){
if(a[x][i] - a[l - 1][i] == x - l + 1) cur |= (1ll << i);
}
return cur >= k;
};
int q;
cin >> q;
while(q --){
int l, k;
cin >> l >> k;
if(x[l] < k) {
cout << -1 << ' ';
continue;
}
int L = l, R = n, mid;
while(L < R){
mid = (L + R + 1) >> 1;
if(check(l, k, mid)) L = mid;
else R = mid - 1;
}
cout << L << ' ';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}位运算的常见结论（x
F. Vasilije Loves Number Theory
题意
给定一个整数 \(n\)，定义询问如下：
\(1~x\)，将 \(n\) 乘上 \(x\)，即 \(n := n \cdot x\)，并判断是否存在整数 \(a\)，使 \(\gcd(a, n) = 1, d(n \cdot a) = n\)，其中 \(d(x)\) 为 \(x\) 的因子个数；
\(2\)，将 \(n\) 赋值为一开始的给定值
现在，给定 \(q\) 次询问，执行对应的操作。
思路
首先，因为 \(\gcd(n, a) = 1\)，所以 \(d(n \cdot a) = d(n) \times k\)。
从而，条件转化为：\(n\) 是 \(d(n)\) 的倍数。
由算术基本定理，若 \(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\cdot \ldots \cdot p_k^{\alpha_k}\)，那么 \(d(n) = (\alpha_1 + 1)(\alpha_2 + 1)\ldots(\alpha_k + 1)\)。
直接算乘积是不可行的，那么我们考虑对质因数考虑：只要对于每个质因子，在 \(d(n)\) 的乘积中的出现次数 \(cnt_1\) 大于等于在 \(n\) 的乘积中出现的次数 \(cnt_2\)，那么就满足条件。
因而，我们维护一下质因子个数的序列即可。
时间复杂度：\(O(太复杂了)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
struct MATH {
private:
struct PRIME {
int Check_Num = 0, Max_Factor = 0;
vector<pii> Dec;
private:
void Get_Fac(int Num) { //寻找 Num 的最大因子
if (Num <= Max_Factor || Num < 2) return;
if (Miller_Rabin(Num)) return void(Max_Factor = max(Max_Factor, Num));
int Fac = Num;
while (Fac >= Num) Fac = Pollard_Rho(Num);//寻 找 因 子
while (!(Num % Fac)) Num /= Fac;
return Get_Fac(Num), Get_Fac(Fac);
}
void Decomposition(int Num) { // 分解 Num 的质因子
if (Num < 2) return;
if (Miller_Rabin(Num)) {
pair<int, int> Now = {Num, 0};
while (Check_Num % Num == 0) Now.second++, Check_Num /= Num;
if (Now.second) Dec.pb(Now);
return;
}
int Fac = Num;
while (Fac >= Num) Fac = Pollard_Rho(Num);//寻 找 因 子
while (!(Num % Fac)) Num /= Fac;
return Decomposition(Num), Decomposition(Fac);
}
public:
__int128 test[16] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 61, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(__int128 P) { //检测 P 是不是质数, 严格保证答案正确
if (P < 3 || P % 2 == 0) return P == 2;
static int i, j;
static __int128 Tem, k, Next;
Tem = P - 1, k = 0;
while (Tem % 2 == 0) Tem >>= 1, ++k;
for (j = 1; j <= 15; j++) {
Next = qp(test[j], Tem, P);
if (Next <= 1 || Next == P - 1) continue;
for (i = 0; i < k; ++i) {
Next = Next * Next % P;
if (Next == P - 1 && i != k - 1) {
Next = 1;
break;
}
if (Next == 1) return false;
}
if (Next != 1) return false;
}
return true;
}
static bool RMiller_Rabin(__int128 P, int test_time = 8) { //检测 P 是不是质数, 基于随机检验
if (P < 3 || P % 2 == 0) return P == 2;
static int i, j;
static __int128 Tem, k, Rand_Num, Now;
Tem = P - 1, k = 0;
while (Tem % 2 == 0) Tem >>= 1, ++k;
for (i = 1; i <= test_time; ++i) {
Rand_Num = rand() % (P - 2) + 2, Now = qp(Rand_Num, Tem, P);
if (Now == 1) continue;
for (j = 0; j < k; ++j) {
if (Now == P - 1) break;
Now = Now * Now % P;
}
if (j >= k) return false;
}
return true;
}
static int Pollard_Rho(int x) {
static int s, t, c, Div, Val;
Val = 1, s = t = 0;
static int Step, Goal;
Step = 0, Goal = 1;
c = (int) rand() % (x - 1) + 1;
for (Goal = 1;; Goal <<= 1, s = t, Val = 1) { // 倍增优化
for (Step = 1; Step <= Goal; ++Step) {
t = ((__int128) t * t + c) % x, Val = (__int128) Val * abs(t - s) % x;
if (!(Step % 127)) {
Div = __gcd(Val, x);
if (Div > 1) return Div;
}
}
Div = __gcd(Val, x);
if (Div > 1) return Div;
}
}
void Get_Max_Fac(int Num) { return Max_Factor = 0, Get_Fac(Num); } //获得 Num 的最大因子 测 试: Luogu P4718
void Dec_Factor(int Num) { return Dec.clear(), Check_Num = Num, Decomposition(Num); } //分解 Num 的本质不同质因子 测 试: Prime Land
int Get_Phi(int Num) { //计算 φ(Num)
if (Num == 1) return 0;
Dec_Factor(Num);
for (auto &Now: Dec) Num = Num / Now.first * (Now.first - 1);
return Num;
}
}pm;
public:
static __int128 qp(__int128 x, __int128 y, __int128 m = mod) {
static __int128 ans;
ans = 1, x %= m;
for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
return ans;
}
//ax+by=gcd(a,b),返回gcd
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = x; x = y; y = t - (a / b) * y;
return d;
}
//x (mod Mi) = Ai
int exCRT(int n, int M[], int A[]) {
int a = A[1], m = M[1], ta, tm, x, y, d, l, t;
for (int i = 2; i <= n; i++) {
tm = M[i], ta = A[i];
d = exgcd(m, tm, x, y);
l = m * tm / d;
if ((ta - a) % d != 0) return -1;
t = tm / d;
x *= ((ta - a) / d);
x = (x % t + t) % t;
a += m * x;
m = l;
}
return a;
}
//欧拉函数，小于等于n和n互质的数的个数
int phi(int n) {
return pm.Get_Phi(n);
}
bool vis[N];
int pri[N], cnt;
//线性筛
void linear_prime(int n) {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[cnt++] = i;
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] > n) break;
vis[i * pri[j]] = true;
if (i % pri[j] == 0)break;
}
}
}
int inv_ex(int n, int m = mod) {
int x, y, ans = exgcd(n, m, x, y);
if (ans == 1) return (x % m + m) % m;
else return -1;
}
int inv(int n, int m = mod) { return qp(n, m - 2, m); }
//p为1e5以内质数，求c(n, m) % p
int lucas(int n, int m, int p) {
if (m == 0) return 1;
return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}
int C(int m, int n, int p) {
int a = 1, b = 1;
if (m < n) return 0;
while (n) {
a = (a * m) % p, b = (b * n) % p;
m--, n--;
}
return a * inv_ex(b, p) % p;
}
void get_phi(int n, int phi[]) {
for (int i = 0; i <= n; i++) phi[i] = i;
for (int i = 2; i <= n; i++)
if (phi[i] == i) for (int j = 2; j <= n; j++) phi[j] = phi[j] / i * (i - 1);
}
//线性求逆元
void get_inv(int n, int inv[], int p = mod) {
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = inv[i] = (p - p / i * inv[p % i] % p) % p;
}
//线性求阶乘，逆元，阶乘逆元
void get_fact_inv(int n, int fac[], int Inv[], int fac_inv[], int p = mod) {
fac[0] = fac_inv[0] = Inv[0] = fac[1] = fac_inv[1] = Inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % p;
Inv[i] = (p - p / i * Inv[p % i] % p) % p;
fac_inv[i] = fac_inv[i - 1] * Inv[i] % p;
}
}
vector<pii> factorize(int x) { return pm.Dec_Factor(x), pm.Dec; }
int max_factor(int x){ return pm.Get_Max_Fac(x), pm.Max_Factor; }
void miller_rabin(__int128 P){ pm.Miller_Rabin(P); }
void random_miller_rabin(__int128 P, int test_time = 8){ pm.RMiller_Rabin(P, test_time); }
int pollard_pho(int x) { pm.Pollard_Rho(x); }
template<class T> T ex_sqrt(T x) { //返回精度更高的sqrt
T sqrtX = sqrt(x) - 1;
while (sqrtX + 1 <= x / (sqrtX + 1)) sqrtX++;
return sqrtX;
}
}math;
void solve() {
int n, q;
cin >> n >> q;
map<int, int> cnt, cnt_n, cnt_d, last;
vector<pii > fac = math.factorize(n);
for (auto it: fac) cnt_n[it.fs] += it.sc;
last = cnt_n;
while (q--) {
int op, x;
cin >> op;
if (op == 2) {
cnt_n = last;
continue;
}
cin >> x;
fac = math.factorize(x);
for (auto e: fac) cnt_n[e.fs] += e.sc;
for (auto it: cnt_n) {
fac = math.factorize(it.sc + 1);
for (auto e: fac) cnt_d[e.fs] += e.sc;
}
bool st = true;
for (auto e: cnt_d) {
if (cnt_n[e.fs] < e.sc) st = false;
}
cnt_d.clear();
cout << (st ? "YES" : "NO") << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}有意思的数论（
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论