牛客周赛 Round 77 题解

签到题

#include <bits/stdc++.h>
using namespace std;int main()
{int a[6] = {20250121,20250123,20250126,20250206,20250208,20250211};int n; cin >> n;cout << a[n - 1];return 0;
}

想法：1~9每个数字的个数都在$[n/9,(n+8)/9]$这个区间范围内，因为满足这个条件，通过排序肯定可以生成一个数独数组。

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int a[10];int main()
{int n; cin >> n;for(int i = 0; i < n; i ++ ){int x; cin >> x;a[x] ++;}for(int i = 1; i <= 9; i ++ )if(a[i] < n / 9 || a[i] > (n + 8) / 9){cout << "NO";return 0;}cout << "YES";return 0;
}

C-小红走网格

想法：a, b, c, d分别表示上下左右四个方向的移动距离，目标是从(0, 0)到(x, y)，我们可以把他们抽象到两个方程去求解，分别是$k1\ast a+k2\ast b=y$、$k3\ast c+k4\ast d=x$，这就是线性同余算法，也就是若y可以被a和b的最大公约数整除，那么y就一定通过a和b两个数字构造出来，x也是同理。

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int x, y, a[4];void solve(){cin >> x >> y;for(int i = 0; i < 4; i ++ )cin >> a[i];int g1 = __gcd(a[0], a[1]), g3 = __gcd(a[2], a[3]);if(x % g3 == 0 && y % g1 == 0)cout << "YES";else cout << "NO";cout << endl;return ;
}int main()
{int _; cin >> _;while(_ --){solve();}return 0;
}

想法：将每个表示权重的数看成二进制表示形式，如果i和j在同一个社交网络即$(w_i\mathrm{and}{w}_j)\geqq 1$，那么这个权重一定在二进制的某一个位上有着相同的1（与运算全1出1，有0出0），因此可以使用并查集来维护这个有着二进制位同为1的集合，就是如果这个两个数可以在同一个社交网络，那么这个两个数所在的两个集合也可在同一个社交网络。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N =  100100;ll n, w[N], p[N];int find(ll x){if(p[x] != x)return p[x] = find(p[x]);return x;
}void solve(){cin >> n;for(int i = 0; i <= n + 64; i ++ ) p[i] = i;for(int i = 1; i <= n; i ++ ){cin >> w[i];for(int j = 0; j <= 61; j ++ )if(w[i] >> j & 1){int wf = find(i);int jf = find(n + j + 1);if(wf != jf)p[wf] = jf;}}map<int, int> cnt;int ans = 0;for(int i = 1; i <= n; i ++ ){int f = find(p[i]);cnt[f] ++;ans = max(ans, cnt[f]);}cout << ans << endl;return ;
}int main(){int _;cin >> _;while(_ -- ){solve();}return 0;
}

核心思路：区间$[l,r]$，用子串的总个数 - 连续都是0的子串个数。

想法：首先或运算的性质是有1出1，全0出0。我们假设字符串为0010010，子串的自审值为0的情况只有一种可能，那就是这个子串全是0，故此我们可以用【核心思路】来快速求自审值的和，因为自审值只可能是0或1，所以有字符1的子串的个数即为答案。

快速计算连续都是0的子串个数的方法有两种：

• 线段树，维护四个值分别是：0子串的个数(sum)， 前缀0的个数(left)， 后缀0的个数(right)， 当前区间的长度(len)。合并区间时会有四种情况。
  1. 左：0011， 右：1100，正常情况
  2. 左：0000， 右：0100，left, sum要特殊处理
  3. 左：0010， 右：0000，right, sum要特殊处理
  4. 左：0010： 右：0100，sum要特殊处理
• 前缀和， 例如00110010011000这是要求的区间，原字符串为00000110010011000000，要注意前缀0和后缀0的处理，去除前缀0和后缀0的中间部分，可以用前缀和来直接计算。

