CSP-J2019 AK记

发表于 | 更新于 | 阅读次数：
本文字数： 2.7k 字 | 阅读时长 ≈ 12 分钟

前言

我叫zps，准考证号JS-00810，来自苏州。今年我AK了CSP-J。总体感觉还是很水的，但是似乎没什么人AK。我表示不理解。总之，写个博客好了。

T1 数字游戏(number)

题面

给定一个保证长度为$8$的01字符串，求这个字符串中有多少1。

题解

这还要解？签到题好吧…只要会打文件就能过。

时间复杂度$O(8)$。你要认为是$O(1)$也珂以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 100
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define CL(x) MEM(x,0)
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	
	char s[N];int n;
	void Input()
	{
		scanf("%s",s+1);n=strlen(s+1);
	}
	
	void Solve()
	{
		int ans=0;
		F(i,1,n) if (s[i]=='1') ans++;
		printf("%d\n",ans);
	}

	void Main()
	{
		bool OPEN_FILE=0; //考场上要改为1，需要开文件
		if (OPEN_FILE)
		{
			#define filename "number"
			freopen(filename ".in","r",stdin);
			freopen(filename ".out","w",stdout);
		}
		Input();
		Solve();
		
	}
}
int main()
{
	Flandre_Scarlet::Main();
	return 0;
}

T2 公交换乘(transfer)

题面

你近期有$n<=1e5$个乘坐公共交通的记录，有些是地铁，有些是公交。每次都有三个值：$p,t,k$。$k=0$表示地铁，$=1$表示公交。$p$表示价格。$t$表示时刻。每坐一次地铁都会在上车时得到一个坐公交车的优惠券。如果两个时刻$t_{bus},t_{subway}$之间满足$t_{bus}-t_{subway}<=45$且$t_{bus}>t_{subway}$，则可以使用一张优惠券，免费乘坐公交。

合理分配优惠券使得总花费最小。保证时间$t$严格递增是顺序给出的。

题解

由于时间是严格递增的，时间差要$<=45$，所以每次至少会$+1$。所以，对于每个公交车，最多有$45$个优惠券满足条件。显然，在所有能用的优惠券中，肯定要选择最早的，因为晚一些的优惠券就能用更久，给后面的公交车用。

用一个$vector$存储每趟公交车能用的优惠券编号。对于已经用过的优惠券编号，我们用一个$vis$数字标记已经用过。每次暴力找$vis=0$且最小的。

时间复杂度$O(45n)$。你也珂以认为是$O(n)$。虽然这常数带的比log还大。

吐槽我的一个同学，考场上坐在我左边两个机位，他用了二分图+Dinic…怎么会有这种人…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define CL(x) MEM(x,0)
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    
    int n;
    int tp[N],price[N],tim[N];
    int Rd(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        return (x=(f==1?x:-x));
    }
    void Input()
    {
        Rd(n);
        F(i,1,n)
        {
            Rd(tp[i]);Rd(price[i]);Rd(tim[i]);
        }
    }
    
    vector<int> use[N]; //第i趟公交车能用的优惠券编号
    bool vis[N]; //判断是否使用过
    void Solve()
    {
        F(i,1,n) use[i].clear();
        CL(vis);
        int cost=0;
        
        F(i,1,n)
        {
            if (tp[i]==0) //如果是地铁，就记录花费并更新优惠券
            {
                cost+=price[i]; //地铁没有优惠券呢~
                F(j,i+1,n) 
                {
                    if (tim[j]-tim[i]>45) break; //这一步保证复杂度
                    if (tp[j]==1) use[j].push_back(i); //要判断是地铁才能用优惠券
                }
            }
            else
            {
                bool cxk=0; //记录有没有能用的
                F(j,0,(int)use[i].size()-1)//use[i].size()<=45
                //由于我们是顺序枚举的i，所以我们的use数组中的每个vector都是有序的
                {int u=use[i][j];
                    if (!vis[u] and price[u]>=price[i]) //第一个满足条件的一定是t最小的
                    {
                        vis[u]=1;cxk=1;break; 
                    }
                }
                
                if (!cxk) cost+=price[i]; // 如果不能用的，没有办法，只能花点小钱了
            }
        }
        printf("%d\n",cost);
    }

    void Main()
    {
        bool OPEN_FILE=0; //同上，考场上改为1
        if (OPEN_FILE)
        {
            #define filename "transfer"
            freopen(filename ".in","r",stdin);
            freopen(filename ".out","w",stdout);
        }
        Input();
        Solve();
    }
}
int main()
{
    Flandre_Scarlet::Main();
    return 0;
}

T3 纪念品(souvenir)

单词释义
(英) [ˌsuːvəˈnɪə(r)]
(美) [ˌsuːvəˈnɪr]

（我才不会告诉你我考场上不认得这个词呢）

题面

有$T$天，$n$个纪念品，一开始你有$m$个金币。接下来一个$T\times n$的矩阵$P$，$p[i][j]$表示第$i$天第$j$个纪念品的价格。

每天有两种操作，买或卖任意一个纪念品，操作次数珂以无限次。当日买的纪念品，当日就珂以卖。当日卖得的钱，当日就珂以买其它纪念品。请你求出，到最后，连本带利最多能有多少钱。

