Codeforces div2 求助
  • 板块灌水区
  • 楼主_Fatalis_
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/5/1 00:33
  • 上次更新2023/10/28 02:32:06
查看原帖
Codeforces div2 求助
414231
_Fatalis_楼主2022/5/1 00:33

T2 我到底错哪里了呀 WA on 3

#include <cstdio>
#include <cstring>

#define abs(x) ((x) < 0 ? -(x) : (x))
#define max(x, y) ((x) < (y) ? (y) : (x))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define doit(x, j) (lst[x] == 0 ? 0 : fl[lst[x] - 1][j - 'a'])

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

    while (T--) {
        static char ch[2000001], fl[2000001][30], lst[200];
        static bool vis[200];
        scanf("%s", ch);
        int len = strlen(ch), mx, mn;
        bool flag = false;
        memset(fl, 0, min(sizeof(int) * (30) * (len + 20), sizeof(fl)));
        memset(lst, -63, sizeof(lst));
        memset(vis, 0, sizeof(vis));

        for (int i = 0; i < len; i++) {
            vis[ch[i]] = true;
        }

        fl[0][ch[0] - 'a'] = 1, lst[ch[0]] = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 'a'; j <= 'z'; j++) {
                fl[i][j - 'a'] = fl[i - 1][j - 'a'];
            }
            fl[i][ch[i] - 'a'] ++;
            if (lst[ch[i]] >= 0) {
                mx = -1e9, mn = 1e9;
                for (int j = 'a'; j <= 'z'; j++) {
                    if (vis[j]) {
                        mx = max(mx, fl[i][j - 'a'] - doit(ch[i], j));
                        mn = min(mn, fl[i][j - 'a'] - doit(ch[i], j));
                    }
                }
                    // printf("%d %d %d %d %d %d\n", lst[ch[i]], i, ch[i], mx, mn, fl[doit('a')][0]);

                if (mx != -1e9 && abs(mx - mn) >= 2) {
                    puts("NO");
                    flag = true;
                    break;
                }
            }
            lst[ch[i]] = i;
        }

        if (!flag) {
            puts("YES");
        }
    }
    return 0;
}
2022/5/1 00:33
加载中...