- A↵
↵
It is easy to figure out that any $s[i]$ and $s[i - 1]$ which $i$ is even ($1$ index) must have same ammount of 'a' and 'b's. So just change it greedily.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
int n; cin >> n;↵
string s; cin >> s;↵
int ans = 0;↵
string st = "";↵
for(int i = 1; i < s.size(); i += 2) {↵
int ans1 = (s[i - 1] != 'a') + (s[i] != 'b');↵
int ans2 = (s[i - 1] != 'b') + (s[i] != 'a');↵
if(ans1 < ans2) ans += ans1, st += "ab";↵
else ans += ans2, st += "ba";↵
}↵
cout << ans << endl << st;↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
↵
- B↵
↵
We don't need to consider "$+1$", because it is a constant. Without it, we can sort the array undecreasing and just implement it one by one. This greedy algorithm can be proved with rearrangement inequality.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int n;↵
int main() {↵
cin >> n;↵
vector < pair < int , int > > v(n);↵
for(int i = 0; i < n; i++) cin >> v[i].first, v[i].second = i + 1;↵
sort(v.begin(), v.end());↵
long long cst = 0, al = 0;↵
for(int i = n - 1; i >= 0; i--) {↵
cst += al * v[i].first + 1;↵
al++;↵
}↵
cout << cst << endl;↵
for(int i = n - 1; i >= 0; i--) cout << v[i].second << " ";↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
- C↵
↵
You can solve this problem intuitively, with checking each "uncovered" point by trying $8$ directions of $(x1, y1)$, which x1 is in x[1...6], y1 is in y[1...6].↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
const int N = 10, n = 6;↵
pair <int, int> a[N];↵
↵
const double dx[8] = {1, -0.5, 0, 0, 0.5, -0.5, 0.5, -0.5};↵
const double dy[8] = {0, 0, 0.5, -0.5, 0.5, 0.5, -0.5, -0.5};↵
↵
bool cov(double x, double y, double aa, double bb, double cc, double dd) {↵
return aa <= x && x <= cc && bb <= y && y <= dd; ↵
}↵
int main() {↵
for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
int x = a[i].first, y = a[j].second;↵
for(int d = 0; d < 8; d++) {↵
double fx = x + dx[d], fy = y + dy[d];↵
if(cov(fx, fy, a[1].first, a[1].second, a[2].first, a[2].second)↵
&& !cov(fx, fy, a[3].first, a[3].second, a[4].first, a[4].second)↵
&& !cov(fx, fy, a[5].first, a[5].second, a[6].first, a[6].second)) {↵
cout << "YES\n";↵
return 0;↵
}↵
}↵
}↵
}↵
cout << "NO\n";↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
- D↵
↵
It is easy to figure that $z$ must be divided by $abs(a[i] - a[i - 1])$. So $z$ will become maximum if we take $z$ as its greatest common divisior, and y will become minimum.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
typedef long long ll;↵
using namespace std;↵
↵
const int N = 200000 + 10;↵
int n, a[N];↵
int main(){↵
cin >> n;↵
int now = 0;↵
for(int i = 1; i <= n; i++) {↵
cin >> a[i];↵
if(i > 1) now = __gcd(now, abs(a[i] - a[i - 1]));↵
}↵
int mx = *max_element(a + 1, a + n + 1);↵
long long ans = 0;↵
for(int i = 1; i <= n; i++) {↵
ans += 1LL * (mx - a[i]) / now;↵
}↵
cout << ans << " " << now << endl;↵
return 0; ↵
}↵
```↵
</spoiler>↵
↵
- E↵
↵
We can do two binary search and solve the problem easily, and check answer with simple math formula.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
// 1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,↵
↵
int num(int x) {↵
int cntt = 0;↵
while(x) cntt ++, x /= 10;↵
return cntt;↵
}↵
↵
long long n;↵
↵
↵
long long pow(int x, int t) {↵
long long res = 1;↵
while(t--) res *= x;↵
return res;↵
}↵
long long check2(int x) {↵
int d = num(x);↵
return 1LL * (x + 1) * d - 1LL * ((pow(10, d) - 1) / 9);↵
}↵
↵
long long check1(int x) {↵
if(x == 0) return 0; ↵
↵
for(int dg = 0; dg <= 9; dg++) {↵
long long bd1 = pow(10, dg), bd2 = pow(10, dg + 1) - 1;↵
if(bd1 <= x && x <= bd2) return check1(bd1 - 1) + 1LL * (check2(bd1) + check2(x)) * (x - bd1 + 1) / 2;↵
}↵
}↵
int main() {↵
int q; cin >> q;↵
while(q--) {↵
cin >> n;↵
if(n == 1) {↵
puts("1");↵
continue;↵
}↵
int l = 1, r = 1000000000, ans = 0;↵
while(l <= r) {↵
int mid = (l + r) >> 1;↵
long long ans1 = check1(mid);↵
if(ans1 >= n) ans = mid, r = mid - 1;↵
else l = mid + 1;↵
}↵
ans--;↵
long long ft = check1(ans);↵
ans++;↵
l = 1, r = ans;↵
ans = 0;↵
while(l <= r) {↵
int mid = (l + r) >> 1;↵
long long ans1 = check2(mid);↵
if(ft + ans1 >= n) ans = mid, r = mid - 1;↵
else l = mid + 1;↵
}↵
↵
if(ans == 1) {↵
puts("1");↵
continue;↵
}↵
ans--;↵
long long final = ft + check2(ans);↵
string s = ""; ans++;↵
long long cop = ans;↵
while(cop) s.push_back(cop % 10 + '0'), cop /= 10;↵
reverse(s.begin(), s.end());↵
cout << s[n - final - 1] << endl;↵
}↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
- F↵
↵
We can construct such DP method: ↵
↵
<spoiler summary="DP">↵
Let $DP(i) = $ The minimum cost we need to connect all room in $[1, i]$ to internet.↵
For each j between $[i-k, i]$, if $s[j] = '1'$, we can update $DP(i)$ using $DP(j - k) + j$.↵
</spoiler>↵
↵
We can maintain it using simple data structure, such as segment tree. And the problem can be solved. ↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
#define ls(p) ((p) << 1)↵
#define rs(p) ((p) << 1 | 1)↵
using namespace std;↵
typedef long long ll;↵
const int N = 200000 + 5;↵
int n, k;↵
char s[N];↵
ll dp[N];↵
↵
struct seg {↵
ll mx[N << 2];↵
seg() {↵
memset(mx, 0x3f, sizeof(mx));↵
}↵
void upd(int p, int l, int r, int v, ll c) {↵
if(l == r) {mx[p] = c; return ;}↵
int mid = (l + r) >> 1;↵
v <= mid ? upd(ls(p), l, mid, v, c) : upd(rs(p), mid + 1, r, v, c);↵
mx[p] = min(mx[ls(p)], mx[rs(p)]);↵
}↵
long long qry(int p, int l, int r, int ql, int qr) {↵
if(ql <= l && r <= qr) return mx[p];↵
int mid = (l + r) >> 1;↵
long long res = 0x3f3f3f3f3f3f3f3fll;↵
if(ql <= mid) res = min(res, qry(ls(p), l, mid, ql, qr));↵
if(qr > mid) res = min(res, qry(rs(p), mid + 1, r, ql, qr));↵
return res;↵
}↵
}t1, t2;↵
int main() {↵
cin >> n >> k >> (s + 1);↵
dp[0] = 0;↵
t2.upd(1, 0, n, 0, 0);↵
for(int i = 1; i <= n; i++) {↵
dp[i] = dp[i - 1] + i;↵
if(s[i] == '1') dp[i] = min(dp[i], dp[max(i - k - 1, 0)] + i);↵
if(max(i - k, 1) <= max(i - 1, 1) && max(i - 1, 1) < i)↵
dp[i] = min(dp[i], t1.qry(1, 1, n, max(i - k, 1), max(i - 1, 1)));↵
if(s[i] == '1') {↵
t1.upd(1, 1, n, i, t2.qry(1, 0, n, max(i - k - 1, 0), max(i - 1, 0)) + i);↵
}↵
else t1.upd(1, 1, n, i, 0x3f3f3f3f3f3f3f3fll);↵
t2.upd(1, 0, n, i, dp[i]);↵
}↵
↵
cout << dp[n] << endl;↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
↵
It is easy to figure out that any $s[i]$ and $s[i - 1]$ which $i$ is even ($1$ index) must have same ammount of 'a' and 'b's. So just change it greedily.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
int n; cin >> n;↵
string s; cin >> s;↵
int ans = 0;↵
string st = "";↵
for(int i = 1; i < s.size(); i += 2) {↵
int ans1 = (s[i - 1] != 'a') + (s[i] != 'b');↵
int ans2 = (s[i - 1] != 'b') + (s[i] != 'a');↵
if(ans1 < ans2) ans += ans1, st += "ab";↵
else ans += ans2, st += "ba";↵
}↵
cout << ans << endl << st;↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
↵
- B↵
↵
We don't need to consider "$+1$", because it is a constant. Without it, we can sort the array undecreasing and just implement it one by one. This greedy algorithm can be proved with rearrangement inequality.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int n;↵
int main() {↵
cin >> n;↵
vector < pair < int , int > > v(n);↵
for(int i = 0; i < n; i++) cin >> v[i].first, v[i].second = i + 1;↵
sort(v.begin(), v.end());↵
long long cst = 0, al = 0;↵
for(int i = n - 1; i >= 0; i--) {↵
cst += al * v[i].first + 1;↵
al++;↵
}↵
cout << cst << endl;↵
for(int i = n - 1; i >= 0; i--) cout << v[i].second << " ";↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
- C↵
↵
You can solve this problem intuitively, with checking each "uncovered" point by trying $8$ directions of $(x1, y1)$, which x1 is in x[1...6], y1 is in y[1...6].↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
const int N = 10, n = 6;↵
pair <int, int> a[N];↵
↵
const double dx[8] = {1, -0.5, 0, 0, 0.5, -0.5, 0.5, -0.5};↵
const double dy[8] = {0, 0, 0.5, -0.5, 0.5, 0.5, -0.5, -0.5};↵
↵
bool cov(double x, double y, double aa, double bb, double cc, double dd) {↵
return aa <= x && x <= cc && bb <= y && y <= dd; ↵
}↵
int main() {↵
for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
int x = a[i].first, y = a[j].second;↵
for(int d = 0; d < 8; d++) {↵
double fx = x + dx[d], fy = y + dy[d];↵
if(cov(fx, fy, a[1].first, a[1].second, a[2].first, a[2].second)↵
&& !cov(fx, fy, a[3].first, a[3].second, a[4].first, a[4].second)↵
&& !cov(fx, fy, a[5].first, a[5].second, a[6].first, a[6].second)) {↵
cout << "YES\n";↵
return 0;↵
}↵
}↵
}↵
}↵
cout << "NO\n";↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
- D↵
↵
It is easy to figure that $z$ must be divided by $abs(a[i] - a[i - 1])$. So $z$ will become maximum if we take $z$ as its greatest common divisior, and y will become minimum.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
typedef long long ll;↵
using namespace std;↵
↵
const int N = 200000 + 10;↵
int n, a[N];↵
int main(){↵
cin >> n;↵
int now = 0;↵
for(int i = 1; i <= n; i++) {↵
cin >> a[i];↵
if(i > 1) now = __gcd(now, abs(a[i] - a[i - 1]));↵
}↵
int mx = *max_element(a + 1, a + n + 1);↵
long long ans = 0;↵
for(int i = 1; i <= n; i++) {↵
ans += 1LL * (mx - a[i]) / now;↵
}↵
cout << ans << " " << now << endl;↵
return 0; ↵
}↵
```↵
</spoiler>↵
↵
- E↵
↵
We can do two binary search and solve the problem easily, and check answer with simple math formula.↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
// 1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,↵
↵
int num(int x) {↵
int cntt = 0;↵
while(x) cntt ++, x /= 10;↵
return cntt;↵
}↵
↵
long long n;↵
↵
↵
long long pow(int x, int t) {↵
long long res = 1;↵
while(t--) res *= x;↵
return res;↵
}↵
long long check2(int x) {↵
int d = num(x);↵
return 1LL * (x + 1) * d - 1LL * ((pow(10, d) - 1) / 9);↵
}↵
↵
long long check1(int x) {↵
if(x == 0) return 0; ↵
↵
for(int dg = 0; dg <= 9; dg++) {↵
long long bd1 = pow(10, dg), bd2 = pow(10, dg + 1) - 1;↵
if(bd1 <= x && x <= bd2) return check1(bd1 - 1) + 1LL * (check2(bd1) + check2(x)) * (x - bd1 + 1) / 2;↵
}↵
}↵
int main() {↵
int q; cin >> q;↵
while(q--) {↵
cin >> n;↵
if(n == 1) {↵
puts("1");↵
continue;↵
}↵
int l = 1, r = 1000000000, ans = 0;↵
while(l <= r) {↵
int mid = (l + r) >> 1;↵
long long ans1 = check1(mid);↵
if(ans1 >= n) ans = mid, r = mid - 1;↵
else l = mid + 1;↵
}↵
ans--;↵
long long ft = check1(ans);↵
ans++;↵
l = 1, r = ans;↵
ans = 0;↵
while(l <= r) {↵
int mid = (l + r) >> 1;↵
long long ans1 = check2(mid);↵
if(ft + ans1 >= n) ans = mid, r = mid - 1;↵
else l = mid + 1;↵
}↵
↵
if(ans == 1) {↵
puts("1");↵
continue;↵
}↵
ans--;↵
long long final = ft + check2(ans);↵
string s = ""; ans++;↵
long long cop = ans;↵
while(cop) s.push_back(cop % 10 + '0'), cop /= 10;↵
reverse(s.begin(), s.end());↵
cout << s[n - final - 1] << endl;↵
}↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
- F↵
↵
We can construct such DP method: ↵
↵
<spoiler summary="DP">↵
Let $DP(i) = $ The minimum cost we need to connect all room in $[1, i]$ to internet.↵
For each j between $[i-k, i]$, if $s[j] = '1'$, we can update $DP(i)$ using $DP(j - k) + j$.↵
</spoiler>↵
↵
We can maintain it using simple data structure, such as segment tree. And the problem can be solved. ↵
↵
<spoiler summary="Solution">↵
```cpp↵
#include <bits/stdc++.h>↵
#define ls(p) ((p) << 1)↵
#define rs(p) ((p) << 1 | 1)↵
using namespace std;↵
typedef long long ll;↵
const int N = 200000 + 5;↵
int n, k;↵
char s[N];↵
ll dp[N];↵
↵
struct seg {↵
ll mx[N << 2];↵
seg() {↵
memset(mx, 0x3f, sizeof(mx));↵
}↵
void upd(int p, int l, int r, int v, ll c) {↵
if(l == r) {mx[p] = c; return ;}↵
int mid = (l + r) >> 1;↵
v <= mid ? upd(ls(p), l, mid, v, c) : upd(rs(p), mid + 1, r, v, c);↵
mx[p] = min(mx[ls(p)], mx[rs(p)]);↵
}↵
long long qry(int p, int l, int r, int ql, int qr) {↵
if(ql <= l && r <= qr) return mx[p];↵
int mid = (l + r) >> 1;↵
long long res = 0x3f3f3f3f3f3f3f3fll;↵
if(ql <= mid) res = min(res, qry(ls(p), l, mid, ql, qr));↵
if(qr > mid) res = min(res, qry(rs(p), mid + 1, r, ql, qr));↵
return res;↵
}↵
}t1, t2;↵
int main() {↵
cin >> n >> k >> (s + 1);↵
dp[0] = 0;↵
t2.upd(1, 0, n, 0, 0);↵
for(int i = 1; i <= n; i++) {↵
dp[i] = dp[i - 1] + i;↵
if(s[i] == '1') dp[i] = min(dp[i], dp[max(i - k - 1, 0)] + i);↵
if(max(i - k, 1) <= max(i - 1, 1) && max(i - 1, 1) < i)↵
dp[i] = min(dp[i], t1.qry(1, 1, n, max(i - k, 1), max(i - 1, 1)));↵
if(s[i] == '1') {↵
t1.upd(1, 1, n, i, t2.qry(1, 0, n, max(i - k - 1, 0), max(i - 1, 0)) + i);↵
}↵
else t1.upd(1, 1, n, i, 0x3f3f3f3f3f3f3f3fll);↵
t2.upd(1, 0, n, i, dp[i]);↵
}↵
↵
cout << dp[n] << endl;↵
return 0; ↵
} ↵
```↵
</spoiler>↵
↵
