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

发布于 2022-10-12  393 次阅读


比赛传送门:第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)

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

K.K Co-prime Permutation(构造 + 签到)

,给定一个排列大小N和一个数字K要求构造一个有K个值与下标的最大公因数为1的排列。

比如样例5, 3,构造如下的排列:

val14523
idx12345
样例

我看可以看到其中下标为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;
}