Back to School '24 P1 - Kicking
按照题意模拟即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, k;
char c;
vector<int> sum[2][N];
vector<int> a[N];
signed main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m + 1; j++) {
sum[0][i].push_back(0);
sum[1][i].push_back(0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
a[i].push_back(c);
sum[0][i][j] = sum[0][i][j - 1] + (c == 'A');
sum[1][i][j] = sum[1][i][j - 1] + (c == 'B');
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j - 1] == '.') {
cout << ".";
}
else if (a[i][j - 1] == 'A') {
if (sum[1][i][min(j + k, m)] - sum[1][i][j - 1] > 0) {
cout << "N";
}
else cout << "Y";
}
else {
if (sum[0][i][j] - sum[0][i][max(0ll, j - k - 1)] > 0) {
cout << "N";
}
else cout << "Y";
}
}
cout << "\n";
}
return 0;
}
Back to School '24 P2 - Cheating
注意到一个重要的性质,就是 \(a_i\) 为递增序列,那么我们会发现,他改的区间一定是上一个区间后面的,模拟即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, a[N], b[N], ans[N];
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
int last = 1;
for (int i = 1; i <= n; i++) {
if (last + b[i] - 1 <= m) {
ans[last] += a[i];
ans[last + b[i]] -= a[i];
last += b[i];
if (last == m + 1) {
last = 1;
}
}
else {
ans[last] += a[i];
ans[m + 1] -= a[i];
b[i] -= (m - last + 1);
ans[1] += a[i];
ans[min(b[i] + 1, last)] -= a[i];
last = min(b[i] + 1, last);
}
}
for (int i = 1; i <= m; i++) {
ans[i] += ans[i - 1];
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << " ";
}
return 0;
}
Back to School '24 P3 - Tournament
我们可以发现,他合并答案是简直和线段树一摸一样,所以直接线段树维护即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (1 << 18) + 5;
struct node {
int maxi, ans;
void clean() {
maxi = ans = 0;
}
}tr[N * 4];
int n, p, a[N];
bool vis[N];
void build(int i, int l, int r) {
if (l == r) {
if (l == 1) {
tr[i].maxi = p, tr[i].ans = 0;
}
else tr[i].maxi = a[l - 1], tr[i].ans = 0;
return ;
}
int mid = (l + r) >> 1;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
tr[i].ans = tr[i * 2].ans + tr[i * 2 + 1].ans + (tr[i * 2].maxi - tr[i * 2 + 1].maxi) * (tr[i * 2].maxi - tr[i * 2 + 1].maxi);
tr[i].maxi = max(tr[i * 2].maxi, tr[i * 2 + 1].maxi);
}
void modify(int i, int l, int r, int p, int x) {
if (l == r) {
tr[i].maxi = x;
tr[i].ans = 0;
return ;
}
int mid = (l + r) >> 1;
if (mid >= p) modify(i * 2, l, mid, p, x);
else modify(i * 2 + 1, mid + 1, r, p, x);
tr[i].ans = tr[i * 2].ans + tr[i * 2 + 1].ans + (tr[i * 2].maxi - tr[i * 2 + 1].maxi) * (tr[i * 2].maxi - tr[i * 2 + 1].maxi);
tr[i].maxi = max(tr[i * 2].maxi, tr[i * 2 + 1].maxi);
}
signed main() {
cin >> n;
for (int i = 1; i < n; i++) {
cin >> a[i];
vis[a[i]] = true;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
p = i;
}
}
build(1, 1, n);
for (int i = 1; i <= n; i++) {
cout << tr[1].ans << " ";
if (i < n) {
modify(1, 1, n, i, a[i]);
modify(1, 1, n, i + 1, p);
}
}
return 0;
}
Back to School '24 P4 - Candidates
我们假如考虑每一种因素,他一定要满足在每个区间内是递增的,用 \(set\) 维护,做一个类似于拓扑排序的即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N], cnt[N];
vector<int> r[N], v[N], ans;
bool vis[N];
priority_queue<int, vector<int>, greater<int> > q;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
r[i].push_back(0);
}
for (int i = 1; i <= n; i++) {
for (int j = 1, c; j <= k; j++) {
cin >> c;
r[i].push_back(c);
}
}
for (int j = 1; j <= k; j++) {
for (int i = 1; i < n; i++) {
if (r[a[i]][j] < r[a[i + 1]][j]) {
cnt[j]++;
vis[i] = true;
v[i].push_back(j);
}
}
}
for (int i = 1; i <= k; i++) {
if (!cnt[i]) {
q.push(i);
}
}
while (!q.empty()) {
int cur = q.top();
q.pop();
ans.push_back(cur);
vector<int> tmp;
for (int i = 1; i < n; i++) {
if (r[a[i]][cur] > r[a[i + 1]][cur] && vis[i]) {
tmp.push_back(i);
}
}
for (auto cur : tmp) {
for (auto u : v[cur]) {
cnt[u]--;
if (!cnt[u]) {
q.push(u);
}
}
vis[cur] = false;
v[cur].clear();
}
}
for (int i = 1; i <= k; i++) {
if (cnt[i]) {
cout << "-1";
return 0;
}
}
for (auto cur : ans) {
cout << cur << " ";
}
return 0;
}
标签:20241006,cur,int,tr,long,maxi,ans
From: https://www.cnblogs.com/libohan/p/18449822