比赛传送门:第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)
题解按照难度从小到大排序。
K.K Co-prime Permutation(构造 + 签到)
,给定一个排列大小N和一个数字K要求构造一个有K个值与下标的最大公因数为1的排列。
比如样例5, 3,构造如下的排列:
val | 1 | 4 | 5 | 2 | 3 |
idx | 1 | 2 | 3 | 4 | 5 |
我看可以看到其中下标为1, 3, 5的三对二元组(1, 1), (5, 3), (3, 5)的gcd为1,满足题意。
其实这个很好想,我们可以先写一个升序排列,然后选定K个进行滚动操作,后面的不动,就可以使得val和idx的差为1,在正整数中差为1的二元组是互质的,所以这样就可以构造出K对val和idx的最大公因数为1的排列。
就比如样例的5, 3我们可以构造这样一个排列:2, 3, 1, 4, 5,这样前三个(val, idx)二元组的gcd都是1,而(4, 4), (5, 5)都是他们本身。
值得注意的是,1和任何数字都互质,所以任意一个排列的K至少都为1,所以特判K == 0时,答案为-1。其他情况就将前K个数字滚动即可。
#include <bits/stdc++.h> #define int long long using namespace std; void solve() { int N, K;cin >> N >> K; if(K == 0)cout << -1 << '\n'; else { //前K个数字向右滚动一格 cout << K << ' '; for(int i = 2;i <= K; ++ i)cout << i - 1 << ' '; for(int i = K + 1;i <= N; ++ i)cout << i << ' '; cout << '\n'; } } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; while(_ --)solve(); return 0; }
L.Let's Play Curling(排序 + 二分)
在一根横轴上有N个红点和M个蓝点,红点坐标ai,蓝点坐标bi,现在求一个c点,可以使得最多的ai(1 <= i <= N)满足:
对于所有bj(1 <= j <= M)有,|c - ai| < |c - bj|。
意思就是选一个c点,可以让最近的点是一个红点儿,而不是蓝点。距离相等也不行,要求严格小于。
我们把这些点画出来。
不难发现,当c落在绿色范围内的时候可以使得范围内的红色点都满足要求,而范围外的一定不满足,所以现在问题就变为了:求位于两个相邻蓝色点中间的最大红色点个数。
我们可以虚拟两个蓝色点,一个为0(点坐标的最小值都为1,所以左边界设为0就够了),一个无穷大,然后以两个相邻的蓝色点为基准做两次二分求出红色点的个数,最后取大即可。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9, inf = 8e18; int a[maxn], b[maxn], N, M; void solve() { cin >> N >> M; for(int i = 1;i <= N; ++ i)cin >> a[i]; for(int i = 1;i <= M; ++ i)cin >> b[i]; //注意排序,以及a、b的长度不同 sort(a + 1,a + 1 + N); sort(b + 1,b + 1 + M); //设置虚拟蓝色点 b[0] = 0; b[M + 1] = inf; int ans = 0; //对于每一对相邻蓝色点做二分找到位于这两个点中间的红色点个数 for(int i = 1;i <= M + 1; ++ i) { int p = upper_bound(a + 1, a + 1 + N, b[i - 1]) - a; int q = lower_bound(a + 1, a + 1 + N, b[i]) - a - 1; ans = max(ans, q - p + 1);//取大 } //判断答案是否为0 if(ans)cout << ans << '\n'; else cout << "Impossible" << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }
E.Evil Coordinate(思维)
在一个地图中,有一颗地雷在(mx, my),对于一个从(0, 0)出发的给定路线,怎样改变行动的顺序(可以对字符串进行任意排列)可以使得不踩到地雷,求出一个合理的方案即可。
首先不难发现有两条路,即先上下再左右,或者先左右再上下,即下图中两种:
而真实情况其实不止这两种,有时需要想像下图这样绕着走。

但是因为地雷只有一颗,所以不难发现答案由很多种,我们不妨每一次都往一个方向走到头,那么方案就一共是4! = 24种,即对"UDLR"四个字符进行全排列。
如果存在答案,那么一定有一个在这24个方案中。如果这24个都没有答案,那就没答案。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9; int N, mx, my, cnt[300]; char s[maxn]; int getabs(int x){return x < 0 ? -x : x;} bool check(char s2[]) { bool res = true; int x = 0, y = 0; if(x == mx && y == my)res = false; for(int i = 0;i < 4; ++ i) { if(s2[i] == 'U') { for(int j = 1;j <= cnt['U']; ++ j) { y ++; if(x == mx && y == my)res = false; } } if(s2[i] == 'D') { for(int j = 1;j <= cnt['D']; ++ j) { y --; if(x == mx && y == my)res = false; } } if(s2[i] == 'L') { for(int j = 1;j <= cnt['L']; ++ j) { x --; if(x == mx && y == my)res = false; } } if(s2[i] == 'R') { for(int j = 1;j <= cnt['R']; ++ j) { x ++; if(x == mx && y == my)res = false; } } } return res; } void solve() { cin >> mx >> my; cin >> s + 1; N = strlen(s + 1); cnt['U'] = cnt['R'] = cnt['L'] = cnt['D'] = 0; for(int i = 1;i <= N; ++ i)cnt[s[i]] ++; char s2[4] = {'D', 'L', 'R', 'U'};//注意一开始要写字典序最小的排列,以便于后面全部遍历到 do { if(check(s2)) { for(int i = 0;i < 4; ++ i) { if(s2[i] == 'U')while(cnt['U'] --)cout << 'U'; if(s2[i] == 'D')while(cnt['D'] --)cout << 'D'; if(s2[i] == 'L')while(cnt['L'] --)cout << 'L'; if(s2[i] == 'R')while(cnt['R'] --)cout << 'R'; } cout << '\n'; return; } }while(next_permutation(s2,s2 + 4)); cout << "Impossible" << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }
F.Fireworks(概率论)
我超,这道题直接考概率论把我整懵了。
正好复习一下一个几何分布。
一个人做烟花,每一个烟花能够成功放飞的概率是p,做一个需要时间n,把所有已经做好的烟花放飞需要时间m(不管放飞多少个都只要时间m),问在最优策略下,第一次成功放飞的最小期望时间。
首先要知道最优策略是每次做k个然后检查(放飞)一次,这是均匀的,我们称“做k个并检查一次”为一轮操作。当某一轮检查到了至少一个成功的,就可以停下了。
现在我们要考虑的就是怎样选择k可以使得轮数最少。
根据几何分布我们可以知道如果在第x轮检查成功,我们设检查有至少一个成功的概率为\(q = 1 - (1 - p)^k\),意思是1减去k个全部不成功的概率,那么概率为\((1 - q)^{x-1} * q\),前x-1次都失败,最后一次成功。而x的取值是无穷大的(几何分布的特点)。
几何分布的期望是\(1 / q = 1 / (1 - (1 - p) ^ k)\),而乘上每一轮需要的时间\(k*n + m\),得最终的期望时间为\( (k*n + m) / (1 - (1 - p) ^ k)\)。
这是一个凹函数,可以通过三分来找到最低点,注意结合快速幂。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9; int n, m, p; double qmi(double a,int b) { double res = 1; while(b) { if(b & 1)res = res * a; a = a * a, b >>= 1; } return res; } double check(int k) { return (k * n + m) / (1 - qmi(1 - (p / 1e4), k)); } void solve() { cin >> n >> m >> p; int l = 0, r = 1e9; while(l + 1 != r) { int lmid = l + (r - l) / 3.0 + 0.5; int rmid = r - (r - l) / 3.0 + 0.5; if(check(lmid) >= check(rmid))l = lmid; else r = rmid; } double ans = min(check(l), check(r)); cout << fixed << setprecision(10) << ans << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }
H.Harmonious Rectangle(dfs + 打表)
给定一个N,M表示二维数组大小,每个元素可能取值为0, 1, 2,意思是一共有\(3^(N*M)\)种取值方案,问有多少种方案可以使得至少有一个矩形(四个点未必相邻)满足以下条件:
\(a[x1][y1] = a[x1][y2] and a[x2][y1] = a[x2][y2]\)或者\(a[x1][y1] = a[x2][y1] and a[x1][y2] = a[x2][y2]\)
首先特判n == 1 || m == 1,这样连矩形都没有。
突破口是这个颜色种类很少,只有三种,想一下当只有两行的情况,第一行和第二行构成诸多个二元组,那么第9个二元组一定会和前面的某一个重复,那么就产生了一个符合题意的矩形。
也就是当n,m中可以找出矩形且有n > 9 || m > 9时,所有方案都至少有一个符合题意的矩形,答案就是\(3^(N * M)\)。
当n < 9 && m < 9时呢?只需要dfs打个表就好了,如果直接交可能会超时。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e3 + 9, p = 1e9 + 7; int a[maxn][maxn], n, m, ans; int mat[10][10]; int qmi(int a,int b) { int res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p, b >>= 1; } return res; } void dfs(int dep) { if(dep == n * m)return ans ++, void(); int x2 = dep / m, y2 = dep % m; //printf("(%lld, %lld)\n", x2, y2); for(int i = 0;i < 3; ++ i)//(x2, y2)设为 i { a[x2][y2] = i; bool tag = true;//是否继续 for(int x1 = 0; x1 < x2 && tag; ++ x1) for(int y1 = 0; y1 < y2 && tag; ++ y1)//遍历(x1, y1) { if(a[x1][y1] == a[x1][y2] && a[x2][y1] == a[x2][y2])tag = false; if(a[x1][y1] == a[x2][y1] && a[x1][y2] == a[x2][y2])tag = false; } if(tag)dfs(dep + 1); } } void solve() { cin >> n >> m; if(n > m)swap(n, m); if(n == 1 || m == 1)cout << 0 << '\n'; else if(n > 9 || m > 9)cout << qmi(3, n * m) << '\n'; else cout << ((qmi(3, n * m) - mat[n][m]) % p + p) % p << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); mat[2][2] = 66; mat[2][3] = 390; mat[2][4] = 1800; mat[2][5] = 6120; mat[2][6] = 13680; mat[2][7] = 15120; mat[3][3] = 3198; mat[3][4] = 13176; mat[3][5] = 27000; mat[3][6] = 13680; mat[3][7] = 15120; mat[4][4] = 24336; mat[4][5] = 4320; mat[5][5] = 4320; int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING