題目1

題目鏈接
題目大意：
有n個人參加投票，小明是第一個；
投票一共k輪，每輪每個人會做出一個選擇，分別用+和-表示，那么一共有三個結果：
+的人數(shù)大于-的人數(shù)，那么-的人出局；
-的人數(shù)大于+的人數(shù)，那么+的人出局；
如果+和-的人數(shù)一樣多，那么所有人出局；
出局的人，不再參與后續(xù)投票。

小明有特權，可以在第一輪投票之前淘汰掉若干個人，現(xiàn)在想知道，最終能有多少個人留到了最后；（小明一定保證自己會留到最后）

輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤1000)
每個樣例n+1行
第一行，整數(shù)?? 和 ?? (1≤??,??≤100)
接下來n行，每行有k個字符，表示每個人都投票結果。

輸出：
輸出留到最后的人數(shù)。

Examples
input

 5
 2 2
 ++
 +-
 1 3
 +-+
 4 1
 +
 -
 -
 +
 5 4
 ++++
 +--+
 ++-+
 +-++
 ++++
 4 2
 ++
 --
 --
 -+

output
1
1
2
2
1

題目解析：
由于題目不需要選擇淘汰的順序，并且小明一定會留在最后，那么和小明相同的投票結果的人會保留；

class Solution {
    static const int N = 201010;
    char s[N], r[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            int ans = 1;
            cin >> s;
            for (int i = 1; i < n; ++i) {
                cin >> r;
                int tmp = 0;
                for (int j = 0; j < k; ++j) tmp += s[j] == r[j];
                ans += tmp == k;
            }
            cout << ans << endl;
        }
    }
}

題目2

題目鏈接
題目大意：
給出一個由整數(shù)和?組成的字符串，其中符號?可以匹配任何單個數(shù)字；
For example:
42 matches 4?;
1337 matches ????;
1337 matches 1?3?;
1337 matches 1337;
3 does not match ??;
8 does not match ???8;
1337 does not match 1?7.

現(xiàn)在問給出的字符串，最多存在多少個合法的匹配數(shù)字；（不包括前導零，整數(shù)大于零）

輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤20000)
每個樣例1行，字符串?? (1≤|??|≤5)

輸出：
每個樣例一行，輸出最多存在多少個合法的匹配數(shù)字；

Examples
input
8
??
?
0
9
03
1??7
?5?
9??99

output
90
9
0
1
0
100
90
100

題目解析：
分情況討論：
1、給出的字符串就存在前導零，那么結果為0；
2、給出的字符串合法，并且存在x個?號，那么有兩種情況：
2.1，?號之前已經(jīng)有整數(shù)，此時?號可以取任意數(shù)字，那么x個?號可以得到10^x個整數(shù)；
2.2，?號前面沒有整數(shù)，此時第一個?號只能取1-9數(shù)字，所以會減少10^(x-1)個答案；

class Solution {
   static const int N = 201010;
   char s[N];
public:
   void solve() {
       int t;
       cin >> t;
       while (t--) {
           cin >> s;
           int n = strlen(s);
           int x = 0;
           for (int i = 0; i < n; ++i) x += (s[i] == '?');
       
           if (s[0] == '0') cout << 0 << endl;
           else if (s[0] == '?') {
               if (!x) cout << 1 << endl;
               else cout << (int)pow(10, x) - (int)pow(10, x - 1) << endl;
           }
           else {
               cout << (int)pow(10, x) << endl;
           }
       }
   }
}
ac;

題目3

題目鏈接
題目大意：
給出一個由n個整數(shù)組成的數(shù)組a，在數(shù)組中選擇區(qū)間[l, r]，將區(qū)間內的整數(shù)按照非降序進行處理得到整數(shù)數(shù)組b，比如說：
整數(shù)數(shù)組a為[6,7,3,4,4,6,5]，選擇區(qū)間[2, 5]得到整數(shù)數(shù)組b為[6,3,4,4,7,6,5]；（區(qū)間外的整數(shù)位置不變）

現(xiàn)在已知整數(shù)數(shù)組a和變化后的整數(shù)數(shù)組b，求區(qū)間最長可能為多少？

輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例3行：
第一行整數(shù)n(2≤??≤2?1e5)
第二行整數(shù)數(shù)組a
第二行整數(shù)數(shù)組b
注意：數(shù)組a和數(shù)組b至少有一個位置的元素不相同。

