TopCoder SRM 634 Div.2[ABC]

TopCoder SRM 634 Div.2[ABC] ACM 题目地址:TopCoder SRM 634 赛后做的，感觉现场肯定做不出来Orz，简直不能多说。 Level One-MountainRanges 【水题】 题意 ： 问序列中有几个完全大于旁边的峰。 分析 ： 傻题，不多说。 代码 ： /** Author: illuz iilluze

TopCoder SRM 634 Div.2[ABC]

ACM

题目地址: TopCoder SRM 634

赛后做的，感觉现场肯定做不出来Orz，简直不能多说。

---

Level One-MountainRanges【水题】

题意： 
问序列中有几个完全大于旁边的峰。

分析： 
傻逼题，不多说。

代码：

/*
*  Author:      illuz <iilluzen>
*  File:        one.cpp
*  Create Date: 2014-09-26 21:01:23
*  Descripton:   
*/

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define repf(i,a,b) for(int i=(a);i h) {
		int ret = 0, sz = h.size();
		if (sz == 1) {
			return 1;
		}
		if (sz == 2) {
			return h[0] != h[1];
		}
		if (h[0] > h[1])
			ret++;
		if (h[sz - 1] > h[sz - 2])
			ret++;
		// cout  h[i - 1] && h[i] > h[i + 1])
				ret++, i++;
		}
		return ret;
	}
};

int main() {
	// ios_base::sync_with_stdio(0);
	MountainRanges a;
	int n, t;
	vector<int> v;
	cin >> n;
	while (n--) {
		cin >> t;
		v.push_back(t);
	}
	cout <br>
<br>

<hr>

<h2>
<span>Level Two-ShoppingSurveyDiv2</span>【数学】</h2>
<p>
<span>题意</span>： <br>
你在做一项调查，一共有N人参加了调查，你得到了一份调查结果，就是每样东西有几个人买过。 <br>
现在你只有这份调查结果，即：第i个物品有s[i]个人买过。 <br>
问你最少有几个人全部东西都买过。</p>
<p>
<span>分析</span>：</p>
<p>
我们可以考虑有多少人次的东西没人买，即每样东西本来应该N人全都有买的，没人买就是<code>sum(N - s[i])</code>。 <br>
这时候我们可以把这些东西尽量分配给每个人，那么剩下的人就是没办法只能全买的了，也就是最少的。如果够分(<code>N >= sum(N - s[i])</code>)，那所有人都有可能没买全了。</p>
<p>
<span>代码</span>：</p>

<pre class="brush:php;toolbar:false">/*
*  Author:      illuz <iilluzen>
*  File:        two.cpp
*  Create Date: 2014-09-26 22:36:58
*  Descripton:   
*/

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define repf(i,a,b) for(int i=(a);i s) {
		int sz = s.size(), sum = 0;
		repf (i, 0, sz - 1) sum += s[i];
		int t = N - (N * sz - sum);
		if (t  v;
	cin >> n >> m;
	repf (i, 0, m - 1) {
		cin >> t;
		v.push_back(t);
	}
	ShoppingSurveyDiv2 a;
	cout <br>
<br>

<hr>

<h2>
<span>Level Three-SpecialStrings</span>【构造】</h2>
<p>
<span>题意</span>： <br>
设定一种特殊的串 <br>
1. 01串 <br>
2. 从任何位置把它分为两个前后串，前面的字典序总是小于后面的。</p>
<p>
现在给出一个保证特殊的串，问你同个长度下的字典序的下一个串是什么，如果是最后一个就返回空。</p>
<p>
<span>分析</span>：</p>
<p>
很明显，这个串必须是字典序的下一个，也就是这个01串是要进位的，所以我们先给它+1，即把最后一个0变成1，后面都变成X表示未知。 <br>
以<code>01101111011110111</code>作为例子，变化后就是<code>01101111011111XXX</code>了。</p>
<p>
后面全放0能符合条件2吗？很明显不能</p>
<p>
我们先考虑修改点的前面部分。 <br>
由于修改之前的那部分都已经严格遵守条件2了，而原先那个0的位置被变成1，所以：以前面的位置作为分割点的话，后半串是比原来变得更大了，所以前面部分不需要更改。</p>
<p>
<span>主要问题在后面部分，我们已修改点为分割点，还是按刚才那个例子，前后串就变成</span><code>01101111011111</code><span>和</span><code>XXX</code><span>了。 </span><br>
<span>那么后面的X串就要比前面大了，由于要是下一个字典序，所以X串直接可以拷前面部分，</span><span><del>然后+1就行了</del></span><span>。 </span><br>
<span><span>这里有个错误：仅仅“X串直接可以拷前面部分，然后+1”这样是不行的，不是+1，而是要找拷贝完的X串的下一个合法串，所以我们继续找最后一个0、拷贝直到最后0在最后一个位置为止。（谢谢forgot93巨巨留言提醒）</span></span></p>
<p>
如何证明这个串在分割点为后面时，也能符合条件2呢，很明显，由于后面部分是完全复制前面的+1，所以分割点在后面跟分割点在后面是一样的，前面的是已经保证符合条件2的，所以后面肯定没问题。想一下就明白了。</p>
<p>
这样一来，这个串就求出来了。</p>
<p>
<span>代码</span>：</p>

<pre class="brush:php;toolbar:false">/*
*  Author:      illuz <iilluzen>
*  File:        three.cpp
*  Create Date: 2014-09-26 21:57:10
*  Descripton:   
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define repf(i,a,b) for(int i=(a);i= 0; i--) {
			if (s[i] == '0') {
				pos = i;
				break;
			}
		}
		if (pos == 0)
			return "";
		for (int i = len - 1; i >= 0; i--) {
			if (s[i] == '0') {
				s[i] = '1';			// 修改及复制
				repf (j, i + 1, len - 1)
					s[j] = s[j - i - 1];
				if (i == len - 1)			// 如果是0在最后一个就结束
					return s;
				else			// 否则让i=len重后面再找
					i = len;
			}
		}
		return s;
	}
};

int main() {
	// ios_base::sync_with_stdio(0);
	SpecialStrings a;
	string s;
	cin >> s;
	cout <br>
<br>


<p><br>
</p>


</algorithm></iostream></cstring></cstdio></iilluzen>