2019.8.13 集训解题报告
浏览 7593 | 评论 0 | 字数 8445
Snowflake_Pink
2019年08月13日
  • 为什么我觉得今天的题这么水,恐怕要被打脸 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;
    }
    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/83/
    最后修改时间:2024-07-02 18:04:24
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论