2020 ICPC南京站训练部分题解+补题

发表于 | 分类于 | 本文总阅读量 次
字数统计: 4.1k 字 | 阅读时长 ≈ 19 分钟

今天是以2020 ICPC南京站作为训练题目，这篇文章主要是对做的题的一个总结以及对于一些差一点做出来题的一个补题。题目顺序是按照个人角度的难度顺序来排的，包括在训练时做的顺序等等。

K. K Co-prime Permutation

题目大意

给定两个数n(1≤n≤106)n(1\le n \le 10^6)，k(0≤k≤n)k(0 \le k \le n)，要求找到一个从1到n的排列，使得这个排列在第i个位置上的数（从1开始）pip_i，恰好有k个i与pip_i互质，如果不存在输出-1。

思路

签到题，是类似CF前两题的一个构造题目，实际上是找到一个从1到n的排列，与从1到n的顺排列相应的位置上恰好有k个数互质。这个实际上是考察了一个互质的性质：相邻的两个数一定互质。因此我们可以恰好使前k个数错一位，后面的n-k个数原样输出即可，复杂度是线性的。

代码

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
#include <bits/stdc++.h>
using namespace std;
int n, k;
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> k;
    if (k == 0)
    {
        cout << -1;
        return 0;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (cnt < k)
        {
            if (i != 1)
            {
                cout << ' ';
            }
            if (i == k)
            {
                cout << 1;
            }
            else
                cout << i + 1;
            cnt++;
        }
        else
        {
            cout << ' ';
            cout << i;
        }
    }
    return 0;
}

L. Let’s Play Curling

题目大意

有红蓝两个队，分别有n,m(1≤n.m≤105)n,m(1\le n.m \le 10^5)（n,m的分别总和不超过5×1055\times 10^5）颗球分布在一维坐标系上。需要找到一个坐标点c（可以是浮点数），当红队存在球，该球到坐标点c的距离小于蓝队所有球到点c的距离时，红队获胜，且得分为红队存在的这种类型的球的数量。问红队的最高得分是多少。

思路

从样例可以看出，同时也比较显然的贪心，那就是如果对两个蓝队之间有一些红队的球，那么将这个坐标点定为两个蓝队球的中点，那么两个点中间的红队的球到该坐标点的距离一定小于两个蓝队球到中心点的距离，因此这种情况所有两个蓝队球之间的红队球都能产生贡献（不包括重合的端点），也是最好的情况。因此可以对于蓝队球与红队球的坐标进行排序，去遍历蓝队的球，用一个指针标记此时扫描到的红队球的下标，去找到每两个蓝队球之间的红队球的个数（如果两个蓝队球坐标相差不大于1，必定没有），找到其中的最大值，便是答案。有一个需要注意的陷阱就是，这个最大情况可能出现在序列的两端，即红队有一些球在蓝队最左边坐标的左边，那么c只要设置到红队最左边球的左边，那么蓝队最左边的那些红队球都会产生贡献。右边同理。在计算完两个相邻的蓝队球以后记得处理两边即可。复杂度排序是nlog⁡nn\log n，遍历寻找是n+mn+m，最后的复杂度应该是max(nlog⁡n,mlog⁡m,n+m)max(n\log n,m\log 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
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
int t;
constexpr int maxn = 1e5 + 10;
int a[maxn];
int b[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin >> t;
    int n, m;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        for (int j = 0; j < m; j++)
        {
            cin >> b[j];
        }
        sort(a, a + n);
        sort(b, b + m);
        int j = 0;
        int ans = 0;
        for (int i = 1; i < m; i++)
        {
            if (b[i] - b[i - 1] > 1)
            {
                int now_ans = 0;
                while (j < n && a[j] < b[i])
                {
                    if (a[j] > b[i - 1])
                        now_ans++;
                    j++;
                }
                ans = max(ans, now_ans);
            }
        }
        j = 0;
        int now_ans = 0;
        while (j < n && a[j] < b[0])
        {
            now_ans++;
            j++;
        }
        ans = max(ans, now_ans);
        j = n - 1;
        now_ans = 0;
        while (j >= 0 && a[j] > b[m - 1])
        {
            now_ans++;
            j--;
        }
        ans = max(ans, now_ans);
        if (ans == 0)
            cout << "Impossible" << '\n';
        else
            cout << ans << '\n';
    }
    return 0;
}

E. Evil Coordinate

题目大意

在无限大的二维平面上，初始在原点(0,0)，给定一个雷的坐标(mx,my)，再给定一个字符串，每一个字符‘UDLR’分别表示向上、向下、向左、向右走一个单位，多组数据串长总和不超过10610^6，让找出一个该串的重排列，使得走的路径不经过雷，不存在则输出Impossible

