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;
}