第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(上海)B D G M题解

发布于 2022-10-07  523 次阅读


比赛链接:[牛客竞赛]第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(上海)

G.Fibonacci(规律 + 组合数学)

在经典的斐波那契数列(1, 1, 2, 3, 5, 8...)中,给出一个N求出满足以下条件的(f(i), f(j))二元组个数:

\(1 \le i < j \le N\)且\(f(i) * f(j) % 2 == 0\)。

分析一下,斐波那契数列如果对2取模的话,会发现它是一个1 1 0循环的数列,意味着每三个数为一组前两个为奇数,最后一个为偶数,所以偶数的个数就是N / 3向下取整,那么奇数的个数就是N减去偶数个数。将奇数格式设为ji,偶数个数设为ou。

有了奇数和偶数的个数就考虑一下哪些相乘可以得到一个偶数呢?我们从N个数字中选出两个来,如果是两个偶数就可以,或者一个奇数一个偶数也可以。那么总的方案数就是\(C_{ou}^{2} + C_{ou}^{1} * C_{ji}^{1}\),其实我们求对立事件也可以,总的方案数为\(C_{N}^{2} - C_{ji}^{2}\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int N;cin >> N;
    int ou = N / 3;
    int ji = N - ou;
    //cout << ou * (ou - 1) / 2 + ou * ji << '\n';
    cout << N * (N - 1) / 2 - ji * (ji - 1) / 2 << '\n';
    return 0;
}

M.Gitignore(树 + 不知道啥)

给定N个需要删除文件夹路径,再给出M个需要保留的文件夹路径,一次操作可以删除一个文件夹,问最少需要操作几次可以将N个需要删除的都删除且保留这M个需要保留的文件。

第一个样例中:

3 0
data/train
data/test
model

我们没有需要保留的文件夹,所以可以删除data和model这两个文件夹就行了,操作次数为2。

而第二个样例:

3 1
data/train
data/test
model
data/sample

在这里我要删除前三个文件夹,但是我要保留data/sample,我就不能直接删除data这个大文件夹,需要先删除data/train再删除data/test,最后删除model,所以操作次数是3。

分析一下,我们知道计算机的文件夹是一个树状结构,我们不妨构建一棵树,每一个字符串表示一个路径,也表示一个节点,父文件夹是子文件夹的父亲节点

我们给每一个路径都进行编号。比如第二个样例中对于路径data/train其实有两个文件夹,我们分别命名为data#和data#train#,并且将data#train#的父亲设置为data#,同理data#test#的父亲也是data#,在处理完N个需要删除的文件夹后我们就会得到下面这样的图(最大的文件夹的父亲是0)。

删除图

这里的每一个点都有一个编号,是通过一个函数来实现动态开点的,这个并不难,只需要检查一下这个字符串是否对应了一个编号,如果没有对应编号说明需要开新的点

接下来我们要开始设置“保留点”了,首先要将0设置为保留点(你不能把整个硬盘都删了吧)。再添加M个保留点,这个样例中是data#sample#,并且给路径都标红说明要路径上这些点都不能直接删除。

删除与保留图

最后只需要遍历1~N看看哪些点的父亲是要保留的,那么这个点就删除掉,而“父亲不需要保留的点”会因为父亲的删除而被删除。

这里还有一个难点就是字符串的划分,C++没有像python或者java那样的split函数,怎么办呢?我们可以用stringstream的getline函数来划分。

像这样写,传入一个字符串ins,并且根据‘/’划分,存入一个vector<string>中,注意这里不要把cin作为istringstream,因为可能有\n导致一些错误。需要在主函数中读入一个ins,然后传入这个函数。

void split(string ins, vector<string> &v)
{
	istringstream in(ins);
	string tmp, s;
	while(getline(in, tmp, '/'))
	{
		s = s + tmp + "#";
		v.push_back(s);
	}
}

最终代码,请使用g++提交,否则将gp_hash_table改为map或者unordered_map。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 1010;
__gnu_pbds::gp_hash_table<string, int> mp_idx;
int fa[maxn];
int idx = -1;

int getidx(string s)
{
	if(mp_idx.find(s) == mp_idx.end())mp_idx[s] = ++ idx;
	return mp_idx[s];
}

void split(string ins, vector<string> &v)
{
	istringstream in(ins);
	string tmp, s;
	while(getline(in, tmp, '/'))
	{
		s = s + tmp + "#";//算出路径对应的字符串
		v.push_back(s);//存入vector中
	}
}

