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(0); cin.tie(0)
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 = 1e5 + 5, mod = 998244353;
ll n, m, _, k;
ll a, b;
int qpow(int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = (ll)a * a % mod)
if (b & 1) ans = (ll)ans * a % mod;
return ans;
}
int main() {
IO;
int c100 = qpow(100, mod - 2);
for (cin >> _; _; --_) {
cin >> n >> a >> b;
int c = __gcd(a, (ll)100);
a = a / c * qpow(100 / c, mod - 2) % mod;
c = __gcd(b, (ll)100);
b = b / c * qpow(100 / c, mod - 2) % mod;
c = __gcd(n, a);
ll d = (n / c * qpow(a / c, mod - 2) - 1) % mod;
m = ((n - d * b) % mod + mod) % mod;
cout << m << '
';
}
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(0); cin.tie(0)
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 = 1e5 + 5;
int n, m, _, k;
char s[N], t[N];
int w, x, y, z;
int res[N];
void work(int k, int a) {
res[k] = w + x + 1 + x + z;
if (!a) {
int c = 1e9, d = 0;
rep(i, k + 1, n) {
if (s[i] == t[i]) ++d;
else --d;
if (s[i] != '1') break;
else {
if (t[i] == '1') c = min(d, c);
else c = min(d + 2, c);
}
if (i == n) ++d;
}
if (k == n) ++d;
res[k] += min(d, c);
}
}
int main() {
IO;
for (cin >> _; _; --_) {
cin >> n >> s + 1 >> t + 1;
w = x = y = z = 0;
rep(i, 1, n) {
if (t[i] != s[i]) work(i, t[i] - '0');
else res[i] = 2e5;
w += (t[i] == '0') && (s[i] == '0');
x += (t[i] == '1') && (s[i] == '0');
y += (t[i] == '0') && (s[i] == '1');
z += (t[i] == '1') && (s[i] == '1');
}
m = x + y, w = 0;
per(i, n, 1) {
m = min(m, res[i] + w);
w += (s[i] != t[i]);
}
cout << m << '
';
}
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 = 1e5 + 5;
int n, m, _, k;
ll a[N];
ll worka() {
int l = k, r = n - m + k - 1, cur = n - m + k;
ll ans = a[cur];
deque<bool> s(k - 1);
rep(i, k, m) s.pb(1);
while (l <= r) {
bool c = s.front(); s.pop_front();
if (!c) s.pb(0), ++l, ans += a[cur];
else s.pb(1), cur = r--, ans += a[cur];
}
return ans;
}
ll workb() {
int l = k + 1, r = n - m + k, cur = k;
ll ans = a[cur];
deque<bool> s(m - k);
rep(i, 1, k) s.pb(1);
while (l <= r) {
bool c = s.front(); s.pop_front();
if (!c) s.pb(0), --r, ans += a[cur];
else s.pb(1), cur = l++, ans += a[cur];
}
return ans;
}
int main() {
IO;
for (cin >> _; _; --_) {
cin >> n >> m >> k; k = m - k + 1;
rep(i, 1, n) cin >> a[i];
sort(a + 1, a + 1 + n);
cout << worka() << ' ' << workb() << '
';
}
return 0;
}