“范式杯”2023牛客暑期多校训练营1
D.Chocolate
题意：
有一个n×m的矩形巧克力，Kelin先手Walk Alone后手选一个点(i, j)并吃掉所有 x <= i, y <= j的巧克力，谁吃掉最后一块巧克力则输。
分析：
对矩形大小进行讨论：
①1×1时，Kelin必输
②1×n或1×m时：Kelin可以选择吃掉n-1或m-1块巧克力，因此Kelin必胜
③n×m时：Kelin吃掉一块后Walk Alone将面对一个对角形状，此时Walk Alone只有两种选择：维持对角形状或者将其吃成矩形。
（1）如果Walk Alone选择维持对角形状，那么Kelin可以选择镜像的和Walk Alone吃同样大小的巧克力，始终保持对称。因此，留给Walk Alone的剩余部分巧克力最终必然会导向我们前面讨论的①和②，所以Kelin必胜。
（2）如果Walk Alone选择将其吃成矩形。如果剩余部分为情况②，Kelin必胜，否则Kelin可以选择将其吃成对角形，依旧必胜。
综上除了1×1Kelin必胜。
代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
if (n == 1 && m == 1)
cout << "Walk Alone";
else
cout << "Kelin";
return 0;
}
H.Matches
题意：
给你两个数组，最多进行一次交换操作（同一数组内部），求$$sum = \sum_{i=1}^n{|a[i] - b[i]|}$$的最小值。
分析：
我们定义(a[i], b[i])和(a[j], b[j])这两对数的大小关系相同为正序，不同为反序。
通过画图，我们可以发现，只有当反序包含和反序相交时，交换才有意义。因此，我们可以需处理出原始的差值绝对值之和sum，将(a[i],b[i])数对按a[i]是否大于b[i]分成A、B两组，不妨选择对A中的每一个数对从B中选择一个与其交集最大的数对计算交集大小，对所有交集大小取个max记为d，答案即为sum - 2·d。
具体到查找部分：
1.对于S中每个元素，在T中二分找到包络当前区间的区间，更新反序包络到正序不交的交换减少量。
2.对于S中每个元素，在T中二分找到相交范围最大的线段(最近的左端点，最近的右端点)，更新反序相交到反序不交的交换减少量。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
typedef pair<LL, LL> PLL;
LL a[N], b[N];
vector<PLL> A, B;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
LL res = 0;
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++)
{
cin >> b[i];
res += abs(a[i] - b[i]);
if (a[i] < b[i])
A.push_back({a[i], b[i]});
else if (a[i] > b[i])
B.push_back({b[i], a[i]});
}
// 预处理，保证A中左右端点均非递减。。
sort(A.begin(), A.end());
vector<LL> Sx, Sy, len;
LL Maxy = -2e18;
for (auto x : A) // 去掉同序包络的情况
{
if (x.second <= Maxy)
continue;
Maxy = x.second;
Sx.push_back(x.first), Sy.push_back(x.second);
len.push_back(abs(x.first - x.second));
}
LL d = 0;
int m = Sx.size();
for (auto t : B)
{
LL d2 = 0;
LL x = t.first, y = t.second;
LL l = upper_bound(Sx.begin(), Sx.end(), x) - Sx.begin();
LL r = lower_bound(Sy.begin(), Sy.end(), y) - Sy.begin();
if (l > 0)
d2 = max(d2, min(y, Sy[l - 1]) - x);
if (r < m)
d2 = max(d2, y - max(x, Sx[r]));
if (l < r)
d2 = max(d2, *max_element(len.begin() + l, len.begin() + r));
d = max(d, d2);
}
cout << res - 2 * d;
return 0;
}
J.Roulette
题意：
Walk Alone初始有n块钱，如果每次投x元，有一半的概率输掉这x元，另一半概率赢得 2x元。现在Walk Alone采取下述策略投注:
如果上一把赢了，这一把投xi=1元
如果上一把输了，这一把投xi=2xi-1元
问Walk Alone 有多大概率拿到n + m元离开。
分析：
模拟一下会发现，无论输多少次，只要最后赢都是赢得1块钱。因此以“输输...输输赢”为一周期，至少需要m个这样的周期才能满足要求。拿到n + m块钱的概率则是每个周期赢钱的概率累乘。由于每次输钱成倍增加：1，2，4，8，...，2k-1,因此假设手上有x块钱，最多能输k = log2(x + 1)次， 则成功赢钱的概率为1 - \(\frac{1}{2^k}\)。
综上拿到n + m元钱的概率为：
由于n，m很大，因此暴力枚举会超时，但可以发现[2i-1, 2i+1 - 2]log值是相同的，则他们的概率相同,因此我们可以每次选择一段区间的概率来相乘以达到缩短时间的目的。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
LL n, m;
cin >> n >> m;
LL ans = 1, p = qmi(2, mod - 2);
for (LL i = n + 1; i <= n + m;)
{
int k = (int)log2(i);
LL t = (1 - qmi(p, k) + mod) % mod;
LL j = min(n + m, ((LL)1 << (k + 1)) - 1);
ans = ans * qmi(t, j - i + 1) % mod;
i = j + 1;
}
cout << ans;
return 0;
}
K.Subdivision
题意:
给出一个n个点m条边的无向图，每个边的长度为1，可以进行任意次以下操作:
选择一个边(u,v)并删除，新加一个点w，新加两条边(u,w)和(w,v)，新加的边长度也为1。
问最后与节点1距离不大于k的点有多少个
分析:
为方便表述，不妨将删边加边简化为往边（u,v）加点。
做一遍BFS，求出每个点到节点1的最短距离，并将所有边分成bfs树边和非bfs树边。对于非bfs树边，往其加点并不会影响其他点到节点1的最短距离。而对于bfs树边，要考虑与u连接的非bfs树边的数量：如果为0且u为bfs树里的叶子节点，则加点影响最小；如果不为0则不能加边，因为会影响非树边的答案，而非树边显然优于树边。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 4e5 + 5;
int h[N], e[M], ne[M], idx;
int p[N], st[N], d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs()
{
memset(d, 0x3f, sizeof d);
queue<int> q;
q.push(1);
d[1] = 0;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] != 0x3f3f3f3f)
continue;
p[j] = t;
st[t] = 1; // 有后继节点
d[j] = d[t] + 1;
q.push(j);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
int n, m, k;
cin >> n >> m >> k;
while (m --)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bfs();
LL res = 1;
for (int i = 2; i <= n; i ++)
{
if (d[i] > k)
continue;
LL cnt = 0;
for (int j = h[i]; j != -1; j = ne[j])
{
int k = e[j];
if (k == p[i] || i == p[k])
continue;
cnt ++;
}
if (!st[i])
cnt = max(cnt, 1LL); // 若i是bfs树的叶子节点，则看它是否有非树边。
res += (k - d[i]) * cnt + 1; // 能加的点以及自己
}
cout << res;
return 0;
}
M.Water
题意:
有一个容积为A和B的容器，现在可以进行以下操作
1.使其中一个容器装满水
2.倒掉其中一个容器的所有水
3.喝光一个容器中的所有水
4.将一个容器中的水转移到另一个，直到其中一个容器的水空或者另一个容器装满
问最少要进行多少次操作，才能使得恰好喝下C单位的水。
分析:
设Ax+By=C。考虑exgcd, 由翡蜀定理知若C不能整除gcd(A, B)则无解，否则用exgcd求出一组解，然后求出离原点最近的一组解(x1, y1), 在其附近(x1 + kB, y1 - kA)对操作数取min。
附exgcd解Ax+By=c:
接下来讨论(x, y)对应的操作数：
首先x和y不可能同时小于0。
1.若x ≥ 0，y ≥ 0,我们只需 2·(x + y)次操作：A装x次，喝x次。B装y次，喝y次。
2.若x ≥ 0, y < 0,我们只需2·(x - y) - 1次操作。
证：不妨令A>B,A(x + y - y) + By = C => A(x + y) + (-y)(A - B)
可以看成喝(x + y)杯A和(-y)杯(A - B)。
前者操作次数ans1 = 2·(x + y)
后者可分4步完成：①将A装满 ②把A转移到B ③喝光A剩余的水 ④倒掉B中的水。注意到最后一次操作可以不用倒掉B中的水，因此后者操作次数ans2 = 4 × ((-y) - 1) + 3
综上ans = ans1 + ans2 = 2·(x - y) - 1;
3.若x < 0,y ≥ 0,同理我们只需要 2·(y - x) - 1次操作。
（以上详细证明参考：https://zhuanlan.zhihu.com/p/644323896）
综上对于一组（x, y）我们最少需要min(2·(x + y), 2·|x - y| - 1)次操作。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
LL a, b, c, x, y;
cin >> a >> b >> c;
LL d = exgcd(a, b, x, y);
LL res = 1e18;
if (c % d != 0)
res = -1;
else
{
a /= d, b /= d, c /= d, x *= c, y *= c;
x = (x % b + b) % b;
y = (c - a * x) / b;
for (int i = -10; i <= 10; i ++)
{
LL x1 = x + i * b, y1 = y - i * a;
if (x1 >= 0 && y1 >= 0)
res = min(res, 2 * (x1 + y1));
else
res = min(res, 2 * abs(x1 - y1) - 1);
}
}
cout << res << endl;
}
return 0;
}
热门相关：倾心之恋：总裁的妻子 神算大小姐 神算大小姐 富贵不能吟 神算大小姐