Znzryb's Blog
0%

2025牛客WC5-C-小L的位运算

Posted on Edited on

思路讲解

我们将不匹配的位置分类，发现最多只有四类，ab 分别是 00*,* 01*,* 10*,* 11 ，任意
两个不同种类不匹配的话，我们一定可以交换其中的某一位 0 和 1 使之两两匹配，

其他的没什么特殊的，我们发现四种情况全部都可以选择其他另外一种情况抵消。

那么问题就来到了怎么样抵消的问题上

我们一定可以交换其中的某一位 0 和 1 使之两两匹配，那么我
们就只看最多的一类不匹配的位置的数量有没有超过总数的一半即可。
如果超过就超过的部分反置，其余匹配，否则一定存在一种分配方式使之匹配后至多
仅剩一个。

官解的匹配方式是这样的，但我相信这个分类讨论大抵是没那么容易想到的，那我们有没有一种策略去匹配不出错那？

用大的去匹配次大的

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75564916

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
priority_queue<ll> pq;
pq.push(rem0);
pq.push(rem1);
pq.push(rem01);
pq.push(rem10);
ll ans=0;
while (SZ(pq) != 1) {
  ll u = pq.top();
  pq.pop();
  ll v = pq.top();
  pq.pop();
  ans += v * Y;
  if (u == v) continue;
  pq.push(u - v);
}
ans += pq.top() * X;

用大的去匹配小的

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75565204

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
priority_queue<ll> pq;
pq.push(rem0);
pq.push(rem1);
pq.push(rem01);
pq.push(rem10);
ll ans = 0;
while (SZ(pq) > 1) {
  ll u = pq.top();
  pq.pop();
  ll v = pq.top();
  pq.pop();
  ans += v * Y;
  pq.push(u - v);
}
if (pq.empty()) {
  cout << ans << '\n';
  return 0;
}
ans += pq.top() * X;
cout << ans << '\n';

似乎都会出问题，这些贪心策略都有瑕疵（见以下hack数据3，5，7，13）

1
2
3
4
5
6
7
28 5 6
0001111100000001111111111111
0001111111111110000000000000
1111111100000000000000000000

应该输出
84（14次交换*6=84）

有些人~~（我）~~可能觉得3，5，7，13根本无法消除（无法完全通过交换消除），通过交换最终会剩余2

但实际上是可以的，只不过比较复杂，需要通过分段的方法消除，具体见下

image

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75568259

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Problem: 小L的位运算
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95337/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
constexpr ll MAXN = static_cast<ll>(1e6) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, X, Y, T;
char A[MAXN], B[MAXN], C[MAXN];
// ll rem[7];
ll rem1, rem0, rem10, rem01;
// vector<ll> pq;
// ll ans=INF;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> X >> Y;
  FOR(i, 1, N) { cin >> A[i]; }
  FOR(i, 1, N) { cin >> B[i]; }
  FOR(i, 1, N) { cin >> C[i]; }
  FOR(i, 1, N) {
    if (((A[i] - '0') ^ (B[i] - '0')) != (C[i] - '0')) {
      if (C[i] == '1') {
        if (A[i] == '0' && B[i] == '0') {
          rem0 += 1;
        } else {
          rem1 += 1;
        }
      } else {
        if (A[i] == '1') {
          rem10 += 1;
        } else {
          rem01 += 1;
        }
      }
    }
  }
  // rem[0]=rem0,rem[1]=rem1,rem[2]=rem10,rem[3]=rem01;
  if (X * 2 > Y) {
    ll sum=rem0+rem1+rem10+rem01;
    ll maxR=max({rem0,rem1,rem10,rem01});
    ll ans=0;
    if(maxR*2<=sum){
    	ans=sum/2*Y+sum%2*X;
    }else{
    	ans=(maxR-(sum-maxR))*X+(sum-maxR)*Y;
    }
    cout << ans << '\n';
  } else {
    cout << (rem1 + rem0 + rem10 + rem01) * X << '\n';
  }
  return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

哈哈，不知道还可以这样分段消除，还以为题目出问题了，我太菜了