首页 > 其他分享 >暑假集训七[One，砖块，数字，甜圈]

暑假集训七[One，砖块，数字，甜圈]

时间：2022-08-21 19:55:31浏览次数：78  
标签：rt std int register tr 砖块 include 集训 甜圈

暑假集训七

您总算更新当天的东西了啊。

A.One

典型的约瑟夫问题，\(t<10，n \leq 1e7\)数据范围需要我们用线性算法。

考虑每次去掉一个人后都重新编号，把编号改为 \([0, n)\) 计算，最后剩下的那个数当前的编号一定为 \(0\)。

倒推，考虑一个个复活，草，所以可以推出来上一轮当前点 \(x\) 的编号为 \((n - i + i + x) \% i\)，这样就可以递推推到第一轮。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int t, n, pos;

inline int read(){
    int x = 0, f = 1;
    char c = getchar();

    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
} 

int main(){
    t = read();
    while(t--){
        pos = 0;
        n = read();

        for(register int i = 2; i <= n; i++)
            pos = (pos + n - i + 1) % i;
        
        printf("%d\n", pos + 1);
    }

    return 0;
}

B.砖块

模拟，不是很麻烦，考场代码贼长，最后 ctrl c，ctrl v 的时候少粘了两行，100 pts → 10 pts。

Code

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define Pair pair< int, int >
#define Make(x, y) make_pair(x, y)

using namespace std;

const int INF = 2147483647;
const int SIZE = 110, MAXN = 1010;
int n, k, len, shape, x, y, num;
int min_x, min_y, max_x, max_y;
char s[SIZE];
map< Pair, int> m;

inline int max(register int &a, register int &b){
    return a > b ? a : b;
}

inline int min(register int &a, register int &b){
    return a < b ? a : b;
}

void Modify_N(){
    int size;

    if(shape == 1){ //立着
        x = x, y = y + 1; //x 不变, y 向前了 1
        size = y + k - 1;
        for(register int i = y; i <= size; i++){
            Pair p = Make(x, i);
            m[p] ++;
        }
        shape = 3;
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
    }
    else if(shape == 2){ //横着
        x = x, y = y + 1;
        size = x + k - 1;
        for(register int i = x; i <= size; i++){
            Pair p = Make(i, y);
            m[p] ++;
        }
        shape = 2;
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
    }
    else if(shape == 3){ //竖着
        x = x, y = y + k;
        m[Make(x, y)] ++;
        shape = 1;
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
    }
}

void Modify_S(){
    int size;

    if(shape == 1){
        x = x, y = y - k;
        size = y + k - 1;
        for(register int i = y; i <= size; i++){
            Pair p = Make(x, i);
            m[p] ++;
        }
        shape = 3;
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
    }
    else if(shape == 2){
        x = x, y = y - 1;
        size = x + k - 1;
        for(register int i = x; i <= size; i++){
            Pair p = Make(i, y);
            m[p] ++;
        }
        shape = 2;
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
    }
    else if(shape == 3){
        x = x, y = y - 1;
        m[Make(x, y)] ++;
        shape = 1;
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
    }
}

void Modify_W(){
    int size;

    if(shape == 1){
        x = x - k, y = y;
        size = x + k - 1;
        for(register int i = x; i <= size; i++){
            Pair p = Make(i, y);
            m[p] ++;
        }
        shape = 2;
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
    }
    else if(shape == 2){
        x = x - 1, y = y;
        m[Make(x, y)] ++;
        shape = 1;
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
    }
    else if(shape == 3){
        x = x - 1, y = y;
        size = y + k - 1;
        for(register int i = y; i <= size; i++){
            Pair p = Make(x, i);
            m[p] ++;
        }
        shape = 3;
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
    }
}

void Modify_E(){
    int size;

    if(shape == 1){
        x = x + 1, y = y;
        size = x + k - 1;
        for(register int i = x; i <= size; i++){
            Pair p = Make(i, y);
            m[p] ++;
        }
        shape = 2;
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
    }
    else if(shape == 2){
        x = x + k, y = y;
        m[Make(x, y)] ++;
        shape = 1;
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
    }
    else if(shape == 3){
        x = x + 1, y = y;
        size = y + k - 1;
        for(register int i = y; i <= size; i++){
            Pair p = Make(x, i);
            m[p] ++;
        }
        shape = 3;
        min_x = min(min_x, x);
        max_x = max(max_x, x + k - 1);
        min_y = min(min_y, y);
        max_y = max(max_y, y + k - 1);
    }
}

void Clear(){
    num = 0;
    m.clear();
    min_x = min_y = INF;
    max_x = max_y = -INF;
}

