CSP-J2 2019 题解

发表于 分类于

CSP-J2 2019 题解

顺手将洛谷上的题解搬运了过来。

T1 数字游戏(number)

20pt

输出 00 即可（笑）。

复杂度 O(1)O(1) 的。

100pt

法一：

每个每个字符读入，若为 11，ans←ans+1ans\gets ans+1 ；否则 ansans 不变。

注意不要用一些奇怪的读入方式，比如 gets 。

复杂度是 O(∣s∣)O(|s|) 的。

法二：

打表，发现总情况只有 83=2568^3=256 种（只有个鬼），可以把每种情况都求出来，然后直接判断输出。

复杂度是 O(1)O(1) 的（我觉得应该没人打）。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#define il inline
using namespace std;

int ans;
char s[50];

int main()
{
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	
	scanf("%s",s);
	int i;
	for (i=0; i<=7; i++)
	{
		if (s[i]=='1') ans++;
	}
	
	printf("%d",ans);
	
	return 0;
}

T2 公交换乘(transfer)

30pt

对于每个地铁，暴力把前面的公交都搜一遍，找到一个最早满足的即可。

复杂度是 O(n2)O(n^2) 的。

60pt

考虑 priceiprice_i 都相同的部分分。

发现 tit_i 两两不相同，又有 tbus−tsubway≤45t_{bus}-t_{subway}≤45 ,所以对于每个地铁，最多只有 4545 个公交满足，那么我们开一个队列，时间之差超过 4545 的 pop 掉，对于每个地铁选 front 即可。

复杂度是 O(Cn)O(Cn) 的，其中 C=45C=45 。

100pt

还是这个关键条件：对于每个地铁，最多只有 4545 个公交满足。

法一：

那么我们可以开一个队列维护，和 6060 的做法一样，时间之差超过 4545 的 pop 掉，用掉的优惠券打个标记就好了。

复杂度是 O(Cn)O(Cn) 的，其中 C=45C=45 。

法二：

发现优惠券要支持中间删除。

那么我们可以用链表维护优惠券，时间之差超过 4545 的删掉，用掉的优惠券也删掉就好了。

链表删除的是 O(1)O(1) 的，查询是 O(C)O(C) 的。

复杂度是 O(Cn)O(Cn) 的，其中 C=45C=45 。

法三：

不要那么多技巧，直接数组暴力维护，删除一个元素以后直接暴力把后面的都往前移，最多只会进行 44 次暴力移的操作。

所以复杂度是 O(Cn)O(Cn) 的，其中 C=180C=180 。

Code:

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
#include <cstdio>
#define il inline
using namespace std;

int n,ans;
struct quan
{
	int t,p;
}q[100001];
int sze;