輸出：
每個樣例一行，輸出區(qū)間[l, r]，表示可以選擇進行操作的最長區(qū)間，如果由多個答案，輸出任意一個；（題目保證有解）

Examples
input
3
7
6 7 3 4 4 6 5
6 3 4 4 7 6 5
3
1 2 1
1 1 2
3
2 2 1
2 1 2

output
2 5
1 3
2 3

題目解析：
假如不考慮復雜度，那么應該枚舉區(qū)間[x, y]，然后計算每個區(qū)間的可行性，這樣復雜度為枚舉復雜度 * 驗證復雜度，枚舉就已經(jīng)超過題目限制；
注意題目給出的條件，數(shù)組a和b有元素不相同，那么至少存在2個位置不相同，否則題目無解；
假定第一個不相同元素的位置是x，最后一個不相同元素的位置是y，那么區(qū)間[x, y]必然是一個解，但不是最長解：
假設區(qū)間[x, y]右邊的元素比區(qū)間[x, y]內的元素更大，那么可以納入到這個區(qū)間內，因為排序完無影響；
同理對于區(qū)間[x, y]左邊的元素，只要小于的等于區(qū)間內最小值，那么同意可以納入到區(qū)間中；

注意：
區(qū)間外的整數(shù)，不一定有序的，比如說：
2 2 4 3 5 4
2 2 3 4 5 4

class Solution {
    static const int N = 201010;
    int a[N];
    int b[N];
public:
    void solve() {
        int t;
        cin >> t;
        int cnt = 0;
        while (t--) {
            int n, x, y = 0;
            cnt++;
            cin >> n;
            for (int i = 0; i < n; ++i) cin >> a[i];
            for (int i = 0; i < n; ++i) cin >> b[i];
            x = -1;
            for (int i = 0; i < n; ++i) {
                if (a[i] != b[i]) {
                    if (x == -1) x = i;
                    else y = i;
                }
            }
            
            int valMin = b[x], valMax = b[y];
            while (x > 0) {
                if (b[x - 1] <= valMin) --x;
                else break;
                valMin = min(valMin, b[x]);
            }
            while (y < n - 1) {
                if (b[y + 1] >= valMax) ++y;
                else break;
                valMax = max(valMax, b[y]);
            }

            cout << (x + 1) << " " << (y + 1) << endl;
            
        }
    }
}

題目4

題目鏈接
題目大意：
給出一個小寫字母組成的字符串s，現(xiàn)在可以對字符串進行多次操作：
選擇若干個不相鄰的位置，移除這些位置上的字符，剩下的字符保持相對順序組成新的字符串s；

假如操作若干次后，剩下的字符串都由相同字符組成，最少需要多少次；

輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例一行，字符串s；（長度不超過200,000）

輸出：
每個樣例一行，輸出最少的次數(shù)。

Examples
input
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul

output
1
3
0
2
4

12345678

題目解析：
先簡化題目，按照題目去掉若干個字符：
去掉字符長度為2，需要2個操作；
去掉字符長度為3，需要2個操作；
去掉字符長度為4，需要3個操作；
去掉字符長度為7，需要3個操作；
去掉字符長度為8，需要4個操作；
...
去除的規(guī)則比較簡單，每次去除所有奇數(shù)位置，就可以最快去除；

題目的要求，最后只剩一種字符，那么結果一共有26種組合。
以字符a為例，遍歷一遍字符串，那么就可以得到若干個由a分隔的區(qū)間，其中最長的區(qū)間假設是x，那么這個區(qū)間的移除代價就是最終的移除代價；
同理得到26個字母的結果，取其最小得到結果。

class Solution {
    static const int N = 201010;
    char s[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> s;
            int n = strlen(s);
            int ans = n;
            for (int i = 0; i < 26; ++i) {
                char c = 'a' + i;
                int len = 0, last = -1;
                for (int j = 0; j < n; ++j) {
                    if (s[j] == c) {
                        last = j;
                    }
                    else {
                        len = max(len, j - last);
                    }
                }
                if (len == 0) {
                    ans = 0;
                    break;
                }
                int tmp = 1;
                while ((1 << tmp) <= len) ++tmp;
                ans = min(ans, tmp);
            }
            cout << ans << endl;
        }
    }
}

