A. Yellow Cards
细心点即可。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int a1, a2, k1, k2;
int n;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> a1 >> a2 >> k1 >> k2;
cin >> n;
int t = (k1 - 1) * a1 + (k2 - 1) * a2;
int Min = max(0, n - t);
int Max = 0;
if(k1 > k2) {
int out = min(n / k2, a2);
n -= out * k2;
Max = out;
if(n >= k1) {
Max += min(n / k1, a1);
}
} else {
int out = min(n / k1, a1);
n -= out * k1;
Max = out;
if(n >= k2) {
Max += min(n / k2, a2);
}
}
cout << Min << ' ' << Max;
return 0;
}
B. The Number of Products
题意：
给出序列(a_1,a_2,cdots,a_n,a_i
ot ={0})，分别计算：
- ([l,r])的对数，满足(a_lcdot a_{l+1}cdot cdots cdot a_n>0)；
- ([l,r])的对数，满足(a_lcdot a_{l+1}cdot cdots cdot a_n<0)；
思路：
- 显然最终结果与(a_i)的正负有关。
- 我们将负数变为(1)，正数变为(0)，那么我们可以看作求区间和为奇数/偶数的区间个数。
- 维护一个前缀和，再拿个桶统计个数即可。
详见代码：
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n;
int a[N], sum[N];
ll cnt[2], ans[2];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] > 0) a[i] = 0;
else a[i] = 1;
}
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i];
}
for(int i = 1; i <= n; i++) sum[i] %= 2;
++cnt[0];
for(int i = 1; i <= n; i++) {
if(sum[i]) {
ans[0] += cnt[1];
ans[1] += cnt[0];
} else {
ans[0] += cnt[0];
ans[1] += cnt[1];
}
++cnt[sum[i]];
}
cout << ans[1] << ' ' << ans[0];
return 0;
}
C. Swap Letters
题意：
给出两个只由(a,b)组成的字符串。
现在可以执行操作：在(s)中选择一个(pos_1)，在(t)中选择一个(pos_2)，然后交换(s_{pos_1},t_{pos_2})。
求使得(s=t)的最小操作次数，或回答不能使其相等。
思路：
我们可以分情况考虑：
- 对于(s_i=t_i)的位置，我们不用管；
- 之后将(s_i=a,t_i=b)的所有位置拿出来，将这样的对记作((a,b))；同理，另外一种情况记作((b,a))。
- 观察可以发现：显然要先将所有属于相同类型的对两两匹配，这样每次只需要操作一次。
- 最后会剩下奇数个数的对数，若只存在一个((a,b))和一个((b,a))，此时需要两次操作；否则就不能使其相等。
简单来说，就是分情况考虑就行了。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n;
char s[N], t[N];
int cnt[4];
bool used[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
cin >> s + 1 >> t + 1;
vector <pii> v;
for(int i = 1; i <= n; i++) {
if(s[i] == t[i]) continue;
if(s[i] == 'a' && t[i] == 'b') {
v.push_back(MP(0, i));
} else v.push_back(MP(1,i));
}
sort(v.begin(), v.end());
vector <pii> ans;
for(int i = 1; i < v.size();) {
if(v[i].fi == v[i - 1].fi) {
ans.push_back(MP(v[i - 1].se, v[i].se));
used[v[i - 1].se] = used[v[i].se] = 1;
i += 2;
} else ++i;
}
vector <pii> t;
for(auto it : v) {
if(!used[it.se]) t.push_back(it);
}
if((int)t.size() & 1) {
cout << -1; return 0;
}
for(int i = 1; i < t.size(); i += 2) {
ans.push_back(MP(t[i].se, t[i].se));
ans.push_back(MP(t[i - 1].se, t[i].se));
}
cout << ans.size() << '
';
for(auto it : ans) {
cout << it.fi << ' ' << it.se << '
';
}
return 0;
}
D. Ticket Game
题意：
(A)和(B)玩博弈游戏，规则如下：
现在给出一个由数字给出的串，长度为偶数，可能会有偶数个位上面的值为(?)。
现在两个人依次在(?)上面填(0)~(9)的数，一直填到不能填为止。
(A)为先手，若最后串的左边部分数字之和等于右边部分的数字之和，那么(B)赢，否则(A)赢。
思路：
感觉还是分情况考虑一下，首先我们记已知的数中左半部分和为(x)，右半部分和为(y)；左边有(a)个(?)，右边有(b)个。
- 若(x=y)：
- 若(a ot ={b})，易知先手必胜；
- 否则，后手每次根据先手填满(9)，后手必胜。
- 若(x
ot ={y})，不妨(x>y):
- 若(ageq b)，易知先手必胜，因为先手会在一边不断放(9)，后手只能不断维持差距，但最终不能弥补上差距；
- 若(a<b)，前面的(2a)回合策略肯定同上，先手不断放(9)，后手则维持平衡；在剩下的回合中，当先手放(x)时，后手唯一优势就是能放一个(y)，使得(x+y=9)。所以当(9|x-y)时，后手必胜；否则，先手放一个较大的数，后面后手没放一个(y)，先手就放一个(x)使得(x+y=9)，那么后手就GG了。
代码如下：
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n;
char s[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
cin >> s + 1;
int x = 0, y = 0, a = 0, b = 0;
for(int i = 1; i <= n; i++) {
if(s[i] != '?') {
if(i <= n / 2) x += s[i] - '0';
else y += s[i] - '0';
} else {
if(i <= n / 2) ++a;
else ++b;
}
}
if(x < y) swap(x, y), swap(a, b);
if(a == b) {
if(x == y) cout << "Bicarp";
else cout << "Monocarp";
} else {
if(a > b) {
cout << "Monocarp";
} else {
int d = x - y;
int t = (b - a) / 2;
if(9 * t == d) {
cout << "Bicarp";
} else cout << "Monocarp";
}
}
return 0;
}
E. Marbles
题意：
给出(n)个数，每个数大小不超过(20)。
现在可以执行操作：任意交换两个相邻的数。
现要求最少的次数使得颜色相同的数在同一块中。
思路：
- 注意到每个数大小不超过(20)，那么我们可以考虑对权值来状压。
- 我们首先维护一个(cnt[i,j])，表示将(i)类颜色放在(j)类后面所需最小代价，注意，此时我们只考虑(i,j)两种颜色，不考虑其余的颜色。
- 之后我们枚举状态(s)，表示某些颜色被分为一块的最小代价。之后枚举一个新的颜色(i)加进去，假设(j_1,j_2,cdots,j_m)的颜色已经分成一块了，代价就加上(sum_{k=1}^{m}cnt[i,j_k])，最后取(min)即可。
做法就说完了，感觉并不是很难。我觉得这个题巧妙的地方就是预处理的这个(cnt)数组。
预处理的时候只考虑了两个数，为什么？
这其实就相当于将(n^2)个关系一一拆开，假设(i,j)中间还有一个颜色(k)，我们一开始考虑时不会算上(k)，(k)的贡献我们会在最后算上。因为无论哪一次交换，都被包含在这(n^2)个关系中。
虽然中间结果可能不正确，最后一定会覆盖到正确的情况，就类似于曼哈顿距离拆绝对值进行枚举，虽然中间结果不一定是正确的，但最终答案肯定能够覆盖到。
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 4e5 + 5, MAX = 1 << 20;
int n;
int a[N];
ll cnt[20][20];
vector <int> v[20];
ll dp[MAX];
void run() {
for(int i = 1; i <= n; i++) {
cin >> a[i], --a[i];
}
for(int i = 0; i < 20; i++) {
v[i].clear();
for(int j = 0; j < 20; j++)
cnt[i][j] = cnt[j][i] = 0;
}
for(int i = 1; i <= n; i++) {
v[a[i]].push_back(i);
}
for(int i = 0; i < 20; i++) {
if(!sz(v[i])) continue;
for(int j = 0; j < 20; j++) {
if(!sz(v[j]) || i == j) continue;
int pos2 = 0;
for(int pos1 = 0; pos1 < sz(v[i]); pos1++) {
while(pos2 < sz(v[j])) {
if(v[j][pos2] > v[i][pos1]) break;
++pos2;
}
cnt[i][j] += sz(v[j]) - pos2;
}
}
}
int lim = 1 << 20;
for(int i = 0; i < lim; i++) dp[i] = INF;
for(int i = 0; i < 20; i++) dp[1 << i] = 0;
for(int s = 0; s < lim; s++) {
vector <int> was;
for(int i = 0; i < 20; i++) {
if(s >> i & 1) was.push_back(i);
}
for(int i = 0; i < 20; i++) {
ll sum = 0;
if((s >> i & 1) == 0) {
for(auto j : was) {
sum += cnt[i][j];
}
}
int ns = (s ^ (1 << i));
dp[ns] = min(dp[ns], dp[s] + sum);
}
}
cout << dp[lim - 1] << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n) run();
return 0;
}