好不容易,现场怼出只有30人过的C题,然后我看了队友D题tle的代码,让我以为不能暴力写D题,思路被带偏,回不到正轨了…其实是队友用了这个东西我却没发现

2019牛客暑期多校训练营(第六场)-LMLPHP
CPalindrome Mouse

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10, N = 1e5 + 10;
queue<int> q;
int rt[maxn], ls[maxn * 50], rs[maxn * 50], sum[maxn * 50], cnt;
#define mid (l + r) / 2
void up(int &o, int pre, int l, int r, int k) {
    o = ++cnt;
    sum[o] = sum[pre] + 1;
    ls[o] = ls[pre];
    rs[o] = rs[pre];
    if (l == r)
        return;
    if (k <= mid)
        up(ls[o], ls[pre], l, mid, k);
    else
        up(rs[o], rs[pre], mid+ 1, r, k);
}
int qu(int o, int l, int r, int k) {
    if (l == r)
        return sum[o];
    if (k <= mid)
        return qu(ls[o], l, mid, k);
    return qu(rs[o], mid + 1, r, k);
}
struct ptree{
    char s[maxn];
    int next[maxn][26],fail[maxn],cnt[maxn],len[maxn], d[maxn];
    int last,n,p;
    long long res;
    ll ans = 0;
    inline int newnode(int l){
        cnt[p]=0;
        len[p]=l;
        memset(next[p], 0, sizeof(next[p]));
        return p++;
    }
    inline void init(){
        n = last = p = ans = 0;
        newnode(0),newnode(-1);
        s[n]=-1;
        fail[0]=1;
    }
    inline int FL(int x){
        while(s[n-len[x]-1]!=s[n]) x=fail[x];
        return x;
    }
    void add(char c){
        c-='a';
        s[++n]=c;
        int cur=FL(last);
        if(!next[cur][c]){
            int now=newnode(len[cur]+2);
            cnt[now] = 1;
            rt[now] = rt[cur];
            int FF = next[FL(fail[cur])][c];
            fail[now]=next[FL(fail[cur])][c];
            next[cur][c]=now;
            while (FF > 1) {
                if (qu(rt[now], 1, N, FF))
                    break;
                up(rt[now], rt[now], 1, N, FF);
                FF = fail[FF];
            }
            up(rt[now], rt[now], 1, N, now);
            ans += sum[rt[now]] - 1;
        }
        last=next[cur][c];
    }
} p;
char s[maxn];
int main(){
    int T, Case = 0;
    scanf("%d", &T);
    while (T--) {
        scanf("%s",s);
        p.init();
        cnt = 0;
        for (int i = 0; s[i]; i++)
            p.add(s[i]);
        printf("Case #%d: %lld\n", ++Case, p.ans);
    }
}

DMove
就是这个暴力,让我翻了历史上最大的一次车

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, k, a[maxn];
int ok(int m) {
    multiset<int> s;
    multiset<int> ::iterator it;
    for (int i = 1; i <= n; i++)
        s.insert(a[i]);
    for (int i = 1; i <= k; i++) {
        int v = m;
        while (v) {
            it = s.upper_bound(v);//查找第一个大于v的位置
            if (it == s.begin())//s最小的数大于v
                break;
            it--;
            v -= *it;
            s.erase(it);
            if (s.empty())
                return 1;
        }
    }
    return 0;
}
int main() {
    int T, Case = 0;
    cin>>T;
    while (T--) {
        int mx = 0, sum = 0;
        cin>>n>>k;
        for (int i = 1; i <= n; i++) {
            cin>>a[i];
            sum += a[i];
            mx = max(mx, a[i]);
        }
        int limit = max(mx, sum / k);
        for (int i = limit;; i++)
        if (ok(i)) {
            printf("Case #%d: %d\n", ++Case, i);
            break;
        }
    }
}

EAndrogynos

2019牛客暑期多校训练营(第六场)-LMLPHP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2010;
char s[maxn][maxn];
int main() {
    int T, Case = 0;
    scanf("%d", &T);
    while (T--) {

        int n;
        scanf("%d", &n);
        printf("Case #%d: ", ++Case);
        if (n % 4 > 1) {
            puts("No");
            continue;
        }
        puts("Yes");
        int m = n / 4 * 4;
        for (int i = 1; i <= n; i++) {
            s[i][n + 1] = '\0';
            for (int j = 1; j <= n; j++)
                s[i][j] = '0';
            if (i % 4 == 1 || i % 4 == 0) {
                if (m != n && i == n) {
                    for (int j = 1; j <= m; j += 4)
                        s[i][j] = s[i][j + 4 - 1] = '1';
                    continue;
                }
                if (i % 4 == 1)
                    s[i][i + 1] = '1';
                else
                    s[i][i - 1] = '1';
                for (int j = 1; j <= n; j++)
                    if ((j + 3) / 4 < (i + 3) / 4) {
                        if (j % 4 <= 1)
                        s[i][j] = '1';
                    }
                    else if ((j + 3) / 4 > (i + 3) / 4)
                        s[i][j] = '1';

            }
            else {
                s[i][i - 1] = s[i][i + 1] = '1';
                for (int j = 1; (j + 3) / 4 < (i + 3) / 4; j += 4)
                    s[i][j] = s[i][j + 3] = '1';

            }
        }
        for (int i = 1; i <= n; i++)
            puts(s[i] + 1);
        for (int i = 0; i < n / 4; i++) {
            int a = 2 + i * 4;
            int b = 4 + i * 4;
            int c = 1 + i * 4;
            int d = 3 + i * 4;
            printf("%d %d %d %d", a, b, c, d);
            if (i == n / 4 - 1) {
                if (n == m)
                    puts("");
                else
                    printf(" ");
            }
            else
                printf(" ");
        }
        if (n != m)
            printf("%d\n", n);
    }
}

08-06 11:23