头像

tom233




离线:4小时前



tom233
21小时前
#include<iostream>
#include<math.h>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N = 1e6 + 10;
int f[N],a[N];
int n, len;

int main(){

    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        int x;
        scanf("%d", &x);
        a[x] = i;
    }

    f[0] = -1;
    for (int i = 1; i <= n; i ++ ){
        int x;
        scanf("%d", &x);
        int k = a[x];
        if (!k) continue;

        int l = 0, r = len;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (f[mid] < k) l = mid;
            else r = mid - 1;
        }
        len = max(l + 1, len);
        f[l + 1] = k;
    }

    cout << len << endl;
    return 0;
}


活动打卡代码 AcWing 1085. 不要62

tom233
1天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 11;
int f[N][N];
int l, r;

void init(){

    for (int i = 0; i <= 9; i ++ ) 
        if (i != 4)
            f[1][i] = 1;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k <= 9; k ++ )
                if (k == 2 && j == 6) continue;
                else if (j == 4) continue;
                else f[i][j] += f[i - 1][k];
}

int dp(int u){

    if (!u) return 1;
    int res = 0, last = -1;
    vector<int> nums;
    while(u) nums.push_back(u % 10), u /= 10;

    for (int i = nums.size() - 1; i >= 0; i -- ){
        for (int j = 0; j < nums[i]; j ++ )
            if (last == 6 && j == 2) continue;
            else if (j == 4) continue;
            else
                res += f[i + 1][j];

        if (nums[i] == 4 || last == 6 && nums[i] == 2) break;
        last = nums[i];

        if (!i && !(last == 6 && nums[i] == 2)) res ++;
    }

    return res;
}

int main(){

    init();

    while(cin >> l >> r, l || r)
        cout << dp(r) - dp(l - 1) << endl;

    return 0;
}



活动打卡代码 AcWing 1084. 数字游戏 II

tom233
1天前

是否考虑前导零,看填了0对答案有没有影响。
如1083.windy数,如果有前导零,013非法, 13合法
而1084.数字游戏,仍然是13, 第三位加了前导零013仍然合法

#include<iostream>
#include<vector>
using namespace std;

const int N = 11, M = 110;
int f[N][N][M];
int l, r, n;

void init(){

    for (int i = 0; i <= 9; i ++ ) f[1][i][i] = 1;
    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = j; k < M; k ++ )
                for (int t = 0; t <= 9; t ++ )
                    f[i][j][k] += f[i - 1][t][k - j];
}

int dp(int u){

    if (!u) return 1;

    int res = 0, last = 0;
    vector<int> nums;
    while(u) nums.push_back(u % 10), u /= 10;

    for (int i = nums.size() - 1; i >= 0; i -- ){
        for (int j = 0; j < nums[i]; j ++ )
            for (int k = 0; k < M; k ++ )
                if ((k + last) % n == 0)
                    res += f[i + 1][j][k];
        last += nums[i];
        if (!i && (last % n) == 0) res ++;
    }

    return res;
}
int main(){

    init();

    while(scanf("%d%d%d", &l, &r, &n) == 3)
        cout << dp(r) - dp(l - 1) << endl;

    return 0;
}


活动打卡代码 AcWing 1083. Windy数

tom233
1天前
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

const int N = 11;
int f[N][N];
int l, r;

void init(){

    for (int i = 0; i <= 9; i ++ )f[1][i] = 1;
    for (int i = 2; i <= N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k <= 9; k ++ )
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int u){
    if (!u) return 0;

    vector<int> nums;
    int res = 0, last = 22;
    while(u) nums.push_back(u % 10), u /= 10;

    for (int i = nums.size() - 1; i >= 0; i -- ){
        for (int j = i == nums.size() - 1; j < nums[i]; j ++ )
            if (abs(j - last) >= 2)
                res += f[i + 1][j];

        if (abs(last - nums[i]) < 2) break;
        last = nums[i];
        if (!i) res ++;
    }

    // 特殊处理有前导零的数
    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];
    return res;
}

int main(){

    init();

    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}


活动打卡代码 AcWing 3502. 不同路径数

tom233
1天前
#include<set>
#include<iostream>
using namespace std;

const int N = 10;
int w[N][N];
int n, m, k;
set<int> s;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
void dfs(int x, int y, int res, int cnt){
    res = res * 10 + w[x][y];
    if (cnt == k){
        s.insert(res);
        return ;
    }
    for (int i = 0; i < 4; i ++ ){
        int xx = dx[i] + x, yy = dy[i] + y;
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            dfs(xx, yy, res, cnt + 1);
        }
    }
}