$T,n<=100$,$m<=1000$。任意时刻，手头的金币的数量不会超过$1e4$。

题解

对于第$i$天，我们只考虑和$i+1$天做交易的情况即珂。因为$(a-b)+(b-c)=a-c$，所以$i$和$i+k$天之间做生意的情况就珂以拆分为$(i,i+1)+(i+1,i+2)…+(i+k-1,i+k)$。这步很关键（但是你们为啥想不到nya）

然后我们第$i$天和第$i+1$天珂以这样求解：对于每个物品$j$，用$p[i+1][j]-p[i][j]$作价值，$p[i][j]$为重量，$M$为背包容积。跑一个完全背包之后，设答案为$ans$，则$ans$就是最大的净赚。所以$m+=ans$就是最后手头上的钱数。做$T-1$遍这样的背包即珂。

有一个小问题：不是说当天赚的前当天就珂以用吗？

答：但是我们考虑的是这一天和下一天。第$i$天考虑的交易会在第$i+1$天的时候当天买来当天用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 122
    #define V 14444
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int t,n,m;
    int p[N][N];
    void Input()
    {
        R1(t),R1(n),R1(m);
        F(i,1,t) F(j,1,n) R1(p[i][j]);
    }

    int w[N],v[N];
    int dp[V];
    void Soviet()
    {
        F(i,1,t-1)
        {
            F(j,1,n) w[j]=p[i][j],v[j]=p[i+1][j]-p[i][j];
            FK(dp);
            F(j,1,n) F(k,w[j],m) dp[k]=max(dp[k],dp[k-w[j]]+v[j]);//做一个DP
            m+=*max_element(dp+1,dp+m+1);//dp中的最大值就是答案，m+=答案
            //max_element: 返回区间最大值第一次出现的指针
        }
        printf("%d\n",m);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}

放松一下

歌曲：

  1. Hop
  2. 极乐净土
  3. Säkkijärven Polkka

番剧&漫画：

  1. 新闻联播
  2. 海峡两岸

游戏：

  1. OSU!
  2. 东方红魔乡~

前方高能！

T4 加工零件(work)

给定一个无向图表示一个工厂里面的流水线的传递网络。第$u$个点要生产一个$L$阶段的零件，就需要$u$连接的所有工厂都生产一个$L-1$阶段的零件。第$0$阶段的零件即原材料。$q$个询问，请你求出$u$号工厂生产$L$阶段的零件是否需要$1$工厂提供原材料。

$n,q<=1e5,1<=u<=n,L<=1e9$。

题解

考场代码有点小问题，但是数据水，问题不大~

提供的代码是各种$OJ$上都能拿满的代码，和前三题不一样，不是考场代码。

转化为：$u$走$L$步能否到$1$，一条边珂以经过无数次。

特判不连通，直接输出No。

然后，由于一条边珂以经过无数次，如果走$k$能到，我们把其中一条边走两遍，$k+2$步也能到。

所以我们从$1$开始维护奇数/偶数长度的最短路即珂。看着转移，很简单的。

同学问：vis怎么开？

我：不用开…我们只有在能更新最短路的时候入队列，不能更新的时候就不用入队列了，这样显然是不会重复的，因为边权都是$1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 455555
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define CL(x) MEM(x,0)
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define p_b push_back
    
    int Rd(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        return (x=(f==1?x:-x));
    }
    vector<int> G[N];
    int n,m,q;
    void Input()
    {
        Rd(n),Rd(m),Rd(q);
        F(i,1,m)
        {
            int u,v;Rd(u),Rd(v);
            G[u].p_b(v);G[v].p_b(u);
        }
    }
    
    namespace lilunAC //理论AC，实际上也AC了呢...
    //考场上害怕，就只写了理论AC
    {
        int dis[N][2];int Q[N];//dis[*][0/1]：偶数/奇数长度的最短路
        void BFS()
        {
            int head=1,tail=1;Q[tail]=1;
            MEM(dis,0x3f);dis[1][0]=0;
            
            while(head<=tail)
            {
                int u=Q[head];++head;
                F(i,0,(int)G[u].size()-1)
                {int v=G[u][i];
                    bool add=0;
                    if (dis[u][1]+1<dis[v][0]) 
                    {
                        dis[v][0]=dis[u][1]+1;
                        add=1;
                    }
                    if (dis[u][0]+1<dis[v][1]) 
                    {
                        dis[v][1]=dis[u][0]+1;
                        add=1;
                    }
                    if (add) Q[++tail]=v;
                }
            }
        }
        
        void Solve()
        {
            BFS();
            F(i,1,q)
            {
                int u,l;Rd(u),Rd(l);
                if (l>=dis[u][l%2])
                {
                    puts("Yes");
                }
                else puts("No");
            }
        }
    }
    
    void Solve()
    {
        if (G[1].size()==0) F(i,1,q) puts("No"); //特判不连通
        else lilunAC::Solve();
    }

    void Main()
    {
        bool OPEN_FILE=0;
        if (OPEN_FILE)
        {
            #define filename "work"
            freopen(filename ".in","r",stdin);
            freopen(filename ".out","w",stdout);
        }
        Input();
        Solve();
    }
}
int main()
{
    Flandre_Scarlet::Main();
    return 0;
}
w