void solve()
{
	mp_idx.clear();
	idx = -1;
	bitset<maxn> save;
    //将根节点设为需要保留的,因为是第一次调用getidx所以根节点的id一定是0
    save[getidx("#")] = true;
	memset(fa, 0, sizeof fa);
	
	int N, M;cin >> N >> M;
	for(int i = 1;i <= N; ++ i)
	{
		vector<string> paths;
		paths.push_back("#");//新增空字符作为根节点
		string s;cin >> s;//输入字符串
		
		//处理划分 
		split(s, paths);
		for(int i = 1;i < paths.size(); ++ i)
            fa[getidx(paths[i])] = getidx(paths[i - 1]);
		
	}
	
	for(int i = 1;i <= M; ++ i)
	{
		vector<string> paths;
		paths.push_back("#");
		string s;cin >> s;//输入字符串
		
		//处理划分 
		split(s, paths);
		for(int i = 1;i < paths.size(); ++ i)save[getidx(paths[i])] = true;
	}
	int ans = 0;
    //注意这里不能从0开始,根节点是不用考虑的,也不能考虑因为没有父亲
	for(int i = 1;i <= idx; ++ i)
	{
        //i不用保留但父亲要保留,那么这个i就是我们要删除的文件夹目录
		if(!save[i] && save[fa[i]])ans ++;
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _;cin >> _;
	while(_ --)solve();
	
	return 0;
}

B.Mine Sweeper II(思维)

给定两个尺寸都为N * M扫雷图A和B,问在至多进行N * M / 2向下取整次取反操作的情况下(取反就是雷变安全区,安全区变雷),如何使得B中的每个安全区的点数之和和A的中的相等。至于点数就不多解释了,不清除的自己去玩扫雷。

注意观察这个N * M / 2,容易让人想到A的反图,对于一个扫雷图,如果将其全部取反,安全区的点数和不变。

所以这道题就变为了,B是否能变为A,如果能就直接输出A,如果不能就输出A的反图,因为在N * M / 2的操作下一定能从B变为A或A的反图,至于证明:如果B变为A的操作数大于等于总点数的一半,那么将原本要取反的不取反,不要取反的却取反,那么操作数就一定小于等于总点数的一半咯。

现在答案就变得很明朗了,算一下B变为A的操作次数,如果小于等于N * M / 2就直接输出A,否则输出a的反图。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1010;
char A[maxn][maxn], B[maxn][maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N, M;cin >> N >> M;
	for(int i = 1;i <= N; ++ i)cin >> A[i] + 1;
	for(int i = 1;i <= N; ++ i)cin >> B[i] + 1;
	
	int cnt = 0;//修改为A图需要的次数 
	for(int i = 1;i <= N; ++ i)
		for(int j = 1;j <= M; ++ j)cnt += (A[i][j] != B[i][j]); 
		
	bool tag = (cnt <= N * M / 2);
	for(int i = 1;i <= N; ++ i)
	{
		for(int j = 1;j <= M; ++ j)
		{
			if(!tag)//如果cnt > N * M / 2,输出反图
			{
				if(A[i][j] == '.')cout << 'X';
				else cout << '.';
			}else cout << A[i][j];
		}
		cout << '\n';
	}
	return 0;
}

D.Walker(思维)

两个人在一个[0, N]的数轴上匀速走,俩人分别有一个初始位置p和速度v,他们可以往任意方向(左或者右)走且调头无需时间,不能走出[0, N]范围,问最少需要多少时间可以使得[0, N]都被覆盖到(走完这整个线段)。

首先我们不妨设p1 < p2,所以需要判断一下p1是否大于p2如果是的话就交换p1和p2,v1和v2。

分析一下,设俩人为A和B,A在左边,B在右边,两个点要走完整个[0, N],有以下3种方法:

1.A跑得飞快,B很慢,A一个人走完全程。反之亦然。

2.A、B往对方的端点那边走到头。

3.A走左边一部分,B走右边一部分。

以后分析类似的走路问题大概也是这三种情况。

第一种和第二种情况很好分析,不过多解释。

#include <iostream>
#include <iomanip>
#define int long long
using namespace std;
const double inf = 8e18;

double ti(double x1, double x2, double p, double v)//在p点覆盖完[x1, x2]需要的最少时间 
{
    //需要保证x1 <= p <= x2
    //先到左边再到右边,以及先到右边再到左边两种方案取小
	return min((x2 - x1 + p - x1) / v, (x2 - x1 + x2 - p) / v);
}

signed main()
{
	int T;scanf("%lld", &T);
	while(T --)
	{
		double n, p1, v1, p2, v2;scanf("%lf %lf %lf %lf %lf", &n, &p1, &v1, &p2, &v2);
		if(p1 > p2)swap(p1, p2), swap(v1, v2);
		double ans = inf;
		//一人走完,取小,因为第一个人到了就能走完咯
		ans = min(ans, min(ti(0, n, p1, v1), ti(0, n, p2, v2)));
		//对向走,取大,如果一个人先到,要等另一个人到才行
		ans = min(ans, max((n - p1) / v1, p2 / v2));
		
		double l = p1, r = p2;
		for(int i = 1;i <= 100; ++ i)//进行100次逼近
		{
			double mid = (l + r) / 2;//mid是中间的那个点
			double tl = ti(0, mid, p1, v1);//计算左边部分需要的时间
			double tr = ti(mid, n, p2, v2);//右边部分需要的时间
			
			ans = min(ans, max(tl, tr));
			
			if(tl < tr)l = mid;//如果左边时间少,说明左边长度短了,需要变长
			else r = mid;//最终尽量让tl == tr就是最优解
		}
		printf("%.10f\n",ans);
	}
	return 0;
}

感谢阅读!