顺利搞出 A B 两题，然后压线晋级了，手速场。
A 题 ， 求排列最小的，肯定从后往前来做，维护一个最小的set，只是第一个字母要特判一下。
1: #line 5 "EllysSortingTrimmer.cpp"
2: #include <vector>
3: #include <list>
4: #include <map>
5: #include <set>
6: #include <deque>
7: #include <stack>
8: #include <bitset>
9: #include <algorithm>
10: #include <functional>
11: #include <numeric>
12: #include <utility>
13: #include <sstream>
14: #include <iostream>
15: #include <iomanip>
16: #include <cstdio>
17: #include <cmath>
18: #include <cstdlib>
19: #include <ctime>
20: #include <cstring>
21: using namespace std;
22: int i,j,k;
23: #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
24: #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
25:
26:
27: class EllysSortingTrimmer
28: {
29: public:
30: string getMin(string S, int L)
31: {
32: vector<char> s;
33: for(int i=1; i<S.size(); i++) s.push_back(S[i]);
34: sort(s.begin(),s.end());
35: vector<char> t;
36: for(int i=0; i<L-1; i++) t.push_back(s[i]);
37: t.push_back(S[0]);
38: sort(t.begin(), t.end());
39: string ret;
40: for(int i=0; i<L; i++) ret += t[i];
41: return ret;
42: }
43:
44:
45: };
46:
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
B题 不要搞成匹配的问题，每一个字母都有一个位置范围，所以只要维护一个set，保证其能够被写入，其余时间都插入最小就OK
1: #line 5 "EllysScrabble.cpp"
2: #include <vector>
3: #include <list>
4: #include <map>
5: #include <set>
6: #include <deque>
7: #include <stack>
8: #include <bitset>
9: #include <algorithm>
10: #include <functional>
11: #include <numeric>
12: #include <utility>
13: #include <sstream>
14: #include <iostream>
15: #include <iomanip>
16: #include <cstdio>
17: #include <cmath>
18: #include <cstdlib>
19: #include <ctime>
20: #include <cstring>
21: using namespace std;
22: int i,j,k;
23: #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
24: #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
25:
26:
27: class EllysScrabble
28: {
29: public:
30: string getMin(string letters, int maxDistance)
31: {
32: pair<char, int> X;
33: vector<pair<char, int> > S;
34: for(int i=0; i<letters.size(); i++)
35: {
36: S.push_back( make_pair(letters[i], i));
37: }
38:
39: string ret;
40:
41: vector<pair<char, int> > tmp;
42: for(int i=0; i< min(letters.size() *1.0,maxDistance + 1.0); i++) tmp.push_back(make_pair(letters[i], i));
43: for(int i=0; i<letters.size(); i++)
44: {
45: // search
46: sort(tmp.begin(), tmp.end());
47: bool flag = 0;
48: for(int j=0; j< tmp.size(); j++)
49: {
50: if(i - tmp[j].second == maxDistance)
51: {
52: ret += tmp[j].first;
53: tmp.erase(tmp.begin() + j);
54: flag = true;
55: break;
56: }
57: }
58: if(flag == false)
59: {
60: ret += tmp[0].first;
61: tmp.erase(tmp.begin());
62: }
63:
64: // push
65: if(i + maxDistance + 1 < letters.size())
66: {
67: tmp.push_back(S[ i+ maxDistance +1]);
68: }
69: }
70: return ret;
71: }
72:
73:
74: };
75:
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
C题 这个题目开始的时候没搞出来，其实当时已经发下了 YYY， NY YN3种情况肯定会有一个是亮的。但是没有仔细想。这个为什么贪心是对的呢？给出每一个序列，NY YN YYY一定是最大的，这个仔细推了一下好像是对的！但是有没有严格证明出来。
#line 5 "EllysLamps.cpp"
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
int i,j,k;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) class EllysLamps
{
public:
int getMin(string lamps)
{
int num = 0; for(int i=0; i<lamps.size();)
{
if(i+1 < lamps.size() && lamps[i] != lamps[i+1])
{
i+=2;
num++;
}else if(i+2 < lamps.size() && lamps[i] == lamps[i+1] && lamps[i] == lamps[i+2] && lamps[i]== 'Y')
{
i+=3;
num++;
}else i++;
}
return num;
} };
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }