第一题：[CSP-J 2021] 分糖果

来源：CCF: 难度：入门

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,l,r,candy=0,sum,maxn=-1;
    cin>>n>>l>>r;
    for(int i=l;i<=r;i++)
    {
        sum=i;
        sum%=n;
        maxn=max(maxn,sum);
        if(maxn==n-1)
            break;
    }
    cout<<maxn;
    return 0;
}

思路：待补

第二题[CSP-J 2021] 插入排序

来源：CCF: 难度：普及-

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=8005;
int n,q;
int t[MAXN];
struct node{
    int pre,id;
}a[MAXN];
bool cmp(node x,node y){
    if(x.pre!=y.pre) return x.pre<y.pre;
    return x.id<y.id;
}//两个元素之间的优先级
int main(){
    //freopen("sort.in","r",stdin);
    //freopen("sort.out","w",stdout);
    scanf("%d%d",&n,&q); 
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].pre);
        a[i].id=i;
    }//输入
    sort(a+1,a+n+1,cmp);//排序
    for(int i=1;i<=n;i++)
        t[a[i].id]=i;
    for(int i=1;i<=q;i++){
        int opt,x,v;
        scanf("%d",&opt);
        if(opt==1){//单点修改
            scanf("%d%d",&x,&v);//Ax->v
            a[t[x]].pre=v;
            for(int j=n;j>=2;j--)
                if(cmp(a[j],a[j-1])){
                    node kkksc03=a[j];
                    a[j]=a[j-1];
                    a[j-1]=kkksc03;
                }//前扫
            for(int j=2;j<=n;j++)
                if(cmp(a[j],a[j-1])){
                    node kkksc03=a[j];
                    a[j]=a[j-1];
                    a[j-1]=kkksc03;
                }//后扫
            for(int i=1;i<=n;i++)
                t[a[i].id]=i;//更新关系
        }
        else{
            scanf("%d",&x);
            printf("%d\n",t[x]);
        }
    }
    return 0;
}

思路：可以发现，对于一个已经有序的数列，单点修改一个值，我们可以通过前后冒泡各一次来保持有序，举个例子：

原序列为 1,1,4,5,6,71,1,4,5,6,7，修改为 1,1,9,5,6,71,1,9,5,6,7。

我们可以从前往后冒泡，再次维持了数列的有序。这样的操作是 \mathcal{O}(n)O(n) 的。

同样的，我们可以维护一个有序数列，并记录原下标与先下标之间的关系（用数组记录），每次修改后更新这种关系。

这样，修改操作是 O(n) 的，查询是 O(1) 的。

第三题：[CSP-J 2021] 小熊的果篮

来源：CCF: 难度：普及/提高-

#include<bits/stdc++.h>
#include<set>
using namespace std;
//stl
//stack queue string vector sort
//set 集合 去重
//存储数据，以及可以非常快的删除元素

set<int> s[2];//建立set数组
//set[0]存储序列1
//set[1]存储序列2
int n; 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        s[t].insert(i);
    }
    while(1)
    {
        if(s[0].empty())
        {
            for(auto it=s[1].begin();it!=s[1].end();it++)
            {
                cout<<*it<<endl;
            }
            break;
        }
        else if(s[1].empty())
        {
            for(auto it=s[0].begin();it!=s[0].end();it++)
            {
                cout<<*it<<endl;
            }
            break;
        }


        //tmp可以计算出哪个水果的首位编号最小 
        int tmp;
        if(*s[0].begin()<*s[1].begin()) 
            tmp=0;
        else
            tmp=1;
        int last_ad=0;//存储上一个元素的编号
        while(true)
        {
            //建立一个指针, 迭代器
            //指向stl容器的类似于指针的东西 
            //指向容器中比last_ad大的第一个编号
            auto it = s[tmp].upper_bound(last_ad);
            if(it==s[tmp].end())
                break;
            cout<<*it <<' ';
            last_ad=*it;
            s[tmp].erase(it);
            tmp=!tmp;   
        } 
        cout<<endl;
    }

    return 0;
}

解释：在代码注释里

第四题：[CSP-J 2021] 网络连接

来源：CCF: 难度：普及/提高-

第一解法：

#include<bits/stdc++.h>
using namespace std;

int n;
string a,b;
map<string,int> ad;
void ser(string t,int x);
void cli(string t);
bool check(string t);

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        if(!check(b))
        {
            cout<<"ERR"<<endl;
        }
        else if(a=="Server")
            ser(b,i);
        else if(a=="Client")
            cli(b);
    }

    return 0;
}
bool check(string t)
{
    int cnt1=0,cnt2=0;
    int cntnum=0;
    int len=t.size();
    for(int i=0;i<len;i++)
    {
        if( t[i]>='0'&&t[i]<='9' )
        {
            if(t[i]=='0'&&isdigit(t[i+1]))
                return 0;
            int num=0;
            cntnum++;
            while(isdigit(t[i]))
            {
                num=num*10+t[i]-'0';
                i++;
            }
            if(cntnum<=4&&num>255)
                return 0;
            if(cntnum==5&&num>65535)
                return 0;
            i--;
        }
        else if(t[i]=='.')
        {
            if(cnt2) return 0;
            cnt1++;
        }
        else if(t[i]==':')
            cnt2++;
    }

    if(cnt1!=3||cnt2!=1||cntnum!=5)
        return 0;

    return 1;
}
void ser(string t,int x)
{
    if(ad[t]==0)
    {
        cout<<"OK"<<endl;
        ad[t]=x;
    }
    else
        cout<<"FAIL"<<endl;
}
void cli(string t)
{
    if(ad[t]==0)
        cout<<"FAIL"<<endl;
    else
        cout<<ad[t]<<endl;
}

第二解法：

#include<bits/stdc++.h>
using namespace std;
const int N=105;
map<string,int>ad;
bool check(char t[]);
void ser(string t,int x)
{
    if(ad[t]==0)
    {
        cout<<"OK"<<endl;
        ad[t]=x;
    }
    else
        cout<<"FAIL"<<endl;
}
void cli(string t)
{
    if(ad[t]==0)
        cout<<"FAIL"<<endl;
    else
        cout<<ad[t]<<endl;
}
char a[N],b[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        string strb(b);
        if(!check(b))
            cout<<"ERR"<<endl;
        else if(a[0]=='S')
            ser(strb,i);
        else if(a[0]=='C')
            cli(strb);
    }
    return 0;
}
bool check(char t[])
{
    int na,nb,nc,nd,ne;
    int x=sscanf(t,"%d.%d.%d.%d:%d",&na,&nb,&nc,&nd,&ne);
    if(x!=5) return 0;
    if(na>255||nb>255||nc>255||nd>255||ne>65535)
        return 0;
    char tmp[N];
    sprintf(tmp,"%d.%d.%d.%d:%d",na,nb,nc,nd,ne);
    if(strcmp(tmp,t)) return 0;
    else return 1;
}

思路：待补

总结：这场比赛并不难，想拿到一等奖也不难，第一题基本上每年很简单，第二低题也不是很难，把1，2两题AC，其他题目骗分就能拿到一等奖了！