~~为什么我觉得今天的题这么水~~，恐怕要被打脸 qwq，是不是我题读错了....

考试

rank

题意有点问题，我赌输出 $k$ 个答案是对的 qwq

JZOJ 评测吃了我 50 分

Test's

Code

：100%

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 5e6 + 5;
const int MAXM = 1e5 + 5;

int n, a[MAXN], k;
int main() {
    scanf ("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &a[i]);
    }
    
    sort (a + 1, a + n + 1);
    
    for (int i = 1; i <= k; i++) {
        printf ("%d ", a[i]);
    }
    return 0;
}

seek

考试的时候用 $KMP$ 生成 next[i] 数组的方式，再加了一个检测，这样瞎搞了以后应该是 0 分吧 qwq

瞎搞搞了 20 分 qwq

好像暴力也有 40 分，早知道分段写了 qwq，说不定可以 60 分 > _ <

上面是闲话： $\Uparrow \Uparrow$

这道题有两种方法，第一种就是 $KMP$ ，但是用来做这种变形我不会 qwq，我到现在只会生成普通的 next[i] ....

第二种是直接生成前缀、后缀哈希，然后再枚举一遍，扫 3 遍就可以了 qwq

我就喜欢像第二种这种简单粗暴的方法......

Test's

Code

：20%

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 4e5 + 5;

char ch[MAXN], len, kmp[MAXN];

bool book[MAXN];

