比赛传送门：第 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