Key Knocking bzoj-4796 CERC-2016
题目大意：描述没有题面短系列..题目链接
注释：$1\le n\le 10^5$。
想法：
乱搞稳AC。考试的时候调试信息又一次杀死了我...
我们考虑：因为总长度是$3n$，要求答案不小于$2n-1$，所以我们期望每$3$个数都贡献$2$，而且最多对于每$3$个数更改一次。
分类讨论一下：
我们只需考虑$0$开头的三元组（$1$开头的同理）
如果是$001$，我们动后两位，变成$010$，贡献为$2$，以此类推。
$010$不动
$011\rightarrow101$。
$000$的话我们判断一下：
如果这个三元组的前一个数是$0$，我们就把它变成$110$，反之我们将它变成$011$，这样我们仍然会让这个三元组对答案造成2的贡献。
如果这个三元组在开头，我们就把前两位取反即可。因为题目中自动给定了一个权值，我们把那个权值送给第一个三元组即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[300010];
int a[300010];
// int s[300010];
int cnt;
inline void SP(int x)
{
if(s[x]=='0') s[x]='1';
else if(s[x]=='1') s[x]='0';
if(s[x+1]=='1') s[x+1]='0';
else if(s[x+1]=='0') s[x+1]='1';
}
int main()
{
// freopen("key.in","r",stdin);
// freopen("key.out","w",stdout);
scanf("%s",s+1);
int k=strlen(s+1);
for(int i=1;i<=k-2;i+=3)
{
if(s[i]=='0'&&s[i+1]=='0'&&s[i+2]=='1') a[++cnt]=i+1,SP(i+1);
// if(s[i]=='0'&&s[i+1]=='1'&&s[i+2]=='0') a[++cnt]=i;
if(s[i]=='0'&&s[i+1]=='1'&&s[i+2]=='1') a[++cnt]=i,SP(i);
if(s[i]=='1'&&s[i+1]=='0'&&s[i+2]=='0') a[++cnt]=i,SP(i);
// if(s[i]=='1'&&s[i+1]=='0'&&s[i+2]=='1') a[++cnt]=i;
if(s[i]=='1'&&s[i+1]=='1'&&s[i+2]=='0') a[++cnt]=i+1,SP(i+1);
if(s[i]=='0'&&s[i+1]=='0'&&s[i+2]=='0')
{
if(i==1) a[++cnt]=i;
else if(s[i-1]=='0') a[++cnt]=i,SP(i);
else a[++cnt]=i+1,SP(i+1);
}
if(s[i]=='1'&&s[i+1]=='1'&&s[i+2]=='1')
{
if(i==1) a[++cnt]=i;
else if(s[i-1]=='1') a[++cnt]=i,SP(i);
else a[++cnt]=i+1,SP(i+1);
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
小结：这种题多做吧！