[bzoj4796][CERC2016]Key Knocking_乱搞

Myth丶恋晨 2021-09-30 15:08 169阅读 0赞

Key Knocking bzoj-4796 CERC-2016

**题目大意**：描述没有题面短系列..[题目链接][Link 1]

**注释**：$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;
    }

**小结**：这种题多做吧！

转载于:https://www.cnblogs.com/ShuraK/p/9557440.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=4796