CSP-J/S2 2021 游记

· · 个人记录

占坑。

upd on 2021.10.25 16:14：先放一张在我自己动态里发过的聊天记录截图。

其他的次要信息有空再补，说不定直接就被咕咕了。

更一波题解。

CSP-J

A

看一眼数据范围就知道是数学题了。

首先假设我们带回去的 k=L。

那么留给我们的

L\mod n

那么考虑如何加大收益，一个显然的想法是使得我们的收益 =n-1。

不难想到计算一个“差距”：

x=(n-1)-(L\mod n)

然后看一看，如果这个“差距”离咱们的上界 R 还很远，就肯定能做到。

反之就是“差距”过大，那么就考虑带回去的越多越好就好啦 \sim

#include<cstdio>
int init(){
    char c = getchar();
    int x = 0, f = 1;
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = (x << 1) + (x << 3) + (c ^ 48);
    return x * f;
}
void print(int x){
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int main(){
    int n = init(), L = init(), R = init();
    int x = (n - 1) - L % n;
    if (L + x <= R)
        print(n - 1), putchar('\n');
    else
        print(R % n), putchar('\n');
}

B

观察数据范围，发现给的 n 是平方级别的数据范围。

但是 q 是线性或者带一个 \log 的范围，于是又观察到操作 1 的执行次数 \le5000 次。

所以说我们就可以得到：

每次操作 1 之后线性扫描一遍，之后 O(1) 或者 O(\log) 查询答案是我们可以接受的复杂度。

首先考虑操作 1 之后，给我们带来的影响是一遍排序，而已知最优排序是 O(n\log n)，简单算一下之后发现不太能过。

考虑桶排，如果我们把有贡献的数字离线下来，顶多不会超过 8000+5000=13000 个数。

然后离散化一下可以缩小值域，至此我们每次操作 1 之后是 O(<13000) 的复杂度就能排序完整个序列。

注意到这个有重复元素，所以再多记录一些信息就好了。

具体而言，需要知道每个数字在对应位置上是第几次出现，还是由于 n\le8000 所以这些信息全部都可以线性扫描维护，每次操作全部更新一遍，这就不难了。

详见代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define findb(x) std::lower_bound(b+1,b+1+len,x)-(b)
#define findc(x) std::lower_bound(c+1,c+1+c[0],x)-(c)
inline int in();
inline void wr(int);
const int N=(int)8e3+5,M=(int)5e3+5,K=(int)2e5+5;
int a[N],b[N+M],c[N];
struct Node{
    int tp,x,v;
}s[K];
int tong[N+M],len,times[N+M],pos[N];
// times[i]: i 出现了几次
// pos[i]: a[i] 第几次出现
inline void translate();
int main(int argc,char**argv){
#ifndef ONLINE_JUDGE
    freopen("7910.in","r",stdin);
    freopen("7910.out","w",stdout);
#endif
    register int n=in(),q=in();
    for(register int i=1;i<=n;++i)
        b[i]=a[i]=in();
    len=n;
    for(register int i=1;i<=q;++i){
        s[i].tp=in();
        if(s[i].tp==1){
            s[i].x=in(),s[i].v=in();
            b[++len]=s[i].v;
        }
        else
            s[i].x=in();
    }
    std::stable_sort(b+1,b+1+len);
    len=std::unique(b+1,b+1+len)-(b+1);
    for(register int i=1;i<=n;++i)
        a[i]=findb(a[i]);
    for(register int i=1;i<=q;++i)
        if(s[i].tp==1)
            s[i].v=findb(s[i].v);
    // 然后咋写……我想想。。。
    for(register int i=1;i<=n;++i)
        ++tong[a[i]];
    memset(times,0,sizeof(times));
    for(register int i=1;i<=n;++i)
        pos[i]=++times[a[i]];
    translate();
    for(register int i=1;i<=q;++i)
        if(s[i].tp==2){
            // 查询
            register int id=findc(a[s[i].x]);
            wr(id+pos[s[i].x]-1),putchar('\n');
            //  1 2 3 4 5
            //  5 5 5 5 5
            //  ^
        }
        else{
            // 修改
            --tong[a[s[i].x]];
            a[s[i].x]=s[i].v;
            ++tong[a[s[i].x]];
            memset(times,0,sizeof(times));
            for(register int i=1;i<=n;++i)
                pos[i]=++times[a[i]];
            translate();
        }
}
inline void translate(){
    c[0]=0;
    for(register int i=1;i<=len;++i){
        register int x=tong[i];
        while(x--)
            c[++c[0]]=i;
    }
}
inline int in(){
    register char c=getchar();
    register int x=0,f=1;
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c&15);
    return x*f;
}
inline void wr(int x){
    if(x<0)putchar('-'),x=-x;
    if(x/10)wr(x/10);
    putchar(x%10+'0');
}

C

小型模拟题。

感觉出题人挺良心，没有什么很大的坑点或者不注意就挂的地方。

这都写不对只能说明代码能力有待提升了。

首先观察可知，原题可以分为两个部分：

  1. 检查一个地址是否合法；
  2. 加入一个地址。

后者可以用 map 维护，是基础操作，所以关键点就落在了前者上。

首先是一波最基础的判断：

然后再模仿我们的快速读入写法，读入的时候注意判断一下前导零就可以了。

注意到本题数据范围，有可能某些写法需要开 long long，但是统计答案的时候动态检验，不合理即退出，这样就不是很困难，也不需要开 long long。

详见代码实现部分吧。

#include<map>
#include<cstdio>
#include<string>
#include<iostream>
const int N=(int)1e3+5;
std::map<std::string,int>map;
inline int in();
inline bool check(std::string);
int main(int argc,char**argv){
#ifndef ONLINE_JUDGE
    freopen("7911.in","r",stdin);
    freopen("7911.out","w",stdout);
#endif
    std::ios::sync_with_stdio(false);
    register int n=in();
    for(register int i=1;i<=n;++i){
        std::string op,ad;
        std::cin>>op>>ad;
        if(!check(ad))std::cout<<"ERR\n";
        else if(op[0]=='S'){
            if(map.count(ad))
                std::cout<<"FAIL\n";
            else{
                map[ad]=i;
                std::cout<<"OK\n";
            }
        }
        else{
            if(map.count(ad)){
                std::cout<<map[ad]<<std::endl;
            }
            else{
                std::cout<<"FAIL\n";
            }
        }
    }
}
inline bool check(std::string str){
    register int cnt1=0,cnt2=0;
    register int len=str.size();
    for(register int i=0;i<len;++i){
        if(str[i]=='.')
            ++cnt1;
        if(str[i]==':')
            ++cnt2;
        if(cnt2==1&&cnt1<3)return 0;
        // 冒号必须出现在点之后
        if((str[i]<'0'||str[i]>'9')&&(str[i]!='.')&&(str[i]!=':'))
            return 0;
        // 出现了我也不知道是啥的奇怪符号
    }
    if(cnt1!=3||cnt2!=1)return 0;
    int num[5]={-1,-1,-1,-1,-1};
    register int now=0;
    str[len]='.';
    for(register int i=0;i<len;++i){
        if(num[now]==-1&&(str[i]<'0'||str[i]>'9'))
            // 非数字
            return 0;
        else if(num[now]==-1&&(str[i]=='0'&&str[i+1]!='.'&&str[i+1]!=':'))
            return 0; // 前导 0
        else if(str[i]<'0'||str[i]>'9')
            // 一个断点
            ++now;
        else if(num[now]==-1)
            num[now]=(str[i]&15);
        else
            num[now]=(num[now]<<1)+(num[now]<<3)+(str[i]&15);
            // 普通数字读入
        if(num[now]>65535)return 0;
    }
    register bool tp1=(0<=num[0]&&num[0]<=255);
    register bool tp2=(0<=num[1]&&num[1]<=255);
    register bool tp3=(0<=num[2]&&num[2]<=255);
    register bool tp4=(0<=num[3]&&num[3]<=255);
    register bool tp5=(0<=num[4]&&num[4]<=65535);
    return tp1&&tp2&&tp3&&tp4&&tp5;
}
inline int in(){
    register int x;
    std::cin>>x;
    return x;
}

D

听说还挺考细节，瞄了眼题还没来得及写，那就先咕着。反正链表模拟题应该不难大家都会。

总结

看来今年 CSP-J 又秉承了一次 A < B < D < C 的传统。