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

TopCoder SRM 634 Div.2[ABC]

ACM

質問アドレス: TopCoder SRM 634

試合後はやりましたorz 現場では絶対に無理だと思います。 。

レベル 1-山脈【水の質問】

質問の意味:
シーケンス内で隣の山よりも完全に大きいピークがいくつあるかを尋ねます。

分析:
愚かな質問ですが、あまり言うことはありません。コード：

rreee

レベル2 shoppingsurveydiv2 、つまり各アイテムを購入した人の数です。

これで、次の調査結果のみが得られます。つまり、s[i] 人が i 番目の商品を購入しました。
少なくとも何人がすべてを購入したかを尋ねています。

分析:

誰も買わなかったものを何人が買ったかを考えることができます。つまり、すべては N 人が買うべきであり、誰も買わなかったのは sum(N - s[i]) です。

現時点では、これらのものをできるだけ全員に配布し、残った人がそれらをすべて購入するしかありません。これが最小限です。十分なポイント (N >= sum(N - s[i])) がある場合、全員がすべてを購入していない可能性があります。

コード:

/**  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;}

レベル 3-SpecialStrings【構築】

質問:

特殊な文字列を設定します

1. 01 文字列
2. 任意の位置から分割します2 つの文字列の間に、前者の辞書編集上の順序は常に後者の順序より小さくなります。

ここで、特別であることが保証されている文字列が与えられた場合、辞書順で同じ長さの次の文字列が何かを尋ねます。それが最後の文字列であれば、空を返します。

分析:

明らかに、この文字列は辞書順で次の文字列である必要があります。つまり、この 01 文字列を保持する必要があるため、最初に +1 を与えます。つまり、最後の 0 を 1 に変更し、残りがXになると不明を意味します。

01101111011110111を例にすると、変更後は01101111011111XXXとなります。

最後にすべて0を置くと条件2を満たすことができますか?明らかにそうではありません

まず、変更点の前の部分を考えてみましょう。

変更前の部分は条件2を厳密に満たしており、元の0の位置が1に変更されているため、前の位置を分割点として使用すると、文字列の後半が元の文字列よりも大きくなりますので、フロント部分に変更は必要ありません。

一番の問題は後半です。先ほどの例に従うと、ポイントを分割点に変更しました。その前後の文字列は 01101111011111 と XXX になります。

すると、次の X 文字列は前の文字列よりも大きくなります。これは、辞書の次の順序にある​​ため、X 文字列は前の部分を直接コピーしてから +1 することができます。

分割ポイントが後ろにあるときにこの文字列が条件 2 を満たすことを証明するにはどうすればよいでしょうか? 明らかに、後ろの部分は前の +1 の完全なコピーであるため、後ろの分割ポイントは分割と同じです。後ろの点は条件2を満たしていることが保証されているので、後は絶対に問題ありません。ちょっと考えてみればわかります。

このようにして文字列が見つかります。

コード:

rree