牛客寒假营第二场题解
签到：A
easy：B、I
mid：E、F、H
hard：J
防AK：C、D、G
shit：B、G
前言
好难！
好难好难！！
好难好难好难好难！！！！
好难好难好难好难好难好难好难好难！！！！！！！！
B很坑，WA了4发才过，H一开始数据错了，爆了long long，但是验题已经过了十多个，我assert了一下发现果然爆了，于是将数据规模减小了。
E题不同的人差距很大，电波对上的话，不到五分钟就能过。
前七题和后三题完全不是同一个难度的，割裂有点大。G还有 的平衡树，非常阴间。
A 比赛安排
签到
由于连续三个不同，那么意味着一定是 循环，最后可以多出
或者
。
整合一下就是排序后最多的数与最少的数差值不超过 。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
array<int, 3> a;
for(auto &i : a){
cin >> i;
}
ranges::sort(a);
if(a[2] - a[0] <= 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
B NCPC
排序、贪心
如果最大的数的个数为奇数：
那么无论如何最后一定会剩一个最大的数，因此最大的数都可以获胜，因为一定会需要将最大的数两两消除，最后剩一个无法消除。
如果最大的数的个数为偶数：
最大的数最终一定会两两消去，除了最大的数都可以获胜，我们只要用一个最大的干掉所有小的，只留一个想让他赢的，最后将最大的数两两消去即可。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
map<int, vector<int>> mp;
string s(n, '0');
for(int i = 0; i < n; i++){
int x;
cin >> x;
mp[x].push_back(i);
}
auto &[x, y] = *prev(mp.end());
int t = 1;
if(y.size() % 2 == 0){
t = -1;
s = string(n, '1');
}
for(auto &i : y){
s[i] += t;
}
cout << s << endl;
}
}
C 炮火轰炸
搜索、二分
如果值域在 以内，我们可以直接暴力染色，暴力染色实际上最终会将雷的外侧空格包围起来，我们能不能快速将雷的外侧包围起来呢？
由于雷的数量为 ，因此我们每次沿着雷的外侧走，就可以用不超过
个标记为
的空格将雷围起来。（只标记周围有雷的空格）
那么每个雷内侧剩余的没被标记的空格就在炮火圈中，我们可以用类似上面的方法用不超过 个标记为
的空格将炮火圈围起来。
对于一个雷我们怎么知道雷的外侧空格和内侧空格是哪个呢？
我们按照从上到下，从左到右的顺序枚举，那么一个连通块中的第一个雷一定会在最左上方被枚举到，第一个雷的左上方一定是雷的外侧空格，从这个点开始搜索就可以绕完这整个连通块的外侧了。
反之，任意一个雷的右方、下方、右下方空格没有被搜索过，说明这个位置一定是内侧空格，在炮火圈中。
注意：如果一个雷已经在炮火圈中，则需要将这个雷删除。
现在每次查询只要知道 在不在炮火圈内即可，如何查询呢？
由于有一些点标记成了 或
：
如果 标记为
，它不在炮火圈里；
如果 标记为
，它在炮火圈里；
如果 上下左右四个方向出现的第一个被标记的空格都是
，则它在炮火圈里；（可以使用二分）
否则说明它不在炮火圈里。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, q;
cin >> n >> q;
vector st(1e6 + 2, set<int>());
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
st[x].insert(y);
}
vector<array<int, 2>> d = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
vector mp(1e6 + 2, map<int, int>());
vector mx(1e6 + 2, set<int>()), my = mx;
auto in = [&](int x, int y){
auto itx = mx[x].lower_bound(y);
auto ity = my[y].lower_bound(x);
if(itx == mx[x].end() || ity == my[y].end()) return 0;
return min(mp[x][*itx], mp[*ity][y]);
};
auto dfs = [&](this auto &&dfs, int x, int y, int cnt){
mp[x][y] = cnt;
mx[x].insert(y);
my[y].insert(x);
for(auto &[dx, dy] : d){
int xx = x + dx;
int yy = y + dy;
if(xx < 0 || yy < 0) continue;
if(st[xx].count(yy)) continue;
if(mp[xx].count(yy)) continue;
int tag = 0;
for(int dx = -1; dx <= 1; dx++){
for(int dy = -1; dy <= 1; dy++){
if(xx + dx >= 0) tag |= st[xx + dx].count(yy + dy);
}
}
if(tag) dfs(xx, yy, cnt);
}
};
for(int x = 1; x <= 1e6; x++){
for(auto &y : st[x]){
if(in(x, y)) continue;
for(int dx = -1; dx <= 1; dx++){
for(int dy = -1; dy <= 1; dy++){
int xx = x + dx;
int yy = y + dy;
if(xx < 0 || yy < 0) continue;
if(st[xx].count(yy)) continue;
if(mp[xx].count(yy)) continue;
if(min(dx, dy) >= 0) dfs(dfs, xx, yy, 1);
else dfs(xx, yy, 0);
}
}
}
}
while(q--){
int x, y;
cin >> x >> y;
if(in(x, y)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
D 数字积木
树形DP、数学
实际上权值就是 。计算所有连通块的
，可以转化成枚举
，求有多少个连通块的
为
（有多少个连通块包含
且不包含
）
然后再进行一步转化，将 的贡献拆分：枚举
，求有多少个连通块包含
。
包含 的连通块中，有些包含
怎么办？实际上这不重要，因为这些连通块一定会在枚举
的时候再次被计算一次。
那么现在问题就转化成了求连通块个数，对于一棵有根树的连通块个数可以用 DP 解决。
定义 为以
为根的子树能产生多少个包含点
的连通块，
。
以权值位 的点为根就可以解决包含
的连通块个数了
枚举 时，显然从
到根的链都必须存在，而其他点则可以选或不选，因此我们可以从
往根走，去除链对连通块数量的贡献。
在本题之前的版本中，数据保证了不会有 的情况，因此可以直接使用乘除法。但是在昨天去掉了这个限制，因此现在我们不可以使用除法，需要手动记录
因子或者使用类似换根 DP 的前后缀进行优化。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
template<const int M = 1e9 + 7>
struct MInt {
using LL = long long;
int x;
MInt(int x = 0) : x(norm(x)) {}
MInt(LL x) : x(norm(x % M)) {}
inline int norm(LL x) const {if (x < 0) x += M; if (x >= M) x -= M; return x;}
inline MInt ksm(MInt x, LL y) const {return x ^= y;}
inline int val() const {return x;}
inline MInt operator - () const {return MInt(norm(M - x));}
inline MInt inv() const {assert(x != 0 ); return *this ^ (M - 2);}
inline MInt& operator *= (const MInt& rhs) {x = LL(x) * rhs.x % M; return *this;}
inline MInt& operator += (const MInt& rhs) {x = norm(x + rhs.x); return *this;}
inline MInt& operator -= (const MInt& rhs) {x = norm(x - rhs.x); return *this;}
inline MInt& operator /= (const MInt& rhs) {return *this *= rhs.inv();}
inline MInt& operator ^= (LL y){
LL ans = 1;
while(y){
if(y & 1) ans = ans * x % M;
x = LL(x) * x % M;
y >>= 1;
}
x = ans;
return *this;
}
inline friend MInt operator * (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res *= rhs; return res;}
inline friend MInt operator + (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res += rhs; return res;}
inline friend MInt operator - (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res -= rhs; return res;}
inline friend MInt operator / (const MInt& lhs, const MInt& rhs) {MInt res = lhs; res /= rhs; return res;}
inline friend MInt operator ^ (const MInt& lhs, LL y) {MInt res = lhs; res ^= y; return res;}
inline friend istream& operator >> (istream& is, MInt& a) {LL v; is >> v; a = MInt(v);return is;}
inline friend ostream& operator << (ostream& os, const MInt& a) {return os << a.val();}
};
using Z = MInt;
int main(){
int n;
cin >> n;
vector<int> a(n + 1), in(n);
for(int i = 1; i <= n; i++){
cin >> a[i];
in[a[i]] = i;
}
vector ve(n + 1, vector<int>());
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
ve[u].push_back(v);
ve[v].push_back(u);
}
struct SafeProd {
int zero = 0;
Z prod = 1;
void mul(const Z& x) {if (x.val() == 0) zero++; else prod *= x;}
void div(const Z& x) {if (x.val() == 0) zero--; else prod /= x;}
Z val() const {return zero ? Z(0) : prod;}
};
vector<int> fa(n + 1), tag(n + 1);
vector dp(n + 1, SafeProd());
auto dfs = [&](auto &dfs, int u) -> void{
if(fa[u]) ve[u].erase(ranges::find(ve[u], fa[u]));
for(auto &v : ve[u]){
fa[v] = u;
dfs(dfs, v);
dp[u].mul(dp[v].val() + 1);
}
};
int root = in[0];
dfs(dfs, root);
vector<int> st(n + 1);
auto sum = dp[root];
Z ans = sum.val();
st[root] = 1;
for(int i = 1; i < n; i++){
int u = in[i];
while(!st[u]){
st[u] = 1;
sum.div(dp[u].val() + 1);
for(auto &v : ve[u]){
sum.mul(dp[v].val() + 1);
}
u = fa[u];
}
ans += sum.val();
}
cout << ans << endl;
}
E 01矩阵
构造
题目给出了答案为 的构造
类推一下答案为 的构造：
00
01
000
011
010
0000
0111
0100
0101
00000
01111
01000
01011
01010
然后就好了。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout << "10"[min(i, j) & 1];
}
cout << endl;
}
}
F x?y?n!
数论、位运算
观察样例可以得出一个猜测：
我们令
是
的倍数，
，此时可以确保
，如何在上述要求下满足
呢？
将 移项可以得到
，现在需要同时满足
这两个式子，继续展开可以得到：
因此只要满足 即可，现在我们需要构造
是
的倍数，且
。
左移操作实际上相当于一个数乘 ，令
，就相当于
，
一定是
的倍数，且满足
，因此我们得出了
，
就得到了
。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
cin >> T;
while(T--){
auto n = 0ll;
cin >> n;
cout << format("{} {}", n << 32, n << 32 | n) << endl;
}
}
G 宝藏拾取
数据结构、平衡树
将问题转化一下就是每次对 的前缀中大于等于
的数进行
操作，这东西在线段树上不容易维护，因为需要加
的那些数是不连续的。
如果我们从前往后一个个数字加入，前缀操作实际上就变成了全局操作，如果序列有序，找到第一个大于等于 的位置后就变成了一个区间
的操作。如果我们可以维护一个有序的序列，每次插入一个数字后还是维持有序，并且能找到第一个大于等于
的位置……
这不就是 set 吗？现在似乎还差区间操作。回忆一下 set的本质，实际上是一棵平衡树，我们只需要手写一棵平衡树实现 set 的 insert 、 lower_bound ，最后用类似线段树懒标记的方法实现区间加即可。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
template<typename T, const int M = 7>
class Splay{
public:
vector<array<T, M>> tr;
Splay(){
tr.push_back({});
tr[0][3] = -9e18;
}
inline void addSon(int u, int t, T x, int idx){
tr[u][t] = tr.size();
tr.push_back({0, 0, u, x, 1, 0, idx});
}
inline void pushup(int u){
tr[u][4] = 1;
if(lson(u)) tr[u][4] += tr[lson(u)][4];
if(rson(u)) tr[u][4] += tr[rson(u)][4];
}
inline void pushdown(int u){
if(lson(u)){
val(lson(u)) += tag(u);
tag(lson(u)) += tag(u);
}
if(rson(u)){
val(rson(u)) += tag(u);
tag(rson(u)) += tag(u);
}
tag(u) = 0;
}
void rotate(int u){
int t = lor(u);
int fa = tr[u][2];
int gf = tr[fa][2];
int os = tr[u][t ^ 1];
pushdown(u);
swap(tr[gf][lor(fa)], tr[fa][t]);
swap(tr[fa][t], tr[u][t ^ 1]);
swap(tr[u][2], tr[fa][2]);
if(os) swap(tr[fa][2], tr[os][2]);
else tr[fa][2] = u;
pushup(fa);
pushup(u);
}
int splay(int u, int v){
while(tr[u][2] != v){
int fa = tr[u][2];
int gf = tr[fa][2];
if(gf != v){
if(lor(u) == lor(fa)) rotate(fa);
else rotate(u);
}
rotate(u);
}
return u;
}
void update(int x){
int u = 0;
while(1){
pushdown(u);
int t = x >= val(u);
if(val(u) >= x) val(u) += x;
if(!t){
if(rson(u)){
tag(rson(u)) += x;
val(rson(u)) += x;
}
}
if(!tr[u][t]) break;
u = tr[u][t];
}
splay(u, 0);
}
void insert(T x, int idx){
int u = 0, t = 0;
while(1){
t = x >= val(u);
if(!tr[u][t]) break;
u = tr[u][t];
}
addSon(u, t, x, idx);
splay(tr.size() - 1, 0);
}
vector<array<T, 2>> toVector(int x = 0){
vector<array<T, 2>> ans;
auto dfs = [&](auto &dfs, int u) -> void{
pushdown(u);
if(tr[u][0]) dfs(dfs, tr[u][0]);
ans.push_back({tr[u][3], tr[u][6]});
if(tr[u][1]) dfs(dfs, tr[u][1]);
};
dfs(dfs, tr[0][x]);
return ans;
}
inline int lor(int u){
return rson(fa(u)) == u;
}
inline T& lson(int u){
return tr[u][0];
}
inline T& rson(int u){
return tr[u][1];
}
inline T& fa(int u){
return tr[u][2];
}
inline T& val(int u){
return tr[u][3];
}
inline T& siz(int u){
return tr[u][4];
}
inline T& tag(int u){
return tr[u][5];
}
inline T& root(){
return rson(0);
}
};
int main(){
int T = 1;
cin >> T;
while(T--){
int n;
cin >> n;
vector<int> a(n + 2);
Splay<LL> st;
for(int i = 1; i <= n; i++){
cin >> a[i];
st.update(a[i]);
st.insert(a[i], i);
}
vector<LL> ans(n + 1);
for(auto &[x, y] : st.toVector(1)){
ans[y] = x;
}
for(int i = 1; i <= n; i++){
cout << ans[i] << " ";
}
cout << endl;
}
}
H 权值计算
计数、容斥
伪代码实际上计算的权值是：一个数组的每个前缀的不同数字个数之和，然后我们需要计算一个数组的每个子数组的权值之和。
我们先思考一个简单的问题，定义一个数组的权值为数组中所有数字的总和，然后计算一个数组的每个子数组的权值之和。
一个常见的转化就是，每个数出现在多少子数组中：对于 ，左端点在
及以前（有
个选择），右端点在
及以后（有
个选择）的所有子数组都包含
，答案就是
。
再思考另一个问题，定义一个数组的权值为数组的不同数字个数，然后计算一个数组的每个子数组的权值之和。
类似上面的问题，将权值转化为每个数字再多少个子数组中有贡献。若数字 出现在
个位置
，那么有多少个子数组至少包含一个
呢？按照上面的结论：
对于第 个
，在
个子数组中包含了第
个
。
对于第 个
，在
个子数组中包含了第
个
。
那么有多少个子数组同时包含了两个 呢？应该是
，如果直接将第
个
的贡献求和，这些区间就会被多算。
所以 的贡献应该是
。
实际上是第
个
的贡献，那么第
个
实际上的贡献就是
，这个式子本质上其实是包含第
个
但不包含第
个
的子数组个数。
如果有第 个
在位置
，那包含第
个
但不包含第
个
的子数组个数就是
，为什么跟
没有关系呢？因为第
个
在第
个
左边，不包含第
个
一定不包含第
个
。
以此类推，对每一个 求出贡献就可以解决这个问题了。
最后回到题目，注意到题目和第二个问题差了一个前缀，现在需要求一个 在每个子数组的多少个前缀有贡献。
很显然如果 在位置
，一个包含
的子数组所有右端点大于等于
的前缀都会有
产生的贡献。
子数组的贡献是 ，实际上这个东西有两部分，
是左端点不同的选法，
是右端点的选法。
如果左端点固定，那么右端点的 种子数组对应的右端点大于等于
的前缀个数分别是
，总贡献就是
。
再乘上左端点的选法，就是 ，若不是第一个出现的
，则为
同第二个问题，对每个 求出贡献即可。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
cin >> T;
while(T--){
int n;
cin >> n;
map<int, vector<int>> mp;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
mp[x].push_back(i);
}
auto ans = 0ll;
for(auto &[x, y] : mp){
y.insert(y.begin(), 0);
for(int i = 1; i < y.size(); i++){
int l = y[i - 1];
int r = n - y[i] + 1;
ans += 1ll * r * (r + 1) / 2 * (y[i] - l);
}
}
cout << ans << endl;
}
}
I 01回文
思维
我们需要发现一个性质：一个长度大于 的
串，首尾都是
，且仅有
个
的话，那么它一定是回文串。
例如： 。
那如果矩阵有超过一个 ，那任意一个
只要找到离他最近的
的路径，就可以保证它们中间全都是
，反之同理。
因此只要 的个数大于
，所有
都是
，
的个数大于
，所有
都是
。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n, m;
cin >> n >> m;
vector s(n, string(m, '0'));
array<int, 50> mp = {};
for(auto &i : s){
cin >> i;
for(auto &j : i){
mp[j]++;
}
}
for(auto &i : s){
for(auto &j : i){
cout << "YN"[mp[j] == 1];
}
cout << endl;
}
}
}
J 终于再见
图论、BFS、最短路
首先需要发现一个结论：繁华度最多有大概 种。
因此直接按繁华度从大到小排序，用每种繁华度进行 BFS ，将初始值设置成 ，更新到达每个点的最短距离即可。
时间复杂度： 。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector ve(n + 1, vector<int>());
vector<int> deg(n + 1);
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
ve[u].push_back(v);
ve[v].push_back(u);
}
map<int, deque<int>> mp;
for(int i = 1; i <= n; i++){
mp[deg[i]].push_back(i);
}
vector<int> dis(n + 1, 1e9), ans(n + 1);
for(auto &[x, q] : mp | views::reverse){
for(auto &i : q){
if(dis[i] > 1e8) dis[i] = -1;
ans[i] = dis[i];
dis[i] = 0;
}
while(q.size()){
auto u = q.front();
q.pop_front();
for(auto &v : ve[u]){
if(deg[v] >= x) continue;
if(dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1;
q.push_back(v);
}
}
}
}
for(int i = 1; i <= n; i++){
cout << ans[i] << " ";
}
cout << endl;
}
京公网安备 11010502036488号