題目1

題目鏈接
題目大意：
給出一個(gè)字符串，由小寫字母組成；
現(xiàn)在Alice和Bob在玩游戲，輪流從字符串中移除一個(gè)子串，Alice先操作；
Alice允許移除偶數(shù)長度子串，Bob允許移除奇數(shù)長度子串；（也允許不移除）
最終看每個(gè)人移除子串的分?jǐn)?shù)總和，字母a是1分，b是2分、、、z是26分；
問最終誰能贏得游戲，以及勝者領(lǐng)先的分?jǐn)?shù)；

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

輸出：
每個(gè)樣例一行，勝者和勝者領(lǐng)先的分?jǐn)?shù)；

Examples
input
5
aba
abc
cba
n
codeforces
output
Alice 2
Alice 4
Alice 4
Bob 14
Alice 93

題目解析：
Alice先手，并且可以移除偶數(shù)字符串，那么字符串如果是偶數(shù)，Alice會(huì)移除所有字符；
如果是奇數(shù)，Alice只會(huì)留下1個(gè)字符串，要么是最左邊，要么是左右邊的字符，選擇一個(gè)較小值；
Bob后手，只能選擇alice剩下的字符串。

class Solution {
    static const int N = 201010;
    string str;

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> str;
            int sum = 0;
            for (int i = 0; i < str.length(); ++i) {
                sum += str[i] - 'a' + 1;
            }
            if (str.length() % 2) {
                int bob = min(str[0], str[str.length() - 1]) - 'a' + 1;
                int alice = sum - bob;
                cout << (alice > bob ? "Alice" : "Bob") << " " << abs(alice - bob) << endl;
            }
            else {
                cout << "Alice " << sum << endl;
            }
        }
    }
}
ac;

題目2

題目鏈接
題目大意：
給出一個(gè)字符串，由小寫字母組成；
如果這個(gè)字符串的所有子串都滿足，構(gòu)成字符串的字符數(shù)相差不超過1，則稱這個(gè)字符串為完美字符串，比如說：

現(xiàn)在給出一個(gè)字符串，詢問是否為完美字符串；

輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤2?1e4)
每個(gè)樣例一行，字符串?? (1≤|??|≤2?1e5)

輸出：
每個(gè)樣例一行，如果是完美字符串則輸出YES；如果不是完美字符串則輸出NO；

Examples
input
5
aba
abb
abc
aaaaa
abcba
codeforces
output
YES
NO
YES
YES
NO

題目解析：
根據(jù)題目的要求，任意子串的字符數(shù)相差要在1以內(nèi)，假設(shè)一共有k個(gè)不同字符；
那么從字符串中任意截取k長度的字符串，必然會(huì)由不同的字符組成，否則就會(huì)出現(xiàn)重復(fù)字符數(shù)>1，然后沒出現(xiàn)的字符數(shù)位0，那么就不符合題目的要求；
并且由于可以任取，我們?cè)赱1, k]是由k個(gè)不同的字符構(gòu)成，[2, k+1]也是k個(gè)不同的字符構(gòu)成，由此可以推導(dǎo)出str[k+1] = str[1]，并由此類推，完美字符串必然是abcd abcd abc 這樣的重復(fù)構(gòu)成；
這樣只需要檢測(cè)字符串是否滿足這個(gè)特性即可。

class Solution {
    static const int N = 201010;
    string str;

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> str;
            int sum = 0, v[26] = {0};
            for (int i = 0; i < str.length(); ++i) {
                int index = str[i] - 'a';
                if (!v[index]) {
                    v[index] = 1;
                    ++sum;
                }
            }
            bool ans = true;
            memset(v, 0, sizeof(v));
            for (int i = 0; i < sum; ++i) {
                int index = str[i] - 'a';
                if (!v[index]) {
                    v[index] = 1;
                }
                else {
                    ans = false;
                    break;
                }
            }
            if (ans) {
                int pos = sum;
                while (pos < str.length() && ans) {
                    for (int i = pos; i < str.length() && i < (pos + sum); ++i) {
                        if (str[i] != str[i - sum]) {
                            ans = 0;
                            break;
                        }
                    }
                    pos += sum;
                }
                if (ans) {
                    cout << "YES" << endl;
                }
            }
            if (!ans) {
                cout << "NO" << endl;
            }
        }
    }
}
ac;

