签到。
签到
由于\(n,m\)很小，直接暴力枚举判断即可。
Code
#include <bits/stdc++.h>
#define MP make_pair
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll n, a, b;
int T;
char s[N];
ll dp[N][2];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
cin >> n >> a >> b;
cin >> s;
for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = INF;
dp[0][0] = b;
for(int i = 1; i <= n; i++) {
if(s[i - 1] == '1' || s[i] == '1') dp[i][1] = min(dp[i - 1][0] + 2 * (a + b), dp[i - 1][1] + a + 2 * b);
else {
dp[i][0] = min(dp[i - 1][1] + 2 * a + b, dp[i - 1][0] + a + b);
dp[i][1] = min(dp[i - 1][1] + a + 2 * b, dp[i - 1][0] + 2 * (a + b));
}
}
cout << dp[n][0] << '\n';
}
return 0;
}题意：
给出\(n\)个二元组\((a_i,b_i)\)，定义一个坏的序列为：序列中按第一关键字或者按第二关键字是非递减的。
相反，好的序列的定义就与之相反。
现在问有多少种打乱方式，能够得到好的序列。
思路：
注意还有特殊情况的判断：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5 + 5, MOD = 998244353;
int n;
pii p[N];
ll fac[N];
ll gao1() {
ll res = 1;
for(int i = 1, j; i <= n; i = j) {
for(j = i; j <= n + 1; j++) {
if(p[i].fi != p[j].fi) break;
}
int cnt = 1;
for(int k = i + 1; k < j; k++) {
if(p[k].se == p[k - 1].se) ++cnt;
else {
res = res * fac[cnt] % MOD;
cnt = 1;
}
}
res = res * fac[cnt] % MOD;
}
return res;
}
ll gao2() {
ll res = 1;
for(int i = 1, j; i <= n; i = j) {
for(j = i; j <= n + 1; j++) {
if(p[i].se != p[j].se) break;
}
int cnt = 1;
for(int k = i + 1; k < j; k++) {
if(p[k].fi == p[k - 1].fi) ++cnt;
else {
res = res * fac[cnt] % MOD;
cnt = 1;
}
}
res = res * fac[cnt] % MOD;
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> p[i].fi >> p[i].se;
}
sort(p + 1, p + n + 1);
fac[0] = 1;
for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
ll ans = fac[n];
ll sum1 = 1, sum2 = 1;
for(int i = 1, j; i <= n; i = j) {
for(j = i; j <= n + 1; j++) {
if(p[i].fi != p[j].fi) break;
}
sum1 = sum1 * fac[j - i] % MOD;
}
sort(p + 1, p + n + 1, [&](pii A, pii B) {
return A.se < B.se;
});
for(int i = 1, j; i <= n; i = j) {
for(j = i; j <= n + 1; j++) {
if(p[i].se != p[j].se) break;
}
sum2 = sum2 * fac[j - i] % MOD;
}
ans -= sum1 + sum2;
ans %= MOD; if(ans < 0) ans += MOD;
bool f = 1;
for(int i = 2; i <= n; i++) {
if(p[i].fi < p[i - 1].fi) f = 0;
}
if(f) ans += gao1();
else {
f = 1;
sort(p + 1, p + n + 1);
for(int i = 2; i <= n; i++) {
if(p[i].se < p[i - 1].se) f = 0;
}
if(f) ans += gao2();
}
cout << ans % MOD;
return 0;
}题意：
交互题。
先有一个数大小不超过\(2^{14}-1\)，给你两次机会，每次询问100个数，对方会告诉你这个数与从100个中随机一个数的异或值。注意所有询问的数都不能重复。
最后输出此答案。
思路：
设答案为\(ans\)。
题意：
现在数轴上有\(500000\)个位置，先有两个操作：
有\(500000\)次询问，对每次\(2\)操作输出答案。
思路：
详见代码：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 500005, E = 750;
int q;
int pos[E][E]; // % x = y
int a[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> q;
while(q--) {
int op, x, y; cin >> op >> x >> y;
if(op == 1) {
a[x] += y;
for(int i = 1; i < E; i++) {
pos[i][x % i] += y;
}
} else {
if(y < 0) y += x;
if(x < E) {
cout << pos[x][y] << '\n';
} else {
int ans = 0;
for(int i = y; i < N; i += x) ans += a[i];
cout << ans << '\n';
}
}
}
return 0;
}先有两种操作：
同时有多组询问，每组询问如：\("i\ t"\)的格式，表示在第
Educational Codeforces Round 71 (Rated for Div. 2)
原文：https://www.cnblogs.com/heyuhhh/p/11440797.html