csp-j 2021 赛后总结及解题报告

Astatinear · 2021-10-27 13:30:26 · 个人记录

前言

更好的阅读体验.

这篇博客主要写一个蒟蒻对于本场考试的一些心得体会，以及这场考试题目的题解。

如有错误，欢迎各位 dalao 批评指出。

t1 分糖果

本题总结:

这个题目我考试的时候没用多久就做出来了，但是由于我那台电脑的问题，导致我找不到我的代码了。所以我又重新打了一遍，这重新一打，就从 accepted 100 降到了 wrong answer 80。

所以下次考试的时候，t1 这个题一定要认真检查，避免粗心大意。

考场错误代码：

#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int main()
{
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    cin>>n>>l>>r;
    int p=l/n;
    if(r-p*l<n)//这里应该是 p*n 而不是 p*l。正解见下文。
    {
        cout<<r-p*n<<endl;
    }
    else
    {
        cout<<n-1<<endl;
    }
    return 0;
}

本题正解:

这个题目要求我们在区间 [l,r] 选一个数字 k 使得你得到的奖励糖数尽量的多。 根据题意，我们可以发现，他得到的奖励糖果最多只能是 n-1 。而且在某些情况下，他不一定可以得到 n-1 的奖励糖果。所以我们就要考虑他能否可以得到 n-1 的奖励糖，如果可以，就直接输出 n-1；不可以就输出的能够得到的最多的奖励糖。

首先，我们可以发现，无论如何，这个拿糖果的过程都要经过 l/n 轮 (向下取整),我们定义 p=l/n 。

接下来，我们来看两种情况。

*如果 $r-pn<n$**

如果满足了以上情况，就说明你在经过了最少的 p 轮之后，你剩下的糖果已经不足 n 个了。 很显然，在这种情况下，我们直接输出剩余的糖果就可以了。

否则

既然剩下的糖数 \ge n 那么我们就直接把 p*n+n-1 这么多个糖放进篮子里，就可以做到还剩下 n-1 个糖果作为奖励糖。 所以最终，在这种情况下，我们直接输出 n-1 即可。

AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int main()
{
    //文件输入输出
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    cin>>n>>l>>r;//输入
    int p=l/n;//那糖果经过的最少轮数
   //根据刚才的思路进行判断
    if(r-p*n<n)
    {
        cout<<r-p*n<<endl;
    }
    else
    {
        cout<<n-1<<endl;
    }
    return 0;//csp记得返回0
}

t2 插入排序

本题总结

这个题目虽然在考场上我是 accepted 了，但是这个题确实不容易打对，我也是调了很久才改对的。

这个题目尤其要注意他的题目描述，其中加粗的那几行尤其要注意，一旦不注意就会死的很惨。

由于这个题目我是 accepted 100 就不放考试代码了。

本题正解

这个题目麻烦的地方不在于操作 1 ，而在于操作 2 他说排完序之后不仅要知道这个数在原数组的哪一个位置上，而且他不会保留这一次的排序结果，这就导致我们在操作 1 修改完值之后不能对原数组直接进行插入思想的排序。 但是如果我们在操作 2 用一个数组来进行排序，最快也需要 nlogn 是肯定会超时的。

所以，我们可以发现，只有操作 1 可以做 O(n) 的操作,操作 2 只能做 O(1) 的操作。

我们可以先维护一个 tot 一维数组，tot_i 表示原数组的第 i 个数字在现在的数组中是排在第几个位置上的。 显然，操作 2 就直接输出 tot_x , 达到了 O(1) 的效果，接下来的难点就是操作 1 ，该怎么运用 \le O(n) 的方法，去修改 tot 的值。

我们可以先将原数组进行从小到大排序，并更新 tot 的值，然后每修改一个 a_x ，我们就可以运用冒泡排序的思想，把修改的这个数往前面挤或者往后面挤。(因为数组有序，且只修改了一个数，所以我们只需要将这一个数的顺序改变)。特别要注意的是，当一个被修改的数在往前面挤的时候，我们需要改变 tot 的值，因为它在现在数组的位置改变了。