思路

题意简单，也比较显然，模拟即可。模拟的方式不唯一，但是要注意模拟过程中的诸多细节，同时要注意模拟的所有情况要具有完备性。

同时官方题解也给出了一种非常巧妙的做法。首先容易证明如果存在可行解，那么必有一解可以通过连续向一个方向走构成，比如都向上，再都向下这样。所以可以枚举udlr走的顺序，计算4!次结果。然后依次去走，看看能不能走到，走不到就输出，如果都会走到雷，就是impossible。

从模拟的角度来说，我的模拟思路是首先可以发现无论怎么走，到达的终点都是固定的，记为(nowx,nowy)，同时，在x方向上，在y方向上，所有该方向走完都是到达了同一个坐标，因此可以先把所有一个轴方向上的字符都输出完，再去输出另一个方向上的。接着考虑点在轴上以及两个点y或者x相同的情况（可能会挡住）即可，也就有了讨论的方向。

首先如果雷在原点或者终点，那么一定是impossible

1.当雷与终点在同一条直线上时

  1. 当雷与终点都在坐标轴上时，考虑雷与终点的关系，如果雷与终点在不同半轴上，那么现在垂直方向上行走，再去终点方向走，再去雷的方向。
    如果在同一半轴上，如果终点比雷更接近原点，那么先垂直方向，再向没有点的半轴，再反向。否则雷比终点更近，判断垂直方向上是否能走，不能走则是impossible，否则先向垂直方向走一下，再平行方向，再垂直方向。
  2. 当不在坐标轴上时，先在垂直方向上走完，再走平行方向即可

2.当雷与终点同一条直线上时

  1. 当雷在坐标轴上时，先在雷所在坐标轴的垂直方向进行运动，再去平行方向运动
  2. 雷不在坐标轴上时，随便运动即可，保证向一个方向完全走完以后再去其他方向即可

复杂度是线性的

