edu 137 D(妙蛙)

题目
题意: 给定01字符串s，任意取两个s中的子串s1和s2，让二者求或，令结果尽可能地大。
思路: 首先可以把s的前导0去掉，对结果没有影响。s1可以取s串本身，s2要尽可能地在s1从大到小的有0的地方放上1。假设从大到小第一个0的位置是idx，子串的长度最大也就n-idx (下标从0开始)。因为长度再长就没有用了，第一个0前边都是1。所以枚举一下长度为n-idx的字串再与s取交即可。时间复杂度理论上可以到O(n^2)
tip: 因为数据是随机生成的，所以idx是n/2的概率很小，需要二分之一的二分之n次方，如果n是1e6，几乎不可能达到一半。所以idx大概率很小，基本能达到O(n)的时间复杂度。怪不得不让hack
代码:

#include
using namespace std;
const int N = 1e6+10;
int n,m,k,T;
string a;
void solve()
{
	cin>>n;
	cin>>a;
	int st = 0;
	int i;
	for(i=0;i<n;++i)
	{
		if(a[i]=='0') ;
		else break;
	}	
	st = i;
	if(st==n)
	{
		cout<<0;
	}
	else
	{
//		n -= st;
		int idx = n;
		for(int i=st;i<n;++i)
		{
			if(a[i]=='0')
			{
				idx = i;
				break;
			}
		}
		if(idx==n)
		{
			for(int i=st;i<n;++i) cout<<a[i]; 
		}
		else
		{
			string res;
			int len = n-idx;
			for(int i=0;i<idx;++i)
			{
				string s2 = a.substr(i,len);
//				cout<
				bool flag = 0;
				for(int j=0;j<s2.size();++j)
				{
					if(s2[j]=='1'||a[idx+j]=='1') s2[j] = '1';
					if(i)
					{
						if(!flag&&res[j]>s2[j]) break;
						else if(res[j]<s2[j])
						{
							flag = 1;	
						}	
					} 
				}
				if(i==0||flag) res = s2;
			}
			for(int i=st;i<n;++i)
			{
				if(i<idx) cout<<a[i];
				else cout<<res[i-idx];
			}
		}
	}
}
signed main(void)
{
	solve();
	return 0;	
} 
/*
010101001001011110
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76