xiaoyu's blog

Coding for a better life!

0%

北京信息科技大学第十一届程序设计竞赛(重现赛)

链接:https://ac.nowcoder.com/acm/contest/940
来源:牛客网

D.kotori和迷宫

题目描述

kotori在一个n*m迷宫里,迷宫的最外层被岩浆淹没,无法涉足,迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的,最近的出口离她有多远?

输入描述:

第一行为两个整数n和m,代表迷宫的行和列数 (1≤n,m≤30)

后面紧跟着n行长度为m的字符串来描述迷宫。’k’代表kotori开始的位置,’.’代表道路,’*’代表墙壁,’e’代表出口。保证输入合法。

输出描述:

若有出口可以抵达,则输出2个整数,第一个代表kotori可选择的出口的数量,第二个代表kotori到最近的出口的步数。(注意,kotori到达出口一定会离开迷宫)

若没有出口可以抵达,则输出-1。

示例1

输入

1
2
3
4
5
6
7
6 8
e.*.*e.*
.**.*.*e
..*k**..
***.*.e*
.**.*.**
*......e

输出

1
2 7

说明

可供选择坐标为[4,7]和[6,8],到kotori的距离分别是8和7步。

思路:广搜,我是直接从k到每个e点,需要注意的是当走到e点时就要退出来不该继续走了。

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
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int n, m, start;
const int maxn = 40;
string maze[maxn];
int steps[maxn * maxn], vis[maxn * maxn];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] != '*';
}
vector<int> v;
void bfs() {
queue<int> q;
q.push(start);
vis[start] = 1;
steps[start] = 0;
while (!q.empty()) {
int cur = q.front();
int x = cur / m, y = cur % m;
q.pop();

if (maze[x][y] == 'e') continue;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
int next = nx * m + ny;
if (valid(nx, ny) && !vis[next]) {
vis[next] = 1;
q.push(next);
if (maze[nx][ny] == 'e') {
v.push_back(next);
}
steps[next] = steps[cur] + 1;
}
}
}
}

int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> maze[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'k') {
start = i * m + j;
}
}
}
v.clear();
bfs();
int _min = 0x3f3f3f3f;
for (int i = 0; i < v.size(); i++) {
_min = min(steps[v[i]], _min);
}
if (v.size() == 0) cout << "-1\n";
else cout <<v.size() << " " << _min << endl;
return 0;
}

E.kotori和素因子

题目描述

kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是,kotori有强迫症,她不允许两个不同的正整数取出相同的素因子。

她想知道,最终所有取出的数的和的最小值是多少?

注:若a%k==0,则称k是a的因子。若一个数有且仅有两个因子,则称其是素数。显然1只有一个因子,不是素数。

输入描述:

第一行一个正整数n,代表kotori拿到正整数的个数。

第二行共有n个数ai,表示每个正整数的值。

保证不存在两个相等的正整数。

1<=n<=10

2<=ai<=1000

输出描述:

一个正整数,代表取出的素因子之和的最小值。若不存在合法的取法,则输出-1。

示例1

输入

1
2
4
12 15 28 22

输出

1
17

说明

分别取3,5,7,2,可保证取出的数之和最小

示例2

输入

1
2
5
4 5 6 7 8

输出

1
-1

备注:

1<=n<=10
2<=ai<=1000

直接找出这些数的所有素因子,由于数据规模小,一个深搜解决。

-1的情况可以预判:就是当所有素因子个数小于n时,一定不存在合法的取法。

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
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
using namespace std;
const int maxn = 10100;
int a[maxn], vis[maxn], prime[maxn];
int n, _min;
void init() {
prime[0] = prime[1] = 1;
for (int i = 2; i <= sqrt(1010); i++) {
if (prime[i] == 0) {
for (int j = i * i; j <= 1010; j += i) {
prime[j] = 1;
}
}
}
}

void dfs(const vector<int> &v, int index, int sum) {
if (index == n) {
_min = min(_min, sum);
return;
}
for (int i = 0; i < v.size(); i++) {
if (!vis[i] && a[index] % v[i] == 0) {
vis[i] = 1;
dfs(v, index + 1, sum + v[i]);
vis[i] = 0;
}
}
}

int main() {
init();
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
set<int> sset;
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 2; j <= a[i]; j++) {
if (a[i] % j == 0 && prime[j] == 0) {
sset.insert(j);
}
}
}
if (sset.size() < n) {
cout << -1 << endl;
} else {
vector<int> v;
int sum = 0, cnt = 0;;
for (auto it : sset) {
v.push_back(it);
}
_min = 0x3f3f3f3f;
dfs(v, 0, 0);
cout << _min << endl;
}
return 0;
}

