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