牛客寒假训练赛第一场
基本状况
赛时开了五题，B题大分讨卡住了，其他题目就看了题面。
有几个基本状况：
- 贪心题没有深入思考，就无脑二分入手，倒是大量罚时。
- 分讨思路不清楚。
- E题很搞，名字叫贪心题但是纯爆搜，爽切。
A
https://ac.nowcoder.com/acm/contest/67741/A
虽然签到题，但是学习一下 jly 写法。
- 我的
void solve() {
string s;
cin >> s;
int n;
cin >> n;
char cmp1[3] = {'d', 'f', 's'};
char cmp2[3] = {'D', 'F', 'S'};
short opt1 = 0, opt2 = 0;
bool flag1 = false, flag2 = false;
for (int i = 0; i < n; i++) {
if (cmp1[opt1] == s[i]) opt1++;
if (cmp2[opt2] == s[i]) opt2++;
if (opt1 == 3) flag1 = true, opt1 = 0;
if (opt2 == 3) flag2 = true, opt2 = 0;
}
cout << flag2 << ' ' << flag1 << endl;
}
- jly
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
for (auto t : {"DFS", "dfs"}) {
int k = 0;
for (int i = 0; i < n; i++) {
if (k < 3 && s[i] == t[k]) {
k++;
}
}
std::cout << (k == 3) << " ";
}
std::cout << "\n";
}
E
https://ac.nowcoder.com/acm/contest/67741/B
继续向jly学习
- 我的爆搜
void dfs(int step)
{
if (step == m)
{
vector<pair<int, int>> res(n + 1);
for (int i = 1; i <= n; i++)
{
res[i].second = a[i], res[i].first = i;
}
sort(all1(res), [&](auto x1, auto x2) {if (x1.second == x2.second) return x1.first == 1;return x1.second > x2.second; });
for (int i = 1; i <= n; i++)
if (res[i].first == 1)
{
ans = min(ans, i);
break;
}
return;
}
a[u[step + 1]] += 3;
dfs(step + 1);
a[u[step + 1]] -= 3;
a[v[step + 1]] += 3;
dfs(step + 1);
a[v[step + 1]] -= 3;
a[u[step + 1]] += 1;
a[v[step + 1]] += 1;
dfs(step + 1);
a[u[step + 1]] -= 1;
a[v[step + 1]] -= 1;
return;
};
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> u[i] >> v[i];
ans = 200;
a[u[1]] += 3;
dfs(1);
a[u[1]] -= 3;
a[v[1]] += 3;
dfs(1);
a[v[1]] -= 3;
a[u[1]] += 1;
a[v[1]] += 1;
dfs(1);
a[u[1]] -= 1;
a[v[1]] -= 1;
cout << ans << endl;
}
- jly的爆搜
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::vector<int> u(m), v(m);
for (int i = 0; i < m; i++) {
std::cin >> u[i] >> v[i];
u[i]--, v[i]--;
}
int ans = n;
auto dfs = [&](auto self, int i) -> void {
if (i == m) {
int res = 1;
for (int j = 0; j < n; j++) {
res += (a[j] > a[0]);
}
ans = std::min(ans, res);
return;
}
for (auto [x, y] : {std::make_pair(3, 0), {0, 3}, {1, 1}}) {
a[u[i]] += x;a[v[i]] += y;
self(self, i + 1);
a[u[i]] -= x;a[v[i]] -= y;
}
};
dfs(dfs, 0);
std::cout << ans << "\n";
}
jly 这里有三点值得学习：
-
可递归的函数写法，我一开始也是这样写但是CE了，要学一下。
auto dfs = [&](auto self, int i) -> void {};//声明 self(self, i + 1);//函数内部调用 dfs(dfs, 0)//函数外部调用 -
找该选手名次的方法，我用的是把选手和分数存入数组再排序，而jly更直接，直接比较大于该选手分数的人的数目。
int res = 1; for (int j = 0; j < n; j++) { res += (a[j] > a[0]); } -
爆搜三种情况的写法，我是复制黏贴，复用性差，jly利用循环来简化代码，而且step传0参进去也不用在函数外写一遍针对step = 1的处理
for (auto [x, y] : {std::make_pair(3, 0), {0, 3}, {1, 1}}) { a[u[i]] += x; a[v[i]] += y; self(self, i + 1); a[u[i]] -= x; a[v[i]] -= y; }
B
https://ac.nowcoder.com/acm/contest/67741/B
神志不清，分讨树精
- 我的
void solve() {
int n;
ll r, c;
map<pair<short, ll>, bool> tag;
cin >> n;
vector<pair<short, ll> > query(n);
for(auto&[r, c] : query) {
cin >> r >> c; r--;
tag[make_pair(r, c)] = true;
}
if (n == 0) {cout << 3 << endl; return ;}
sort(all(query), [&](auto x1, auto x2) {return x1.second < x2.second;});
int sum = 4, i = 0;
int ldif = query.front().second < 0, rdif = query.back().second > 0;
for (; i < n && query[i].second <= 0; i++) {
auto [r, c] = query[i];
if (tag.count(make_pair(r ^ 1, c))
|| tag.count(make_pair(r ^ 1, c - 1)) || tag.count(make_pair(r ^ 1, c + 1))) {
ldif = 2;
}
}
if (i > 0 && query[i - 1].second == 0) i--;
for (; i < n && query[i].second >= 0; i++) {
auto [r, c] = query[i];
if (tag.count(make_pair(r ^ 1, c))
|| tag.count(make_pair(r ^ 1, c - 1)) || tag.count(make_pair(r ^ 1, c + 1))) {
rdif = 2;
}
}
sum -= ldif + rdif;
if (tag.count(make_pair(1, 0))) {
if (ldif == 2) {
sum = min(sum, 1);
}
if (rdif == 2) sum = min(sum ,1);
}
sum = min<int>(sum, 3 - tag.count(make_pair(0, 1)) - tag.count(make_pair(0, -1)) - tag.count(make_pair(1, 0)));
if (tag.count(make_pair(0, -1))) {
if (rdif == 2) sum = min<int>(sum, 1);
}
if (tag.count(make_pair(0, 1))) {
if (ldif == 2) sum = min<int>(sum, 1);
}
cout << sum << endl;
}
大方向肯定是没错的，用 pair<int,int> 来标记坐标，然后分讨。
我的做法是先按正负坐标排序，然后左右分讨，最后在讨论三角形情况。
但是复杂、并且有一个很明显的问题：
if (tag.count(make_pair(r ^ 1, c))
|| tag.count(make_pair(r ^ 1, c - 1)) || tag.count(make_pair(r ^ 1, c + 1)))
这样会重复计算，对于一对坐标，遍历到左的会算一次右的，遍历到右的又算一次左的。
然而改完还是出错，直接学习 jiangly 的代码。
- jly
void solve() {
int n;
std::cin >> n;
int left1 = 0, left2 = 0;
int right1 = 0, right2 = 0;
std::set<std::pair<int, int>> s;
for (int i = 0; i < n; i++) {
int r, c;
std::cin >> r >> c;
if (c <= 0) {
left1 = 1;
}
if (c >= 0) {
right1 = 1;
}
s.emplace(r, c);
}
for (auto [r, c] : s) {
if (c == 0) {
continue;
}
if (s.count({r ^ 3, c}) || s.count({r ^ 3, c + (c > 0 ? -1 : 1)})) {
if (c > 0) {
right2 = 1;
} else {
left2 = 1;
}
}
}
int ans = 4 - left1 - left2 - right1 - right2;
ans = std::min(ans, int(3 - s.count({2, 0}) - s.count({1, -1}) - s.count({1, 1})));
std::cout << ans << "\n";
}
- 不排序，而是利用
std::set特性，自动按第一二键值对排序，遍历时的序列程：”第一行有序，第二行有序“状态。- C等于零，不处理（交给下面的处理来计算）
- C大于零，找左边一个或者上\下相邻的
- 这里找左边是有讲究的，既是防止重复计数，更是要考虑如果左边是0的情况，如果改成加一找右边也是出错。
- C小于零，找右边一个或者上\下相邻的
- 最后再无脑讨论三角形即可。
G
https://ac.nowcoder.com/acm/contest/67741/G
一开始写成对每一段进行二分，正确性应该没问题但是太复杂了，不知道哪里细节错误。
后面发现这题可以直接贪心求答案。
已经犯过很多次这类错误，当一个做法很绕很复杂的时候，要考虑能不能换做法。
贪心思路很简单，维护前缀和判断就行。
但是这题之所以要写个博客，是因为这种只要维护一个前缀和的题目，我一直在无脑写前缀和数组。
老样子。
- 我的
void solve() {
int n, m;
cin >> n >> m;
vector<pair<ll, ll> > a(n);
for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
vector<ll> s(n);
sort(all(a));
for (int i = 0; i < n; i++)
if (i == 0) s[i] = a[i].second;
else s[i] = s[i - 1] + a[i].second;
ll ans = m;
for (int i = 0; i < n; i++) {
if (m + s[i] >= a[i].first) ans = max(ans, m + s[i]);
}
cout << ans << endl;
}
- jly
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int>> a(n);
for (int i = 0; i < n; i++) {
int x, y;
std::cin >> x >> y;
a[i] = {x, y};
}
std::sort(a.begin(), a.end());
i64 ans = m;
i64 sum = 0;
for (auto [x, y] : a) {
sum += y;
if (x - sum <= m) {
ans = std::max(ans, sum + m);
}
}
std::cout << ans << "\n";
}
用一个sum动态维护前缀和即可。
L
https://ac.nowcoder.com/acm/contest/67741/L
结论题，其实一开始想法是对的，贴地的照明范围最大，但是没啥信心也没做下去。
也是因为审题不认真，实际上墙和光源的距离是光源和背景墙的两倍，就是用中位线算就完全可以处理。
I
https://ac.nowcoder.com/acm/contest/67741/I
第一次见，毫无思路
核心思路
- 找到两种方法会使得哪个统计量有显著区别，尝试区分这个统计量的均值
- 如果这个统计量不好直接求，可以本地真的实现以下两种生成方式，然后生成大量数据，真的随机出这个统计量的真实值
- 比如求出法 \(1\) 该统计量均值 \(m_1\)、法 \(2\) 该统计量均值 \(m_2\)，那对于输入数据，直接看输入 数据的该统计量 \(m\) 和 \(m_1\) 与 \(m_2\) 谁更近就行了。
太抽象了，是一种很新的题，似乎是模拟了机器学习的一些理论。
F
https://ac.nowcoder.com/acm/contest/67741/F
-
相关知识：第二类斯特林数
- 将 \(n\) 个 bit 每个 bit 看作一件物品
- 将 \(m\) 个数字每个看作一个集合
- 注意到这几乎就是第二类斯特林数 \(S(n,m)\) 的定义：\(n\) 个有区别球放到 \(m\) 个无区别盒子
- 还差在哪里呢？我们发现，本题的盒子（\(a_i\)）并不是无区别的，但因为第二个条件要求了 每个盒子里的数从小到大有序，所以对于 \(S(n,m)\) 中的每一种方案，对其按 \(a_i\) 大小排序就得 到了本题的一种方案，且可以证明这是一种一一映射（重点是证明没有多对一）
- 因此，本题答案就是斯特林数 \(S(n,m)\)
- 第二类斯特林数的容斥求法，可以在log复杂度里做出这题
-
第二类斯特林数
-
将 \(n\) 个有区别的球放入 \(m\) 个无区别的盒子的方案数 \(S_{n,m}\)
- 有区别的定义
- \(C^3_5\) 五个有区别的球选三个
- \(1\) 五个没区别的数选三个
- 有区别的定义
-
\(S_{4,2}\)（此题要求盒子非空）
-
无区别的定义
- \((1,234)\) 和 \((234,1)\) 是同一种方案。
-
方案数为 \(7\)
- \((1,234)\)
- \((12,34)\)
- \((13,24)\)
- \((14,23)\)
- \((123,4)\)
- \((124,3)\)
- \((134,2)\)
-
若不要求非空，显然答案为 \(8\)，即 \(m^n\).
-
若有 \(k\) 个为空，且盒子和球都有区别，则方案数为 \(C^k_m(m - k)^n\)
-
然后用容斥原理，容斥成非空个数（错排数），最后为了转化有区别为无区别，再除以 \(m!\)
\(S_(n,m) = \frac 1 {m!} \sum^m_k(-1)^kC^k_m(m - k)^n\)
-
-
H
https://ac.nowcoder.com/acm/contest/67741/H
位运算好题
- 先考虑每个物品的重量都只含 \(1bit\) 的情况，可以帮助对这题要解决什么问题有个大致了解
- 记所选物品重量或起来是 \(𝑐\)，枚举 𝑚 里是 \(1\) 的某个 \(bit\)，强制 𝑐 里该位为 \(0\)，则该位将 𝑚 分成了前后两部分
- 对于前面的那部分位（更高位），要求所选的物品这些位必须是𝑚的子集（即𝑚对应位是 \(1\) 才能选）
- 对于后面的那部分位（更低位），没有任何限制
- 因此，枚举 𝑚 里每一位作为这个分界，每个物品就变成了要么能选要么不能选、彼此之间也不影响，所以把能选的都选上就好，最后再特判一下 \(c=m\) 的状况，即可保证枚举了所有情况
void solve() {
int n, m;
cin >> n >> m;
vector<int> v(n), w(n);
for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
ll ans = 0;
auto get = [&](int s) {
ll res = 0;
for (int i = 0; i < n; i++) {
if ((s & w[i]) == w[i]) {
res += v[i];
}
}
ans = max(ans, res);
};
for (int i = 29; i >= 0; i--) {
if (m >> i & 1) {
get((m ^ (1 << i)) | ((1 << i) - 1));//很关键
}
}
get(m);//处理C=M的情况
cout << ans << endl;
}
get函数内穿的参数用了几个 trick.
-
m ^ (1 << i)//把 m 的第 i 位取反，这里是置为 0 -
(m ^ (1 << i) | ((1 << i) - 1))//把 i 位之前（右边）的位数全部变成 1，因为由题解，更低位不限制 //1 << i 是第 i 位为 1，右边都是 0 //1 << i - 1 则会把第 i 位变成 0， 右边全部变成 1
通过这个参数与 \(w_i\) 进行按位与，显然能自动检测符合题解思路条件的物品，全部加上即可。
K
https://ac.nowcoder.com/acm/contest/67741/H
基环外向树？折磨！
大意：第 \(i\) 题的选项表明了 \(a_i\) 题的答案。
-
基环外向树
- \(n\) 条边
- 每个点出度为 \(1\)
- 即所有点必然入环
-
首先，每个 \(i\) 向 \(a_i\) 连一条有向边，表示 \(a_i\) 的答案被 \(i\) 限制住了；该题的依赖性质构成了基环外向树森林
- 首先所有连到环的链可以直接无视，它们不影响答案
- 因为这个链所连接的环那个点确定答案后、链上每个点的答案可以由此反向传播依次得到（至于为何每个点答案唯一？这是因为该点走到环的路径上所有排列复合得到的仍是排列），因此，环上点确定方案、则链也随之确定唯一一种方案，所以可以忽略链
- 对于环，我们随机选个起点，暴力枚举这个点选 ABCDE 中哪个选项然后暴力模拟来 check 这个选项是否能让这个环满足条件即可
- 因此，每个基环内向树的答案是0~5之间整数
- 最后的答案是每个基环内向树答案的乘积
int main() { int n; std::cin >> n; std::vector<int> a(n); std::vector<std::string> s(n); for (int i = 0; i < n; i++) { std::cin >> a[i] >> s[i]; a[i]--; } Z ans = 1; std::vector<int> vis(n, -1); for (int i = 0; i < n; i++) { int j = i; while (vis[j] == -1) { vis[j] = i; j = a[j]; } if (vis[j] == i) { int k = j; int len = 0; do { k = a[k]; len++; } while (k != j); int res = 0; for (int x = 0; x < 5; x++) { int v = x; for (int i = 0; i < len; i++) { v = s[k][v] - 'A'; k = a[k]; } res += v == x; } ans *= res; } } std::cout << ans << "\n"; return 0; } - 首先所有连到环的链可以直接无视，它们不影响答案
D
https://ac.nowcoder.com/acm/contest/67741/D
通过题目分析出特性，进而剪枝
核心是要注意到：询问的 \(M\) 范围不大，所以数组稍微长一点儿，就很可能溢出 \(10^9\) 的范围，所以要考虑的方案其实很少；
- 最终数组，绝对值非 \(1\) 的最多 \(30\) 个
- 枚举哪个数变成 \(1\) 或 \(-1\)，然后把此时数组乘积算出来，在枚举前先判断一下这 个数变的话能不能保证变后绝对值非 \(1\) 的最多 \(30\) 个，所以真正要枚举的数不多；
- \(𝑛≤30\)，此时要么第一个数绝对值在 \(10^9\) 内、要么第二个数绝对值在 \(10^9\) 内，否则，前两个数乘积的绝对值一定大于 \(10^9\)；因此我们 \(\sqrt {10^9}\times n\) 的暴力枚举就可以；
#include <bits/stdc++.h>
using i64 = long long;
constexpr int K = 4E4;
constexpr int inf = 1E9;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, Q;
std::cin >> n >> Q;
std::map<int, int> cnt;
for (int i = 0; i < n; i++) {
int a;
std::cin >> a;
cnt[a] += 1;
}
std::set<int> S{0};
if (cnt.size() <= 20) {
std::vector<std::pair<int, int>> a(cnt.begin(), cnt.end());
n = a.size();
int x = a[0].first - K;
for (int i = 0; i < n; i++) {
for (x = std::max(x, a[i].first - K); x <= a[i].first + K; x++) {
i64 res = 1;
for (int j = 0; j < n; j++) {
int v = a[j].first - x;
if (v == 1) {
continue;
}
if (v == -1) {
if (a[j].second % 2) {
res *= -1;
}
continue;
}
for (int c = 0; c < a[j].second; c++) {
res *= v;
if (std::abs(res) > inf) {
break;
}
}
if (std::abs(res) > inf) {
break;
}
}
if (std::abs(res) <= inf) {
S.insert(res);
}
}
}
}
while (Q--) {
int M;
std::cin >> M;
if (S.count(M)) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
}
return 0;
}
J
https://ac.nowcoder.com/acm/contest/67741/J
思维难度有点大
-
最关键的性质：考虑第 \(i\) 个任务结束时，一定有一个人在 𝑎𝑖 处；（听上去是废话）
- 这提示我们，只需要记录，另一个人可能的位置，可以用 set 来存；
-
具体做法
- 二分答案 \(mid\)，
check的写法是遍历所有的人物，用一个set存：此时，一个人在 𝑎𝑖 处，另一个人可能的位置集合； - 若某个时刻set为空，则check失败；否则，check成功；
- 注意向 set 里插入 \(a_i\) 的时机需要仔细考虑，一种正确的插法是
- 在 \(𝑎_{𝑖+1}\) 处判断若 $a_i - a_{i + 1} < 𝑚𝑖𝑑 $ 是否成立
- 若成立，插入 \(a_i\)
- 二分答案 \(mid\)，
void solve() {
int n, x, y;
cin >> n >> x >> y;
vector<int> a(n);
for (auto&i : a) cin >> i;
auto check = [&](int d) {
int last = y;
set<int> S;
if (abs(x - y) <= d) S.insert(x);
for (auto x : a) {
if (!S.empty() && abs(x - last) <= d)
S.insert(last);
while(!S.empty() && *S.begin() < x - d) S.erase(S.begin());
while(!S.empty() && *S.rbegin() > x + d) S.erase(*S.rbegin());//rebegin()倒叙迭代的begin，同理还有rend(),并且rbegin() < rend()
last = x;
}
return !S.empty();
};
int lo = 0, hi = 1E9;
while(lo <= hi) {
int mid = lo + hi >> 1;
if (check(mid)) hi = mid - 1;
else lo = mid + 1;
}
cout << lo << endl;
}