int main(){
    scanf("%d", &n);
    while(n--){
        Clear();

        scanf("%d", &k);
        scanf("%s", s + 1);

        shape = 1; //1 是立着，2 是横着躺，3是竖着躺 
        x = 0, y = 0; //矩形左下角的坐标
        m[Make(x, y)] ++;
        len = strlen(s + 1);
        for(register int i = 1; i <= len; i++){
            if(s[i] == 'N') //向北走
                Modify_N();
            else if(s[i] == 'S')
                Modify_S();
            else if(s[i] == 'W')
                Modify_W();
            else if(s[i] == 'E')
                Modify_E();
        }

        for(register int i = min_x; i <= max_x; i++){
            for(register int j = min_y; j <= max_y; j++)
                num = max(num, m[Make(i, j)]);
        }

        if(shape == 1)
            printf("%d\n%d\n", x, y);
        else if(shape == 2){
            int size = x + k - 1;
            for(register int i = x; i <= size; i++)
                printf("%d ", i);
            puts("");
            for(register int i = 1; i <= k; i++)
                printf("%d ", y);
            puts("");
        }
        else if(shape == 3){
            int size = y + k - 1; 
            for(register int i = 1; i <= k; i++)
                printf("%d ", x);
            puts("");
            for(register int i = y; i <= size; i++)
                printf("%d ", i);
            puts("");
        }
        printf("%d\n", num);
    }

    return 0;
}

C.数字

不会，可以去看这里。

D.甜圈

用线段树维护哈希值。

考场上想到了，但是就剩十五分钟了没打完。

把 \(1,...,n\) 当做一个序列，同样，把每个甜甜圈经历的工序也当成一个序列，只有当两个序列哈希值相同的时候才算合法。

区间修改哈希值可以看做区间加法，当然需要修改的只有叶子节点，可以pushdown解决，再pushup更新区间内有多少合法的序列。

同时需要下放的还有新加的序列的长度，维护哈希值的时候要用。当更新了哈希值后不合法的序列还要减去。

最后记得扫一遍没下放下去的lazy标记。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>

#define ULL unsigned long long 

using namespace std;

const int Base = 233;
const int MAXN = 2e5 + 10;
int n, k, t;
ULL hash_std;
ULL power[MAXN];

inline int read(){
    int x = 0, f = 1;
    char c = getchar();

    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}

ULL Get_Hash(int k){
    ULL res = 1;

    for(register int i = 1; i <= k; i++)
        res = res * Base + i;

    return res;
}

void init(){
    power[0] = 1;
    for(register int i = 1; i <= n; i++)
        power[i] = power[i - 1] * Base;
}

struct Segment_Tree{
    struct Tree{
        int l, r;
        int sum;
        ULL val;
        ULL lazy_val;
        int lazy_num;
    }tr[MAXN << 2];

    inline int lson(int rt){
        return rt << 1;
    }

    inline int rson(int rt){
        return rt << 1 | 1;
    }

    inline void Pushup(int rt){
        tr[rt].sum = tr[lson(rt)].sum + tr[rson(rt)].sum;
    }

    inline void Pushdown(int rt){
        if(tr[rt].lazy_val || tr[rt].lazy_num){
            tr[lson(rt)].lazy_num += tr[rt].lazy_num;
            tr[rson(rt)].lazy_num += tr[rt].lazy_num;
            tr[lson(rt)].val = tr[lson(rt)].val * power[tr[rt].lazy_num] + tr[rt].lazy_val;
            tr[rson(rt)].val = tr[rson(rt)].val * power[tr[rt].lazy_num] + tr[rt].lazy_val;
            tr[lson(rt)].lazy_val = tr[lson(rt)].lazy_val * power[tr[rt].lazy_num] + tr[rt].lazy_val;
            tr[rson(rt)].lazy_val = tr[rson(rt)].lazy_val * power[tr[rt].lazy_num] + tr[rt].lazy_val;

            if(tr[lson(rt)].l == tr[lson(rt)].r && tr[lson(rt)].val == hash_std)
                tr[lson(rt)].sum++;
            if(tr[rson(rt)].l == tr[rson(rt)].r && tr[rson(rt)].val == hash_std)
                tr[rson(rt)].sum++;
            if(tr[lson(rt)].l == tr[lson(rt)].r && tr[lson(rt)].val != hash_std && tr[lson(rt)].sum)
                tr[lson(rt)].sum--;
            if(tr[rson(rt)].l == tr[rson(rt)].r && tr[rson(rt)].val != hash_std && tr[rson(rt)].sum)
                tr[rson(rt)].sum--;

            tr[rt].lazy_val = 0;
            tr[rt].lazy_num = 0;
        }
    }

