2021 牛客寒假多校2 筛法 构造 思维
牛牛与整除分块
时
化简可得
于是以为界，在左边或者右边找对应的位置即可。
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int main() {
ll T, n, x;
sc(T);
while (T--) {
sc(n), sc(x);
ll a = sqrt(n);
if (x <= a)
pr(x);
else {
ll l = n / a;
ll ans = 0;
if (a != l) ++ans;
ll now = n / x;
ans += a - now + a;
pr(ans);
}
}
return 0;
} 牛牛与交换排序
简单分析后可知
- 第一次操作必然使最小的、不在其位的数让它归位
- 那么长度就已经固定了
- 那么接下来要做的就是模拟，看能否完成排序即可
可以用deque双端队列模拟，也可以用平衡树
#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int n, a[N];
deque<int> q;
int main() {
sc(n);
rep(i, 1, n) sc(a[i]);
int x = 0; //第一个不在正确位置上的数
// aka 不在正确位置上的 最小的数
rep(i, 1, n) if (a[i] != i) {
x = i;
break;
}
if (!x) return puts("yes\n1"), 0; //当前已经有序
int now, len;
rep(i, x + 1, n) if (a[i] == x) {
now = i; // 这个最小的错位数 现在在now这个位置
len = i - x + 1; // 需要翻转的线段长度
break;
}
rep(i, x, now - 1) q.emplace_front(a[i]);
bool tag = 0;
for (int i = x; i + len - 1 <= n; i++) {
if (!tag)
q.emplace_front(a[i + len - 1]);
else
q.emplace_back(a[i + len - 1]);
if (tag) {
if (q.front() != i) tag = 0;
} else {
if (q.back() != i) tag = 1;
}
if (tag) {
if (q.front() != i) return puts("no"), 0;
q.pop_front();
} else {
if (q.back() != i) return puts("no"), 0;
q.pop_back();
}
}
for (int i = n - len + 2; i <= n; i++) {
if (tag) {
if (q.front() != i) return puts("no"), 0;
q.pop_front();
} else {
if (q.back() != i) return puts("no"), 0;
q.pop_back();
}
}
printf("yes\n%d", len);
return 0;
} 牛牛与比赛颁奖
本题其实是一道非常基础的离散化+差分的板子题。
#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d ", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
pii a[N];
vector<int> ori; // 存储原值
unordered_map<int, int> pos; // key:原值 val: 离散化后
int d[N * 2]; // 差分数组
int num[N]; // num[x]表示过x题的队伍数目
int main() {
int n, m;
sc(n), sc(m);
rep(i, 1, m) sc(a[i].first), sc(a[i].second);
// 离散化
rep(i, 1, m) {
ori.emplace_back(a[i].first);
ori.emplace_back(a[i].second + 1);
}
sort(ori.begin(), ori.end());
ori.erase(unique(ori.begin(), ori.end()), ori.end());
int sz = ori.size();
for (int i = 0; i < sz; ++i) pos[ori[i]] = i;
// 差分
rep(i, 1, m) {
d[pos[a[i].first]]++;
d[pos[a[i].second + 1]]--;
}
// 前缀和
for (int i = 1; i < sz; ++i) d[i] += d[i - 1];
// 统计过x题的人数
--sz;
int maxAcNum = 0;
for (int i = 0; i < sz; ++i) {
int acNum = d[i]; //该区间过题数目
maxAcNum = max(maxAcNum, acNum); //更新最多过题数
int teamNum = ori[i + 1] - ori[i]; //该区间队伍数目
num[acNum] += teamNum;
}
// 计算名额
int au = (n + 10 - 1) / 10;
int ag = (n + 4 - 1) / 4;
int cu = (n + 2 - 1) / 2;
// 计算答案
int ans1 = 0, ans2 = 0, ans3 = 0;
for (int i = maxAcNum; i; --i) // 要求至少过1题
if (ans1 < au)
ans1 += num[i];
else if (ans1 + ans2 < ag)
ans2 += num[i];
else if (ans1 + ans2 + ans3 < cu)
ans3 += num[i];
cout << ans1 << ' ' << ans2 << ' ' << ans3;
return 0;
} 更优雅的做法是直接查询差分的map，这样就省去了离散化的过程，码量很小。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int g[N];
map<int, int> mp;
int num[5];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
mp[x]++, mp[y + 1]--;
}
num[1] = (n + 10 - 1) / 10;
num[2] = (n + 4 - 1) / 4;
num[3] = (n + 2 - 1) / 2;
int now = 0, pre = 1, maxn = 0;
for (auto &i : mp) { // 遍历差分map
maxn = max(maxn, now);
g[now] += i.first - pre; // 前后位置差值就是这个区间的人数
now += i.second; // 加上差分量 差分量就是过题数的位移量
pre = i.first;
}
int ans1 = 0, ans2 = 0, ans3 = 0;
for (int i = maxn; i; --i) // 要求至少过1题
if (ans1 < num[1])
ans1 += g[i];
else if (ans1 + ans2 < num[2])
ans2 += g[i];
else if (ans1 + ans2 + ans3 < num[3])
ans3 += g[i];
cout << ans1 << ' ' << ans2 << ' ' << ans3;
return 0;
} 牛牛的“质因数”
埃筛做法
首先什么是埃筛：
#include <stdio.h>
#include <string.h>
const int N = 100 + 8;
int isPrime[N];
void sieve() {
memset(isPrime, -1, sizeof isPrime);
isPrime[0] = isPrime[1] = 0;
for (int i = 2; i < N; ++i)
if (isPrime[i])
for (int j = 2; i * j < N; ++j) isPrime[i * j] = 0;
}
int main() {
sieve();
for (int i = 2; i < N; ++i)
if (isPrime[i]) printf("%d ", i);
return 0;
} 可以发现，在朴素的埃筛里，对于每一个合数，它会被每个它的质因数筛到。而如果是质数，他的质因数合并就是它本身。
所以只需要实时更新下每个数的质因数合并即可。
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 4e6 + 7;
const int mod = 1e9 + 7;
bitset<N> isPrime;
ll ans[N];
int main() {
ll w[10] = {1};
rep(i, 1, 9) w[i] = w[i - 1] * 10;
ll n;
sc(n);
isPrime.set();
rep(i, 2, n) {
if (isPrime[i]) {
ans[i] = i;
int len = log10(i) + 1;
for (int j = 2; i * j <= n; ++j) {
int now = i * j;
isPrime[now] = 0;
do {
ans[i * j] = (ans[i * j] * w[len] % mod + i) % mod;
now /= i;
} while (now % i == 0);
}
}
}
ll res = 0;
rep(i, 2, n) res = (res + ans[i]) % mod;
pr(res);
return 0;
} 这种做法时间复杂度，本题300ms
欧拉筛 + DFS
欧拉筛是近似线性的筛法，这意味着不能像埃筛一样，对每个数更新答案。
但是可以从另一个角度出发：
- 对于每个质数，它的质因数合并就是它本身。
- 对于每个合数，它的质因数合并是它所有质因数的拼接。
- 反过来说，可以用所有的质因数乘出来所有的数，对于质因数合并，也就是拼接。
- 所以每个数和它的质因数合并都是一一对应的。
所以，可以直接去尝试拼接就可以了，如果是在所求范围内的，就加上权重即可，这也是唯一分解定理的逆向应用，非常巧妙。
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 4e6 + 7;
const int mod = 1e9 + 7;
bitset<N> isPrime;
int prim[N + 10];
int pn = 0;
ll ans, n;
int w[10] = {1};
int pw[N];
void pre(int N) {
rep(i, 1, 9) w[i] = w[i - 1] * 10;
isPrime.set();
for (int i = 2; i <= N; i++) {
if (isPrime[i]) pw[pn] = w[int(log10(i) + 1)], prim[pn++] = i;
for (int j = 0; j < pn && i * prim[j] <= N; ++j) {
isPrime[i * prim[j]] = 0;
if (i % prim[j] == 0) break;
}
}
}
void dfs(int pos, ll key, ll val) {
ans = (ans + val) % mod;
for (int i = pos; i < pn; ++i) { // merge with bigger prime num
if (key * prim[i] > n) return;
dfs(i, key * prim[i], (val * pw[i] % mod + prim[i]) % mod);
}
}
int main() {
sc(n);
pre(n);
for (int i = 0; i < pn && prim[i] <= n; ++i)
// start dfs from each prime num
dfs(i, prim[i], prim[i]);
pr(ans);
return 0;
} 这种做法时间复杂度，本题70ms
牛牛想要成为hacker
本题很容易想到用斐波那契数列构建，但是fib很快就会超过1e9，数据项并不够。
所以：
- 不可能找不到三角形，只能推迟，但无法阻止
- 时间复杂度提示
>>> from math import log2 >>> log2(100000) 16.609640474436812
比赛的时候我想到了这里，但当时以为就是要让i循环走到16之后即可，所构建的数据也让i循环走到了21。但其实这是不够的：因为对于每个i循环，k并没有走次。
所以为了让次数尽可能多，必须降序构建。
最优的构造应当是降序的fib序列。
fib = [1, 1]
while fib[-1]+fib[-2] < 1e9:
fib.append(fib[-1]+fib[-2])
fib.reverse()
n = int(input())
sz = len(fib)
for i in range(n):
print(fib[i] if i < sz else 1, end=' ')
这也是一种比较有趣的写法
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld ", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int main() {
int n;
scanf("%d", &n);
int x = 1 << 29;
for(int i = 1;i <= n;i++){
printf("%d ", x);
if(x > 1) x >>= 1;
}
return 0;
} 
查看7道真题和解析