// 线段树解法
#include <bits/stdc++.h>
#define int long long
using namespace std;const int N =  200010;int n, q;
string s;struct Info{int l, r;int sum, left, right, len;
}tr[4*N];void merge(Info& res, Info l, Info r){
//     res.l = l.l; res.r = r.r;res.sum = l.sum + r.sum + l.right * r.left;res.len = l.len + r.len;res.left = l.left;res.right = r.right;if(l.left == l.len) res.left += r.left;if(r.right == r.len) res.right += l.right;
}// 合并操作
void pushUp(int u)
{merge(tr[u], tr[u << 1], tr[u << 1 | 1]);
}// 线段树初始化
void build(int u, int l, int r)
{tr[u].l=l, tr[u].r=r, tr[u].len = 1;if(l==r) return ;int mid=l+r>>1;build(u<<1, l, mid); build(u<<1|1, mid+1, r);
}// 查询
Info query(int u, int l, int r)
{if(tr[u].l>=l&&tr[u].r<=r) return tr[u];int mid=tr[u].l+tr[u].r>>1;Info lson, rson;lson = rson = {0, 0, 0, 0, 0, 0};if(l <= mid){lson = query(u << 1, l, r);}if(r > mid){rson = query(u << 1 | 1, l, r);}Info res;merge(res, lson, rson);res.l = lson.l; res.r = rson.r;if(lson.l == 0) res.l = rson.l;if(rson.r == 0) res.r = lson.r;return res;
}// 修改
void modify(int u, int x, int v)
{if(tr[u].l==x&&tr[u].r==x) tr[u].sum=v, tr[u].left = v, tr[u].right = v;else{int mid=tr[u].l+tr[u].r>>1;if(x<=mid) modify(u<<1, x, v);else modify(u<<1|1, x, v);pushUp(u);}
}signed main(){cin >> n >> s;s = " " + s;build(1, 1, n);for(int i = 1; i <= n; i ++ )modify(1, i, (s[i] == '0'?1:0));/*l r累加（r - l + 1)公式就是(1 + r - l + 1) * (r - l + 1) / 2;计算出子串的个数连续子串0的个数子串的个数 - 连续子串0的个数 = 答案*/cin >> q;while(q -- ){int l, r;cin >> l >> r;int ans = (1LL + r - l + 1) * (r - l + 1LL) / 2;Info t = query(1, l, r);ans -= t.sum;cout << ans << endl;}return 0;
}

// 前缀和做法
#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N =  200010;int n;
string s;
ll l[N], r[N];
ll p1[N], p2[N], p3[N];int main(){cin >> n >> s;s = " " + s;p1[0] = p2[n + 1] = p3[0] = 0;int t = 0;for(int i = 1; i <= n; i ++ ){p3[i] = (s[i] == '0') + p3[i - 1];if(s[i] == '0')l[i] = l[i - 1] + 1;else l[i] = 0;}for(int i = n; i >= 1; i -- ){p2[i] = l[i] + p2[i + 1];if(s[i] == '0')r[i] = r[i + 1] + 1;else r[i] = 0;}for(int i = 1; i <= n; i ++ )p1[i] = r[i] + p1[i - 1];int q; cin >> q;while(q -- ){int x, y;cin >> x >> y;ll len = y - x + 1;ll ans = (1 + len) * len / 2;int _x = x + r[x];int _y = y - l[y];if(_x <= _y){ans -= (1 + r[x]) * r[x] / 2;ans -= (1 + l[y]) * l[y] / 2;ans -= p1[_y] - p1[_x - 1];}else{ans = 0;}cout << ans << endl;}return 0;
}

F-计树

核心思路：启发式合并算法。

想法：分类讨论，有序的组合数量等于无序组合数量的两倍。

1. 当前点是集合中的点时，它要为LCA，当且仅当另个点在它的子树中或者两个点分别在它的两个不同的子树中。
2. 当前点不是集合中的点时，它要为LCA，当且仅当两个点分别在它的两个不同的子树中。

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 100010, M = N * 2;int n;
int e[M], ne[M], h[N], idx;
int k, vis[N];
int cnt[N];void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int dfs(int u, int f){if(vis[u]) cnt[u] = 1;int s = 0, t = 0;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(j == f) continue;int sons = dfs(j, u);t += sons * s; // 计算总的组合数量s += sons; // 计算有多少个集合中的点}cnt[u] += t * 2; // 有序的组合数量等于无序组合数量的两倍if(vis[u]){// 情况1，反之情况2cnt[u] += s * 2;s ++;}return s;
}signed main(){memset(h, -1, sizeof h);cin >> n;for(int i = 0; i < n - 1; i ++ ){int u, v;cin >> u >> v;add(u, v); add(v, u);}cin >> k;for(int i = 0; i < k; i ++ ){int x; cin >> x;vis[x] = 1;}dfs(1, 1);for(int i = 1; i <= n; i ++ )cout << cnt[i] << ' ';return 0;
}