int main(){
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )  
            cin >> w[i][j];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            dfs(i, j, 0, 0);

    cout << s.size() << endl;
}


活动打卡代码 AcWing 3499. 序列最大收益

tom233
2天前
#include<iostream>
#include<cstring>
using namespace std;

const int N = 210;
int f[N][N], w[N][N], a[N], n, m, k;

int main(){
    cin >> n >> k >> m;

    for (int i = 1; i <= m; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];

    memset(f, -0x3f, sizeof f);   
    f[1][0] = 0;
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j <= k; j ++ )
            for (int t = 1; t < i; t ++ )
                if (j >= i - t - 1)
                    f[i][j] = max(f[i][j], f[t][j - (i - t - 1)] + w[a[t]][a[i]]);

    int res = 0;
    for (int i = 0; i <= k; i ++ )
        res = max(res, f[m][i]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1082. 数字游戏

tom233
2天前
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N = 35;
int f[N][N];
int l, r;

void init(){
    for (int i = 0; i <= 9; i ++ )f[1][i] = 1;
    for (int i = 2; i <= N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = j; k <= 9; k ++ )
                f[i][j] += f[i - 1][k];
}

int dp(int u){

    if (!u) return 1;

    vector<int> nums;
    int res = 0, last = 0;

    while(u)nums.push_back(u % 10), u /= 10;

    for (int i = nums.size() - 1; i >= 0; i -- ){
        for (int j = last; j < nums[i]; j ++ )
            res += f[i + 1][j];

        if ( nums[i] < last) break;
        last = nums[i];

        if (!i) res ++;
    }
    return res;
}

int main(){

    init();

    while(scanf("%d%d", &l, &r) == 2)
        cout << dp(r) - dp(l - 1) << endl;

    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

tom233
3天前
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL sum[N], state[N], real[N], w[N];
int n, k;

int main(){

    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ){
        cin >> w[i];
        sum[i] += sum[i - 1] + w[i];
    }
    for (int i = 1; i <= n; i ++ ){
        cin >> state[i];
        if (state[i]){
            real[i] = real[i - 1] + w[i];
        }else real[i] = real[i - 1];
    }

    LL res = 0;
    for (int i = 1; i + k - 1 <= n; i ++ ){
        res = max(res, (sum[i + k - 1] - sum[i - 1] + real[i - 1] + real[n] - real[i + k - 1]));
    }

    cout << res << endl;

    return 0;
}


分享 trie树删除

tom233
4天前

不再根据son[p][u]来走,而是根据cnt[son[p][u]]。cnt记录经过此节点的数的数量

原题链接:最大异或和

#include<iostream>
using namespace std;

const int N = 1e5 * 31 + 10, M = 1e5 + 10;
int son[N][2], idx, cnt[N], sum[M];
int n, m;

void insert(int x, int op){
    int p = 0;
    for (int i = 30; i >= 0; i -- ){
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += op;
    }
}

int query(int x){
    int res = 0, p = 0;
    for (int i = 30; i >= 0; i -- ){
        int u = x >> i & 1;
        if (cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;
        else p = son[p][u], res = res * 2;
    }
    return res;
}

int main(){

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        cin >> sum[i];
        sum[i] ^= sum[i - 1];
    }

    insert(sum[0], 1);
    int res = -1;
    for (int i = 1; i <= n; i ++ ){
        if (i > m) insert(sum[i - m - 1], -1);
        res = max(res, query(sum[i]));
        insert(sum[i], 1);
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 3485. 最大异或和

tom233
4天前
#include<iostream>
using namespace std;

const int N = 1e5 * 31 + 10, M = 1e5 + 10;
int son[N][2], cnt[N], sum[M], idx;
int n, m;

void insert(int x, int op){
    //op=1,add   op=-1,remove
    int p = 0;
    for (int i = 30; i >= 0; i -- ){
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += op;
    }
}

int search(int x){
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- ){
        int u = x >> i & 1;
        if (cnt[son[p][!u]])p = son[p][!u], res = res * 2 + 1;
        else p = son[p][u], res = res * 2;
    }
    return res;
}

int main(){

    cin >> n >> m;

    for(int i = 1; i <= n; i ++ ){
        cin >> sum[i];
        sum[i] ^= sum[i - 1];
    }

    int res = -1;
    insert(sum[0], 1);

    for (int i = 1; i <= n; i ++ ){
        if (i > m) insert(sum[i - m - 1], -1);
        res = max(res, search(sum[i]));
        insert(sum[i], 1);
    }

    cout << res << endl;

    return 0;
}