TopCoder SRM 634 Div.2[ABC]
來源：程序員人生 發(fā)布時(shí)間：2014-10-16 10:00:32 閱讀次數(shù)：2999次
TopCoder SRM 634 Div.2[ABC]
ACM
題目地址: TopCoder SRM 634
賽后做的，感覺現(xiàn)場肯定做不出來Orz，簡直不能多說。
Level One-MountainRanges【水題】
題意：
問序列中有幾個(gè)完全大于旁邊的峰。
分析：
傻逼題，不多說。
代碼：
/*
* 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;
}
題意：
你在做一項(xiàng)調(diào)查，一共有N人參加了調(diào)查，你得到了一份調(diào)查結(jié)果，就是每樣?xùn)|西有幾個(gè)人買過。
現(xiàn)在你只有這份調(diào)查結(jié)果，即：第i個(gè)物品有s[i]個(gè)人買過。
問你最少有幾個(gè)人全部東西都買過。
分析：
我們可以考慮有多少人次的東西沒人買，即每樣?xùn)|西本來應(yīng)該N人全都有買的，沒人買就是sum(N - s[i])。
這時(shí)候我們可以把這些東西盡量分配給每個(gè)人，那么剩下的人就是沒辦法只能全買的了，也就是最少的。如果夠分(N >= sum(N - s[i]))，那所有人都有可能沒買全了。
代碼：
/*
* 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【構(gòu)造】
題意：
設(shè)定一種特殊的串
1. 01串
2. 從任何位置把它分為兩個(gè)前后串，前面的字典序總是小于后面的。
現(xiàn)在給出一個(gè)保證特殊的串，問你同個(gè)長度下的字典序的下一個(gè)串是什么，如果是最后一個(gè)就返回空。
分析：
很明顯，這個(gè)串必須是字典序的下一個(gè)，也就是這個(gè)01串是要進(jìn)位的，所以我們先給它+1，即把最后一個(gè)0變成1，后面都變成X表示未知。
以01101111011110111作為例子，變化后就是01101111011111XXX了。
后面全放0能符合條件2嗎？很明顯不能
我們先考慮修改點(diǎn)的前面部分。
由于修改之前的那部分都已經(jīng)嚴(yán)格遵守條件2了，而原先那個(gè)0的位置被變成1，所以：以前面的位置作為分割點(diǎn)的話，后半串是比原來變得更大了，所以前面部分不需要更改。
主要問題在后面部分，我們已修改點(diǎn)為分割點(diǎn)，還是按剛才那個(gè)例子，前后串就變成01101111011111和XXX了。
那么后面的X串就要比前面大了，由于要是下一個(gè)字典序，所以X串直接可以拷前面部分，然后+1就行了。
這里有個(gè)錯(cuò)誤：僅僅“X串直接可以拷前面部分，然后+1”這樣是不行的，不是+1，而是要找拷貝完的X串的下一個(gè)合法串，所以我們繼續(xù)找最后一個(gè)0、拷貝直到最后0在最后一個(gè)位置為止。（謝謝forgot93巨巨留言提醒）
如何證明這個(gè)串在分割點(diǎn)為后面時(shí)，也能符合條件2呢，很明顯，由于后面部分是完全復(fù)制前面的+1，所以分割點(diǎn)在后面跟分割點(diǎn)在后面是一樣的，前面的是已經(jīng)保證符合條件2的，所以后面肯定沒問題。想一下就明白了。
這樣一來，這個(gè)串就求出來了。
代碼：
/*
* 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) {
if (s == "0") return "1";
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 "";
for (int i = len - 1; i >= 0; i--) {
if (s[i] == '0') {
s[i] = '1'; // 修改及復(fù)制
repf (j, i + 1, len - 1)
s[j] = s[j - i - 1];
if (i == len - 1) // 如果是0在最后一個(gè)就結(jié)束
return s;
else // 否則讓i=len重后面再找
i = len;
}
}
return s;
}
};
int main() {
// ios_base::sync_with_stdio(0);
SpecialStrings a;
string s;
cin >> s;
cout << a.findNext(s) << endl;
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
