震撼了！OpenAI的新模型秒杀题目！
原题链接：45866.[NOIP2024] 编辑字符串
2025-05-17 11:37:46
发布于：日本
36阅读
5回复
1点赞
模型：o4-mini-high
思考持续时间：4分25秒
图片证据：
AC代码：
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using vi = vector<int>;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
string s1, s2, t1, t2;
cin >> s1 >> s2 >> t1 >> t2;
s1 = " " + s1;
s2 = " " + s2;
t1 = " " + t1;
t2 = " " + t2;
// prefix sums of ones for s1 and s2
vector<int> p1(n+1, 0), p2(n+1, 0);
for(int i = 1; i <= n; i++){
p1[i] = p1[i-1] + (s1[i]=='1');
p2[i] = p2[i-1] + (s2[i]=='1');
}
// events: at segment start i, add (end, count0, count1)
vector<vector<array<int,3>>> ev1(n+2), ev2(n+2);
// build s1 segments
for(int i = 1; i <= n; ){
if(t1[i]=='1'){
int L = i;
int j = i;
while(j <= n && t1[j]=='1') j++;
int R = j-1;
int ones = p1[R] - p1[L-1];
int len = R - L + 1;
int zeros = len - ones;
ev1[L].push_back({R, zeros, ones});
i = R + 1;
} else i++;
}
// build s2 segments
for(int i = 1; i <= n; ){
if(t2[i]=='1'){
int L = i;
int j = i;
while(j <= n && t2[j]=='1') j++;
int R = j-1;
int ones = p2[R] - p2[L-1];
int len = R - L + 1;
int zeros = len - ones;
ev2[L].push_back({R, zeros, ones});
i = R + 1;
} else i++;
}
// min-heaps of deadlines for supplies
priority_queue<int, vector<int>, greater<int>> h1[2], h2[2];
ll ans = 0;
for(int i = 1; i <= n; i++){
// 1) remove expired supplies
for(int b = 0; b < 2; b++){
while(!h1[b].empty() && h1[b].top() < i) h1[b].pop();
while(!h2[b].empty() && h2[b].top() < i) h2[b].pop();
}
// 2) add new segment supplies
for(auto &seg : ev1[i]){
int R = seg[0], c0 = seg[1], c1 = seg[2];
for(int k = 0; k < c0; k++) h1[0].push(R);
for(int k = 0; k < c1; k++) h1[1].push(R);
}
for(auto &seg : ev2[i]){
int R = seg[0], c0 = seg[1], c1 = seg[2];
for(int k = 0; k < c0; k++) h2[0].push(R);
for(int k = 0; k < c1; k++) h2[1].push(R);
}
// 3) process this position
bool can1 = (t1[i]=='1');
bool can2 = (t2[i]=='1');
if(!can1 && !can2){
// both fixed
if(s1[i] == s2[i]) ans++;
}
else if(can1 && !can2){
// s1 supply -> s2 fixed
int bit2 = s2[i] - '0';
if(!h1[bit2].empty()){
h1[bit2].pop();
ans++;
} else if(!h1[1-bit2].empty()){
h1[1-bit2].pop();
}
}
else if(!can1 && can2){
// s2 supply -> s1 fixed
int bit1 = s1[i] - '0';
if(!h2[bit1].empty()){
h2[bit1].pop();
ans++;
} else if(!h2[1-bit1].empty()){
h2[1-bit1].pop();
}
}
else {
// both supply: type3
// try match same bits first
if(!h1[0].empty() && !h2[0].empty()){
h1[0].pop();
h2[0].pop();
ans++;
}
else if(!h1[1].empty() && !h2[1].empty()){
h1[1].pop();
h2[1].pop();
ans++;
}
else {
// no direct match, consume one from each if available
if(!h1[0].empty() || !h1[1].empty()){
// pick earliest deadline to consume
int d0 = h1[0].empty() ? INT_MAX : h1[0].top();
int d1 = h1[1].empty() ? INT_MAX : h1[1].top();
if(d0 <= d1) h1[0].pop();
else h1[1].pop();
}
if(!h2[0].empty() || !h2[1].empty()){
int d0 = h2[0].empty() ? INT_MAX : h2[0].top();
int d1 = h2[1].empty() ? INT_MAX : h2[1].top();
if(d0 <= d1) h2[0].pop();
else h2[1].pop();
}
}
}
}
// finished this test
cout << ans << "\n";
}
return 0;
}
有帮助，赞一个