2021 Jiangxi Provincial Collegiate Programming Contest

发表于 分类于

链接

题目链接

题目

A. Mio visits ACGN Exhibition

设 $f_{i,j,k}$ 表示到达 $(i,j)$ 时用了 $k$ 个 $0$ 的方案数，最终将结果就是 $\sum_i f_{n,m,i}$。

滚动数组优化空间即可。

时间复杂度 $O(n^3)$。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y;return x>=mod?x-mod:x;}
const int N=503;
int n,m,p,q;
int a[N][N];
ll f[2][N][N+N];
int d;

int main()
{
	n=read(); m=read(); p=read(); q=n+m-1-read();
	fo(i,1,n)
		fo(j,1,m)
			a[i][j]=read();
	f[0][1][0]=1;
	d=0;
	fo(i,1,n)
	{
		d=1-d;
		fo(j,1,m) fo(k,0,n+m) f[d][j][k]=0;
		fo(j,1,m) fo(k,0,n+m) f[d][j][k+(!a[i][j])]=Add(f[d][j-1][k],f[1-d][j][k]);
	}
	ll ans=0;
	fo(i,p,q) ans=Add(ans,f[d][m][i]);
	printf("%lld\n",ans);
	return 0;
}

B. Continued Fraction

直接模拟欧几里得过程即可。

写到一半才看到 $\gcd(x,y)=1$ 的条件。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> vec;
int x,y;
int main()
{
	CASET
	{
		x=read(); y=read();
		vec.clear(); vec.pb(x/y);
		x%=y; swap(x,y);
		for(;y;)
		{
			vec.pb(x/y);
			x%=y;
			swap(x,y);
		}
		printf("%d ",vec.size()-1);
		for(int v:vec) printf("%d ",v);
		printf("\n");
	}
	return 0;
}

C. Crystal Caves

有一个重要的性质：每一层只会选择它的两个端点中的一个。

从后往前进行DP，设 $f_{i,j}$ 表示考虑到第 $i$ 层时，$[i,n]$ 层中有 $j$ 个用了左边时，第 $i\sim n$ 层对答案的贡献的最小值。

那么只需要算第 $i$ 层的贡献即可。

时间复杂度 $O(n^2)$。

D. Character Distance

构造题好麻烦。。。

首先特判掉存在只出现一次的数，这时候只需要排序后输出就好了。

显然最优的方案只有可能是选出一种数，然后剩下的排序。

假设选择了 $x$，那么就会有两种情况：

  1. 从 $x$ 的开头 $i$ 开始选，后面的数足够多，能选上，也就是 $i+(num-1)\times d\le n$。

  2. 不满足第一种的条件时，只能让 $x$ 的开头往后延。

对于两种情况，我们贪心的从后面开始选，显然开头的位置是越大越好的。

对两种方法，取字典序最小的就可以了。

E. The Legend of God Flukehn in Eastern

题意

在一二维平面上 $n$ 个卒子，每次你能且仅能选择一个往下走一步。

将军初始在 $(0,0)$ 上，每次必须选择上左下右，上左，上右六个方向中的一个走一格。

任意时刻将军与卒子在同一格，则卒子被吃掉。你和将军轮流走，你先走。

问走最优策略时，将军最多能吃多少个卒子。

$n\le 10^6$。

题解

大毒瘤题。

三人用了差不多1h分析性质：

  1. 设卒子相对于将军形成的向量为 $(x,y)$，则当且仅当 $y<|x|$ 时卒子能走掉。

证明：显然。

  1. 最多只能保留一个卒子。

证明：当只剩下两个卒子时，先走到其中一个卒子的列中，如果此时该卒子在将军上方，那么能吃掉其中一个，否则一直追着这个卒子，直到第二个卒子满足性质1的条件为止。

  1. 如果能吃完所有卒子，那么一定是按 $y$ 从小到大的顺序吃的。

证明：显然。

  1. 对于某个时刻，如果有任何一个卒子满足性质一，那么它就能走掉。

证明：显然。

  1. 对于两个卒子 $i,j$ （不妨设 $y_i\le y_j$），若存在某个时刻使得 $y_j-y_i<|x_j-x_i|$，且 $|x_j-x_i|>1$，那么其中一个可以走掉。

证明：根据性质3，将军要先去吃 $y$ 比较小的卒子，再它吃掉这个卒子后，另外一个卒子一定满足性质 $1$。

  1. 对于两个卒子 $i,j$ （不妨设 $y_i\le y_j$），若在初始时刻使得 $y_j-y_i-y_i<|x_j-x_i|$，且 $|x_j-x_i|>1$，那么其中一个可以走掉。

根据性质5，任何两个 $|x_j-x_i|>1$ 的卒子，如果想要保住卒子 $j$，那么就需要在将军吃掉 $i$ 之前，$j$ 一直往下，直到 $i,j$ 满足性质5为止。而将军吃掉卒子 $i$ 大概需要花费 $y_i$ 步，也就是 $j$ 能走 $y_i$ 步向下。（这里的大概是因为需要下方的点不满足性质7才可以）

  1. 对于两个卒子 $i,j$ 满足 $|x_j-x_i|=1$ ， $y_j-y_i-y_i\le 0$ 且存在第三者 $k$ 使得 $x_i\neq x_k,x_j\neq x_k$，且 $y_k\geq y_i$， 那么这三个的其中一个可以走掉。

如果没有第三者，这两个卒子一定走不掉，因为可以先吃完 $k$ 再去吃 $i,j$（这里 $k,i$ 或 $k,j$ 均不满足性质6，否则可以溜掉）。否则显然可以走掉。

综上，根据如上性质，我们只需要判断：

  1. 是否存在一个卒子 $i$，使得 $y_i<|x_i|$。

  2. 是否存在两个卒子 $i,j$，使得 $y_i\le y_j,y_j-2y_i < |x_j-x_i|,1 < |x_j-x_i|$。

  3. 是否存在三个卒子 $i,j,k$，使得 $y_i\le y_j,y_i\le y_k,y_j-2y_i < 1 = |x_j-x_i|,x_i\neq x_k,x_j\neq x_k$。

代码过于丑陋就不放了。。。

F. Four Column Hanoi Tower

设 $f_i$ 表示4座塔的答案，$g_i$ 表示3座塔的答案。

那么就有：$f_i=\min(2f_k+g_{n-k}),f_1=1$ 以及 $g_i=2g_{i-1}+1,g_1=1$。

然后打个表，发现前几项为 $1,3,5,9,13,17,25,33,41,49,\cdots$。一阶差分为 $2,2,4,4,4,8,8,8,8,\cdots$。

直接上 Python 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
a = [0,1]
now = cnt = 2
las = 0
for i in range(2,10001):
	las = las+1
	a.append(a[-1]+now)
	if las == cnt:
		cnt = cnt+1
		las = 0
		now = now+now
n = int(input())
for x in range(0,n):
	print(a[int(input())])

G. Magic Number Group

对每个数分解质因数后，剩下的是区间众数。每个位置最多挂上 $7$ 个数。

直接使用莫队即可。时间复杂度 $O(7n\sqrt{n})$。

有点小卡常。

H. Hearthstone So Easy

只有三种情况：

  1. $n=1$，A直接死了。
  2. A能在第一次干剩B到最多一滴血，A赢。
  3. 否则B赢。

I. Homework

换根DP即可。

J. LRU

显然满足二分性，于是二分后，然后随便判断。可以做到 $O(n\log n)$。

K. Many Littles Make a Mickle

输出 $m\sum_{i=1}^ni^2$。

L. It Rains Again

线段投影到 $x$ 轴，然后随便做。