比赛链接:[牛客竞赛]第 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; }
感谢阅读!
文章评论