其余的都没有什么要说的，就是要注意在修改 tot 值的时候不要写错就可以了。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int tot[100005];//要维护的tot数组 
struct node
{
    int a,id;//记得储存这个数在原数组的编号。 
    bool operator <(const node &n)const
    {
        return a<n.a||(a==n.a&&id<n.id);//排序方式 
    }
}arr[100005];
int s;
int main()
{
    //文件输入输出 
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    {
        //输入，变换id的值 
        arr[i].id=i;
        scanf("%d",&arr[i].a);
    }
    sort(arr+1,arr+n+1);//排序 
    for(int i=1;i<=n;++i)
    {
        tot[arr[i].id]=i;//第一次排序后，tot的值 
    }
    while(q--)
    {
        //操作 
        int op,x,y;
        scanf("%d%d",&op,&x);
        if(op==1)
        {
            scanf("%d",&y);
            s=tot[x];
            arr[tot[x]].a=y;//由于x是指的原数组的下标，而现在数组的下标是 tot[y] 
            //向前挤 
            for(int i=s-1;i>=1;--i)
            {
                if(arr[i].a>y||(arr[i].a==y&&x<arr[i].id))
                {
                    //交换tot值和arr值，注意先后顺序 
                    swap(tot[x],tot[arr[i].id]);
                    swap(arr[s],arr[i]);
                    s=tot[x];
                }
                else
                break;
            }
            //向后挤 
            for(int i=s+1;i<=n;++i)
            {
                if(arr[i].a<y||(arr[i].a==y&&x>arr[i].id))
                {
                    swap(tot[x],tot[arr[i].id]);
                    swap(arr[s],arr[i]);
                    s=tot[x];
                }
                else
                break;
            }
        }
        else
        {
            //O(1)操作，直接输出 
            printf("%d\n",tot[x]);
        }
    }
    return 0;//记得返回0 
}

t3 网络连接

本题总结

这个题目我考场上是 wrong answer 65 。 错因比较简单，就是在判断 err 的时候判断错了几个地方:

1.前导零。2.. 和 : 的顺序我没有判断。3.他没有输入任何数字的时候，我会默认这些数字为 0 。

所以这个题目一定要特别注意 err 的条件，一不小心就会把 err 给判错。最好考试的时候自己写几个毒瘤数据测试一下。

考场错误代码

#include<bits/stdc++.h>
using namespace std;
int n;
int tot;
string p[10005];
int ans[10005];
bool check(string s,int len)//这个判断err函数有很大的漏洞，是导致65分的原因。
{
    bool flg=0;
    int bj1=0,bj2=0;
    int cnt=1;
    int p[10]={0,0,0,0,0,0};
    for(int i=0;i<len;++i)
    {
        if(s[i]=='0')
        {
            if(i>0)
            {
                if(flg==0&&(s[i-1]=='0'||s[i+1]=='0'))
                {
                    return 0;
                }
            }
            p[cnt]*=10;
        }
        else if(s[i]=='-')
        return 0;
        else if(s[i]=='.')
        {
            bj1++;
            cnt++;
            flg=0;
        }
        else if(s[i]==':')
        {
            bj2++;
            cnt++;
            flg=0;
        }
        else if(s[i]>='1'&&s[i]<='9')
        {
            p[cnt]=p[cnt]*10+s[i]-'0'; 
            flg=1;
        }
        else
        return 0;
    }
    if(p[1]<=255&&p[2]<=255&&p[3]<=255&&p[4]<=255&&p[5]<=65535&&cnt==5&&bj1==3&&bj2==1)
    return 1;
    else
    return 0;
}
int main()
{
//  freopen("network.in","r",stdin);
//  freopen("network.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) 
    {
        string op,s;
        cin>>op>>s;
        if(!check(s,s.length()))
        {
            printf("ERR\n");
            continue;
        }
        bool flg=0;
        if(op=="Server")
        {
            for(int j=1;j<=tot;++j)
            {
                if(s==p[j])
                {
                    flg=1;
                    break;
                }
            }
            if(flg==0)
            {
                printf("OK\n");
                p[++tot]=s;
                ans[tot]=i;
            }
            else
            {
                printf("FAIL\n");
            }
        }
        else
        {
            for(int j=1;j<=tot;++j)
            {
                if(p[j]==s)
                {
                    printf("%d\n",ans[j]);
                    flg=1;
                    break;
                }
            }
            if(flg==0)
            {
                printf("FAIL\n");
            }
        }
    }
    return 0; 
}

