Codeforces Round 971 (Div. 4)A-G1题解

Codeforces Round 971 (Div. 4)

A

就是b - a

#include <bits/stdc++.h>
#define int long longusing namespace std;void solve()
{int a, b;cin >> a >> b;cout << b - a << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}

B

简单模拟, 逆序输出即可

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 100010;int stk[N];void solve()
{int n;cin >> n;for(int i = 1; i <= n; i ++ ){string temp;cin >> temp;stk[i] = temp.find("#");}for(int i = n; i >= 1; i -- ){cout << stk[i] + 1 << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}

C

简单模拟

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 100010;int stk[N];void solve()
{int x, y, k;cin >> x >> y >> k;int ansx = (x + k - 1) / k, ansy = (y + k - 1) / k;int ans = 0;if(ansx <= ansy){ans = ansy * 2;}else{ans = ansx * 2 - 1;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}

D

看似复杂, 实则简单模拟

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 200010;int n;
int d[N][2];void init()
{for(int i = 0; i <= n; i ++ ){d[i][0] = 0;d[i][1] = 0;}
}void solve()
{cin >> n;init();for(int i = 1; i <= n; i ++ ){int x, y;cin >> x >> y;d[x][y] ++;}int ans = 0;for(int i = 0; i <= n; i ++ ){if(i != 0 && d[i][0] && d[i - 1][1] && d[i + 1][1]){ans += min({d[i][0], d[i - 1][1], d[i + 1][1]});}if(i != 0 && d[i][1] && d[i - 1][0] && d[i + 1][0]){ans += min({d[i][1], d[i - 1][0], d[i + 1][0]});}if(d[i][0] && d[i][1]){ans += n - d[i][0] - d[i][1];}}cout << ans << endl; }signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}

E

可以分为大于 0 和小于 0 两部分, 答案是离 0 最近的那个数, 二分出最小的正数或负数对应的 i 即可

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 200010;int n, k;int ss(int k, int i)
{return (2 * k + i - 1) * i / 2 - (2 * k + n + i - 1) * (n - i) / 2;
}bool check(int x)
{return ss(k, x) <= 0;
}int b_search(int l, int r)
{while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}return l;
}void solve()
{cin >> n >> k;cout << min(abs(ss(k, temp)), abs(ss(k, temp + 1))) << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}

F

前缀和, 预处理

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 200010;int n, q, all = 0;int a[N];
int b[N];int solve2(int l, int r)
{int ll = (l + n - 1) / n - 1;l %= n;if(l == 0) l = n;int rr = (r + n - 1) / n - 1;r %= n;if(r == 0) r = n;int res = (rr - ll - 1) * b[n];res += b[ll + n] - b[ll + l - 1];res += b[rr + r] - b[rr];return res;
}void solve()
{cin >> n >> q;for(int i = 1; i <= n; i ++ ){cin >> a[i];b[i] = b[i - 1] + a[i];}for(int i = n + 1; i <= 2 * n; i ++ ){b[i] = b[i - 1] + a[i - n];}for(int i = 1; i <= q; i ++ ){int l, r;cin >> l >> r;cout << solve2(l, r) << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}

G1

滑动窗口

这里有一个非常好用的技巧, 当我们需要找一个连续的加一上升序列时, 我们在输入时可以输入a[i]后减 i, 然后找相同的数就是连续的加一上升序列

一开始没有想到用滑动窗口, 但是发现超时, 所以用滑动窗口提前处理好, 这样不需要每一次都求一遍

rbegin() 是一个迭代器, 指向最后一个数, rend() 与之相反, 指向第一个数

本题中的 multiset 与 set 的不同在于其中可以有多个相同的数

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 200010;int n, k, q;int a[N], b[N];void solve()
{map<int, int> mp;multiset<int> S;cin >> n >> k >> q;for(int i = 1; i <= n; i ++ ){cin >> a[i];a[i] -= i;}for(int i = 1; i <= k; i ++ ){if(mp.find(a[i]) != mp.end()) S.erase(S.find(mp[a[i]]));mp[a[i]] ++;S.insert(mp[a[i]]);b[i] = k -  *S.rbegin();}for(int i = k + 1; i <= n; i ++ ){S.erase(S.find(mp[a[i - k]]));mp[a[i - k]] --;S.insert(mp[a[i - k]]);if(mp.find(a[i]) != mp.end()) S.erase(S.find(mp[a[i]]));mp[a[i]] ++;S.insert(mp[a[i]]);b[i] = k -  *S.rbegin();}for(int i = 1; i <= q; i ++ ){int l, r;cin >> l >> r;cout << b[r] << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T -- ){solve();}}