    void Build(int rt, int l, int r){
        tr[rt].l = l;
        tr[rt].r = r;

        if(l == r){
            tr[rt].val = 1;
            tr[rt].sum = 0;
            return;
        }

        int mid = (l + r) >> 1;
        Build(lson(rt), l, mid);
        Build(rson(rt), mid + 1, r);

        Pushup(rt);
    }

    void Update(int rt, int l, int r, int data){
        if(tr[rt].l >= l && tr[rt].r <= r){
            tr[rt].lazy_num += 1;
            tr[rt].val = tr[rt].val * Base + data;
            tr[rt].lazy_val = tr[rt].lazy_val * Base + data;

            if(tr[rt].l == tr[rt].r && tr[rt].val == hash_std)
                tr[rt].sum++;

            return;
        }

        Pushdown(rt);

        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) Update(lson(rt), l, r, data);
        if(r > mid) Update(rson(rt), l, r, data);

        Pushup(rt);
    }

    void Get_Sum(int rt){
        if(tr[rt].l == tr[rt].r){
            if(tr[rt].val == hash_std)
                tr[rt].sum = 1;
            else if(tr[rt].sum)
                tr[rt].sum = 0;
            return;
        }

        Pushdown(rt);

        Get_Sum(lson(rt));
        Get_Sum(rson(rt));

        Pushup(rt);
    }
}S;

int main(){
    n = read(), k = read();
    t = read();
    init();
    hash_std = Get_Hash(k);

    S.Build(1, 1, n);
    for(register int i = 1; i <= t; i++){
        int l, r, x;
        l = read(), r = read(), x = read();
        S.Update(1, l, r, x);
    }

    S.Get_Sum(1);

    printf("%d\n", S.tr[1].sum);

    return 0;
}

标签：rt,std,int,register,tr,砖块,include,集训,甜圈
From： https://www.cnblogs.com/TSTYFST/p/16610671.html

相关文章

  • 暑期集训7
    130rank39T1:T2:暴力模拟T3T4：【甜圈】线段树(hash区间加乘或者直接维护区间信息)T4：给你n个盒子，初始为空，支持t个操作，每次(l,r,xi),表示在[l,r]区间编号的盒子有序放上x......
  • 暑假集训7(建议等我改完再点开)
    A.One用vector把out的及时删掉，然后就可以直接加位置了，STL真好用，不过它T了……#include<bits/stdc++.h>usingnamespacestd;intT,n;vector<int>a;inline......
  • 集训3/4总结
    这几次考试题难度和在家集训五天的难度差不多，但是考试状态好了很多，故成绩还看得过去。感觉基本集训几天第一次学的算法都没太学懂，还需要自己去复习。上新课的速度没我想的......
  • 集训总结
    集训总结收获学习了一些从未接触的数据结构：线段树，树状数组，单调栈，单调队列可以实现一些基本操作，但与灵活运用还有一定距离，也无法与其他算法相结合使用提升了图......
  • A层邀请赛6 && 暑假集训加试1
    A.菜暴力做法：2^n枚举哪些人是正向上菜的，然后记录答案。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=20;constin......
  • 2022暑假集训总结
    经过简介7月20日到达内江天立学校，在小学部的机房上课。这里没什么人，比较安静，也没有那么热，学习环境挺好的。开始是老姚给我们上的课，主要讲了tarjan，然后由几位学长讲课。期......
  • 状压DP-1815. 得到新鲜甜甜圈的最多组数
    问题描述有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前所有 甜甜圈都必须已经全部销售完毕。给你一个整数batchSi......
  • 2022暑假集训总结
    2022暑假集训总结收获做了██道题跟着多校联训学的时候，主要收获是学会了一些基本的暴力算法和一些以前不知道的算法概念后来高烧休息了几天回来以后主要的收获是考试......
  • 暑假集训6
    前两题只会打暴力，本来以为又要垫底了，结果还可以？A.接力比赛确实是背包，排序后每次跑上界为\(\sumw_i\),然后刚刚好卡过？？随机数据跑的还是挺快的code#include<cstring>......
  • 暑假集训六[接力比赛,树上竞技,虚构推理,记忆碎片]
    暑假集训六接力比赛我是真没想到这玩意还能跟背包扯上关系，学到了但这里写的不是题解的做法，这里写的是类似的一种解法考虑\(dp\)的定义\(dp[1/0][j]\)表示\(0\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99