头像

lty2019




离线:20分钟前


最近来访(2)
用户头像
final_trump
用户头像
T-D-S

活动打卡代码 AcWing 1875. 贝茜的报复

lty2019
6小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

map<char, int> mp1, mp2, a;
string s = "BESIGOM";
int res;

void dfs(int u, int x){
    if(u == 7){
        if((a['B'] + a['I']) % 2 && (a['G'] + a['O'] + a['E'] + a['S']) % 2 && a['M'] % 2) return;
        res += x;
        return;
    }

    char ch = s[u];
    a[ch] = 1, dfs( u + 1, x * mp1[ch]);
    a[ch] = 2, dfs( u + 1, x * mp2[ch]);
}

int main(){

    int n;
    scanf("%d", &n);
    while(n -- ){
        char c;
        int x;
        cin >> c >> x;
        if(x % 2) mp1[c] ++ ;
        else mp2[c] ++ ;
    }

    dfs(0, 1);
    printf("%d", res);

    return 0;
}



lty2019
1天前

简单的AC自动机

C++ 代码

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

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int tr[N * S][26], cnt[N * S], ne[N * S], idx;
char str[M];
int q[N * S];

void insert(){
    int p = 0;

    for (int i = 0; str[i]; i ++ ){
        int t = str[i] - 'a';
        if(!tr[p][t]) tr[p][t] = ++ idx ;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build(){//AC自动机的构建
    int hh = 0, tt = -1;

    for (int i = 0; i < 26; i ++ ){
        if(tr[0][i])
        q[ ++ tt ] = tr[0][i];
    }

    while(hh <= tt){
        int t = q[hh ++ ];

        for (int i = 0; i < 26; i ++ ){
            int p = tr[t][i];

            if(p){
                int j = ne[t];
                while(j && !tr[j][i]) j = ne[j];
                if(tr[j][i]) j = tr[j][i];
                ne[p] = j;
                q[ ++ tt ] = p;
            }
        }
    }
}

int main(){

    int T;
    scanf("%d", &T);

    while (T -- ){
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(cnt, 0, sizeof cnt);
        idx = 0;

        int n;
        scanf("%d", &n);

        for (int i = 1; i <= n; i ++ ){
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ ){
            int t = str[i] - 'a';

            while(j && !tr[j][t]) j = ne[j];
            if(tr[j][t]) j = tr[j][t];

            int p = j;
            while(p){
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}

优化为Trie图

C++ 代码

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

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int tr[N * S][26], cnt[N * S], ne[N * S], idx;
char str[M];
int q[N * S];

void insert(){
    int p = 0;

    for (int i = 0; str[i]; i ++ ){
        int t = str[i] - 'a';
        if(!tr[p][t]) tr[p][t] = ++ idx ;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build(){
    int hh = 0, tt = -1;

    for (int i = 0; i < 26; i ++ ){
        if(tr[0][i])
        q[ ++ tt ] = tr[0][i];
    }

    while(hh <= tt){
        int t = q[hh ++ ];

        for (int i = 0; i < 26; i ++ ){
            int p = tr[t][i];

            if(!p) tr[t][i] = tr[ne[t]][i];//将节点直接赋为父节点的指针所指向节点的相同字符的子节点
            else{
                ne[p] = tr[ne[t]][i];//将节点的指针指向父节点所指向节点的具有相同字符的子节点
                q[ ++ tt ] = p;
            }
        }
    }
}

int main(){

    int T;
    scanf("%d", &T);

    while (T -- ){
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(cnt, 0, sizeof cnt);
        idx = 0;

        int n;
        scanf("%d", &n);

        for (int i = 1; i <= n; i ++ ){
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ ){
            int t = str[i] - 'a';
            j = tr[j][t];

            int p = j;
            while(p){
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 1282. 搜索关键词

lty2019
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int tr[N * S][26], cnt[N * S], ne[N * S], idx;
char str[M];
int q[N * S];

void insert(){
    int p = 0;

    for (int i = 0; str[i]; i ++ ){
        int t = str[i] - 'a';
        if(!tr[p][t]) tr[p][t] = ++ idx ;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build(){
    int hh = 0, tt = -1;

    for (int i = 0; i < 26; i ++ ){
        if(tr[0][i])
        q[ ++ tt ] = tr[0][i];
    }

    while(hh <= tt){
        int t = q[hh ++ ];

        for (int i = 0; i < 26; i ++ ){
            int p = tr[t][i];

            if(!p) tr[t][i] = tr[ne[t]][i];
            else{
                ne[p] = tr[ne[t]][i];
                q[ ++ tt ] = p;
            }
        }
    }
}

int main(){

    int T;
    scanf("%d", &T);

    while (T -- ){
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(cnt, 0, sizeof cnt);
        idx = 0;

        int n;
        scanf("%d", &n);

        for (int i = 1; i <= n; i ++ ){
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ ){
            int t = str[i] - 'a';
            j = tr[j][t];

            int p = j;
            while(p){
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

lty2019
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char s[M], p[N];
int ne[N];

int main(){

    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ ){
        while( j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ ){
        while( j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++ ;

        if(j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

lty2019
2天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str){
    int p = 0;

    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';

        if(!son[p][u]) son[p][u] = ++ idx ;
        p = son[p][u];
    }

    cnt[p] ++ ;
}

int query(char *str){
    int p = 0;

    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';

        if(!son[p][u]) return 0;
        p = son[p][u];
    }

    return cnt[p];
}

int main(){

    int n;
    scanf("%d", &n);

    while (n -- ){
        char op[2];
        scanf("%s%s", op, str);

        if(*op == 'I') insert(str);
        else printf("%d\n",query(str));
    }

    return 0;
}


活动打卡代码 AcWing 1884. COW

lty2019
2天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main(){

    int n;
    string s;
    cin >> n >> s;

    LL c = 0, co = 0, cow = 0;
    for(auto ch : s ){
        if(ch == 'C') c ++ ;
        else if(ch == 'O') co += c;
        else cow += co;
    }

    printf("%lld",cow);

    return 0;
}


活动打卡代码 AcWing 1904. 奶牛慢跑

lty2019
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
vector<int> a;

int main(){

    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ){
        int x, v;
        scanf("%d%d", &x, &v);
        while(a.size() && v < a.back()) a.pop_back();
        a.push_back(v);
    }

    printf("%d",a.size());

    return 0;
}


活动打卡代码 AcWing 1913. 公平摄影

lty2019
4天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

map<int, int> mp;
vector<PII> a;
int res;

int main(){

    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ){
        int x;
        char b;
        cin >> x >> b;
        a.push_back({x, ((b == 'H') << 1) - 1});
    } 

    sort(a.begin(), a.end());

    mp[0] = 0;
    int h = 1e9, g = 1e9, q = 0;
    for (int i = 0; i < n; i ++ ){
        int x = a[i].x;
        if(a[i].y == 1) h = min(h, x), res = max(res, x - h), g = 1e9;
        else g = min(g, x), res = max(res, x - g), h = 1e9;

        q += a[i].y;
        if(mp.find(q) == mp.end()) mp[q] = a[i + 1].x;
        else res = max(res, x - mp[q]);
    }

    printf("%d", res);

    return 0;
}


活动打卡代码 AcWing 1922. 懒惰的牛

lty2019
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

int n, k;
int res;

int main(){

    scanf("%d%d", &n, &k);

    vector<int> d(n), pre(n + 1);
    vector<PII> a(n);

    for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i].y, &a[i].x);

    sort(a.begin(), a.end());

    for (int i = 0; i < n; i ++ ) d[i] = a[i].x, pre[i + 1] = pre[i] + a[i].y;

    for (int i = 0; i < n; i ++ ){
        int x = d[i];
        int s = upper_bound(d.begin(), d.end(), x + k * 2) - d.begin();

        res = max(res, pre[s] - pre[i]);
    }

    printf("%d",res);

    return 0;
}


活动打卡代码 AcWing 1929. 镜子田地

lty2019
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char g[N][N];
int res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int d, int s){
    int nd;
    int nx, ny;
    if(g[x][y] == '/') nd = d ^ 1;
    else nd = d ^ 3;

    nx = x + dx[nd], ny = y + dy[nd];

    if(nx && nx <= n && ny && ny <= m)
       dfs(nx, ny, nd, s + 1 );
    else res = max(res, s);
}

int main(){

    scanf("%d%d", &n, &m);

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

    for(int i = 1; i <= m; i ++ ){
        dfs(1, i, 2, 1);
        dfs(n, i, 0, 1);
    }

    for (int i = 1; i <= n; i ++ ){
        dfs(i, 1, 1, 1);
        dfs(i, m, 3, 1);
    }

    printf("%d",res);

    return 0;
}