本题正解

这个题目还是比较简单的，判断 err 的话就全凭大家的细心，这里不做过多的阐述，下面给大家说 3 个客户机匹配服务机和判断服务机是否重复的方法。

1.直接暴力，判断他以前的那些有没有和一模一样的字符串。

2.运用 map ，键类型为 string 就可以做了。假设当前要判断是否重复的服务机的字符串为 s 。如果 map_s 有值，就说明以前有这个字符串，如果没有，就说明以前没有这个字符串。客户机匹配服务机时也同样。

3.运用字符串 hash 。其实这个方法就是将方法 1 给优化了一下，因为我们判断两个字符串完全相等时，需要一个一个枚举这个字符串里面的每个字符，很浪费时间，虽然可以过，但是有一些浪费。 由于判断 2 个字符串是否相等，我们可以通过 hash 来判断。 所以我们每有一个新的字符串，我们就把他的 hash 值给存下来，然后在匹配或者判断是否重复时，直接判断两个 hash 值是否相等就可以了。

我在这里就直接给出第一种最简单的方法的代码。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
int tot;
string q[10005];
int ans[10005];
bool check(string s,int len)
{
    bool flg=0;
    int bj1=0,bj2=0;
    int cnt=0;
    long long p[105],q[105];//有可能五个数中有的会爆int
    memset(p,0,sizeof(p));
    for(int i=0;i<=100;++i)
    q[0]=-1;
    for(int i=0;i<len;++i)
    {
        if(bj2==1&&bj1<3)//已经出现:但.还没有出现 
        return 0;
        if(cnt+1<=bj1+bj2)//符号个数和数字个数不匹配 
        return 0;
        if(s[i]=='0')//特判一下0 
        {
            if(flg==0)
            cnt++;
            q[cnt]=0;
            if(i>=0)//判断前导0 
            {
                if(flg==0&&((s[i-1]<='9'&&s[i-1]>='0')||(s[i+1]<='9'&&s[i+1]>='0')))
                {
                    return 0;
                }
            }
            else
            {
                if(flg==0&&(s[i+1]<='9'&&s[i+1]>='0'))
                {
                    return 0;
                }   
            }
            flg=1;
            p[cnt]*=10;
        }
        else if(s[i]=='-')//如果有负数 
        return 0;
        else if(s[i]=='.')//特判. 
        {
            bj1++;
            flg=0;
        }
        else if(s[i]==':')//特判: 
        {
            bj2++;
            flg=0;
        }
        else if(s[i]>='1'&&s[i]<='9')//如果是数字 
        {
            if(flg==0)
            cnt++;
            q[cnt]=0;
            p[cnt]=p[cnt]*10+s[i]-'0'; 
            flg=1;
        }
        else if(s[i]==' ')//特判一下空格(没必要) 
        continue;
        else//如果有其他奇奇怪怪的符号 
        return 0;
    }
    if(p[1]<=255&&p[2]<=255&&p[3]<=255&&p[4]<=255&&p[5]<=65535&&cnt==5&&bj1==3&&bj2==1&&q[1]>=0&&q[2]>=0&&q[3]>=0&&q[4]>=0&&q[5]>=0)//奇奇怪怪的判断 
    return 1;
    else
    return 0;
}
int main()
{
//  freopen("network12.in","r",stdin);
//  freopen("network.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) 
    {
        string op,s;
        cin>>op>>s;
        if(!check(s,s.length()))
        {
            printf("ERR\n");
            continue;
        }
        bool flg=0;
        if(op=="Server")
        {
            //暴力判断以前是否出现过 
            for(int j=1;j<=tot;++j)
            {
                if(s==q[j])
                {
                    flg=1;
                    break;
                }
            }
            if(flg==0)
            {
                printf("OK\n");
                q[++tot]=s;
                ans[tot]=i;
            }
            else
            {
                printf("FAIL\n");
            }
        }
        else
        {
            //暴力判断有没有与之匹配的 
            for(int j=1;j<=tot;++j)
            {
                if(q[j]==s)
                {
                    printf("%d\n",ans[j]);
                    flg=1;
                    break;
                }
            }
            if(flg==0)
            {
                printf("FAIL\n");
            }
        }
    }
    return 0; 
}

