暑假集训七

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

题面

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;
}