2019 CSP-J 题解

前言

咕咕咕了好久,终于今天把 T3 的坑给补回来了,于是打算写一波题解。

勿吐槽码风,丑是必然的,毕竟好久前写的代码了。

T1 数字游戏

P5660 数字游戏

大意:给定长度为 8 的 01 串,求 1 的个数

sb 题,考察字符串基本使用,当时好像 2:30 还没到就已经切完了

考场代码:

#include <iostream>
#include <cstdio>
#include <string>
//#define LOCAL

using namespace std;

int main()
{
#ifndef LOCAL
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
#endif
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1') ans++;
    }
    printf("%d\n",ans);
    return 0;
}

T2 公交换乘

P5661 公交换乘

大意:坐一次地铁可以获取一张有效期 45 分钟的优惠券,可以凭券免费坐票价不超过地铁票价的公交车,优惠票可累积,使用时优先使用最先获得的

模拟即可,这里使用 vector 模拟优惠票的队列,代码并不优美但是能过。

坑点就在于

  • 使用票要使用最先获得的
  • 优惠票用过要删掉

记得当时在考场上发现队列不能用之后还自己研究 vector::erase 的用法

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
//#define LOCAL
struct ticket{
    int price;
    ll time;
};
vector<ticket> q;

int main()
{
#ifndef LOCAL
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
#endif
    int n;
    scanf("%d",&n);
    ll ans=0;
    while(n--)
    {
        int type,price;
        ll t;
        scanf("%d %d %lld",&type,&price,&t);
        if(type==0)//如果坐地铁
        {
            ans+=price;//更新答案
            ticket tt={price,t};
            q.push_back(tt);//插入候选队
        }
        else if(type==1)//如果是公交
        {
            while(!(q.empty())&&t-q.front().time>45) q.erase(q.begin());//先删掉超时的优惠票
            bool flag=0;
            for(int i=0;i<q.size();i++)//查询符合标准的第一张优惠票
            {

                if(q[i].price>=price)
                {
                    q.erase(q.begin()+i);//直接删掉
                    flag=1;
                    break;
                }
            }
            if(!flag) ans+=price;//如果不存在就需要付原价
        }
    }
    printf("%lld\n",ans);
    return 0;
}

T3 纪念品

P5662 纪念品

谁叫我太菜,当时考场上骗了 10 分走人,现在看题解才写出正解。

大意:T 天,N 种纪念品,每天不同的纪念品都有不同的价格,小伟一开始有 M 金币,每天可以卖掉手中的纪念品换取金币,买进纪念品花费金币或者什么都不做。在第 T 天一定会卖出手中所有纪念品,求最高收益

分析题意,可以发现需要使用 dp,发现状态貌似很复杂,又可以买进又可以卖出,然而,注意到买进和卖出都可以进行无数次,因此我们可以把所谓一直持有的纪念品看成先将其卖出,又将其买进,效果是一样的,实质上就是每一天都做一次完全背包。

f_{i,j,k} 表示第 i 天,考虑前 j 种物品,手里有 k 金币时,在下一天全部卖出能达到的最大收益,则有方程

f_{i,j,k}=\max(f_{i,j,k},f_{i,j-1,k+p_i,j}+p_{i,j}-p_{i+1,j})

表示如果要了第 j 个物品,那么净收益即为 p_{i,j}-p_{i+1,j},从 f_{i,j-1,k+p_i,j} 转移而来,利用完全背包思想压一下维度然后改循环顺序即可以达到正确结果。

(第一维的天数是可以不要的,第二维的物品也是可以用滚动数组优化掉的,保留第三维即可)

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int n,t,p[105][105],f[10005];

int main()
{
    t=read(),n=read();
    int m=read();
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            p[i][j]=read();
    int ans=m;
    for(int i=1;i<t;i++)
    {
        memset(f,~0x3f,sizeof(f));//先赋负无穷
        f[ans]=ans;//初始值,什么都不干的情况
        for(int j=1;j<=n;j++)//枚举物品,从小到大即为完全背包
            for(int k=ans;k>=p[i][j];k--)//枚举金钱
                f[k-p[i][j]]=max(f[k-p[i][j]],f[k]+p[i+1][j]-p[i][j]);
        int maxn=0;//统计最优答案用
        for(int j=0;j<=ans;j++)
            maxn=max(maxn,f[j]);
        ans=maxn;
    }
    printf("%d\n",ans);
    return 0;
}

