第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）题解 E F H K L

2022年10月12日 243点热度 0人点赞 0条评论

题解按照难度从小到大排序。

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;
}

本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可