t4 小熊的果篮

本题总结

这个题目考场上我是又 Time limit exceed 还 wrong answer 只有 10 分。我那个代码可是错误百出，虽然想到了用链表来维护删除操作，但合并操作却想到了并查集，想错了。最让人烦恼的是那些喜欢打暴力不想正解的同学却全都是 Time limit exceed 70，比我高整整 60 分 。

这个故事让我懂得了什么呢？ 就是:只要没有 100 \% 的肯定自己的正解是对的，就乖乖打暴力吧！

由于漏洞太多，这里就不放出我考试的代码了。

本题正解

这个题目其实就是一个模拟，比较难想的就是当中间有一个块被删除时，他们之间的删除操作和左右两个块的合并操作。

删除操作比较好想，我们直接运用一个双向链表来实现，这里用一个 vis 数组来描述。 vis_{i_0} 表示他的上一个块是哪一个， vis_{i_1} 表示他的下一个块是多少。 假设我们现在正在删除第 i 个块。先定义两个变量 head 和 tail 表示 vis_{i_0} 和 vis_{i_1} 。显然，我们只需要将 head 的下一个指向 tail ，tail 的上一个指向 head 。也就是 vis_{head_1}=tail , vis_{tail_0}=head 。

接下来就是合并操作。其实我们没有必要去死板的去合并，因为题目要求的是相邻两块水果种类相同才可以把这两个块合并为一个块，所以我们就可以想出一种解法。我们只需要判断这个块的上一个块是否和它水果种类相同，如果相同，就说明他和前面一个是在一个共同的块里，不需要取出水果；如果不相同，就说明他是这个块最左边的一个，那我们就需要将最左边的水果编好输出。

其他的就没有什么要说的了，就是在储存每个块的水果时，我们运用队列储存，因为队列满足先进先出的规律。

AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n;
int a[200005];
int cnt;
struct node
{
    queue<int> p;//储存块里的水果编号 
    int bj,flg;//块的种类和这个块是否存在 
}edge[200005];
int vis[200005][2];
int main()
{
    //输入 
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        edge[i].bj=-1;
    }
    //由于要判断是否与上一个种类相同，所以我们要设一个不同的种类。 
    a[0]=-1;
    edge[0].bj=-1;
    //分块 
    for(int i=1;i<=n;++i)
    {
        if(a[i]!=a[i-1])
        {
            cnt++;
            edge[cnt].p.push(i);
            edge[cnt].bj=a[i];
            edge[cnt].flg=1;
            vis[cnt][0]=cnt-1;
            vis[cnt][1]=cnt+1;
        }
        else
        {
            edge[cnt].p.push(i);
        }
    }
    //将0指向第一个 
    vis[0][1]=1;
    while(1)
    {
        bool ch=0;//判断有没有输出 
        //先去掉没有水果的块 
        for(int i=0;i<=cnt;i=vis[i][1])
        {
            if(edge[i].p.empty())
            {
                edge[i].flg=0;
                int head=vis[i][0],tail=vis[i][1];
                vis[head][1]=tail;
                vis[tail][0]=head;
            }
        }
        for(int i=0;i<=cnt;i=vis[i][1])
        {
            int x=edge[i].p.front();
            if(edge[vis[i][0]].bj!=edge[i].bj)//判断是否他这个块最左边的一个 
            {
                ch=1;//标记打上 
                printf("%d ",x);
                edge[i].p.pop();
            }
        }
        if(ch==0)//如果没有输出，就说明所有水果编号已经输出了 
        break;
        printf("\n");//换行 
    }
    return 0;
}