题解 | #练习赛129题解#
数数
https://ac.nowcoder.com/acm/contest/90074/A
前言
F不会，剩下的感觉写的也挺丑陋，如果有问题欢迎大家指出
题解
A.数数
埃氏筛的写法，可以枚举所有质数，给因子中有该质数的数字标记+1，
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> cnt(n + 1);
for (int i = 2; i <= n; i++) {
if (!cnt[i]) {
for (int j = i; j <= n; j += i) {
cnt[j] += 1;
}
}
}
int ans = 0;
for (int i = 2; i <= n; i++) {
if (cnt[i] > 1) {
ans++;
}
}
std::cout << ans << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
B.三位出题人
本题可能最大的阻力是读题吧，就是某一道题不可以被所有人一起看，也不允许某一道题没有人看，那对于每一道题而言，可以被做，那就是
，这个数就是
，由于有
道题，再对这个数求个
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
const int mod = 1e9 + 7;
i64 ksm (i64 a, i64 b) {
i64 res = 1;
while(b) {
if (b & 1) {
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}
void solve() {
i64 n, m;
std::cin >> n >> m;
std::cout << ksm((ksm(2, m) - 2 + mod) % mod, n) << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
C.和天下
就是一个拆位来做的东西啊，可能是实现起来的时候把大家卡柱了。先考虑一下版本当
的时候，是不是只要是任意两个按位与起来大于
就可以建边，这个东西实现的时候就是枚举每一位嘛，如果某些数的该二进制位上的数是
就把他们放到同一个集合里面他们之间可以两两建边，给大家写一段伪代码参考一下
std::vector<std::vector<int> > a(35);
for (int j = 0; j <= 32; j++) {
for (int i = 1; i <= n; i++) {
if ((a[i] >> j) & 1) {
v[j].push_back(a[i]);
}
}
}
for (int i = 0; i <= 32; i++) {
for (int j = 1; j < v[i].size(); j++) {
merge(v[i][j], v[i][j - 1]);
}
}
再来看本题不就是把变了嘛，但思路不变啊，如果
的二进制串是
，最高位
在
这位，那假设有
和
这两个数，他们的最高位
在
这位，这两个数按位与运算之后的数是不是一定大于
了，那你可能会问了，那最高位
与
的最高位
在同一个位置的怎么办，那我们就继续去看下一位嘛，比如
的二进制串是
，你有两个数是
和
，发现了什么，这两个数虽然最高位
与
的相同，但次高位比
的大，这个时候我们其实可以就不管
位上的那个
，把这些数的下一个
的位置看做是最高位
的位置，在实现的时候可以把这三个数直接减去
，这样就可以做到消除最高位相同
的影响了啊，剩下的不就回到了hard版本开始的时候，看看那些数的二进制位置上有
是比
中的“最高位”
的位置还高，实现起来可以参考我的代码
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
i64 n, k;
std::cin >> n >> k;
std::vector<i64> a(n + 1);
std::vector<int> p(n + 1), cnt(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
p[i] = i;
cnt[i] = 1;
}
auto find = [&] (auto self, int x) ->int {
if (x == p[x]) {
return x;
}
else {
return p[x] = self(self, p[x]);
}
};
auto merge = [&] (int u, int v) -> void {
int fx = find(find, u), fy = find(find, v);
if (fx != fy) {
p[fx] = fy;
cnt[fy] += cnt[fx];
}
};
if (k == 0) {
std::cout << n << '\n';
return;
}
int target = 0;
for (int i = 63; i >= 0; i--) {
if ((k >> i) & 1) {
target = i;
break;
}
}
// std::cout << target << '\n';
//这里是在k不改变的情况下，有那些数进行按位与操作之后的大小比k大
std::map<int, std::vector<int> > mp;
for (int i = 1; i <= n; i++) {
for (int j = 63; j > target; j--) {
if ((a[i] >> j) & 1) {
mp[j].push_back(i);
}
}
}
//这里是有哪些数的最高位1，小于等于k的最高位1的时候
std::vector<int> vis(n + 1, 1);
for (int i = 1; i <= n; i++) {
for (int j = target; j >= 0; j--) {
if (((k >> j) & 1) == 0) {
if ((a[i] >> j) & 1 && vis[i]) {
mp[j].push_back(i);
}
}
if (vis[i] && ((k >> j) & 1) && (((a[i] >> j) & 1) == 0)) {
vis[i] = 0;
}
}
}
std::vector<int> v;
for (int i = 1; i <= n; i++) {
if (vis[i]) {
v.push_back(i);
}
}
for (int i = 1; i < v.size(); i++) {
merge(v[i], v[i - 1]);
}
for (auto [it, v] : mp) {
for (int i = 1; i < v.size(); i++) {
merge(v[i], v[i - 1]);
}
}
int ans = -1;
for (int i = 1; i <= n; i++) {
ans = std::max(ans, cnt[i]);
}
std::cout << ans << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
D.搬家
这个算是很板的倍增题吧，首先用双指针实现从任意一个位置开始装满一个箱子会到哪个位置，然后就是倍增的板子，最后算答案的时候就枚举看看从哪个位置开始装的东西最多，且不会超过
，这个不知道还能说点什么了，大家不会的可以先去学一下倍增的思想。代码仅供参考
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
void solve() {
i64 n, m, k;
std::cin >> n >> m >> k;
std::vector<i64> a(n + 1);
for (i64 i = 1; i <= n; i++) {
std::cin >> a[i];
}
i64 sum = 0;
i64 logn = 31 - __builtin_clz(n);
std::vector<std::vector<i64> > nxt(logn + 5, std::vector<i64> (n + 2));
i64 l = 1, r = 1;
while (l <= r && l <= n) {
if (r == n + 1) {
nxt[0][l] = r;
sum -= a[l];
l++;
continue;
}
sum += a[r];
while(sum > k) {
nxt[0][l] = r;
sum -= a[l];
l++;
}
r++;
}
nxt[0][n + 1] = n + 1;
for (i64 i = 1; i <= logn; ++i) {
for (i64 j = 1; j <= n + 1; ++j) {
nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
}
}
i64 ans = -1;
for (i64 i = 1; i <= n; i++) {
i64 num = m, tmp = 0, l = i;
for (i64 j = logn; j >= 0; j--) {
if (num >= (1 << j)) {
num -= (1 << j);
tmp += nxt[j][l] - l;
l = nxt[j][l];
if (l == n + 1) break;
}
}
ans = std::max(ans, tmp);
}
std::cout << ans << '\n';
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
std::cin >> t;
while (t--) {
solve();
}
}
}
E.Alice and Bod
精彩的线段树来了，我这里开了两棵线段树维护正反哈希，且在每一棵树中分别开了个懒标记，线段树中维护的
数组就是每个字母对应的哈希值，比如某一个字符串
那
的
代表的哈希值就是
+
+
与常规哈希不同，是把每个字母对应的位置进行哈希。然后就是维护这些东西了，在修改的时候比如是把这一段中的
修改成
了，那我们可以先记录一下
的哈希值，然后把
的哈希值赋给
类似操作
的字母就可以实现区间修改，我说不太明白再具体的维护方法，大家有问题可以来私信或评论。
#include<bits/stdc++.h>
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using i64 = long long;
using u64 = unsigned long long;
const int mod=1610612741;
const int base=13331;
i64 ha[100005][2][26], p[100005], tmp[26];
int n, m;
std::string s;
struct treenode {
int lz = 0;
int len = 0;
i64 vis[26];
treenode (){
for (int i = 0; i < 26; i++) {
vis[i] = 0;
}
}
};
struct Segment_Tree {
std::vector<treenode> tr;
void init (int n, int i) {
tr.resize((n + 1) << 2);
build(1, 1, n, i);
}
treenode merge (int rt, treenode a, treenode b) {
treenode res;
res.lz = tr[rt].lz;
res.len = a.len + b.len;
for (int i = 0; i < 26; i++) {
res.vis[i] = a.vis[i] * p[b.len] % mod + b.vis[i];
res.vis[i] %= mod;
}
return res;
}
void change(int rt, int x) {
tr[rt].lz += x;
tr[rt].lz %= 26;
for (int j = 0; j < 26; j++) {
tmp[j] = tr[rt].vis[j];
}
for (int j = 0; j < 26; j++) {
int t = (j + x) % 26;
tr[rt].vis[t] = tmp[j];
}
}
void push_down(int rt) {
if (tr[rt].lz) {
change(rt << 1, tr[rt].lz);
change(rt << 1 | 1, tr[rt].lz);
tr[rt].lz = 0;
}
}
void build(int rt, int l, int r, int i) {
tr[rt].lz = 0;
if (l == r) {
if (i == 0) {
tr[rt].vis[s[l] - 'a'] = 1;
}
else {
tr[rt].vis[s[n - l + 1] - 'a'] = 1;
}
tr[rt].len = 1;
return;
}
int mid = l + r >> 1;
build(lson, l, mid, i);
build(rson, mid + 1, r, i);
tr[rt] = merge(rt, tr[rt << 1], tr[rt << 1 | 1]);
}
void update(int rt, int l, int r, int L, int R, int x) {
if (l >= L && r <= R) {
change(rt, x);
return;
}
push_down(rt);
int mid = l + r >> 1;
if (mid >= L)
update(lson, l, mid, L, R, x);
if (mid < R) {
update(rson, mid + 1, r, L, R, x);
}
tr[rt] = merge(rt, tr[rt << 1], tr[rt << 1 | 1]);
}
treenode query(int rt, int l, int r, int L, int R) {
if (l >= L && r <= R) {
return tr[rt];
}
push_down(rt);
treenode ans;
int mid = l + r >> 1;
if (mid >= L)
ans = merge(rt, ans, query(lson, l, mid, L, R));
if (mid < R)
ans = merge(rt, ans, query(rson, mid + 1, r, L, R));
return ans;
}
}tr[2];
void solve() {
std::cin >> n >> m;
std::cin >> s;
s = ' ' + s;
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * base % mod;
for (int j = 0; j < 26; j++) {
ha[i][0][j] = (s[i] == ('a' + j));
ha[n - i + 1][1][j] = ha[i][0][j];
}
}
tr[0].init(n, 0);
tr[1].init(n, 1);
while(m--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r;
std::cin >> l >> r;
auto v1 = tr[0].query(1, 1, n, l, r);
auto v2 = tr[1].query(1, 1, n, n - r + 1, n - l + 1);
bool flag = 1;
for (int i = 0; i < 26; i++) {
flag &= (v1.vis[i] == v2.vis[i]);
}
if (flag) {
std::cout << "YES" << '\n';
}
else {
std::cout << "NO" << '\n';
}
}
else {
int l, r, x;
std::cin >> l >> r >> x;
x %= 26;
if (x == 0) continue;
tr[0].update(1, 1, n, l, r, x);
tr[1].update(1, 1, n, n - r + 1, n - l + 1, x);
}
}
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
i64 t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
看来商家也喜欢jd
投递美团等公司6个岗位 >