題目3

題目鏈接
題目大意：
給出一個(gè)數(shù)字n，將數(shù)字n可以拆分成若干個(gè)整數(shù)之和；
現(xiàn)在想知道，有多少種拆分方法，要求拆分出來的整數(shù)都是回文數(shù)；
（拆分出來的數(shù)字至少有一個(gè)不同，才算不同組合）

輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤1e4)
每個(gè)樣例一行，整數(shù) ?? (1≤??≤4?1e4)

輸出：
每個(gè)樣例一行，輸出不同的組合數(shù)字；結(jié)果可以對(duì)1e9+7取模；

Examples
input
2
5
12
output
7
74

題目解析：
首先，把1到40000的回文數(shù)全部列出來，得到若干個(gè)回文數(shù)；
題目的要求是計(jì)算數(shù)字n拆分有多少種組合，我們只看數(shù)字1和2，就是將數(shù)字n拆成1和2的和；
這個(gè)和動(dòng)態(tài)規(guī)劃的經(jīng)典題目類似：上n個(gè)臺(tái)階，每次有1步或者2步，最后有多少走法；

但是這個(gè)題目有點(diǎn)不同，就是對(duì)不同走法的判斷，這里只有新增不同數(shù)字的情況，才認(rèn)為是不同的；（1+2和2+1是一樣的）
那么我們將回文數(shù)數(shù)字從小到大排列，然后判斷每次回文數(shù)是否可以替換已有數(shù)字即可。
比如說：
考慮數(shù)字1，有dp[1]=1，dp[2]=1, dp[3]=1, dp[4]=1;（dp[i]表示數(shù)字i有多少總走法）
考慮數(shù)字2，有dp[1]=1，dp[2]=2, dp[3]=2, dp[4]=3；對(duì)于dp[2]，引入2的時(shí)候多了2=2的選擇，同時(shí)還有原來的2=1+1；對(duì)于dp[4]，可以在dp[2]的基礎(chǔ)上+2（新增2種選擇4=2+2, 4=1+1+2），也可以不使用2，保留原來的4=1+1+1+1；

按照這種思路分析，可以得到狀態(tài)轉(zhuǎn)移方程還是dp[i]=dp[i]+dp[i-k]；（k是回文數(shù)）

class Solution {
    static const int N = 40100;
    static const int MOD = 1e9 + 7;
    int dp[N];
    
    bool check(int k) {
        vector<int> vec;
        while (k) {
            vec.push_back(k % 10);
            k /= 10;
        }
        for (int i = 0; i < vec.size() / 2; ++i) {
            if (vec[i] != vec[vec.size() - i - 1]) {
                return false;
            }
        }
        return true;
    }

public:
    void solve() {
        vector<int> vec;
        for (int i = 1; i < N; ++i) {
            if (check(i)) {
                vec.push_back(i);
            }
        }
        dp[0] = 1;
        
        for (int j = 0; j < vec.size(); ++j) {
            for (int i = vec[j]; i < N; ++i) {
                dp[i] = ((lld)dp[i] + dp[i - vec[j]]) % MOD;
            }
        }
         
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            cout << dp[n] << endl;
        }
    }
}
ac;

題目4

題目鏈接
題目大意：
給出n個(gè)數(shù)字??1,??2,?,???? ，要求構(gòu)造一個(gè)長度不超過300的整數(shù)數(shù)組b，要求：
數(shù)組b中沒有重復(fù)的元素；
數(shù)組b包括了數(shù)組a的所有數(shù)字；
數(shù)組b任意兩個(gè)數(shù)字的差，其絕對(duì)值可以在數(shù)組b中找到相同數(shù)字。

