2024牛客寒假算法基础集训营1

A

找dfs这三个字符即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 55;int n;
char s[N];void solve()
{cin >> n >> s + 1;int pos1 = -1, pos2 = -1, pos3 = -1;int f1 = 1, f2 = 1;for(int i = 1; i <= n; i ++){if(s[i] == 'D'){pos1 = i;break;}}if(pos1 == -1)f1 = 0;for(int i = n; i >= 1; i --){if(s[i] == 'S'){pos3 = i;break;}}if(pos3 == -1)f1 = 0;for(int i = pos1 + 1; i < pos3; i ++){if(s[i] == 'F'){pos2 = i;break;}}if(pos2 == -1)f1 = 0;pos1 = -1, pos2 = -1, pos3 = -1;for(int i = 1; i <= n; i ++){if(s[i] == 'd'){pos1 = i;break;}}if(pos1 == -1)f2 = 0;for(int i = n; i >= 1; i --){if(s[i] == 's'){pos3 = i;break;}}if(pos3 == -1)f2 = 0;for(int i = pos1 + 1; i < pos3; i ++){if(s[i] == 'f'){pos2 = i;break;}}if(pos2 == -1)f2 = 0;cout << f1 << ' ' << f2 << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

B

枚举情况

考虑左右各堵住了几格和特判(1,-1)(1,1)(2,0)这三个点

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010;void solve()
{int n;cin >> n;map<PII, int> mp;for(int i = 0; i < n; i ++){int x, y;cin >> x >> y;mp[{x, y}] = 1;}int l = 0, r = 0;for(auto t : mp){int x = t.first.first, y = t.first.second;//cout << "===" << x << ' ' << y << endl;if(y < 0){l = max(l, 1);int tmp = 1;if(x == 1)tmp = 2;if(mp.count({tmp, y - 1}) || mp.count({tmp, y}) || mp.count({tmp, y + 1})){l = 2;}}else if(y > 0){r = max(r, 1);int tmp = 1;if(x == 1)tmp = 2;if(mp.count({tmp, y - 1}) || mp.count({tmp, y}) || mp.count({tmp, y + 1})){r = 2;}}}int res = 4 - l - r;int tmp = 4;if(mp[{2, 0}]){tmp = 2;if(mp[{1, -1}])tmp --;if(mp[{1, 1}])tmp --;if(r == 2)res = min(res, 1);if(l == 2)res = min(res, 1);}res = min(res, tmp);if(mp[{1, -1}]){res = min(res, 2);if(mp[{1, 1}])res = min(res, 1);}if(mp[{1, 1}]){res = min(res, 2);}res = min(res, 3);cout << res << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

C

可以排序然后前缀和预处理出来在哪个人前面插队增加的时间，对每次询问可以二分来找

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010;ll a[N], b[N];void solve()
{int n, Q, t;cin >> n >> Q >> t;for(int i = 1; i <= n; i ++)cin >> a[i];sort(a + 1, a + 1 + n);for(int i = 1; i <= n; i ++)a[i] += a[i - 1];for(int i = 1; i <= n; i ++)//第i个时刻前插队 {b[i] = (ll)(n - i + 1) * t;}b[n + 1] = 0;while(Q --){ll x;cin >> x;int l = 1, r = n + 1;while(l < r){int mid = l + r >> 1;if(b[mid] <= x)r = mid;else l = mid + 1;}cout << a[l - 1] + t << endl;}
}int main()
{IOSint _ = 1;//cin >> _;while(_ --){solve();}return 0;
}

E

范围只有10，可以3的n次方枚举所有情况

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 15;int a[N], b[N];
int q1[N], q2[N];void solve()
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 0; i < m; i ++){cin >> q1[i] >> q2[i];}int num = 1;for(int i = 0; i < m; i ++)num *= 3;int ans = 2e9;for(int i = 0; i < num; i ++){for(int j = 1; j <= n; j ++)b[j] = a[j];int t = i;for(int j = 0; j < m; j ++){int A = q1[j], B = q2[j];if(t % 3 == 0){b[A] += 3;}else if(t % 3 == 1){b[B] += 3;}else{b[A] ++;b[B] ++;}t /= 3;}  int x = b[1];sort(b + 1, b + 1 + n);int l = 1, r = n;while(l < r){int mid = l + r + 1 >> 1;if(b[mid] <= x)l = mid;else r = mid - 1;}ans = min(ans, n + 1 - l);}cout << ans << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

F

第二类斯特林数

将n个不同的元素分为k个集合或者将n个不同的小球放进k个相同的箱子

S(n, k) = S(n - 1, k) + k * S(n - 1, k)

n=k时为1，S(n, k) = 1

S(n, 0) = 0，特别地S(0, 0) = 1

容斥原理计算公式

$S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^{k}C(m,k)(m-k)^{n}$

搭配快速幂可以mlogn求出来

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010, mod = 1e9 + 7;int n, m;
int fact[N], infact[N], inv[N];int C(int a, int b)
{if(a < b)return 0;return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}ll qmi(ll a, ll k)
{ll res = 1;while(k){if(k & 1)res = res * a % mod;a = a * a % mod;k >>= 1;}return res;
}int main()
{IOSfact[0] = fact[1]= infact[0] = infact[1] = inv[1] = 1;for(int i = 2; i < N; i ++){fact[i] = ((ll)fact[i - 1] * i) % mod;inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;infact[i] = (ll)infact[i - 1] * inv[i] % mod;}cin >> n >> m;int sign = 1;ll ans = 0;for(int k = 0; k <= m; k ++){ll res = C(m, k) * qmi(m - k, n) % mod * sign;ans = (ans + res) % mod;sign *= -1;} ans = (ans + mod) % mod;ll tmp = 1;for(int i = 2; i <= m; i ++){tmp = tmp * i % mod;}ans = ans * qmi(tmp, mod - 2) % mod;cout << ans;return 0;
}

G

本金+b[i] >= a[i]时就说明可以买，可以先把所有b[i]加到本金里，然后从最大的a[i]往小枚举，不满足的话就-b[i]

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010;PII a[N];bool cmp(PII A, PII B)
{return A.first - A.second < B.first - B.second;
}void solve()
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i ++){int x, y;cin >> x >> y;a[i] = {x, y};}sort(a + 1, a + 1 + n);ll t = m;for(int i = 1; i <= n; i ++){t += a[i].second;}for(int i = n; i >= 1; i --){if(t < a[i].first){t -= a[i].second;}}cout << t << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

H

标题说是背包但其实解法跟背包也没什么关系

如果背包容量为10101 （二进制）

物品重量为10101 10011

如果选了第一个物品第二个就选不了，如果选了第二个第一个就选不了，无法同时选

可以考虑将背包容量的某一位1强制转为0，然后这一位上为1的物品都不选，只要在这一位之前，物品的重量的位为1时背包这一位也为1就说明可选。这一位之后怎么都无所谓的，不论怎么选都会小于原背包容量的

这样在每次过程中每个物品都变成了可选和不可选两种情况。

然后背包原重量也这么来一遍，取一个最大值即可

这样枚举是包含所有情况的

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010;int n, m;
int v[N], w[N];void solve()
{cin >> n >> m;for(int i = 1; i <= n; i ++){cin >> v[i] >> w[i];}ll ans = 0;for(int i = 1; i <= n; i ++){if((w[i] | m) == m){ans += v[i];}}while(m){if(m & 1){m >>= 1;ll res = 0;for(int i = 1; i <= n; i ++){if(w[i] & 1){w[i] >>= 1;continue;}w[i] >>= 1;if((w[i] | m) == m){res += v[i];}}ans = max(ans, res);}else {m >>= 1;for(int i = 1; i <= n; i ++)w[i] >>= 1;}}cout << ans << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

I

正统解法其实是看点的分布概率，第一个人的点分布概率是平均的，第二个人的点分布概率是偏中心的。

我想的是算两个人半径的期望，第二个人的期望一定比第一个人的期望大

最终半径的平均值离谁更近就说明是谁，那肯定有一个临界值，我的想法是找这个临界值

或者也可以真的按这两个人的办法分别模拟1e5或者更多次，看期望是多少

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;int main()
{IOSint n;cin >> n;double r = 0;for(int i = 1; i <= n; i ++){double tmp;cin >> tmp >> tmp >> tmp;r += tmp;}r /= (double)n;if(r <= 20.0)cout << "bit-noob";else cout << "buaa-noob";return 0;
}

K

一个题的选项是对应题的答案，可以构建出一个基环树（其实是若干个基环树，或者说森林）。

一个环可以有好几条链，所以从链的起点出发其实不好算，但也可以发现后者答案固定后前者的答案是可以逆推出来的，所以可以从一个环上的任意一个点当成起点出发，枚举A-F选项，如果选项合理就计入答案

最终答案数其实就是每个环的方案数相乘

这里学到了一种很好写的方法，用vector存这次遍历到的所有点，然后看最后一个点的下一个点是否在vector中，如果在就说明有环，把这个点之前的点清除剩下的就是一个环。如果最后一个点的下一个点没在vector中就说明没环（环已经被标记了），非常方便的写法

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010, mod = 998244353;int n;
int a[N];
string s[N];
bool st[N];int main()
{IOScin >> n;for(int i = 1; i <= n; i ++){cin >> a[i] >> s[i];}ll ans = 1;for(int i = 1; i <= n; i ++){if(st[i])continue;int j = i;vector<int> v;for(; !st[j]; j = a[j]){st[j] = true;v.push_back(j);}vector<int>::iterator it = find(v.begin(), v.end(), j);if(it == v.end())continue;v.erase(v.begin(), it);//这样只剩下环里的点了ll res = 0;for(char ch = 'A'; ch <= 'E'; ch ++){int t = ch - 'A';for(auto x : v){t = s[x][t] - 'A';}if(ch - 'A' == t)res ++;}ans = ans * res % mod;}cout << ans;return 0;
}

L

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 100010;ll a[N], b[N];void solve()
{ll c, d, h, w;cin >> c >> d >> h >> w;cout << 3 * w * c << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

M

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 55;void solve()
{int n;cin >> n;if(n % 6){cout << n / 6 * 2 << endl;}else cout << n / 6 << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}