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

TopCoder SRM 634 Div.2[ABC]

ACM

Question address: TopCoder SRM 634

I did it after the game. I feel like I can’t make Orz on site. There simply can’t be more. explain.

Level One-MountainRanges [Water Question]

Meaning of the question:
Asking how many peaks in the sequence are completely larger than the ones next to them.

Analysis:
Silly question, not much to say.

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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<=(b);i++)typedef long long ll;const int N = 0;class MountainRanges {public:	int countPeaks(vector<int> 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 << sz << ' ' << ret;		repf (i, 1, sz - 2) {			if (h[i] > 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 << a.countPeaks(v) << endl;	return 0;}

Level Two-ShoppingSurveyDiv2【Math】

Question meaning:
You are doing a survey. A total of N people participated in the survey. You got a survey result, which is how many people bought each item.
Now you only have this survey result, that is: s[i] people have bought the i-th item.
Asking you how many people at least have bought everything.

Analysis:

We can consider how many people bought something that no one bought, that is, everything should have been bought by N people, and no one bought it is sum(N - s[i ]).
At this time, we can distribute these things to everyone as much as possible, then the remaining people will have no choice but to buy them all, which is the minimum. If there are enough points (N >= sum(N - s[i])), then everyone may not have bought everything.

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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<=(b);i++)typedef long long ll;const int N = 0;class ShoppingSurveyDiv2 {public:	int minValue(int N, vector<int> s) {		int sz = s.size(), sum = 0;		repf (i, 0, sz - 1) sum += s[i];		int t = N - (N * sz - sum);		if (t < 0) t = 0;		return t;	}};int main() {	// ios_base::sync_with_stdio(0);	int n, m, t;	vector<int> v;	cin >> n >> m;	repf (i, 0, m - 1) {		cin >> t;		v.push_back(t);	}	ShoppingSurveyDiv2 a;	cout << a.minValue(n, v);	return 0;}

Level Three-SpecialStrings[Construction]

Meaning of the question:
Set a special string
1. 01 string
2. Divide it into two front and rear strings from any position, the front one is always smaller than the back one in lexicographic order .

Now given a string that is guaranteed to be special, ask you what is the next string of the same length in lexicographic order. If it is the last one, it will return empty.

Analysis:

Obviously, this string must be the next one in dictionary order, that is, this 01 string needs to be carried, so we give it 1 first, that is, change the last 0 becomes 1, and all subsequent values ​​become X to indicate unknown.
Taking 01101111011110111 as an example, after the change, it becomes 01101111011111XXX.

Can putting all 0s at the end meet condition 2? Obviously it can't

Let's consider the front part of the modification point first.
Since the part before modification has strictly complied with condition 2, and the original position of 0 has been changed to 1, so: if the previous position is used as the dividing point, the second half of the string will become larger than the original one. , so the front part does not need to be changed.

The main problem is in the latter part. We have changed the point to the dividing point. If we still follow the example just now, the strings before and after will become 01101111011111 and XXX.
Then the following X string will be larger than the previous one. Since it is the next dictionary order, the X string can directly copy the front part, and then 1 will do.

How to prove that this string can also meet condition 2 when the split point is at the back? Obviously, since the back part is a complete copy of the previous 1, the split point at the back is the same as the split point at the back. , the first one is guaranteed to meet condition 2, so there will definitely be no problem later. Just think about it and you’ll understand.

In this way, the string is found.

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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<=(b);i++)typedef long long ll;const int N = 0;class SpecialStrings {public:	string findNext(string s) {		int len = s.length(), pos = 0;		for (int i = len - 1; 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 << a.findNext(s) << endl;	return 0;}