T4 加工零件

P5663 加工零件

大意:一个工厂正在生产零件,工人从 1 到 n 标号,某些工人之间有双向传送带。

如果 x 号工人想生产一个被加工到第 L (L \gt 1) 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要生产一个被加工到第 L – 1 阶段的零件(但 x 号工人自己无需生产第 L – 1 阶段的零件)。

如果 x 号工人想生产一个被加工到第 1 阶段的零件,则所有与 x 号工人有传送带直接相连的工人,都需要为 x 号工人提供一个原材料。

给定一些工单,即需要某工人生产某阶段的零件,求 1 号是否需要提供原材料。


先将其抽象成图论问题,以工人为节点,传送带为边来建图。

考虑暴力,虽然一定超时,但还是能给我们一些启示,不难发现暴力就是在看 a 与 1 之间是否存在长度为 L 的路径,同时我们又注意到:如果 L 为奇数,且从 1 到 a 存在一条奇数路径,且最小奇数路径长小于等于 L,那么 1 就必须提供原材料(为什么可以:你可以两个传送带之间来回跳,比如 1->2->1->2->1…,但如果最小的奇数路径大于 L,说明从 aL 个阶段也轮不到 1,就不行)同样的,如果 L 为偶数,且从 1 到 a 存在一条偶数路径,且最小偶数路径长小于等于 L,那么 1 就必须提供原材料。

这就给我们了正解的方法:找到每个点距离 1 点的最小奇数路径与偶数路径即可,这一过程实现可以使用 bfs(因为我当时还没学过最短路),然后判定每一个工单的时候按照奇偶数去找最短奇偶路径是否小于等于工单给定阶段就可以判定 YesNo

当然,我写的考场代码有一个小 bug,就是没有判断 1 点不连通的情况,然而 ccf 的数据没有这种特殊情况,所以也就 A 了这道题

