首页 >web前端 >html教程 >TopCoder SRM 634 Div.2[ABC]_html/css_WEB-ITnose

TopCoder SRM 634 Div.2[ABC]_html/css_WEB-ITnose

WBOY
WBOY原创
2016-06-24 11:57:031264浏览

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>  <p></p>  <p class="sycode">  </p>  <h2> Level Two-ShoppingSurveyDiv2【数学】</h2>  <p> 题意: <br> 你在做一项调查,一共有N人参加了调查,你得到了一份调查结果,就是每样东西有几个人买过。 <br> 现在你只有这份调查结果,即:第i个物品有s[i]个人买过。 <br> 问你最少有几个人全部东西都买过。</p>  <p> 分析:</p>  <p> 我们可以考虑有多少人次的东西没人买,即每样东西本来应该N人全都有买的,没人买就是sum(N - s[i])。 <br> 这时候我们可以把这些东西尽量分配给每个人,那么剩下的人就是没办法只能全买的了,也就是最少的。如果够分(N >= sum(N - s[i])),那所有人都有可能没买全了。</p>  <p> 代码:</p>  <p> </p>  <pre name="code" class="sycode">/**  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>  <p></p>  <p class="sycode">  </p>  <h2> Level Three-SpecialStrings【构造】</h2>  <p> 题意: <br> 设定一种特殊的串 <br> 1. 01串 <br> 2. 从任何位置把它分为两个前后串,前面的字典序总是小于后面的。</p>  <p> 现在给出一个保证特殊的串,问你同个长度下的字典序的下一个串是什么,如果是最后一个就返回空。</p>  <p> 分析:</p>  <p> 很明显,这个串必须是字典序的下一个,也就是这个01串是要进位的,所以我们先给它+1,即把最后一个0变成1,后面都变成X表示未知。 <br> 以01101111011110111作为例子,变化后就是01101111011111XXX了。</p>  <p> 后面全放0能符合条件2吗?很明显不能</p>  <p> 我们先考虑修改点的前面部分。 <br> 由于修改之前的那部分都已经严格遵守条件2了,而原先那个0的位置被变成1,所以:以前面的位置作为分割点的话,后半串是比原来变得更大了,所以前面部分不需要更改。</p>  <p> 主要问题在后面部分,我们已修改点为分割点,还是按刚才那个例子,前后串就变成01101111011111和XXX了。 <br> 那么后面的X串就要比前面大了,由于要是下一个字典序,所以X串直接可以拷前面部分,然后+1就行了。</p>  <p> 如何证明这个串在分割点为后面时,也能符合条件2呢,很明显,由于后面部分是完全复制前面的+1,所以分割点在后面跟分割点在后面是一样的,前面的是已经保证符合条件2的,所以后面肯定没问题。想一下就明白了。</p>  <p> 这样一来,这个串就求出来了。</p>  <p> 代码:</p>  <p> </p>  <pre name="code" class="sycode">/**  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 "";		s[pos] = '1';		repf (i, pos + 1, len - 1)			s[i] = s[i - pos - 1];		for (int i = len - 1; i >= 0; i--) {			if (s[i] == '0') {				s[i] = '1';				return s;			}		}	}};int main() {	// ios_base::sync_with_stdio(0);	SpecialStrings a;	string s;	cin >> s;	cout   <br>  <br>  <p></p>  <p class="sycode">   <br>  </p> </algorithm></iostream></cstring></cstdio></iilluzen>
声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn