0%

2019 杭电多校 第六场

2019 Multi-University Training Contest 6

补题链接:2019 Multi-University Training Contest 6

1002 Nonsense Time (HDU 6635)

题意

给定包含 $n$ 个不同数字的排列 $p$。一开始所有数字都冻住。再给出一个长度为 $n$ 的数组 $k$,$k[i]$ 表示 $p[k[i]]$ 在第 $i$ 时刻解冻。输出 $n$ 个数,表示第 $i$ 个时刻数组 $p$ 中解冻的数字的最长上升子序列的长度。

题解

思维 LIS

倒过来考虑 (时光倒流)。一开始所有数都是解冻的,一个一个开始冰冻。每冰冻一个数字,判断是否在当前最长上升子序列内,如果不在就输出当前最长上升子序列的长度,否则重新计算最长上升子序列。

由于给定的排列是随机的,随机排列的期望 $LIS$ 的长度是 $O(\sqrt{n})$,一个数在最长上升子序列内的概率为 $1 / \sqrt{n}$,那么期望删除 $O(\sqrt{n})$ 个数才会修改 $LIS$。期望时间复杂度为 $O(n\sqrt{n}logn)$。

1008 TDL (HDU 6641)

$solved by zmz$

题意

定义 $f(n, m)$ 为第 $m$ 小的整数 $x$ 满足 $x>n$ 并且 $gcd(x,n)=1$。给定 $m$ 和 $k$,求满足 $(f(n,m)-n)⊕n=k$ 的最小正整数 $n$。($⊕$ 代表按位异或)

题解

质数的密度分布

$f(n,m)-n$ 不会超过第 $m$ 个与 $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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#pragma GCC optimize(2)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iomanip>
#include <set>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}

int main() {
ll k, m;
int T;
scanf("%d", &T);
while (T--) {
// cout << 1 << endl;
cin >> k >> m;
ll left = k - 1000;
if (left < 0)left = 1;
ll right = k + 1000;
int flag = 0;
for (ll i = left; i <= right; i++) {
ll cnt = 0, tmp = i + 1;
while (cnt < m) {
if (gcd(tmp, i) == 1) {
cnt++;
// cout << i << " " << tmp << endl;
}
tmp++;
}
// cout << i << endl;
// cout << "tmp:" << tmp << endl;
if ((k ^ i) == tmp - i - 1) {
flag = 1;
cout << i << endl;
break;
}
}
if (!flag)cout << -1 << endl;
}
return 0;
}

1012 Stay Real (HDU 6645)

题意

给定一个小根堆,两个人每次从叶子节点取出一个数累加到自身的分数,堆为空时游戏结束,两个人选择最优策略。求两个人最终的分数。

题解

贪心 排序

两个人每次取最大的值,因此直接排序后间隔着累加就行,也可以使用优先队列。时间复杂度 $O(nlogn)$。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
typedef long long ll;

ll a[maxn];

int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
}
sort(a, a + n);
ll s1 = 0, s2 = 0;
for(int i = n - 1; i >= 0; --i) {
if((n - i) % 2) s1 += a[i];
else s2 += a[i];
}
printf("%lld %lld\n", s1, s2);
}
return 0;
}

欢迎关注我的其它发布渠道