比赛 - AtCoder Beginner Contest 142

【AtCoder Beginner Contest 142】
比赛链接: https://atcoder.jp/contests/abc142

前言

这次比赛略水，真是上分的好比赛。作为仅有300+rating的我直接安排，AK比赛后直接上到900+。

比赛中有几个题对我还是比较有意义的。

题解

A

题意翻译：

给出一个数$N$，从$1~N$中随机抽取，求抽到奇数的概率。

这题还挺简单，再看数据范围$1 <= N <= 100$，太水了！

B

题意翻译：

第一行给出一个数$N$代表一个数列的长度，再给出$K$。第二行给出数列各项的值。求数列中大于等于$K$的个数。

数据范围$1 <= N <= 10^5$，也很水，入门难度。

C

题意翻译：

一个教室中有$N$名同学，给出每个同学到达教室时教室中的人$A_i$（包括自己），求出到达顺序。

数据范围$1 <= N <= 10^5$，正常范围。

直接上排序，按$A_i$从小到大排序，最后依次输出编号。

D

这题看了好长时间才看懂题目。

题意翻译：

给出两个数$A$、$B$，求出两个数的共同约数集合的一个子集。这个子集满足各元素两两直接都互质，求出子集最多包含多少元素。

数据范围$1 <= A,B <= 10^{12}$。

看起来好像有点麻烦，但实际上我们先求出$C=gcd(A, B)$，那么$C$的约数就是两个数的共同约数。然后再分解质因数即可，题目转换为求一个较大的数的质因数个数。

核心代码：

1
2
3

long long gcd(long long a, long long b) {
	return b ? gcd(b, a % b) : a;
}

1
2
3
4
5
6
7
8

long long ans= 1;
for(long long i= 2; i * i <= m; i++) {
    if(m % i == 0) {
        ++ans;
        while(m % i == 0) m/= i;
    }
}
if(m > 1) ++ans;

E

题目到这已经不再那么水了。

题意翻译：

给出一个数$N$代表多少上锁的盒子，再给出一个数$M$代表有多少钥匙。每个钥匙需要花$A_i$来购买，可以打开$B_i$个盒子，分别为$C_{ij}$，一个钥匙可以多次使用。问打开所有盒子的最小花费，若无解输出-1。

数据范围$1 <= N <= 12$、$1 <= M <= 10^3$、$1 <= A_i <= 10^5$

一开始没看数据范围我以为是舞蹈链，差点自闭了。然后再看数据范围，$N$比较小，于是想到状压DP。

设置一个数组$F[1 << N]$表示打开某些盒子的最小花费。

先枚举$M$个钥匙钥匙，对将钥匙能打开的盒子二进制压缩到数$X$，然后取最小值。

核心代码：

1
2
3
4
5

int getx(int x) {
	int res= 0;
	for(int i= 1; i <= b[x]; i++) res+= (1 << (c[x][i] - 1));
	return res;
}

然后再写转移方程，由于我比较傻，所以一开始写了$F[i | j] = min(F[i] + F[j])$，结果反而枚举的是$x = i | j$。看起来复杂度$2^{3N}$，然后确实TLE了。

然后我想把方程改为$F[i] = min(F[i], f[j] + f[i ^ j])$，现在想想好像枚举i,j就可以了，那样复杂度$2^{2N}$好像能过，可惜我比赛时没想这种方法。

我在比赛时用了更麻烦的方法，因为我想起了之前一道题，在初始化时枚举二进制所有子集全部更新。这样预处理复杂度最大$M * 2^{N}$能过，然后再DP。我就来Blog上擅用搜索引擎，搜到了AT2657 - Mole and Abandoned Mine。

然后非常套路的预处理出每个数二进制下1的个数。

核心代码：

1
2
3
4
5

int getg(int x) {
	int res= 0;
	while(x) ++res, x-= (x & -x);
	return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int maxx= (1 << n);
for(int i= 0; i < maxx; i++) w[i]= getg(i);
memset(f, 0x3f, sizeof(f));
for(int i= 1, j; i <= m; i++) {
    j= getx(i);
    for(int k= j; k; k= (k - 1) & j) f[k]= min(f[k], a[i]);
}
for(int i= 1; i <= n; i++) {
    for(int j= 0; j < maxx; j++) {
        if(w[j] != i) continue;
        for(int k= 0; k < maxx; k++) {
            if(j == k || w[k] >= i || (k & (~j))) continue;
            f[j]= min(f[j], f[k] + f[k ^ j]);
        }
    }
}

F

终于到最后一题，比较激动。题目还挺复杂的。

题意翻译：

给出一个图G，有$N$个点，$M$条单向边，无自环和重边。求出一个子图包含$N’$个点，$M’$为这些点构成的边，满足所有点的入度和出度都为1。如果有多个子图，输出任意一个。输出$N’$和包含的点。无解输出-1。

数据范围$1 <= N <= 1000$、$1 <= M <= 2000$

感觉有点难，但毕竟SpecialJudge可以一试，可能会有简单做法。

先手膜一些图，发现暴力DFS可做。虽然是类似ACM的赛制，但剩余时间不多了，先打个试试吧。

再膜一下第三组数据，发现只要有环就一定有解。

因为入度出度为一，可以把这个图称为单环。我们从每个点DFS，让途中经过的点的所有能到达的点入度+1。这样DFS时，如果一个点入度已经大于1，那么从起始点开始一定不能与当前状态构成单环。所以我们每次DFS一个能到达的入度为1的点。点。再记录我们已经走过的点，如果又一次到达某点，那么一定形成了单环。如果某次更新时，途中走过的点的入度>1了，那么这个点也不能与当前状态构成单环。

解释不清楚，核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int n, m, tmpx, tmpy, r[1005], st[1005], ans[1005];
vector< int > edg[1005];
int dfs(int nown) {
	if(st[nown]) return 1;
	st[nown]= 1;
	for(int i= 0; i < edg[nown].size(); i++) {
		++r[edg[nown][i]];
		if(r[edg[nown][i]] > 1 && st[edg[nown][i]]) {
			for(int j= 0; j <= i; j++) --r[edg[nown][j]];
			st[nown]= 0;
			return 0;
		}
	}
	for(int i= 0; i < edg[nown].size(); i++) {
		if(r[edg[nown][i]] == 1 && dfs(edg[nown][i])) {
			ans[++ans[0]]= nown;
			return 1;
		}
	}
	for(int i= 0; i < edg[nown].size(); i++) --r[edg[nown][i]];
	st[nown]= 0;
	return 0;
}

我一开始的做法是，枚举每个点为起始点跑一次DFS，直到找出答案，然后就TLE了几个点，但是AC了大部分就还能救。

既然DFS都是乱搞，那就再加一个随机化。本题时限2s，那么不到1.8s我们就继续DFS。

然后复杂度我也不太会证明，因为DFS复杂度也非常玄学。大概是O(能过)。最后输出答案我还sort了一遍，因为样例是排序好的。

核心代码：

1
2
3

srand(time(0));
while(clock() < CLOCKS_PER_SEC * 1.8)
	if(dfs(rand() % n + 1)) break;

后记

仍犯了很多错误，A题一开始竟把奇数看成质数，D题枚举因数没开long long。