Educational Codeforces Round 152 A~D
A
#include <bits/stdc++.h> #define endl '\n' #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) using namespace std; typedef pair<int, int> PII; const int N = 2e5 + 10; const int MOD = 1e9 + 7; int T; void solve() { int b, c, h; cin >> b >> c >> h; if (c + h < b - 1) { cout << 2 * (c + h) + 1 << endl; } if (c + h >= b - 1) { cout << 2 * (b - 1) + 1 << endl; } } signed main() { ios; int T = 1; cin >> T; while (T--) { solve(); } }
B
#include <bits/stdc++.h> #define endl '\n' #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) using namespace std; #define int long long typedef pair<int, int> PII; #define int long long const int N = 3e5 + 10; const int MOD = 1e9 + 7; int T; int n, k; #define int long long typedef pair<int, int> PII; bool cmp(PII a, PII b) { if (a.first != b.first) return a.first > b.first; else return a.second < b.second; } void solve() { cin >> n >> k; vector<PII> a; for (int i = 1; i <= n; i++) { int x; cin >> x; if (x > k) { if (x % k == 0) a.push_back({k, i}); else a.push_back({x % k, i}); } else a.push_back({x, i}); } sort(a.begin(), a.end(), cmp); for (auto x : a) { cout << x.second << ' '; } // for (int i = 1; i <= n; i++) // { // cout << a[i].second << ' '; // } cout << endl; } signed main() { ios; int T = 1; cin >> T; while (T--) { solve(); } }
C
#include <bits/stdc++.h> #define endl '\n' #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) using namespace std; typedef pair<int, int> PII; const int N = 2e5 + 10; const int MOD = 1e9 + 7; int T; int n, m; char str[N]; int l[N], r[N]; void solve() { cin >> n >> m >> str + 1; int last = 0; for (int i = 1; i <= n; i++) { if (str[i] == '0') last = i; l[i] = last; } last = n + 1; for (int i = n; i; i--) { if (str[i] == '1') last = i; r[i] = last; } set<PII> S; while (m--) { int x, y; cin >> x >> y; if (r[x] > y || l[y] < x) //这是每个询问右端点前面最近的0都在区间左边(区间里全为1)或者最近离左端点后面的1在区间右边(区间全为0)这种情况不会改变区间,也就是原来状态 S.insert({0, 0}); else { x = r[x], y = l[y]; if (x > y) S.insert({0, 0}); //当为类似000111情况时,排序也没有变化序列,仍为原序列 else S.insert({x, y}); //每一个区间的排序都和l[y]和r[x]的组合 一 一对应 } } cout << S.size() << endl; // set的size就是我们排序的所有的 } int main() { ios; T = 1; cin >> T; while (T--) solve(); return 0; }
D
先将2的向两遍扩展再将1向一边扩展(尽量向有1的地方扩展)每一次扩展完成需要一代价,剩下的只能花费代价
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int a[N], vis[N]; // vis数组判断是否被扩展过 inline void solve() { int n, ans = 0; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { if (a[i] == 0) continue; int j = i, flag = 0; while (j <= n && a[j] != 0) { if (a[j] == 2) flag = 1; j++; } if (flag) { vis[i - 1] = vis[j] = 1; //当有数为2时,我们将第一个2的左边和类似21121这类不含0的连续串的右边都扩展; } else { if (i - 1 >= 1 && !vis[i - 1]) //当该数为1时,若前面有未扩展过的1,我们向前面的1扩展,否则我们向后面扩展 vis[i - 1] = 1; else vis[j] = 1; } ans++; i = j - 1; } for (int i = 1; i <= n; i++) if (a[i] == 0 && !vis[i]) ans++; cout << ans << endl; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T = 1; // cin >> T; while (T--) solve(); }