写在前面：随便刷到的好题

ABC288D

有差分和剩余系的思想，但是不用真的差分，把整个序列按 分类，会发现，每次只改变每一类数中的一个，所以要想把所有数消成 ，只需要区间内每类数之和相等即可，挨个消，消到最后，一定可以整成 这种形式

P9753

跟括号匹配一点都不一样

首先要找两个相邻且相同的字符，然后才能往外消，不妨设 为第 个字符往后最小的 ，使 可被消除，然后 表示从第 个字符跳多少段最小可消除段才能到不能跳为止，答案就是

至于 转移，需要只需要再记录一个 表示从 开始跳可消除段，跳到 这个字符的所在下标，倒序遍历就行了

P5369

数据范围可以看出来是状压

考虑最大前缀和有什么性质，假设从 加到 为最大前缀和（ 为满足条件的最大 ） ：

  1. 在 区间内，所有的后缀和都 ，除了整体，整体可以 ，因为必须要算上一个数

  2. 在 区间内 ，所有的前缀和都

所以对于每个状态 ，我们记录用全集合内的元素可以满足 1. 的方案数 以及可以满足 2. 的方案数

对于 的特殊情况，我们可以多开一维 ，记录是否整体

关于转移，用向外转移，即 就不会漏辣

2022ICPC_Nanjing_D

乐子题，打表看出来最后一定会成为一个不变的序列，只有第一个数与别的数不同，是其他数的两倍，那个 可以看成无限次

2022CCPC_Guangzhou_H

直接想嘛，记录每个序列里没有的数的奇偶性，A一定填奇数更优，B一定填偶数更优，直接模拟

2022ICPC_Jinan_E

每次滑动进出的元素奇偶性相同，考虑根据奇偶性一定相同的元素分块，有 个大小为 的块，有 个大小为 的块，解 这个方程，用exgcd求出一个特殊解 好了，然后通解就是 ，根据限制分别求出来 的取值范围，看看有无交集

是个小nb题

代码放这了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//头文件
int t;
int n,k,p,q;

int exgcd(int &x,int &y,int a,int b){
    if(b==0){x=1,y=0;return a;}
    int g=exgcd(y,x,b,a%b);
    y-=(a/b)*x;
    return g;
}

int main(){

    read(t);
    while(t--){
        read(n),read(k);
        int a,b,x,y;

        a=n/k+1,b=n/k;
        p=n%k,q=k-p;
        int g=exgcd(x,y,a,b);
        if((n/2)%g!=0){cout<<"No"<<endl;continue;}

        x*=(n/2)/g;
        y*=(n/2)/g;
        
        int l1=-x/b,l2=(y-q)/a;
        if(l1*b+x<0) l1++;
        if(y-l2*a>q) l2++;
        int r1=(p-x)/b,r2=y/a;
        if(r1*b+x>p) r1--;
        if(y-r2*a<0) r2--;
        if(max(l1,l2)<=min(r1,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

    return 0;
}

2022CCPC_Mianyang_G

纯模拟，但是有意思的地方在于对时间复杂度的预测，为什么暴力能过，因为在一个 的排列里面，极值最多只可能有 个，所以模拟最劣复杂度为

本文采用CC-BY-SA-3.0协议，转载请注明出处
作者: wsy_jim