il int read()
{
	int res=0,sign=1;
	char c;
	
	while ((c=getchar())<'0'||c>'9') if (c=='-') sign=-1;
	
	res=c-'0';
	while ((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	
	return res*sign;
}

int main()
{
	freopen("transfer.in","r",stdin);
	freopen("transfer.out","w",stdout);
	
    n=read();
    int i,j,g,opt,p,t;
    for (i=1; i<=n; i++)
    {
    	opt=read(),p=read(),t=read();
    	if (opt==0)
    	    ans+=p,q[++sze]=(quan){t,p};
    	else
    	{
    		g=0;
    		for (j=1; j<=sze; j++)
    		{
    			if (t-q[j].t<=45&&q[j].p>=p)
    			{
    				g=j;
					break;
				}
			}
			
			if (g==0) ans+=p;
			else
			{
				for (j=g+1; j<=sze; j++)
				{
					q[j-1]=q[j];
				}
				sze--;
			}
		}
		
		g=0;
		for (j=1; j<=sze; j++)
		{
			if (t-q[j].t>45) g++;
		}
		for (j=g+1; j<=sze; j++)
		{
			q[j-g]=q[j];
		}
		sze-=g;
	}
	
	printf("%d",ans);
	
	return 0;
}

T3 纪念品(souvenir)

10pt

直接输出 mm 即可（笑）。

复杂度是 O(1)O(1) 的。

30pt

暴力搜索即可（这题暴力比正解还难写，本人现在还是不会写这题暴力）。

复杂度是 O(O(玄学)) 的（笑）。

45pt

考虑 N=1N=1 的部分分。

考虑贪心，如果今天买进的东西明天卖出可以赚钱，就花所有的前来买，这显然是无误的。

复杂度是 O(T)O(T) 的。

60pt

考虑 T=2T=2 的部分分。

这是藏的比较深的背包。

因为不管第一天买多少，第二天都要卖掉，那么其实就是以 mm 为背包体积，第 ii 号物品的体积是 P1,iP_{1,i} ，价值是 P2,i−P1,iP_{2,i}-P_{1,i} ，每个物品都有无限个，求最大价值。

这不就是个完全背包吗！

复杂度是 O(NM)O(NM) 的。

100pt

把 N=1N=1 和 T=2T=2 的部分分合起来，就成了正解。

还有就是每次的资金要最多，才更有主动权。

那其实就是 T−1T-1 次背包，第 ii 次背包求 ii 和 i+1i+1 的最大价值。

复杂度是 O(TNP)O(TNP) ，其中 P=10000P=10000 。

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
#include <cstdio>
#include <algorithm>
#define il inline
using namespace std;

int t,n,m;
int p[101][101];
int mm,f[1100001];

il int read()
{
	int res=0,sign=1;
	char c;
	
	while ((c=getchar())<'0'||c>'9') if (c=='-') sign=-1;
	
	res=c-'0';
	while ((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	
	return res*sign;
}

int main()
{
	freopen("souvenir.in","r",stdin);
	freopen("souvenir.out","w",stdout);
	
	t=read(),n=read(),m=read();
	int T,i,j;
	for (i=1; i<=t; i++)
	{
		for (j=1; j<=n; j++)
		{
			p[i][j]=read();
		}
	}
	
	for (T=2; T<=t; T++)
	{
		for (i=0; i<=m; i++)
		{
			f[i]=0;
		}
		
		for (i=1; i<=n; i++)
		{
			for (j=p[T-1][i]; j<=m; j++)
			{
				f[j]=max(f[j],f[j-p[T-1][i]]+p[T][i]-p[T-1][i]);
			}
		}
		
		mm=0;
		for (i=0; i<=m; i++)
		{
			mm=max(mm,f[i]);
		}
		
		m+=mm;
	}
	
	printf("%d",m);
	
	return 0;
}

T4 加工零件(work)

20pt

直接看第 aa 号节点与第 11 号节点有没边相连就行了。

如果是用链式前向星，复杂度是 O(nq)O(nq) 的；如果是用领接矩阵，复杂度是 O(q)O(q) 的。

40pt

BFS 预处理，从第 11 节点出发，看看走 LL 不可不可以到第 aa 号节点，之后直接离线就好了。

复杂度是 O(O(玄学+q)+q) 的。

60pt&80pt

本人还没有比较好的做法。。。。。。

100pt

有一个十分显然的结论：设 disi,0/1dis_{i,0/1} 分别为第 11 号节点到第 ii 号节点的偶数最短路和奇数最短路。

若 L≥disa,L mod 2L \geq dis_{a,L \bmod 2} 的话，那么是可以的。

这是为什么呢？假设 L=disa,L mod 2+2xL=dis_{a,L\bmod 2}+2x 那么我们可以先走最短路到 aa ，接着再随便选择一条与 aa 相连的边，来往 xx 次即可。

那么奇偶最短路怎么求呢？直接BFS就可以了，因为边权都是 11 。

复杂度是 O(n+q)O(n+q) 的。

Code:

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
#include <cstdio>
#include <queue>
#define il inline
using namespace std;

int n,m,q;
struct Edge
{
	int to,next;
}edge[200001];
int head[100001],sze;
int dis[100001][2];

il int read()
{
	int res=0,sign=1;
	char c;
	
	while ((c=getchar())<'0'||c>'9') if (c=='-') sign=-1;
	
	res=c-'0';
	while ((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	
	return res*sign;
}

il void add(int u,int v)
{
	edge[++sze]=(Edge){v,head[u]},
	head[u]=sze;
}

il void bfs()
{
	queue<pair<int,int> > q;
	int i;
	
	q.push(make_pair(1,0));
	while (!q.empty())
	{
		int u=q.front().first,l=q.front().second;
		q.pop();
		for (i=head[u]; i; i=edge[i].next)
		{
			int v=edge[i].to;
			if (dis[v][l^1]==1e9)
				dis[v][l^1]=dis[u][l]+1,q.push(make_pair(v,l^1));
		}
	}
}

int main()
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	
	n=read(),m=read(),q=read();
	int i,u,v;
	for (i=1; i<=m; i++)
	{
		u=read(),v=read();
		add(u,v),add(v,u);
	}
	
	for (i=1; i<=n; i++)
	{
		dis[i][0]=1e9,dis[i][1]=1e9;
	}
	dis[1][0]=0;
	bfs();
	
	int x,l;
	while (q--)
	{
		x=read(),l=read();
		if (head[1]==0) printf("No\n");
		else if (l<dis[x][l&1]) printf("No\n");
		else printf("Yes\n");
	}
	
	return 0;
}