int main() {
    scanf ("%s", ch);
    len = strlen (ch);
    
    int k=0;
    for(int i = 1; i < len; i++){
        
        if (k && ch[i] != ch[k]) {
            bool flag = true;
            for (int j = 0; j < k; j++) {
                if (ch[j] != ch[len - k + j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                book[k] = true;
            }
        }
        
        while(k && ch[i] != ch[k])
            k = kmp[k];
        if(ch[i] == ch[k]) {
            kmp[i + 1] = ++k;
        }
    }
    
    bool flag = true;
    for (int j = 0; j < k; j++) {
        if (ch[j] != ch[len - k + j]) {
            flag = false;
            break;
        }
    }
    if (flag) {
        book[k] = true;
    }
    
    //book[k] = true;
    book[len] = true;
    
    for (int i = 1; i <= len; i++) {
        if (book[i]) {
            printf ("%d ", i);
        }
    }
    return 0;
}

Fixed

Code

：100%（哈希）

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 4e5 + 5;

unsigned long long len, lhash[MAXN], rhash[MAXN];

char ch[MAXN];

int main() {
    scanf ("%s", ch + 1);
    len = strlen (ch + 1);
    
    for (int i = 1; i <= len; i++) {
        lhash[i] = (lhash[i - 1] * 17 + ch[i] - 'a' + 1);
    }
    unsigned long long t = 1;
    for (int i = len; i >= 1; i--) {
        rhash[i] = ((ch[i] - 'a' + 1) * t + rhash[i + 1]);
        t = t * 17;
    }
    
    for (int i = 1; i <= len; i++) {
        if (lhash[i] == rhash[len - i + 1]) {
            printf ("%d ", i);
        }
    }
    return 0;
}

这题有一些细节，就是进行哈希加密的时候，需要选质数，不然可能会有问题.......

这题不知道为什么我取模之后会出错，可能哈希就是不能取模吧......

可能因为我太菜了.....

pot

打了一个线段树，但是没有打完，最后因为答案要求不能全取，然后我就一直想怎么用 $O(\log n)$ 的方法搜出答案 qwq

这题用线段树维护最大字段和和最小子段和就可以了。因为不能取一整个环，所以最后答案在 $(1,n]$ 和 $[1,n)$ 这两个区间中取一个 $Max$ 就可以了。对于这个最长子段和，@lzc 是这么求的，直接引用了。。。（不会侵权吧。。。）

在线段树每个结点上维护这个区间的和、最大前缀和、最大后缀和、最大子段和。那么合并儿子信息的时候，区间和很简单；最大前缀和有两种选择，一种是左儿子的区间和 + 右儿子的最大前缀和，一种是左儿子的最大前缀和；后缀和类似；最大子段和要么是左儿子的最大子段和，要么是右儿子的最大子段和，要么是左儿子的最大后缀和 + 右儿子的最大前缀和。
—— lzc

嗯，就酱紫吧？

Test's

Code

：0%

#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int INF = 2e9;
int n, m, rt, a[MAXN << 1];

struct Tree {
    #define lson (x << 1)
    #define rson (x << 1) + 1
    int size[MAXN << 2], Max[MAXN << 2], num[MAXN << 2], sum[MAXN << 2];
    
    inline void pushup_normal (int x) {
        size[x] = size[lson] + size[rson];
        sum[x] = sum[lson] + sum[rson];
        Max[x] = max (Max[lson], Max[rson]);
        Max[x] = max (Max[x], sum[x]);
        return;
    }
    
    inline void pushup_ans (int x) {
        size[x] = size[lson] + size[rson];
        Max[x] = max (Max[lson], Max[rson]);
        return;
    }
    
    void insert (int x, int l, int r) {
        if (l == r) {
            size[x] = 1;
            sum[x] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        insert (lson, l, mid);
        insert (rson, mid, r);
        if (r - l + 1 > n) {
            pushup_ans (x);
        }
        
        else {
            pushup_normal (x);
        }
        return;
    }
    
    void Change (int x, int l, int r, int k, int val) {
        if (l == r) {
            Max[x] = val;
            sum[x] = val;
            return;
        }
        
        int mid = (l + r) >> 1;
        if (mid < k) {
            Change (rson, mid, r, k, val);
        }
        else {
            Change (lson, l, mid, k, val);
        }
        pushup_normal (x);
        return;
    }
    
};
Tree T;

int main() {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &a[i]);
        a[n + i] = a[i];
    }
    T.insert (rt, 1, 2 * n);
    
    scanf ("%d", &m);
    for (int i = 1; i <= m; i++) {
        int k, val;
        scanf ("%d%d", &k, &val);
        T.Change (rt, 1, 2 * n, k, val);
        T.Change (rt, 1, 2 * n, n + k, val);
        int MAX = -INF;
        for (int i = 1; i <= n; i++) {
            MAX = max (MAX, T.query (rt, 1, 2 * n, i, n + i - 2));
        }
        printf ("%d\n", MAX);
    }
    return 0;
}

Fixed

Code

：

#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;

struct Tree {
    #define lson (x << 1)
    #define rson (x << 1) + 1
    int presum_Max[MAXN << 2], sufsum_Max[MAXN << 2], Max[MAXN << 2];
    int presum_Min[MAXN << 2], sufsum_Min[MAXN << 2], Min[MAXN << 2];
    int sum[MAXN << 2], Min_val[MAXN << 2], rt;
    
    inline void pushup (int x) {
        presum_Max[x] = max (presum_Max[lson], sum[lson] + presum_Max[rson]);
        sufsum_Max[x] = max (sufsum_Max[rson], sufsum_Max[lson] + sum[rson]);
        presum_Min[x] = min (presum_Min[lson], sum[lson] + presum_Min[rson]);
        sufsum_Min[x] = min (sufsum_Min[rson], sufsum_Min[lson] + sum[rson]);
        sum[x] = sum[lson] + sum[rson];
        Max[x] = max (Max[lson], Max[rson]);
        Max[x] = max (Max[x], sufsum_Max[lson] + presum_Max[rson]);
        Min[x] = min (Min[lson], Min[rson]);
        Min[x] = min (Min[x], sufsum_Min[lson] + presum_Min[rson]);
        Min_val[x] = min (Min_val[lson], Min_val[rson]);
        return;
    }
    
    void insert (int x, int l, int r) {
        if (l == r) {
            scanf ("%d", &sum[x]);
            presum_Max[x] = sum[x];
            sufsum_Max[x] = sum[x];
            presum_Min[x] = sum[x];
            sufsum_Min[x] = sum[x];
            Max[x] = sum[x];
            Min[x] = sum[x];
            Min_val[x] = sum[x];
            return;
        }
        int mid = (l + r) >> 1;
        insert (lson, l, mid);
        insert (rson, mid + 1, r);
        pushup(x);
        return;
    }
    
    void change (int x, int l, int r, int k, int val) {
        if (l == r) {
            sum[x] = val;
            presum_Max[x] = val;
            sufsum_Max[x] = val;
            presum_Min[x] = val;
            sufsum_Min[x] = val;
            Max[x] = val;
            Min[x] = val;
            Min_val[x] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (k > mid) {
            change (rson, mid + 1, r, k, val);
        }
        else {
            change (lson, l, mid, k, val);
        }
        pushup(x);
        return;
    }
};
Tree T;

int n, m;
int main() {
    scanf ("%d", &n);
    T.rt = 1;
    T.insert (T.rt, 1, n);
    
    scanf ("%d", &m);
    for (int i = 1; i <= m; i++) {
        int k, val;
        scanf ("%d%d", &k, &val);
        T.change (T.rt, 1, n, k, val);
        int temp;
        if (T.sum[T.rt] != T.Max[T.rt]) {
            temp = T.Max[T.rt];
        }
        else {
            temp = T.sum[T.rt] - T.Min_val[T.rt];
        }
        printf ("%d\n", max (temp, T.sum[T.rt] - T.Min[T.rt]));
    }
    return 0;
}

这题改了很久，有一点，需要注意。因为不能取全部，所以如果最后有两种情况：

最长子段和 $=$ 总和：答案有两种情况取 $Max$ ：总和 $-$ 最小的单点值；总和 $-$ 最小子段和。
最长子段和 $\not=$ 总和：答案有两种情况取 $Max$ ：最长子段和；总和 $-$ 最小子段和（最长子段和的区间和最小子段和的区间可能在环的交界处）

游戏节目(show)

算了一下， $C_{34}^{17} \approx 5 \times 10^7$ ，如果剪枝可以的话，应该可以卡过 qwq（这是我考试后口胡的，不用管）

为什么只有 40 分鸭 qwq，成功翻车......

这道题远没有我考试时想的那么简单....

好像说要用什么树套树，折半搜索......信息量有点大，以后再订这道题.....

Test's

Code

：40%

#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 40;
const int MAXK = 7;

long long n, k, ans, a[MAXN], b[MAXN], c[MAXN];
long long A, B, C;

void dfs (int now, int K, int last, int cnt) {
    if (now >= cnt) {
        if (A > B && A > C) {
            ans ++;
        }
        return;
    }
    
    for (int i = last + 1; i <= n - K + 1; i++) {
        A += a[i];
        B += b[i];
        C += c[i];
        dfs (now + 1, K - 1, i, cnt);
        A -= a[i];
        B -= b[i];
        C -= c[i];
    }
    return;
}
int main () {
    freopen ("show.in", "r", stdin);
    freopen ("show.out", "w", stdout);
    
    scanf ("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &b[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &c[i]);
    }
    
    for (int i = k; i <= n; i++) {
        dfs (0, i, 0, i);
    }
    
    printf ("%lld\n", ans);
    fclose (stdin);
    fclose (stdout);
    return 0;
}

2019.8.13 集训解题报告

2019.8.13 集训解题报告

考试

rank

seek

pot

游戏节目(show)