CSP-J2019复赛解析

· · 题解

数字游戏

题目传送门

签到题，根据题意模拟即可

这题都不会就别打CSP了，浪费名额

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
        if(s[i]=='1') ans++;
    cout<<ans;
    return 0;
}

公交换乘

题目传送门

原本想用 O(n^2) 的时间复杂度暴力，但很明显是会超时的。

题目中说到:优惠卷的有效期只有45分钟，所以我们每次暴力搜一遍，把过期的优惠卷给它扔掉。

题目保证乘车时间单调递增，先拿到的优惠卷先过期，所以我们用队列储存优惠卷

#include<bits/stdc++.h>
using namespace std;
struct yhj
{
    int ti;
    int pri; 
}dl[100005];
int n,head=1,tail=0;
long long sum;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==0)
        {
            dl[++tail].ti=c;
            dl[tail].pri=b;
            sum+=b;
        }
        if(a==1)
        {
            while(dl[head].ti<c-45 && head<=tail) head++;//把过期的优惠卷扔了 
            bool can=false;
            for(int i=head;i<=tail;i++)
            {
                if(dl[i].pri>=b)
                {
                    can=true;
                    dl[i].ti=0;
                    dl[i].pri=0;//删掉这张优惠卷 
                    break;
                }
            } 
            sum+=(!can)*b;
        }
    }
    printf("%lld",sum);
    return 0;
}

纪念品

题目传送门

一道完全背包dp题

题目中提到了一句话：是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量

说明什么？说明我们在第一天买个东西，在第五天卖出，可以将其理解为：第一天买入，第二天卖出，第二天买入，第三天卖出，第三天买入，第四天卖出，第四天买入，第五天卖出。

所以完全背包的重量为当天的价格，利益为明天的价格减去今天的价格

设 dp_k 表示有 k 块钱最后最多能有多少钱

状态转移方程如下：pri_{ij} 表示第i天第j个纪念平的价钱

dp_k = dp_{k-pri_{ij}}-pri_{ij}+pri_{i+1j}

最后别忘了在一个纪念品上赚的钱还能投资下一个纪念品

#include<bits/stdc++.h>
using namespace std;
int T,N,M;
int pri[105][105],dp[10005]; 
int main()
{
    scanf("%d%d%d",&T,&N,&M);
    for(int i=1;i<=T;i++)
        for(int j=1;j<=N;j++)
            scanf("%d",&pri[i][j]);
    for(int i=1;i<T;i++)
    {   
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=N;j++)
        {
            for(int k=pri[i][j];k<=M;k++)
                dp[k]=max(dp[k],dp[k-pri[i][j]]-pri[i][j]+pri[i+1][j]);//状态转移方程
        }
        M+=dp[M];
    }
    printf("%d",M);
    return 0;
}

加工零件

题目传送门

不可以，总司令！

一道图论题，求第 a 个点和第 1 个点之间有没有长度为 L 的路径。

但是如果有一条长度为 y-2k 的，那么可以在一条边上往返 k 次。所以答案还是成立的。

那么我们要记录长度为奇数的最短路径和长度为偶数的最短路径。

直接用Dijistra跑也不是不行，但也有另外一种方法：建立双层图。

我们每次连边，连 (u,v+n) , (v+n,u) , (u+n,v) , (v,u+n) 。

这样， 1 到 i+n 就是第 i 个点到第 1 个点的奇距离， 1 到 i 为第 i 个点到第 1 个点的偶距离。

然后我们直接判断 L 的奇偶性就ok了

Q:为什么要用Dijistra，不用SPFA呢？

A:讲个悲伤的故事

有一位神犇，在NOIP2018的考场上，看到一道最短路的题目，二话不说，迅速敲了个SPFA

然后，100—>65分，和自己的高校说了句西游辣丝坦（see you last time）

最后总结的时候，出题人的ppt出现了这样一行字：

关于spfa，他死了

废话讲完，上代码

#include<bits/stdc++.h>
using namespace std;
struct EDGE
{
    int nxt,v;
}edge[400005];
int n,m,q,head[200005],idx=1;
void add_bian(int u,int v)//连边
{
    edge[idx].v=v;
    edge[idx].nxt=head[u];
    head[u]=idx++;
}
int dist[200005];
bool st[200005];
void dijkstra()//最短路 
{
    memset(dist,0x3f3f3f3f,sizeof(dist));
    dist[1]=0;
    priority_queue< pair < int , int > , vector< pair<int,int> > , greater< pair<int,int> > > heap;
    heap.push({0,1});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int vel=t.second;
        if(st[vel]) continue;
        st[vel]=true;
        for(int i=head[vel];i;i=edge[i].nxt)
        {
            int j=edge[i].v;
            if(dist[j]>dist[vel]+1)
            {
                dist[j]=dist[vel]+1;
                heap.push({dist[j],j});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add_bian(u,v+n);add_bian(v+n,u);
        add_bian(v,u+n);add_bian(u+n,v);
        //建立双层图 
    }
    dijkstra();
    for(int i=1;i<=q;i++)
    {
        int a,L;
        scanf("%d%d",&a,&L);
        int ji=dist[a+n],ou=dist[a];
        if(L%2==1)//判断 
        {
            if(ji>L) printf("No\n");
            else printf("Yes\n");
        }
        else
        {
            if(ou>L) printf("No\n");
            else printf("Yes\n");
        }
    }
    return 0;
}