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