模拟
【补题】18年多校3
目录
Euler Function
Description
Giving an integer $k$, your task is to find the $k-th$ smallest positive integer $n$, that $\phi(n)$ is a composite number.
Solution
由$gcd(n,\ k)=gcd(n,\ n-k)$，易得$n>2$时$\phi(n)$为偶数，则不难证明当$n\le 7$时，$\phi(n)$恒为合数。
1 |
|
Grab The Tree
Description
Giving an integer $k$, your task is to find the $k-th$ smallest positive integer $n$, that $\phi(n)$ is a composite number.
Solution
由$gcd(n,\ k)=gcd(n,\ n-k)$，易得$n>2$时$\phi(n)$为偶数，则不难证明当$n\le 7$时，$\phi(n)$恒为合数。
1 |
|
【补题】18年多校2
目录
Game
Description
Alice and Bob are playing a game.
The game is played on a set of positive integers from 1 to $n$.
In one step, the player can choose a positive integer from the set, and erase all of its divisors from the set. If a divisor doesn’t exist it will be ignored.
Alice and Bob choose in turn, the one who cannot choose (current set is empty) loses.
Alice goes first, she wanna know whether she can win. Please judge by outputing Yes or No.
Solution
考虑$n>1$时先手取1等价于互换先后手，故Alice必胜。
1 |
|
Swaps and Inversions
Description
Long long ago, there was an integer sequence a.
Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay $x$ yuan for every inversion in the sequence.
You don’t want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay $y$ yuan to swap any two adjacent elements.
What is the minimum amount of money you need to spend?
Solution
交换相邻项使数组有序需要的最小次数等于逆序数。
故所求为逆序数$\ *min(x, y)$。逆序数使用归并排序求出。
1 |
|
【补题】18年多校1
目录
- Maximum Multiple [HDU 6298]
- Triangle Partition [HDU 6300]
- Time Zone [HDU 6308]
- Balanced Sequence [HDU 6299]
Maximum Multiple
Description
Given an integer $n$, Chiaki would like to find three positive integers $x,\ y$ and $z$ such that: $n=x+y+z\ (1<n<10^6),\ x∣n,\ y∣n,\ z∣n$ and $xyz$ is maximum.
Solution
$n<3$时，无解。
$n|3$时，$max(xyz)=(n/3)^3$。
$n|4$时，$max(xyz)=2(n/4)^3$。
其他时候，$x=y=z$显然不是解；不妨设$x<y$，可知$x\leq \frac{1}{5}n,\ y\leq\frac{1}{2}n$，显然也无解。
1 |
|
Triangle Partition
Description
Chiaki has $3n,\ 1<n<1000$ points $p_1,\ p_2,\ …,\ p_{3n}$. It is guaranteed that no three points are collinear.
Chiaki would like to construct n disjoint triangles where each vertex comes from the $3n$ points.
Solution
贪心。按坐标从小到大排序，三个一组依次输出即可。
1 |
|
Time Zone
Description
Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.
Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.
Solution
简单模拟。经由时间戳进行计算。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
int T;
scanf("%d", &T);
for (int tt = 1; tt <= T; tt++)
{
int x, y;
double z;
scanf("%d%d UTC%lf", &x, &y, &z);
int sum = (x - 8) * 60 + y;
if (z > 0)
sum += int((z * 10 + 0.1) * 6);
else
sum += int((z * 10 - 0.1) * 6);
if (sum < 0)
sum += 1440;
sum %= 1440;
printf("%02d:%02d\n", sum / 60, sum % 60);
}
return 0;
}
Balanced Sequence
Description
Chiaki has $n$ strings $s_1,\ s_2,\ \dots,\ s_n$ consisting of ‘(‘ and ‘)’. A string of this type is said to be balanced:
- if it is the empty string
- if A and B are balanced, AB is balanced,
- if A is balanced, (A) is balanced.
Chiaki can reorder the strings and then concatenate them get a new string t. Let $f(t)$ be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of $f(t)$ for all possible t.
Solution
首先对每个串进行处理，消除匹配后的串为左侧若干个右括号（数量记为r）和右侧若干个左括号（数量记为l）组成。
为了使括号匹配尽可能多而排列所有串。显然应将所有$l-r > 0$的串放在所有$l-r < 0$的串左侧。
对于$l-r > 0$的串，从左至右依次放置时，显然未匹配的左括号数L不断增大；故为尽可能匹配，应该将r小的串排在前面。
同理，对于$l-r < 0$的串，应将l大的串放在前面。
依上述策略排序，然后再处理一次，得到最后剩下未匹配括号的数量。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
83
84
85
using namespace std;
const int MAXN = 100000 + 10;
char str[MAXN];
int cnt = 0;
struct Pair
{
int id, l, r;
int v;
Pair(int id = 0, int l = 0, int r = 0) : id(id), l(l), r(r)
{
v = l - r;
}
bool operator<(const Pair &b) &
{
if (v >= 0 && b.v <= 0)
return true;
else if (v <= 0 && b.v >= 0)
return false;
else if (v > 0 && b.v > 0)
return r < b.r;
else if (v < 0 && b.v < 0)
return l > b.l;
}
}a[MAXN];
void analyse(char *s)
{
int l = 0, r = 0;
for ( ; *s; ++s)
{
if (*s == '(') //)
l++;
else if (l)
l--;
else
r++;
}
a[cnt] = Pair(cnt, l, r);
cnt++;
}
int solve(int n)
{
sort(a, a + n);
int L = 0, R = 0;
for (int i = 0; i < n; i++)
{
if (L < a[i].r)
{
R += a[i].r - L;
L = a[i].l;
}
else
{
L += a[i].v;
}
}
return L + R;
}
int main()
{
int T;
scanf("%d", &T);
for (int tt = 1; tt <= T; tt++)
{
cnt = 0;
int n;
scanf("%d%d", &n);
int sum = 0;
for (int i = 0; i < n; i++)
{
scanf("%s", str);
sum += strlen(str);
analyse(str);
}
printf("%d\n", sum - solve(n));
}
return 0;
}
Distinct Values
Description
Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.
Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.
Solution
简。
Chiaki Sequence Revisited
Description
Chiaki is interested in an infinite sequence $a_1,\ a_2,\ a_3,\ …,$ which is defined as follows:
Chiaki would like to know the sum of the first n terms of the sequence, i.e. $\sum\limits_{i=1}^{n}a_i$. As this number may be very large, Chiaki is only interested in its remainder modulo (1e9+7).
Solution
通项难以通过化简得出，于是打表找规律。
观察发现数列从1开始递增，并且每个数字重复出现若干次数。不考虑$a_1$从第二项开始计数，则设数列$b_n$为数字n在$a_n$中出现的次数，不难得到 $b_{2^n}=n+1$，$b_{2^nk}=b_{2^n}=n+1$。