D. Genius‘s Gambit (构造、细节)

谁借莪１个温暖的怀抱￠ 2021-07-16 15:00 285阅读 0赞

[题目][Link 1]

这一道题思路其实都有，主要细节比较多，我就wa了很多次…

对于x的构造前面b个a后面全是0  
如 3 6 6 x:111111000

再看b的构造

首先当k<=a  
前面1—b-1全为1，第b+k个元素为1，其余0  
如 4 3 2

x:1110000  
y:1100100

当a<k<=a+b-2  
第a+b个元素为1，再从b-(k-a)+1—b为1，然后就是还剩下的1的个数c=b-1-(k-a)使最开始的c个元素为1,即1—c为1。

如 3 6 6

x: 111111000  
y: 110111001

还有一些特殊情况  
当 0 1 0 时 x,y都只有一个元素 1  
当b=1||a=0 时k必须得为0

其余情况为No

构造思路：对于x的构造，想着如何能让k大一些，那么x尽量大就让前面的位多一些1，然后模拟一下发现如果k<=a，就让y也先让前面填满，剩下一个1，第b+k个放最后一个1(因为从第b位这个1每往后移一位答案就会多出一个1)。然后当k>a，通过模拟可以发现x y后方每有一个重合1就会多出一个1，那么先让y的第a+b个元素为1答案就已经有了a个1，还剩下的k-a个再让其x y重合k-a个1，其余的补到前面即可。感觉就是多模拟一下，找找规律，然后多注意特殊情况。

Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int a_[Max], b_[Max];
    int main()
    { 
    	int a, b, k;cin >> a >> b >> k;
    	if (a == 0 && b == 1 && k == 0) cout << "Yes" << endl << 1 << endl << 1;
    	else if (k > a + b - 2 || b == 1 && k != 0 || a == 0 && k != 0)cout << "No" << endl;
    	else
    	{ 
    		cout << "Yes" << endl;
    		a_[1] = 1, b_[1] = 1;
    		for (int i = 1;i <= b;i++)a_[i] = 1;
    		if (k <= a)
    		{ 
    			for (int i = 1;i <= b - 1;i++)b_[i] = 1;
    			b_[b + k] = 1;
    		}
    		else
    		{ 
    			for (int i = b;i >= b - (k - a) + 1;i--)b_[i] = 1;
    			for (int i = 2;i <= 2 + b - (2 + k - a) - 1;i++)b_[i] = 1;
    			b_[a + b] = 1;
    		}
    		for (int i = 1;i <= a + b;i++)cout << a_[i];
    		cout << endl;
    		for (int i = 1;i <= a + b;i++)cout << b_[i];
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1492/D