最近做的一点题的整理emm

G. Maximize the Remaining String
CF 1506G 【2000 贪心 单调栈】
题意： 给一个字符串， 每个字符只能保留一个， 要求字典序最大。
自己写的时候写假了emm 因为每次判断的时候并不知道后面的字母是不是已经被选过了qwq
辣鸡wa2代码：

void solve(){
    scanf(" %s", s + 1);
    memset(a, 0, sizeof a);
    n = strlen(s + 1);
    vector<int> v[30];
    for(int i = 1; s[i]; ++ i){
        v[s[i] - 'a'].push_back(i);
    }
    for(int i = 0; i <= 25; ++ i){
        if(v[i].size() > 1){
            bool f = false;
            int cnt = 0;
            for(auto u : v[i]){
                cnt ++;
                if(f)    s[u] = s[u + 1], a[u] = 1;
                else{
                    if(cnt == v[i].size())    break;
                    if(s[u] > s[u + 1])    f = true;
                    else    s[u] = s[u + 1], a[u] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= n; ++ i)    if(!a[i])    printf("%c", s[i]);
    cout << endl;
} 

正解： 使用单调栈。 如果当前栈顶的比当前的小， 就一直弹出， 但是如果栈顶的元素是这个元素的最后一个， 就不要继续弹出了。
注意如果某个字母已经用过了，直接continue即可。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 30, M = 200010;

stack<int> s;
char str[M];
int n, mp[N];
bool used[N];

void solve(){
    cin >> str + 1;
    memset(mp, 0, sizeof mp);
    memset(used, 0, sizeof used);
    n = strlen(str + 1);
    for(int i = 1; i <= n; ++ i){
        mp[str[i] - 'a'] = i;
    }
    s.push(str[1] - 'a'), used[str[1] - 'a'] = true;
    for(int i = 2; i <= n; ++ i){
        if(used[str[i] - 'a'])    continue ;
        while(s.size() && s.top() <= str[i] - 'a' && i < mp[s.top()])    used[s.top()] = false, s.pop();
        if(!used[str[i] - 'a'])    s.push(str[i] - 'a'), used[str[i] - 'a'] = true;
        //printf("i = %d sz = %d\n", i, s.size());
    }
    stack<int> ans;
    while(s.size()){
        ans.push(s.top()); 
        s.pop();
    }
    while(ans.size()){
        printf("%c", ans.top() + 'a');
        ans.pop();
    }
    cout << endl;
}

int main(){
    int _;
    cin >> _;
    while(_ --)    solve();
    return 0;
} 

Early Orders
双倍经验， 就是上面那个题把字典序最大变成最小。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 200010;

stack<int> s;
int n, k, a[N], mp[N];
bool used[N];

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        mp[a[i]] = i;
    }
    s.push(a[1]), used[a[1]] = true;
    for(int i = 2; i <= n; ++ i){
        if(used[a[i]])    continue ;
        while(s.size() && s.top() > a[i] && i < mp[s.top()])    used[s.top()] = false, s.pop();
        if(!used[a[i]])    s.push(a[i]), used[a[i]] = true;
        //printf("i = %d sz = %d\n", i, s.size());
    }
    stack<int> ans;
    while(s.size()){
        ans.push(s.top()); 
        s.pop();
    }
    while(ans.size()){
        printf("%d ", ans.top());
        ans.pop();
    }
    return 0;
} 

Paint Box 【组合数学， 容斥原理】
题意：
共有n个空盒子，m种颜色，盒子涂色使得相邻颜色不同，并且恰好涂了k种不同颜色，问有多少种涂色方案~

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 1000010, mod = 1e9 + 7;

ll fact[N],inv[N];
int n,m,t,k;

ll ksm(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)    res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    } 
    return res;
}

void init(int n){
    fact[0] = fact[1] = 1;
    for(int i = 2; i <= n; ++ i)    fact[i] = fact[i - 1] * i % mod;
    inv[n - 1] = ksm(fact[n - 1], mod - 2);
    for(int i = n - 2; i >= 0; -- i)    inv[i] = inv[i + 1] * (i + 1) % mod;
} 

ll C(ll n, ll m){
    if(!m || m > n)    return 0;
    return fact[n] * inv[m] % mod * inv[n - m] % mod;
}

int main(){
    init(N - 5);
    cin >> t;
    while(t --){
        cin >> n >> m >> k;
        ll ans = k * ksm(k - 1, n - 1) % mod;
        for(int i = k - 1, cur = -1; i > 0; -- i, cur = -cur){
            ans = (ans + mod + cur * C(k, i) * i % mod * ksm(i - 1, n - 1) % mod) % mod;
        }
        ll up = 1, down = 1;
        for(int i = 1, j = m; i <= k; ++ i, -- j){
            up = up * j % mod;
            down = down * i % mod;
        }
        ans = ans * up % mod * ksm(down, mod - 2) % mod;
        cout << ans << endl;
    }
    return 0;
}

回文字D 【字符串Hash】
太妙了www
因为小于d的串本来就是回文字D串， 所以只需要考虑>=d的。
考虑正着hash一次， 再反着hash一次， 如果是回文串， 那两个hash值应该相同。【一定注意反着hash的值是h[l] - h[r + 1] * p...】
每次考虑i -> j这一段， 如果可以， j ++继续往后移动； 否则表示这个串不是回文的， 只能切割了。
【这个贪心是没问题的， 不存在类似aaaabcdcbaa这种情况， 看似可以分成aa aabcdcbaa而不是 aaaa bcdcb aa。 但是这题的回文必须长度都是d, 上面的显然不满足长度要求】
tips: 这个代码会被d = 1卡死【i == j一直不动】， 那就多加一个判断条件即可。
注意check(i, j)是不行的， 因为j ++之后，i（起点）也应该同时往后加。

#include<bits/stdc++.h>
#define ll unsigned long long 
using namespace std;

const int N = 10000010, P = 131;

char s[N];
ll p[N], h[N], h2[N];
int n, d, ans;

bool check(int l, int r){ 
    return h[r] - h[l - 1] * p[r - l + 1] == h2[l] - h2[r + 1] * p[r - l + 1];
}

int main(){
    cin >> n >> d;
    scanf(" %s", s + 1);
    p[0] = 1;
    for(int i = 1; i <= n; ++ i){
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    for(int i = n; i >= 1; -- i)    h2[i] = h2[i + 1] * P + s[i];
    for(int i = 1, j = 0; i <= n; i = j){
        j = i + d - 1;
        while(j <= n && check(j-d+1, j))    j ++;    
        ans ++;
    }
    cout << ans;
    return 0;
}