月赛 F 90 pts 求助/kel
  • 板块学术版
  • 楼主mesan
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/8/7 17:07
  • 上次更新2023/10/27 16:36:09
查看原帖
月赛 F 90 pts 求助/kel
313849
mesan楼主2022/8/7 17:07

做法是随机交换两个数(

但是是这种先构造出符合 A 的个数做法错了,还是因为随机的做法错了(

/*******************************
| Sublime Text 3
| Problem: T258621 [Aya Round 1 F] 琪露诺的选择题
| URL:     https://www.luogu.com.cn/problem/T258621?contestId=76791
| When:    2022-08-07 14:15:14
| Memory:  512 MB
| Time:    2000 ms
*******************************/

#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for(auto i = (l); i <= (r); ++i)
#define per(i, r, l) for(auto i = (r); i >= (l); --i)

int ck(string s, string t, int sz) {
  int ans = 0;
  for (int i = 1; i <= sz; ++i) {
    ans += s[i] != t[i];
  }
  return ans;
}

void solve() {
  int n, a, e; cin >> n >> a >> e;
  string ans, my = "$"; cin >> ans; ans = '$' + ans; n *= 2;
  int putA = 0;
  for (int i = 1; i <= n; ++i) {
    if (putA < a && ans[i] == 'A') my += 'A', putA++;
    else my += 'B';
  }
  int WA = ck(ans, my, n);
  srand(time(0));
  for (int i = 1; i <= (int)1e5; ++i) {
    int pos1 = rand() % n + 1, pos2 = rand() % n + 1;
    string q = my;
    swap(q[pos1], q[pos2]);
    int WA2 = WA;
    if (q[pos1] == ans[pos1] && my[pos1] != ans[pos1]) WA2--;
    if (q[pos2] == ans[pos2] && my[pos2] != ans[pos2]) WA2--;
    if (q[pos1] != ans[pos1] && my[pos1] == ans[pos1]) WA2++;
    if (q[pos2] != ans[pos2] && my[pos2] == ans[pos2]) WA2++;
    if (abs(WA - e) > abs(WA2 - e)) WA = WA2, my = q;
    if (WA == e) {
      for (int i = 1; i <= n; ++i) cout << my[i]; cout << endl;
      return ;
    }
  }
  cout << -1 << endl;
}

int main() {
  int _; cin >> _;
  while (_--) solve();
}
2022/8/7 17:07
加载中...