G.kotori和抽卡(二)

题目描述

kotori最近喜欢上了lovelive这个游戏,因为她发现自己居然也是里面的一个人物。

lovelive有个抽卡系统。共有R、SR、SSR、UR四个稀有度,每次单抽对应稀有度的概率分别是80%,15%,4%,1%。

然而,kotori抽了很多次卡还没出一张UR,反而出了一大堆R,气得她想删游戏了。她想知道n次单抽正好出m张R卡的概率是多少?

输入描述:

两个正整数n和m(1<=m<=n<=50)

输出描述:

n次单抽正好出m张R的概率。保留四位小数。
示例1

输入

1
1 1

输出

1
0.8000

其实就是一个二项分布问题,即求C(n, m) * p^m * (1-p)^(n - m) 的值

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
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 50 + 10;

double f(int m, int n) {
double ans = 1;
for (int i = 1; i <= n; i++) {
ans = ans * m / i;
m--;
}
return ans;
}

double _pow(double n, int k) {
double ans = 1;
while (k--) {
ans *= n;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
double n, m;
cin >> m >> n;
printf("%.4f\n", f(m, n) * _pow(0.8, n) * _pow(0.2, m - n));

return 0;
}

H.andy和购物

题目描述

andy要去市场买n件货物,每件货物的价格为ai。商家为了吸引顾客,给每个买N件货物的顾客一个折扣清单,清单上有N个小于1的小数bj表示折扣。对于每个折扣bj,由用户自行决定用它使哪个货物的价格变成bj * ai,并且只能用一次。

andy想让你帮他算一下他最少的花费。

输入描述:

先输入一个正整数t,代表样例的组数。(1≤t≤10)

对于每个样例:

第一行,输入一个正整数n(1≤n≤1000)。

第二行包含n个整数,第i个整数a[i]代表第i个商品的原价。(1≤a[i]≤1e9)

第三行包含n个小数b[i],含义如题目描述。(0≤b[i]≤1)

输出描述:

对于每个样例,输出一个实数s,保留3位小数,表示最小的花费。

示例1

输入

1
2
3
4
1
5
1 2 3 4 5
0.1 0.2 0.3 0.4 0.5

输出

1
3.500

这道题贪心就完事了,让价格最高的商品打最多的折,也就是让最大的 a[i] 乘以 最小的 b[i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e3 + 10;
double a[maxn], b[maxn];
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
sort(a, a + n);
sort(b, b + n);
double ans = 0;
for (int i = 0; i < n; i++) {
ans += a[i] * b[n - i - 1];
}
printf("%.3lf\n", ans);
}
return 0;
}

I.andy种树

题目描述

andy在他的庄园里种了n棵树,排列成一排,标号为1到n。最开始的时候n棵树的高度都是0,也就是种子刚刚被埋下,树还没有长出来。

andy会一种魔法,他每使用一次魔法,就可以让树标号落在连续区间[l, r]里的树的高度增加1。他可以使用q次这种魔法,然后他很好奇,在使用了q次魔法之后,他的所有树的高度分别是多少呢?

输入描述:

第一行输入两个整数n,q。(1<= n, q <= 1e5)

接下来q行,每行输入两个整数l, r(l <= r),表示andy让标号落在区间[l, r]里的数高度都加1

输出描述:

输出有一行n个整数,每个整数后面有空格。输出末尾没有换行

第i个数表示第i棵树的高度

示例1

输入

1
2
3
4
10 3
1 3
2 4
3 3

输出

1
1 2 3 1 0 0 0 0 0 0

说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
andy种了10棵树

第一次使用魔法使得1、2、3棵树的高度增加1,

所有树的高度为

1 1 1 0 0 0 0 0 0 0

第二次使用魔法使得2、3、4棵树的高度增加1,

所有树的高度为

1 2 2 1 0 0 0 0 0 0

第三次使用魔法使得第3棵树的高度增加1

所有树的高度为

1 2 3 1 0 0 0 0 0 0

典型的区间修改,点查询,上来就是套树状数组板子

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1e5 + 10;
int sum[maxn], a[maxn];
int n, q, l, r;
int lowbit(int x) {
return x & (-x);
}
void update(int index, int val) {
for (int i = index; i > 0; i -= lowbit(i))
sum[i] += val;
}
int ask(int index) {
int ans = a[index];
for (int i = index; i <= n; i += lowbit(i))
ans += sum[i];
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> q;
while (q--) {
cin >> l >> r;
update(r, 1);
update(l - 1, -1);
}
for (int i = 1; i <= n; i++) {
cout << ask(i) << " ";
}
return 0;
}