輸入：
第一行是整數(shù)t，表示有t個(gè)樣例 (1≤??≤50 ).
每個(gè)樣例第一行是整數(shù)?? (2≤??≤100)；
第二行是n個(gè)整數(shù) ??1,??2,?,???? (?100≤????≤100)

輸出：
如果有解，先輸出YES，再輸出整數(shù)k，表示有k個(gè)整數(shù)； (??≤??≤300)
??1,??2,?,???? (?1e9≤????≤1e9)
如果無解則輸出NO；

Examples
input
4
3
3 0 9
2
3 4
5
-7 3 13 -2 8
4
4 8 12 6

output
yes
4
6 0 3 9
yEs
5
5 3 1 2 4
NO
Yes
6
8 12 6 2 4 10

題目解析：
構(gòu)造出來的數(shù)組b中不會(huì)存在負(fù)數(shù)，證明：
假設(shè)a[i]-a[j]，a[j]小于零，則必然需要一個(gè)比a[i]的數(shù)字a[k]，但是a[k]-a[j]又會(huì)產(chǎn)生更大的數(shù)字；

所以數(shù)組a中存在負(fù)數(shù)無解；
其他的情況，就用1、2、3、4到max來填充即可。

class Solution {
    static const int N = 200010;
public:

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int maxNum = 0, minNum = 200;
            for (int i = 1; i <= n; ++i) {
                int k;
                cin >> k;
                maxNum = max(maxNum, k);
                minNum = min(minNum, k);
            }
            if (minNum < 0) {
                cout << "NO" << endl;
            }
            else {
                cout << "YES" << endl;
                cout << maxNum + 1 << endl;
                for (int i = 0; i <= maxNum; ++i) {
                    cout << i << " ";
                }
                cout << endl;
            }
        }
    }
}
ac;

題目5

題目鏈接
題目大意：
給出n個(gè)整數(shù)的數(shù)組，從左到右可以依次選擇若干個(gè)整數(shù)，要求累加和在過程中始終不能為負(fù)數(shù)。
已知初始數(shù)字和為0，想知道最多能選擇多少個(gè)數(shù)字。

輸入：
第一行是整數(shù) ?? (1≤??≤2000)
第二行是n個(gè)整數(shù)??1 , ??2, ... ,???? (?1e9≤????≤1e9)
輸出：
輸出能選擇的最多整數(shù)。

Examples
input
6
4 -4 1 -3 1 -3
output
5

題目解析：
一種簡單的策略：
遇到正的就吃，遇到負(fù)的就看當(dāng)前能否吃下，能夠吃則直接吃；
如果不能吃，則考慮是否將吃過的負(fù)數(shù)吐出來，如果存在某個(gè)負(fù)數(shù)的絕對(duì)值 比這個(gè)數(shù)字的絕對(duì)值要大，則可以把原來的負(fù)數(shù)吐出來，把這個(gè)數(shù)字吃進(jìn)去；

可以用優(yōu)先隊(duì)列來記錄負(fù)數(shù)，復(fù)雜度O（NlogN）；

class Solution {
    static const int N = 200010;
public:
    int a[N];
    priority_queue<int, vector<int>, greater<int> > q;
public:
    void solve() {
        int t = 1;
        while (t--) {
            int n;
            cin >> n;
            while (!q.empty()) {
                q.pop();
            }
            lld sum = 0, ans = 0;
            for (int i = 0; i < n; ++i) {
                int tmp;
                scanf("%d", &tmp);
                if (sum + tmp >= 0) {
                    ++ans;
                    sum += tmp;
                    if (tmp < 0) {
                        q.push(tmp);
                    }
                }
                else {
                    int top = 0;
                    if (!q.empty()) {
                        top = q.top();
                    }
                    if (top < tmp) {
                        q.pop();
                        q.push(tmp);
                        sum = sum - top + tmp;
                    }
                }
            }
            cout << ans << endl;
            
        }
    }
}
ac;