A
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 2e5 + 5;
int n, m, _, k;
ll a[N];
int main() {
IO;
for (cin >> _; _; --_) {
cin >> n >> a[1];
bool f = 1;
rep (i, 2, n) {
cin >> a[i];
if (a[i] != a[i - 1]) f = 0;
}
if (n == 1) { cout << 1 << '
'; continue; }
else if (n == 2) { cout << (a[1] == a[2] ? 2 : 1) << '
'; continue; }
else if (!f) cout << 1 << '
';
else cout << n << '
';
}
return 0;
}
B
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 2e5 + 5;
int n, m, _, k;
ll a[N], c;
int main() {
IO;
for (cin >> _; _; --_) {
cin >> n >> c >> a[1];
int mx = 1, mi = 1;
rep (i, 2, n) {
cin >> a[i];
if (a[i] > a[mx]) mx = i;
if (a[i] < a[mi]) mi = i;
}
if (c & 1) {
rep (i, 1, n) cout << a[mx] - a[i] << ' ';
cout << '
';
} else {
rep (i, 1, n) cout << a[i] - a[mi] << ' ';
cout << '
';
}
}
return 0;
}
C
记录上次一增加了多少, 可以无缝衔接给下次, 贪心
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 2e5 + 5;
int n, m, _, k;
ll a[N];
int main() {
IO;
for (cin >> _; _; --_) {
cin >> n >> a[1];
ll mx = a[1], m = 0, ans = 0;
rep (i, 2, n) {
cin >> a[i];
if (a[i] > mx) mx = a[i], m = 0;
else if (a[i] == mx) m = 0;
else {
ll cur = mx - a[i] - m;
if (cur > 0) ans += cur, m += cur;
else m = mx - a[i];
}
}
cout << ans << '
';
}
return 0;
}
D
发现连续两个都是合法的, 所以对于 三个连续的 必须改一次
肯定是改连续的第三个字母啦
1.对于全是一种字母的, 每3次改一次, 对于最后多出来的 1 或 2个再改一次就好
2.混合的, 我们断环, 当然是从 s[i] != s[i - 1] 处断环, 使得字母每段都是连续的
还是每3次改一次, 但是对于每段多出来的 1 或 2个, 比如 RRR RR L 发现由于余出的 RR 左边变成了 L, 并不用修改 (相当于 RRR -> RRL, 已经被改好了)
即, 每段长度 / 3即可
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 2e5 + 5;
int n, m, _, k;
string s;
int main() {
IO;
for (cin >> _; _; --_) {
cin >> n >> s;
int f = -1;
rep (i, 1, n - 1) {
s += s[i - 1];
if (s[i] != s[i - 1]) {
f = i;
break;
}
}
if (f == -1) cout << n / 3 + (n % 3 != 0) << '
';
else {
int ans = 0, cnt = 1;
rep (i, f + 1, f + n - 1)
if (s[i] == s[i - 1]) ++cnt;
else ans += cnt / 3, cnt = 1;
cout << ans + cnt / 3 << '
';
}
}
return 0;
}
E
每个位置无非是从 上和左走来, 所以确保 次对角线 上的每个点的 数值范围 不相交 即可
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 25;
int n, m, _, k;
ll a[N][N];
PII ans[N << 1];
PLL b[N][N];
int main() {
IO; cin >> n;
rep (k, 1, (n - 1) << 1) {
ll cur = -1;
rep (i, max(0, k - n + 1), min(k, n - 1)) {
int j = k - i;
ll mn = 1e18, mx = -1e18;
if (i) mn = min(mn, b[i - 1][j].fi), mx = max(mx, b[i - 1][j].se);
if (j) mn = min(mn, b[i][j - 1].fi), mx = max(mx, b[i][j - 1].se);
b[i][j] = {cur + 1, cur += 1 + mx - mn};
a[i][j] = b[i][j].fi - mn;
}
}
rep (i, 0, n - 1) {
rep (j, 0, n - 1) cout << a[i][j] << ' ';
cout << '
';
}
cout.flush();
cin >> m;
rep (i, 1, m) {
ll k; cin >> k;
int x = n - 1, y = n - 1;
per (i, n - 1 << 1, 0) {
ans[i] = {x + 1, y + 1};
k -= a[x][y];
if (x && k >= b[x - 1][y].fi && k <= b[x - 1][y].se) --x;
else --y;
}
rep (i, 0, n - 1 << 1) cout << ans[i].fi << ' ' << ans[i].se << '
';
cout << '
';
cout.flush();
}
return 0;
}
F
给的序列递增, 只有在 (a_1, a_1 + 1, ..., a_1 + n - 1) 的情况下, 泥土不在移动
只要高层泥土能移动, 必然顺着下滑, 故, 泥土最终会使得, 原序列变为, (a_1 + x, a_1 + x + 1, ..., a_1 + x + m - 1, a_1 + x + m - 1, a_{ m + 1}, .. a_n)
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 1e6 + 5;
int n, m, _, k;
ll a[N];
int main() {
IO;
cin >> n >> a[1]; ll sum = 0;
rep (i, 2, n) cin >> a[i], sum += a[i] - i + 1 - a[1];
ll x = sum / n, y = sum % n;
rep (i, 1, n) cout << a[1] + x + (y > 0) + i - 1 << ' ', --y;
cout << '
';
return 0;
}