前言
萬物皆貪心。
正文
1.Filling Shapes
題目連結
題目大意：
有基礎的三角圖案（如下圖-左邊），需要填充到3xN的大矩形中，要求：
1、不留白隙；
2、沒有重疊；
問，有多少種填充的組合方式。
輸入：
數字n，表示3*N的大圖案寬度；(1≤?≤60)
輸出：
多少種填充方式。
Examples
input
4
output
4
input
1
output
題目解析：
n為奇數，則會出現填不滿的情況（面積和不相等），此時為0；
n為偶數，對于每3*2的6個格子，隻有兩種組合方式， 那麼總共的方案是2^(n/2)的個數。
代碼：
int n;
cin >> n;
if (n % 2) {
cout << 0 << endl;
}
else {
lld ans = 1;
for (int i = 0; i < n / 2; ++i) {
ans *= 2;
}
cout << ans << endl;
} 複制
2.Plus from Picture
題目連結
題目大意：
h行w列的字元，由'*'和'.'兩種符号組成。
問字元中是否僅存在一個'+'号，加号的組成方式：
1、中心點是一個'*'号；
2、中心點的上下左右四個方向有一個或以上的連續'*'符号；
并且，除了這個'+'号，其他左右的字元都是'.'。
如果滿足上面的條件，則輸出"YES"，否則輸出"NO"。
輸入：
第一行是h, w; (1≤ℎ, ?≤500)
接下來是h行字元，每行有w個。
輸出：
滿足上面的條件，則輸出"YES"，否則輸出"NO"。
Examples
input
5 6
......
..*...
.****.
..*...
..*...
output
YES
input
3 5
..*..
****.
.*...
output
NO 複制
題目解析：
先找到中心點，判斷中心點是否為星号；
然後從四個方向去周遊，每個方向至少有1個星号，得到每個方向的星号；
總的星号是否等于圖中的星号。
思考?：
另外一種簡單的做法，以5個星号作為基礎圖案，周遊整個圖找到一個最小的+号。
然後延伸去看長度，最後看是否等于所有星号字元數量。
代碼位址。
3.Beautiful Lyrics
題目連結
題目大意：
一段悅耳的歌詞有兩行，每行有兩個單詞，并且要求：
1、第一行的第一個單詞中元音數量，和第二行第一個單詞相同；
2、第一行的第二個單詞中元音數量，和第二行第二個單詞相同；
3、第一行的第二個單詞中的最後一個元音，和第二行第二個單詞相同。
給出n個單詞，問最多能拼出多少段悅耳的歌詞，每個單詞隻能用一次。
輸入：
第一行n，表示n個單詞；（n<=10^5）
接下來n行，每行包括一個單詞。
所有單詞的字元總數不會超過10^6。
輸出：
第一行數字m，表示m段歌詞。
接下來是m段歌詞，每段兩行。
Examples
input
14
wow
this
is
the
first
mcdics
codeforces
round
hooray
i
am
proud
about
that
output
3
about proud
hooray round
wow first
this is
i that
mcdics am
題目解析：
先去除無關因素的影響，把每個單詞的元音提取出來，分類成：
1、單詞中元音的長度，分别是len=1、2、3.。。
2、相同長度的元音，分别有a/e/i/o/u 五種結尾的類型。
我們用vec[i][j]表示長度為i，結尾是第j個元音的字元串集合。
再來看看題目的要求，拼出最多的歌詞，并且每個單詞隻能用一次。
而歌詞的要求，可以表述為：
1、從相同長度字元串中，取出結尾相同的兩個單詞，作為第1、2行的第二個單詞；
2、從相同長度字元串中，取出長度相同的兩個單詞，作為第1、2行的第一個單詞；
從這裡，我們可以得到一個貪心的政策：
a.先兩個兩個的取出所有長度相同并且元音結尾相同的單詞，得到x組，這是可能的最大歌詞數量；
b.從剩下的所有單詞中，兩兩取出所有長度相同的單詞，得到y組，ans=min(x, y)組；
如果x>y，那麼剩下(x-y)組單詞還可以兩兩組成歌詞，此時還有ans+=(x-y)/2；
思考?：
當x>y時，能否取出x組中3個單詞，取出1個步驟b剩下的單詞，進行配對呢？
答案是可以，但是沒有必要。因為步驟b隻會剩下0個或者1個某個長度的單詞。
代碼位址。
4. Split a Number
題目連結
題目大意：
有一個字元串str，表示一個數字（沒有前導零)，現在需要把這個數字分成兩個合法的數字，并且希望和盡可能的小。
輸入：
第一行，數字n，表示字元串str的長度；(2≤n≤100000)
第二行，字元串str，表示數字；
輸出：
最小的和。
Examples
input
7
1234567
output
1801
input
3
101
output
11
題目解析：
先不考慮複雜度，對于每個位置pos，隻要str[pos]不是字元0，那麼就可以切分成兩個字元串[0, pos) 和 [pos, n)兩部分。
那麼可以枚舉每一個位置，計算一遍數字的和，最終得到一個最小的數字和。
枚舉複雜度是O(N)，分割數字和計算數字和是(N)，總的複雜度是O(N^2)；
因為n最大可以為10w，那麼這個複雜度是不可以接受的。
容易知道，很多位置的分割，是不可能成為最小和的值。比如說字元串1234567，如果分割成12+34567或者1+234567是明顯重複的計算。
由貪心的思想可以知道，分割出來的字元串a、b的長度應該盡可能接近。
對于長度為n字元串，分割成長度為n/2和n-n/2 ，或者(n+1)/2和n-(n+1)/2的組合是最好的。
那麼是否枚舉這個情況即可？
并不是！因為存在一個數字0的情況。比如說數字123000321，中間的位置都是0。
綜合上面的考慮，我們可以将n/2向左延伸，直到找到一個不為零的數字，作為分割點；
同樣的，将(n+1)/2向右延伸，知道找到一個不為零的數字，作為分割點。
然後從上面的兩個可能，選擇一個最小的值。
時間複雜度O(N)；
代碼：
int n;
cin >> n;
string str;
cin >> str;
/*
所有的切分都是[0, t-1], [t, n) 不同的是t的位置不同
要求，str[t]不能為字元0.
t可以是n/2,n/2+1等
*/
int x = (n + 1) / 2, y = n / 2;
string ansX = str, ansY = str;
while (x < str.length() && str[x] == '0') {
++x;
}
if (x < str.length()) {
ansX = getSplitSum(str, x);
}
while (y >= 0 && str[y] == '0') {
--y;
}
if (y >= 0) {
ansY = getSplitSum(str, y);
}
cout << getMinStr(ansX, ansY) << endl; 複制
具體方法的實作。
總結
題目1：根據題目的特性，可以看出三角形無法填充33的矩形，隻能填充32的矩形，那麼大問題就可以劃分成多個小問題；
題目2：思路比較明顯，重點是在于如何找到中心點，我采用的是看每一行每一列的累積星号數量，求交點；别人直接判斷一個最小星号，這種做法更加便捷、快速、簡練；
題目3：題目的要求看起來很複雜， 通過分析、細化、抽象，提示要素就隻有長度、結尾類型兩個參數；按照我們歸類出來的參數，進行聚合就很容易決策；
題目4：直接的想法很容易想到，比如說從中間分開；但是考慮到前導零的case，用合适的表達方式，會更加容易去計算。
Coding如逆水行舟，不練則廢。