考场代码:

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
//#define LOCAL
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
vector<int> g[100020];//存图
bool vis0[100020],vis1[100020];//bfs用
int minans0[100020],minans1[100020];//存储奇偶最短路
struct node{
    int n,time;
};
queue<node> q;
void bfs()
{
    memset(minans0,inf,sizeof(minans0));
    memset(minans1,inf,sizeof(minans1));
    q.push((node){1,0});
    while(!q.empty())
    {
        int curn=q.front().n;//当前的点
        int nxtc=q.front().time+1;//下一个点会经过的路径长
        q.pop();
        for(int i=0;i<g[curn].size();i++)
        {
            int nxt=g[curn][i];
            if(nxtc%2==0)//如果下一个点是偶数到达
            {
                if(vis0[nxt]==0)//如果未访问
                {
                    vis0[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans0[nxt]=min(nxtc,minans0[nxt]);//就更新这里的结果
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
            if(nxtc%2==1)//反之如果是奇数,也一样
            {
                if(vis1[nxt]==0)
                {
                    vis1[nxt]=1;
                    q.push((node){nxt,nxtc});
                    minans1[nxt]=min(nxtc,minans1[nxt]);
                    //cout<<"no."<<nxt<<" "<<nxtc<<endl;
                }
            }
        }
    }
    return;
}

void add_edge(int u,int v)
{
    g[u].push_back(v);//注意是无向图
    g[v].push_back(u);
    return;
}


int main()
{
#ifndef LOCAL
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
#endif
    int n,m,q;
    scanf("%d %d %d",&n,&m,&q);
    while(m--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        add_edge(u,v);
    }
    bfs();//预处理
    while(q--)
    {
        int a,l;
        scanf("%d %d",&a,&l);
        bool flag=0;
        if(l%2==0&&vis0[a]==1&&minans0[a]<=l) flag=1;//如果是偶数阶段并且能到达
        if(l%2==1&&vis1[a]==1&&minans1[a]<=l) flag=1;
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

解题报告 P1563 玩具谜题 【NOIP2016TGD1T1】

题目内容

P1563

大意:一圈小人,有的面朝内,有的面朝外,先告诉你你的眼镜被xx向左/右数的xx人那里,还原眼镜的位置

解题思路

大水题,大模拟,只需注意减到小于0和大于n的情况即可。注意判断内外左右即可

#include <iostream>
#include <string>

const int maxn=1e5+5;
int n,m;
bool face[maxn];
std::string s[maxn];

int main()
{
    std::ios::sync_with_stdio(false);//加速cin
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
        std::cin>>face[i]>>s[i];
    int cur=1;
    bool a;
    int b;
    for(int i=1;i<=m;i++)//在线处理指令
    {
        std::cin>>a>>b;
        if(!a)
            b=-b;
        if(face[cur])
            b=-b;
        cur+=b;
        if(cur<1)
            cur+=n;
        if(cur>n)
            cur%=n;
    }
    std::cout<<s[cur]<<std::endl;
    return 0;
}

解题报告 P2670 扫雷游戏【NOIP2015PJT2】

题目内容

P2670

大意:现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。

解题思路

红题模拟,智障题目,扫入一颗雷更新周围八个点即可

只需要注意读入即可

#include <cstdio>

int n,m,f[105][105];
const int inf=0x3f3f3f3f;
const int fx[8]={1,1,1,-1,-1,-1,0,0};
const int fy[8]={0,1,-1,0,1,-1,1,-1};

int main()
{
    scanf("%d %d\n",&n,&m);//先干掉回车符
    char tmp;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            tmp=getchar();
            if(tmp=='*')
            {
                f[i][j]=inf<<1;//雷的那一个点标记一下
                for(int k=0;k<8;k++)
                {
                    int xx=i+fx[k],yy=j+fy[k];
                    f[xx][yy]++;
                }
            }
        }
        getchar();//干掉每行末尾回车符
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(f[i][j]<=inf)
                printf("%d",f[i][j]);
            else
                printf("*");//如果是雷的话输出星号
        }
        printf("\n");
    }
    return 0;
}

解题报告 P1042 乒乓球 【NOIP2003PJ】

题目内容

P1042

大意:给出一串乒乓球对战结果,分析11分制和21分制的异同。只有当有一人分数到达11或21分且分差大于等于2时一局才结束。

解题思路

纯模拟,但我半年前看了一点思路都没有,可能是因为语文不好读不懂乒乓球的规则吧。一局比赛的结束一定是两者中一人到达11或21分且两者分差大于等于2分。然后最后如果新开了一局,也一定要输出0:0

注意E后面的东西要忽略掉。

具体的思路是先读入,然后分别根据两种分制离线处理(因为做不到在线)。

#include <cstdio>

int a[25*2500+5],n=0;//a数组一定要开足
int f[2]={11,21};//两种分制下的分数

inline int abs(int x)//绝对值
{
    return x>=0?x:-x;
}

int main()
{
    char c;
    while(1)
    {
        c=getchar();//听说getchar会快
        if(c=='E')//读到E就停止
            break;
        if(c=='W')
            a[++n]=1;//1代表这球华华赢的
        if(c=='L')
            a[++n]=0;//否则就是0
    }
    for(int k=0;k<2;k++)//开始统分
    {
        int tmp1=0,tmp2=0;//分别记录双方得分
        for(int i=1;i<=n;i++)
        {
            if(a[i])//积分
                tmp1++;
            else
                tmp2++;
            if((tmp1>=f[k] || tmp2>=f[k]) && abs(tmp1-tmp2)>=2)//如果满足一局结束的标准
            {
                printf("%d:%d\n",tmp1,tmp2);
                tmp1=tmp2=0;//每次清零
            }
        }
        printf("%d:%d\n\n",tmp1,tmp2);//最后没进行完的也要输出而且要空行
    }
    return 0;
}

解题报告 P2003 平板

题目内容

P2003

大意:给定n个平板,支柱可以互相搭,求支柱花费

解题思路

第一眼看到的时候我都惊了,一道普及-的题居然会有线段树的标签。

先不管,分析思路:

首先,上面的平板大概率要搭在下面的平板上,所以处理的时候一定要从下往上处理。这里可以使用结构体排序。

然后,为了得到当前板子需要的支柱高度,就需要搞清楚下面有没有板子,板子的高度是多少,所以定义一数组h,储存坐标[i,i+1]区间内的最高值。

接下来搞定了支柱高度,就要刷新当前范围内的h了,但是很明显需要将一片区间赋值为当前的高度。所以可以使用线段树进行区间赋值。但一看数据范围,发现所有坐标不大于1e4,所以n方暴力完全可以跑过去。

代码:

#include <cstdio>
#include <algorithm>
using std::sort;

int h[10005],n;//表示[i,i+1]板子的最高高度
struct pad
{
    int y,x1,x2;
}p[105];

bool cmp(pad a,pad b)
{
    return a.y<b.y;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d %d %d",&p[i].y,&p[i].x1,&p[i].x2);
    sort(p+1,p+1+n,cmp);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int x1=p[i].x1,x2=p[i].x2,y=p[i].y;
        ans+=(y-h[x1]+y-h[x2-1]);
        for(int j=x1;j<x2;j++)
            h[j]=y;
    }
    printf("%d\n",ans);
    return 0;
}

解题报告 P1097 统计数字(NOIP2007TGT1)

题目内容

P1097

解题思路

嗯。。。提高第一题水题。

主要思想还是离散化,可以用HASH做,但我懒得写(不会),于是我选择了万能的map,这个东西真好用。

使用了一个新函数unique(),这个函数拿来在有序的序列中去重,将重复的元素都放回了序列尾端并返回去重后最后一个元素的指针。

代码实现:

#include <map>
#include <cstdio>
#include <algorithm>//sort和unique都定义在algorithm头文件中
#define R register
using namespace std;

const int maxn=200000+5;
map<int,int> m;//map用来存储这个数字出现的次数

int n,a[maxn];

inline int read()//快读
{
    int s=0,w=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

int main()
{
    int n=read();
    for(R int i=1;i<=n;i++)
    {
        a[i]=read();//读入数据
        m[a[i]]++;//记录次数
    }
    sort(a+1,a+n+1);//先将无序的序列有序化
    int nn=unique(a+1,a+n+1)-(a+1);//去重,再获得去重后剩余元素的个数
    for(R int i=1;i<=nn;i++) printf("%d %d\n",a[i],m[a[i]]);//输出
    return 0;
}

map太好用了

解题报告 洛谷P1022 计算器的改良

题目内容

P1022

思路

首先,一个一元一次方程可以化为kx+b=0的形式,然后
kx=-b
x=-\frac{b}{k}
即可解决

难点在于字符串的处理以及一些特判。

代码

#include <cstdio>
#include <cctype>
#include <string>
using namespace std;
int main()
{
    char mode;
    int b=0,k=0,tmp=0;
    bool equal=1,flag=1;
    string s;
    for(int i=0;;i++)
    {
        char c=getchar();
        if(c==EOF) break;
        s[i]=c;
        if(isalpha(c))
        {
            mode=c;
            if(s[i-1]=='-')
            {
                k+=equal?-1:1;
            }
            else if(s[i-1]=='+'||i==0||s[i-1]=='=')
            {
                k+=equal?1:-1;
            }
            else
            {
                k+=equal?tmp:-tmp;
                tmp=0;
            }
        }
        if(isdigit(c))
        {
            tmp*=10;
            tmp+=flag?(c-'0'):-(c-'0');
        }
        if(c=='+')
        {
            flag=1;
            b+=equal?-tmp:tmp;
            tmp=0;
        }
        if(c=='-')
        {
            flag=0;
            b+=equal?-tmp:tmp;
            tmp=0;
        }
        if(c=='=')
        {
            flag=1;
            b+=equal?-tmp:tmp;
            tmp=0;
            equal=0;
        }
        //rintf("c:%c,tmp:%d,k:%d,b:%d,equal:%d,flag:%d\n",c,tmp,k,b,equal,flag);
    }
    if(tmp!=0) b+=tmp;
    //printf(",tmp:%d,k:%d,b:%d,equal:%d,flag:%d\n",tmp,k,b,equal,flag);
    double ans=(double)b/k;
    if(ans==-0.0000) ans=0;
    printf("%c=%.3f",mode,ans);
    return 0;
}

坑点

注意每个符号都要清算一次b

-0和0是两个东西,输出时要把-0输出为0