重游程序设计竞赛
AtCoder Regular Contest 168
A - <Inversion>
题意：一个长度为N-1的字符串S(只含有字符< ,> )，构造一个长度为N的序列X，均为整数
X序列相邻两个数字依次满足字符串S的关系，求该序列逆序对数最少值
数据范围：
- $2 \le N \le 250000$
思路：对于>>>取值依次取值为 x+3>x+2>x+1>x，对于<<<依次取 y<y+1<y+2<y+2
对于x+?的数字，整体依次递增取值，而y+?的数字，整体也依次递增
这样答案只存在于每段>>>：对于每段>>>长度为n,答案为n(n+1)/2
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 1e5 + 9;
string s;
int n;
void solve() {
cin >> n;
cin >> s;
s = s + "<";
int ans = 0;
for (int i = 0, j = 0; i < n; i++) {
if (s[i] == '>') {
ans += j;
} else {
ans += j * (j + 1) / 2;
j = 0;
}
}
cout << ans << "\n";
}
constexpr bool test = 0;
signed main() {
cin.tie(0)->ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}B - Arbitrary Nim
题意：尼姆博奕之类问题，不会┭┮﹏┭┮
数据范围：
- $2 \le N \le 250000$
- $1 \le A_{i} \le 10^{9}$
AtCoder Regular Contest 167
A - Toasts for Breakfast Party
题意：N个数$A_{i}$，分成M组，每组最多2个，设每组和为$B_{j}$
求min ${\textstyle \sum_{j=1}^{M}}$ $B_{j}^{2}$
数据范围：
- $1 \le N \le 2 \times 10^{5}$
- $\frac{N}{2} \le M \le N$
- $1 \le A_{i} \le 2 \times 10^{5}$
思路：对数组A递增排序后，依次对前N-M组分2个，后2M-N组分一个
对于前N-M组，设 a ≤ b ≤ c ≤ d，因为$(a+d)^{2}$+$(b+c)^{2}$ ≤ $(a+b)^{2}$+$(c+d)^{2}$
所以将A数组前2（N-M）个，同上形式两两组合
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 1e6 + 9;
void solve() {
int n, m;
cin >> n >> m;
vector<int>a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a.begin() + 1, a.end());
int ans = 0;
for (int i = 1; i <= n; i++) {
ans += a[i] * a[i];
}
int l = 1, r = (n - m) * 2;
while (l < r) {
ans += 2 * a[l] * a[r];
l += 1;
r -= 1;
}
cout << ans << "\n";
}
constexpr bool test = 0;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(20);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}B - Product of Divisors
题意：$A^{B}$ 的所有因子乘积可以除以多少次A，答案对998244353取模
数据范围：
- $2 \le A \le 10^{12}$
- $0 \le B \le 10^{18}$
- A,B都为整数
思路：因数是成对出现的，对每个因数$x$都有$x \times \frac{A^{B}}{x}$
设$A^{B}$有K个因子
若K为偶数，把因数两两结合，则$A^{B}$的因数之积是$A^{\frac{BK}{2}}$，答案$\frac{BK}{2}$
若K为奇数，说明$A^{B}$为完全平方数，同理$A^{B}$的因数之积是$A^{\frac{B(K-1)}{2}}\times\sqrt{A^{B}}$，答案也是$\frac{BK}{2}$，但不能直接运算
两者算K是一样的，但在后续运算乘2逆元时有差异，也可理解为向下取整影响答案
补充：$A^{B}$为完全平方数时，A为平方数或B为偶数，乘B时将B * y写成B%mod * y，避免爆数据范围
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 998244353;
constexpr int N = 1e5 + 9;
template<typename T>
T qmi(T n, long long k) {
T res = 1;
while (k) {
if (k & 1) res = res * n;
n *= n;
k >>= 1;
}
return res;
}
template <const int M>
struct ModInt {
int x;
int norm(int x) {
if (x < 0) {
x += M;
}
if (x >= M) {
x -= M;
}
return x;
}
ModInt(int x = 0) : x(norm(x % M)) {}
int val() const {
return x;
}
ModInt operator -() const {
return ModInt(norm(M - x));
}
ModInt inv() const {
assert(x != 0);
return qmi(*this, M - 2);
}
ModInt &operator *=(const ModInt &rhs) {
x = (long long)(x) * rhs.x % M;
return *this;
}
ModInt &operator +=(const ModInt &rhs) {
x = norm(x + rhs.x);
return *this;
}
ModInt &operator -=(const ModInt &rhs) {
x = norm(x - rhs.x);
return *this;
}
ModInt &operator /=(const ModInt &rhs) {
return *this *= rhs.inv();
}
bool operator < (const ModInt &rhs) {
return x < rhs.x;
}
bool operator == (const ModInt &rhs) {
return x == rhs.x;
}
bool operator != (const ModInt &rhs) {
return x != rhs.x;
}
friend ModInt operator *(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res *= rhs;
return res;
}
friend ModInt operator +(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res += rhs;
return res;
}
friend ModInt operator -(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res -= rhs;
return res;
}
friend ModInt operator /(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator >>(std::istream &is, ModInt &a) {
long long v;
is >> v;
a = ModInt(v);
return is;
}
friend std::ostream &operator <<(std::ostream &os, const ModInt &a) {
return os << a.val();
}
};
using Z = ModInt<(int)(998244353)>;
void solve() {
int a, b;
cin >> a >> b;
map<int, int>mp;
bool flag = 0;
int t = sqrt(a);
if (t * t == a) {
flag = 1;
}
for (int i = 2; i * i <= a; i++) {
while (a % i == 0) {
mp[i] += 1;
a /= i;
}
}
if (a > 1) {
mp[a] += 1;
}
Z ans = 1;
for (auto [x, y] : mp) {
ans = ans * (b % mod * y + 1);
}
if (b % 2 == 0 || flag) {
ans -= 1;
ans /= 2;
ans *= b;
ans += b / 2;
} else {
ans /= 2;
ans *= b;
}
cout << ans << "\n";
}
constexpr bool test = 0;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(20);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}
AtCoder Regular Contest 166
A - Replace C or Swap AB
题意：T组样例，每组两个长度相同的字符串X, Y，且只含有A,B,C三种字符
对X有如下三种操作：
- 选择一个字符C变为A
- 选择一个字符C变为B
- 选择字符串AB变为BA
能否从X->Y
数据范围：
- $1 \le T \le 2 \times 10^{5}$
- $1 \le N \le 2 \times 10^{5}$
- $\sum_{i=1}^{T} N_{i} \le 2 \times 10^{5}$
思路：如果$Y_{i}$是C显然不合法，除去Y中字符C的位置，那么字符C位置只能出现在X中。
以字符C的位置分段考虑，AB替换成BA，相当于将字符A向后移动一个位置。可以贪心地将A放到前面，B放后面
得到结论：
每段从前往后判断，截止目前位置X中A, C的数量是否大于等于Y中A的数量
每段从后往前判断，截止目前位置X中B, C的数量是否大于等于Y中B的数量
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 1e5 + 9;
void solve() {
int n;
cin >> n;
string x, y;
cin >> x >> y;
x = "#" + x;
y = "#" + y;
for (int i = 1; i <= n; i++) {
if (x[i] != 'C' && y[i] == 'C') {
cout << "No\n";
return ;
}
}
auto check = [&](int l, int r)->bool{
if (l > r) {
return true;
}
int cnta = 0, cntb = 0;
for (int i = l; i <= r; i++) {
if (x[i] == 'A' || x[i] == 'C') {
cnta += 1;
}
if (y[i] == 'A') {
cntb += 1;
}
if (cnta < cntb) {
return false;
}
}
cnta = 0, cntb = 0;
for (int i = r; i >= l; i--) {
if (x[i] == 'B' || x[i] == 'C') {
cnta += 1;
}
if (y[i] == 'B') {
cntb += 1;
}
if (cnta < cntb) {
return false;
}
}
return true;
};
int last = 1;
for (int i = 1; i <= n; i++) {
if (y[i] == 'C') {
if (check(last, i - 1)) {
last = i + 1;
} else {
cout << "No\n";
return ;
}
}
}
if (check(last, n)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
constexpr bool test = 1;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(10);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}B - Make Multiples
题意：给定长度为N的序列A，三个数值a,b,c
每次可以操作$A_{i}$->$A_{i}$ + 1
问最少可以操作多少次，使序列A中有a的倍数，b的倍数，c的倍数
数据范围：
- $1 \le N \le 2 \times 10^{5}$
- $1 \le a,b,c \le 10^{6}$
- $1 \le A_{i} \le 10^{18}$
思路：有以下几种情况
3个数分别对应一个数
2个数对应一个数，剩下一个数对应一个数
3个数对应一个数
$根据x成为y的倍数，所需最小操作次数为(y-x\bmod y)\bmod y$
状压dp代码（暴力代码太丑不发了）：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 1e5 + 9;
int lcm(int a, int b) {
return a / __gcd(a, b) * b;
}
void solve() {
int n;
cin >> n;
vector<int>a(3);
for (int i = 0; i < 3; i++) {
cin >> a[i];
}
vector<int>x(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
vector<int>y(8, 1);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 3; j++) {
if (i >> j & 1) {
y[i] = lcm(y[i], a[j]);
}
}
}
vector<vector<int>>f(n + 1, vector<int>(8, INF));
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 8; j++) {
for (int k = 0; k < 8; k++) {
if ((j & k) == 0) {
f[i][j | k] = min(f[i][j | k], f[i - 1][k] + (y[j] - x[i] % y[j]) % y[j]);
}
}
}
}
cout << f[n][7] << "\n";
}
constexpr bool test = 0;
signed main() {
cin.tie(0)->ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}AtCoder Regular Contest 165
A - Sum equals LCM
题意：给定一个整数N，是否可以表示为
$A_{1}+A_{2}+···+A_{n}=N$
$A_{1},A_{2},···,A_{n}小公倍数为N$
$n \ge 2$
数据范围：
- $1\le T\le 100$
- $1\le N\le 10^{9}$
思路：当$N={p}^{e}(1\le e)$时$A_{i}$ 最大为 ${p}^{k}(k<e)$ ,显然最大公约数为 ${A}^{k}$ 不满足题意
当N不为上述情况时，$N\ge 6$即N具有至少两个不同质因数p，q
令$k=N-\frac{N}{p}-\frac{N}{q}\ge N-\frac{N}{2}-\frac{N}{3}=\frac{N}{6}>0$
我们有$(A_{1},A_{2},···,A_{k},A_{k+1},A_{k+2})=(\underbrace{1,1,···,1}_{k},\frac{N}{p},\frac{N}{q})$
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 2e5 + 9;
void solve() {
int n;
cin >> n;
int sum = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
sum += 1;
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
sum += 1;
}
cout << (sum > 1 ? "Yes" : "No") << "\n";
}
constexpr bool test = 1;
signed main() {
cin.tie(0)->ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}B - Sliding Window Sort 2
题意：给定长度为n的排列P和一个整数K
可进行一次操作，选择一个长度为K的区间，对区间进行升序排列，求最大的字典序排列
数据范围：
- $1\le K \le N \le 2 \times 10^{5}$
思路：首先无论如何，排序之后一定会使字典序变小或不变，则如果存在一个长度为K的递增区间
我们一定操作此区间，否则将操作尽可能往后放，即区间[n-k+1,n]
然后向前寻找前一个位置的值是否大于左端点，若大于说明向前移动一个位置后，字典序比移动前更小
所以直接操作移动前的区间，若向前寻找前一个位置的值小于左端点，因为[n-k]往前找满足左边值递增
且[n-k]右边最小值大于啊[n-k]才能往前找，若小于[n-k]则排序之后比之前更小，显然此区间不能取
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
constexpr int mod = 1e9 + 7;
constexpr int N = 2e5 + 9;
void solve() {
int n, k;
cin >> n >> k;
vector<int>a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int t = 1;
for (int i = 1; i < n; i++) {
if (a[i] < a[i + 1]) {
t += 1;
if (t == k) {
for (int i = 1; i <= n; i++) {
cout << a[i] << " \n"[i == n];
}
return ;
}
} else {
t = 1;
}
}
vector<int>f(n + 1);
f[n - k] = INF;
for (int i = n - k + 1; i <= n; i++) {
f[i] = min(f[i - 1], a[i]);
}
int x = n - k + 1;
for (int i = n - k; i >= 1; i--) {
if (a[i] < a[i + 1] && f[i + k - 1] > a[n - k]) {
x = i;
}
if (a[i] > a[i + 1]) {
break;
}
}
sort(a.begin() + x, a.begin() + x + k);
for (int i = 1; i <= n; i++) {
cout << a[i] << " \n"[i == n];
}
}
constexpr bool test = 1;
signed main() {
cin.tie(0)->ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int T = 1;
if (test) cin >> T;
for (int i = 1; i <= T; i++) solve();
return 0;
}
