A题:
输出-1,当且仅当数组大小为2,并且不递增。
如果已经递增,输出0。
否则至多三次完成操作,如果最小或最大在开头或者结尾,可证只需一次操作。
如果两者出现在中间,可证只需二次操作。
不然,要求三次操作。
#include <bits/stdc++.h> using namespace std; int main() { int tt; cin >> tt; while (tt -- ) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i ++ ) cin >> a[i]; if (is_sorted(a.begin(), a.end())) cout << 0 << endl; else { if (n == 2) cout << -1 << endl; else { auto [mn, mx] = minmax_element(a.begin(), a.end()); if (*mn == a[0] || *mx == a[n - 1]) cout << 1 << endl; else { bool ok = false; for (int i = 1; i < n; i ++ ) { if (a[i] == *mx) ok = true; } for (int i = 0; i < n - 1; i ++ ) { if (a[i] == *mn) ok = true; } if (ok) cout << 2 << endl; else { cout << 3 << endl; } } } } } return 0; }
b题:
题目要求的是变换最少使得单增,转一下思路。
找到最长上升子序列。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> dp(n + 1, 1e9); int len = 0; for (int i = 1; i <= n; i ++ ) { int x; cin >> x; if (len == 0 || x >= dp[len]) { dp[++ len] = x; }else { *upper_bound(dp.begin() + 1, dp.end(), x) = x; } } cout << n - len << endl; return 0; }
c题:
先处理[1, r]
后面这就可以当作[1, l - 1]放到dp里了
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { string s; cin >> s; int n = s.size(); s = " " + s; int c0 = 0, c1 = 0, c2 = 0; int dp[2][2][2]{}; dp[0][0][0] = 1; ll ans = 0; for (int i = 1; i <= n; i ++ ) { if (s[i] == 'j') { c0 ++; }else if (s[i] == 'q') { c1 ++; c2 += c0; } c0 %= 2, c1 %= 2, c2 %= 2; for (int a = 0; a < 2; a ++ ) { for (int b = 0; b < 2; b ++ ) { for (int c = 0; c < 2; c ++ ) { int t = (c2 - c + 2) % 2; t -= a * (c1 - b + 2) % 2; t = (t % 2 + 2) % 2; if (t == 0) ans += dp[a][b][c]; } } } dp[c0][c1][c2] ++; } cout << ans << endl; return 0; }
d题:
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int n; cin >> n; ll cnt0, cnt1 = 0; ll ans = 0; for (int i = 1; i <= n; i ++ ) { int x; cin >> x; if (x == 0) continue; if (x > 0) { if (cnt0 >= x) { cnt0 -= x; cnt1 += x; }else { ans += x - cnt0; cnt0 = 0; cnt1 += x; } }else { x = -x; if (cnt1 >= x) { cnt1 -= x; cnt0 += x; }else { ans += x - cnt1; cnt1 = 0; cnt0 += x; } } } cout << ans << endl; return 0; }
e题:
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 998244353; const int N = 3e5 + 9; ll f[N]; ll qmi(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; } ll inv(ll x) { return qmi(x, mod - 2); } void iniv() { f[0] = f[1] = 1; for (int i = 2; i <= 3e5; i ++ ) { f[i] = f[i - 1] * i % mod; } } ll C(ll a, ll b) { return f[a] * inv(f[b]) % mod * inv(f[a - b]) % mod; } int main() { iniv(); int n; cin >> n; ll ans = 1; for (int i = 1; i <= n / 3; i ++ ) { int a[3]{}; int minv = 1e9; for (int j = 0; j < 3; j ++ ) { cin >> a[j]; minv = min(minv, a[j]); } int cnt = 0; for (int j = 0; j < 3; j ++ ) { if (minv == a[j]) cnt ++; } ans = ans * cnt % mod; } ans = ans * C(n / 3, n / 6) % mod; cout << ans << endl; return 0; }
g题:
#include <bits/stdc++.h> using namespace std; int main() { int tt; cin >> tt; while (tt -- ) { long long n; cin >> n; if (n == 1 || n == 5 || n == 6) cout << "WIN\n"; else cout << "LOSE\n"; } return 0; }
全部评论
(0) 回帖