社区讨论
NOIP2024T1求助,玄关
P11361[NOIP2024] 编辑字符串参与者 3已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mhj1rz2t
- 此快照首次捕获于
- 2025/11/03 19:19 4 个月前
- 此快照最后确认于
- 2025/11/03 19:19 4 个月前
思路大概就是先分段,彼此可以交换的在一起,固定的单独成段,然后去贪心的匹配
可能是匹配的思路有问题,大样例过不去,能不能帮忙看看是哪里有问题,谢谢了
CPP可能是匹配的思路有问题,大样例过不去,能不能帮忙看看是哪里有问题,谢谢了
#include<bits/stdc++.h>
using namespace std;
int ttt, len;
string a, b, c, d;
int jsb[100010][3], jsa[100010][3];
int xb1[100010], xb2[100010];
int main()
{
scanf("%d", &ttt);
while(ttt--)
{
scanf("%d", &len);
cin >> a >> b >> c >> d;
int cntb = 0, cnta = 0;
for(int i = 0; i < len; i++)
{
jsb[i][0] = jsb[i][1] = 0;
xb1[i] = xb2[i] = 0;
}
for(int i = 0; i < len; i++)
{
if((c[i] == '1') && ((i == 0) || ((i != 0) && (c[i-1] != '1')))) if((((i+1) < len) && (c[i+1] != '1')) || ((i+1) == len)) c[i] = '0';
if((i != 0) && (c[i] == c[i-1]) && (c[i] == '1')) jsa[cnta][a[i]-'0']++;
else jsa[++cnta][a[i]-'0']++;
xb1[i] = cnta;
}
for(int i = 0; i < len; i++)
{
if((d[i] == '1') && ((i == 0) || ((i != 0) && (c[i-1] != '1')))) if((((i+1) < len) && (d[i+1] != '1')) || ((i+1) == len)) d[i] = '0';
if((i!= 0) && (d[i] == '1') && (d[i] == d[i-1])) jsb[cntb][b[i]-'0']++;
else jsb[++cntb][b[i]-'0']++;
xb2[i] = cntb;
}
int ans = 0;
for(int i = 0; i < len; i++)
{
if(jsa[xb1[i]][1])
{
if(jsb[xb2[i]][1])
{
ans++;
jsb[xb2[i]][1]--;
jsa[xb1[i]][1]--;
}
}
else if(jsa[xb1[i]][0])
{
if(jsb[xb2[i]][0])
{
ans++;
jsa[xb1[i]][0]--;
jsb[xb2[i]][0]--;
}
}
}
cout << ans << '\n';
}
return 0;
}
回复
共 8 条回复,欢迎继续交流。
正在加载回复...