題目5

題目鏈接
題目大意：
有一排格子排成一行，編號從左到右分別為0、1、2、3；
小明站在第0個格子，每次小明有三個選擇可以進行操作：
1、移動到下一個格子：從格子x移動到格子x+1；
2、按下shift按鈕；
3、松開shift按鈕，小明在按下shift按鈕期間經(jīng)過的格子會被染色；

現(xiàn)在只有若干個區(qū)間[x, y]允許染色，區(qū)間外的格子不允許染色；
現(xiàn)在想要染色k個格子，問最少需要操作多少次；

1e18

輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例3行：
第一行，整數(shù) ?? 和 ?? (1≤??≤2?1e5; 1≤??≤1e9)
第二行，整數(shù) ??1,??2,…,????，表示n個區(qū)間的起點 (1≤??1<??2<?<????≤1e9)
第三行，整數(shù) ??1,??2,…,???? ，表示n個區(qū)間的終點 (1≤????≤109; ????≤????<????+1?1)
n個區(qū)間沒有重合；

輸出：
每個樣例一行，輸出最少的操作次數(shù)，如果無解則輸出-1；

Examples
input
4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000

output
8
-1
7
1000000004

題目解析：
簡單策略，小明從左到右，只要經(jīng)過允許的區(qū)間就染色，直到k個格子；
考慮到要最小操作次數(shù)，那么同一個區(qū)間的染色操作要合并，那么策略可以進行優(yōu)化：
對于每一個區(qū)間，先考慮區(qū)間是否小于需要染色數(shù)量，是的話則直接染色整個區(qū)間；
如果當前區(qū)間足夠剩余染色數(shù)量，則選擇需要染色的x個格子即可。
但是這種策略少考慮了一種情況：
以題目樣例3為例，假設一種情況是1011111111，其實先選擇前面的1，則會花費3的代價（兩次shift+1次移動），總的花費是8；如果不選擇前面1，而是選擇后面位置3開始的1，則只需要花費的代價是7；
為什么會出現(xiàn)這種情況？
因為前面會有2次選中操作，但是后面則只需要1次選中操作，減少了1次選中操作（即是2次shift），雖然多花費了1次move操作，但是總的花費還是減少了1；
所以在這種情況下，簡單的策略在以下這種情況：
101010....011111....0110..101010....1111111... 都會難以處理，因為在決策是否要染色時，還可能受到后續(xù)方塊的影響。

為了簡化思考過程，可以我們把移動和選擇拆分來看，先假設小明從0開始移動到第i個可以染色區(qū)間，小明經(jīng)過的區(qū)間可以分為三類：
1、長度為1區(qū)間；
2、第1個到第i-1個區(qū)間中，長度大于1的區(qū)間；
3、第i個區(qū)間；（為什么第i個單獨列出來，是因為第i個允許僅染色部分）

移動的代價分為兩部分，首先是移動到第i個區(qū)間起始位置，另外一個是在第i個區(qū)間移動的距離；
選擇的代價，首先是長度大于>1的區(qū)間，然后是第i個區(qū)間，接著是長度為1的區(qū)間；

Example：
k=10
10101010101010101010111011111111111111
19+2*10=39
20+4+7+4=35

class Solution {
    static const int N = 201010;
    int a[N], b[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            for (int i = 0; i < n; ++i) cin >> a[i];
            for (int i = 0; i < n; ++i) cin >> b[i];
            lld sum = 0, oneCnt = 0;
            lld ans = 0xffffffffffff;
            for (int i = 0; i < n; ++i) {
                lld len = b[i] - a[i] + 1;
                if ((sum + len) >= k && k >= (sum - oneCnt)) {
                    if (sum - oneCnt + len >= k) {
                        ans = min(ans, a[i] - 1 + (i - oneCnt + 1) * 2 + (k - (sum - oneCnt)));
                    }
                    else {
                        ans = min(ans, a[i] - 1 + (i - oneCnt + 1) * 2 + len + 2 * (k - (sum - oneCnt + len)));
                    }
                }
                if (len == 1) ++oneCnt;
                sum += len;
            }
            if (ans == 0xffffffffffff) cout << "-1" << endl;
            else cout << ans << endl;
        }
    }
}