代码

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
//讨论的做法
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e5 + 10;
char s[maxn];
using ll = long long;
ll num_u, num_d, num_l, num_r;
void move(ll &x, ll &y, char action)
{
    if (action == 'U')
        y++, num_u++;
    else if (action == 'D')
        y--, num_d++;
    else if (action == 'L')
        x--, num_l++;
    else if (action == 'R')
        x++, num_r++;
}
void outl()
{
    for (int i = 0; i < num_l; i++)
    {
        cout << 'L';
    }
}
void outr()
{
    for (int i = 0; i < num_r; i++)
    {
        cout << 'R';
    }
}
void outu()
{
    for (int i = 0; i < num_u; i++)
    {
        cout << 'U';
    }
}
void outd()
{
    for (int i = 0; i < num_d; i++)
    {
        cout << 'D';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    ll mx, my;
    while (t--)
    {
        cin >> mx >> my;
        cin >> s;
        num_d = num_u = num_l = num_r = 0;
        ll s_len = strlen(s);
        ll nowx = 0, nowy = 0;
        for (int i = 0; i < s_len; i++)
        {
            move(nowx, nowy, s[i]);
        }
        if ((mx == 0 && my == 0) || (nowx == mx && nowy == my))
        {
            cout << "Impossible" << '\n';
            continue;
        }
        if (mx == 0 && nowx == 0)
        {
            if (my * nowy < 0 || abs(nowy) < abs(my))
            {
                outl();
                outr();
                if (my * nowy < 0)
                {
                    if (nowy < 0)
                    {
                        outd();
                        outu();
                    }
                    else
                    {
                        outu();
                        outd();
                    }
                }
                else
                {
                    if (nowy == 0)
                    {
                        if (my > 0)
                        {
                            outd();
                            outu();
                        }
                        else
                        {
                            outu();
                            outd();
                        }
                    }
                    else if (nowy < 0)
                    {
                        outu();
                        outd();
                    }
                    else
                    {
                        outd();
                        outu();
                    }
                }
            }
            else if (num_l == 0 && num_r == 0)
            {
                cout << "Impossible" << '\n';
                continue;
            }
            else
            {
                outl();
                outu();
                outd();
                outr();
            }
        }
        else if (my == 0 && nowy == 0)
        {
            if (mx * nowx < 0 || abs(nowx) < abs(mx))
            {
                outu();
                outd();
                if (mx * nowx < 0)
                {
                    if (nowx < 0)
                    {
                        outl();
                        outr();
                    }
                    else
                    {
                        outr();
                        outl();
                    }
                }
                else
                {
                    if (nowx == 0)
                    {
                        if (mx > 0)
                        {
                            outl();
                            outr();
                        }
                        else
                        {
                            outr();
                            outl();
                        }
                    }
                    else if (nowx < 0)
                    {
                        outr();
                        outl();
                    }
                    else
                    {
                        outl();
                        outr();
                    }
                }
            }
            else if (num_u == 0 && num_d == 0)
            {
                cout << "Impossible" << '\n';
                continue;
            }
            else if (num_u != 0)
            {
                outu();
                outr();
                outl();
                outd();
            }
            else if (num_d != 0)
            {
                outd();
                outr();
                outl();
                outu();
            }
        }
        else if (mx == nowx)
        {
            outu();
            outd();
            outl();
            outr();
        }
        else if (my == nowy)
        {
            outl();
            outr();
            outu();
            outd();
        }
        else if (my == 0 || mx == 0)
        {
            if (my == 0)
            {
                outu();
                outd();
                outl();
                outr();
            }
            else
            {
                outl();
                outr();
                outu();
                outd();
            }
        }
        else
        {
            outl();
            outr();
            outu();
            outd();
        }
        cout << '\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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//题解计算排列的模拟巧妙解法
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e5 + 10;
char s[maxn];
using ll = long long;
ll cnt[5];
void move(ll &x, ll &y, char action)
{
    if (action == 'U')
        y++, cnt[1]++;
    else if (action == 'D')
        y--, cnt[2]++;
    else if (action == 'L')
        x--, cnt[3]++;
    else if (action == 'R')
        x++, cnt[4]++;
}
void out(char ch, ll cnt)
{
    for (int i = 0; i < cnt; i++)
    {
        cout << ch;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    ll mx, my;
    while (t--)
    {
        cin >> mx >> my;
        cin >> s;
        memset(cnt, 0, sizeof(cnt));
        ll s_len = strlen(s);
        ll desx = 0, desy = 0;
        for (int i = 0; i < s_len; i++)
        {
            move(desx, desy, s[i]);
        }
        if ((mx == 0 && my == 0) || (desx == mx && desy == my))
        {
            cout << "Impossible" << '\n';
            continue;
        }
        int arrange[4] = {1, 2, 3, 4};
        int fflag = 0;
        do
        {
            //cout<<"cnt";
            ll now_x = 0, now_y = 0;
            int flag = 1;
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < cnt[arrange[i]]; j++)
                {
                    if (arrange[i] == 1)
                        now_y++;
                    else if (arrange[i] == 2)
                        now_y--;
                    else if (arrange[i] == 3)
                        now_x--;
                    else if (arrange[i] == 4)
                        now_x++;
                    if (now_x == mx && now_y == my)
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag == 0)
                    break;
            }
            if (flag == 1)
            {
                fflag = 1;
                for (int i = 0; i < 4; i++)
                {
                    for (int j = 0; j < cnt[arrange[i]]; j++)
                    {
                        if (arrange[i] == 1)
                            cout<<'U';
                        else if (arrange[i] == 2)
                            cout<<'D';
                        else if (arrange[i] == 3)
                            cout<<'L';
                        else if (arrange[i] == 4)
                            cout<<'R';
                    }
                }
                cout << '\n';
                break;
            }

        } while (next_permutation(arrange, arrange + 4));
        if (fflag == 0)
        {
            cout << "Impossible" << '\n';
            // for(int i=0;i<4;i++)
            // {
            //     cout<<arrange[i]<<' ';
            // }
            // cout<<'\n';
        }
    }
}

F - Fireworks

题目大意

制作一个烟花需要n分钟，点燃之前制作好的所有烟花需要m分钟，每个烟花有p10000\frac{p}{10000}的概率（后面认为p实际上就是p10000\frac{p}{10000} ）完美绽放。当有一只烟花完美绽放的时候，便可以去睡觉，问采取最优策略时，所能够去睡觉的最短期望时间。10410^4组数据，每组三个数n,m,p(1≤n,m≤109,1≤p≤104)n,m,p(1\le n,m \le 10^9,1\le p \le 10^4)

思路

典型的数学题（当然有时候也有可能需要结合递推）。首先考虑一下什么是最优策略，显然是在制作h个烟花后再去点燃，所用时间应该是h*n+m。如果要多加点燃次数的话，显然不会使方案最优。每一个烟花是否完美都是独立的，因此概率一样。当当前没有完美烟花的时候那需要再次用该策略再做一次（因为每次都是独立，前面不成功不会说使后续的概率增大，因此后续的最优策略不会变）。

基于这个思想，可以得到期望时间的计算公式（注意可以取反面，即所有烟花都不完美 对应 至少有一个烟花是完美的）：

E=(hn+m)(1−(1−p)h)+(1−p)h2(hn+m)(1−(1−p)h)+...+(1−p)h(k−1)k(hn+m)(1−(1−p)h)E=(hn+m)(1-(1-p)^h)+(1-p)^h2(hn+m)(1-(1-p)^h)+...+(1-p)^{h(k-1)}k(hn+m)(1-(1-p)^h)

E=(hn+m)(1−(1−p)h)∑i=1i(1−p)h(i−1)E=(hn+m)(1-(1-p)^h)\sum_{i=1}i(1-p)^{h(i-1)}

到这里，我们发现后面的式子是一个等差乘等比数列的形式，先计算一下该值，设：

S=∑i=1i(1−p)h(i−1)−−−1S=\sum_{i=1}i(1-p)^{h(i-1)}---1

(1−p)hS=∑i=1i(1−p)hi−−−2(1-p)^hS=\sum_{i=1}i(1-p)^{hi}---2

由1式减去2式错位相减得：

(1−(1−p)h)S=∑i=1(1−p)h(i−1)(1-(1-p)^h)S=\sum_{i=1}(1-p)^{h(i-1)}

一个单纯的等比数列了，进行求和：

(1−(1−p)h)S=lim⁡i→∞1−(1−p)hi1−(1−p)h(1-(1-p)^h)S=\lim\limits_{i\rightarrow \infty}\frac{1-(1-p)^{hi}}{1-(1-p)^h}

S=lim⁡i→∞1−(1−p)hi(1−(1−p)h)2S=\lim\limits_{i\rightarrow \infty}\frac{1-(1-p)^{hi}}{(1-(1-p)^h)^2}

S=1(1−(1−p)h)2S=\frac{1}{(1-(1-p)^h)^2}

原式：

E=hn+m1−(1−p)hE=\frac{hn+m}{1-(1-p)^h}

得到这个式子以后，可以直接猜测，或者测试前面的一部分数，可以发现它是一个单峰函数，可以对其进行三分。也可以求导以后对其零点进行二分。求解出某一个h，使其对应的E最小。复杂度为tlog⁡t\log{}或者tlog⁡2t \log{} ^2左右。对于二分或者三分如果不理解的话，在我的博客tag为“模板”的地方有这两种算法的解释。

求导的结果如下：

E′=h(1−(1−p)h)+(hn+m)(1−p)hln⁡(1−p)E'=h(1-(1-p)^h)+(hn+m)(1-p)^h\ln (1-p)

有一点要注意就是在计算时hn+m是整数运算，下面才会变成浮点数，而上面有可能在计算时就会溢出，考虑提前转换成double。

同时，在计算(1−p)h(1-p)^h时，由于h可能很大，所以正常计算的复杂度还是很高的，需要考虑用快速幂优化，另外就是如果使用二分，log(1-p)可能会是log(0)，对于p为1时需要特殊处理。

代码

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
//二分做法
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, pp;
double p;
double ksm(double b, long long p)
{
	double ans = 1;
	while (p > 0)
	{
		if (p & 1)
		{
			ans = ans * b;
		}
		b *= b;
		p >>= 1;
	}
	return ans;
}
bool check(ll mid)
{
	return n * (1 - ksm(1 - p, mid)) + (mid * n + m) * ksm(1 - p, mid) * log(1 - p) >= 0;
}
double cal(ll h)
{
	return (double(h) * n + m) / (1 - ksm(1 - p, h));
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{

		cin >> n >> m >> pp;
		if (pp == 10000)
		{
			cout << n + m << '\n';
			continue;
		}
		p = pp / 10000.0;
		ll l = 1, r = 100000000;
		while (l < r)
		{
			ll mid = (l + r) / 2;
			if (check(mid))
			{
				r = mid;
			}
			else
			{
				l = mid + 1;
			}
		}

		if (l == 1)
			printf("%.12f\n", cal(l));
		else
			printf("%.12f\n", min(cal(l), cal(l - 1)));
	}
	return 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//三分代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, pp;
double p;
double ksm(double b, long long p)
{
    double ans = 1;
    while (p > 0)
    {
        if (p & 1)
        {
            ans = ans * b;
        }
        b *= b;
        p >>= 1;
    }
    return ans;
}

double cal(ll h)
{
    return (double(h) * n + m) / (1 - ksm(1 - p, h));
}
int main()
{
    ll t;
    cin >> t;
    while (t--)
    {

        cin >> n >> m >> pp;
        p = pp / 10000.0;
        ll l = 1, r = 100000000;
        double lv, rv;
        while (l < r)
        {
            ll lm = l + (r - l) / 3;
            ll rm = r - (r - l) / 3;
            lv = cal(lm);
            rv = cal(rm);
            if (lv <= rv)
                r = rm - 1;
            else
                l = lm + 1;
        }
        printf("%.12f\n", min(lv, rv));
    }
    return 0;
}