我只想说一句 我好菜啊 QWQ(还是leetcode适合我)

1. 字符串修改

算个差值然后模26即可

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

char s[N];

int main(){

    int n; cin >> n;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1;i <= n;i ++ ){
        if(i & 1){
            s[i] = ((s[i] - 'a' + i % 26) % 26) + 'a';
        }else{
            s[i] = ((s[i] - 'a' - i % 26 + 26) % 26) + 'a';
        }
        // printf("%c", s[i]);
    }
    printf("%s\n", s + 1);

    return 0;
}

2. 学姐的编码1.0

首先想到dp[i][j]表示以i个字符结尾且以j结尾的集合
属性：数量

转移方程：
if(s[i] > s[j]) dp[i][get(s[i])] += dp[j][get(s[j])];

但是这样的话如何去除重复呢？？
如果i和前面一个k字符相同 那么以i结尾的字符会把i前面比它小的都算上去
但是i和k所共有的前面会被算两次 所以我们要把dp[k][get(s[k])]减去
只算k后面i前面的所有的比s[i]小的 然后tle 65分到手

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N];
int dp[N][20];

int get(char c){
    if(c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}
int main(){

    scanf("%s", s + 1);
    n = strlen(s + 1);

    for(int i = 1;i <= n;i ++ ){
        dp[i][get(s[i])] = 1;
        for(int j = 1;j < i;j ++ ){
            if(get(s[i]) > get(s[j])) dp[i][get(s[i])] += dp[j][get(s[j])];
            else if(get(s[i]) == get(s[j])) dp[i][get(s[i])] -= dp[j][get(s[j])];
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++ ) ans += dp[i][get(s[i])];
    cout << ans << endl;

    return 0;
}

考虑我们这样算会不会做了很多的无用功？？
我们算前面的时候架上它，到后面碰到相同的减去，最后ans再把两者加回来
这样不就等于把dp[k][get(s[k])] = 0，然后统计i前面比s[i]小的吗？

dp[get(s[i])]表示以s[i]结尾的所有的递增方案
dp[get(s[i])] += dp[j] { j < get(s[j]) }
即我只从最后一个字符转过来

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N];
int dp[20];
int last[20];

int get(char c){
    if(c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}
int main(){

    scanf("%s", s + 1);
    n = strlen(s + 1);

    for(int i = 1;i <= n;i ++ ){
        dp[get(s[i])] = 1;
        last[get(s[i])] = i;

        for(int j = 0;j < get(s[i]);j ++ )
            dp[get(s[i])] += dp[j];
    }
    int ans = 0;
    for(int i = 0;i < 20;i ++ ) ans += dp[i];
    cout << ans << endl;

    return 0;
}

3. 被三整除的子序列

dp[i][j]表示枚举到i且当前mod3为j的集合
属性：数量
最后减一除去空的情况
dp[i + 1][(j + a[i]) % 3] += dp[i][j];
dp[i + 1][j] += dp[i][j];
ans = dp[n][0] - 1;

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;
const int mod = 1e9 + 7;

char s[N];
int dp[N][3];

int main(){

    scanf("%s", s + 1);
    int n = strlen(s + 1);


    dp[0][0] = 1;

    for(int i = 1;i <= n;i ++ ){
        for(int j = 0;j < 3;j ++ ){
            (dp[i][j] += dp[i - 1][j]) %= mod;
            (dp[i][(j + (s[i] - '0')) % 3] += dp[i - 1][j]) %= mod;
        }
    }
    cout << (dp[n][0] - 1 + mod) % mod << endl;

    return 0;
}

dp[i][j]表示以i结尾且当前mod3为j的集合
属性：数量
dp[i + 1][(j + a[i]) % 3] += dp[k][j]; { k = [1, i - 1] }
ans = sum(dp[i][0])

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;
const int mod = 1e9 + 7;

char s[N];
int dp[N][3];

int main(){

    scanf("%s", s + 1);
    int n = strlen(s + 1);

    int ans = 0;
    dp[1][(s[1] - '0') % 3] = 1;
    ans = dp[1][0];
    for(int i = 2;i <= n;i ++ ){
        for(int j = 0;j < 3;j ++ ){
            for(int k = 1;k < i;k ++ )
                (dp[i][(j + (s[i] - '0')) % 3] += dp[k][j]) %= mod;
        }
        dp[i][(s[i] - '0') % 3] ++ ;
        (ans += dp[i][0]) %= mod;
    }

    cout << ans % mod << endl;

    return 0;
}

4. 迷阵

直接做不好做 可以先二分时间 然后枚举起点 这样就可以确定一个区间
然后直接dfs(1, 1)就可以了

类似枚举： 昂贵的聘礼

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n;
int g[N][N];
bool st[N][N];

void dfs(int x, int y, int s, int e){
    if(x == n && y == n) return ;
    for(int i = 0;i < 4;i ++ ){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
        if(g[nx][ny] < s || g[nx][ny] > e) continue;
        if(st[nx][ny]) continue;
        st[nx][ny] = true;
        dfs(nx, ny, s, e);
    }
}
int main(){

    cin >> n;
    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= n;j ++ ){
            cin >> g[i][j];
        }
    }

    int l = 0, r = 3000;
    while(l < r){
        int mid = l + r >> 1;
        bool flag = false;
        for(int s = 0;s < 3000 - mid;s ++ ){
            if(g[1][1] < s || g[1][1] > s + mid) continue;
            memset(st, false, sizeof st);
            st[1][1] = true;
            dfs(1, 1, s, s + mid);
            if(st[n][n]){
                // cout << s << " " << s + mid << endl;
                flag = true;
                break;
            }
        }
        // cout << r << " " << flag << endl;
        if(flag) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;

    return 0;
}