LinhoNotes

外观

Codeforces Round 988 赛后复盘 ​

写代码的效率还是太慢了

E. Kachina's Favorite Binary String ​

思路比较简单的交互题，但是细节处理较多（也有可能是个人的处理方法不够优）

需要多练习特殊处理的能力，在写代码的时候避免畏难情绪（尤其不要跑去玩手机了）

F. Ardent Flames ​

是一个标算二分答案 + 扫描线的题，思路挺巧妙的，但也不是无迹可寻

解法 ​

我们将二分解决 k 个敌人的攻击次数，然后在每次 check 的时候，我们将处理出每名敌人能够被消灭的站位区间（这显然是一个以其为中心的连续区间），然后应用扫描线算法（感觉说是扫描线有点过了）判断此时是否存在某一站位可以使得至少 k 名敌人被消灭。

每次二分的开销来自扫描线所需的排序过程以及检查站位是否存在的过程，总计是 O(nlog⁡n) ，加上最外围的二分过程，整体时间复杂度为 O(nlog⁡(n)log(xmax)) ，可以接受

此外我们将设置一个显然不合理的二分上限，如果二分的结果为这个上限，就可以判断不存在任何方法达成目标

思路分析 ​

注意到坐标 x 的范围在 1e9 直接按照坐标处理显然会爆时间，所以必须按照每一个敌人进行处理，接下来考虑怎么进行求解：

扫描线 ​

扫描线算法多用于求解多区间覆盖下合法点的存在性，或者是统计区间的特性，经常配合线段树（实现区间修改与查询）使用，特征是题目出现了显然不能逐一处理的大坐标 / 时间轴元素，并且要求的问题可被抽象为多区间背景下的问题

二分查找 ​

我们无法简单地推导或者通过动态规划、贪心等算法来求解某一 “最值” 问题的时候，就可以考虑二分查找，要想二分查找，首先需要满足两个条件：

  • 答案是单调的
  • 答案可以被 check

对于这种题，条件一显然，条件二往往会是重点：怎么进行 check

我们不难发现固定下攻击次数与伤害基数之后可以缺定其有效区间，那就可以结合扫描线来查找是否有符合要求的站位

AC 代码 ​

cpp
#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#define OO cout << ">>>>";

using namespace std;

mt19937_64 rnd(time(0));

typedef long long ll;
typedef uint64_t ull;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt;

    while (tt--) {
        ll n, m, k;
        cin >> n >> m >> k;
        vector<ll> h(n + 1), x(n + 1);

        for (ll i = 1; i <= n; i++)
            cin >> h[i];

        for (ll i = 1; i <= n; i++)
            cin >> x[i];

        ll l = 1, r = 1e9 + 1, mid, ans = 1e9 + 1;

        while (l <= r) {
            mid = (l + r) / 2;

            vector<pair<ll, ll>> g;

            for (ll i = 1; i <= n; i++)
                if ((h[i] + mid - 1) / mid <= m) {
                    g.emplace_back(make_pair(
                        max(1ll, x[i] - (m - (h[i] + mid - 1) / mid)), 1));
                    g.emplace_back(make_pair(
                        x[i] + (m - (h[i] + mid - 1) / mid) + 1, -1));
                }

            sort(g.begin(), g.end());
            //			OO cout<<mid<<endl;
            //			for(auto [x,y]:g)
            //				cout<<x<<' '<<y<<endl;

            ll cnt = 0, flag = 0;

            for (auto [x, y] : g) {
                cnt += y;

                if (cnt >= k)
                    break;
            }

            if (cnt >= k)
                ans = min(ans, mid), r = mid - 1;
            else
                l = mid + 1;
        }

        //		OO
        if (ans > 1e9)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }

    return 0;
}

G. Natlan Exploring ​

一眼动态规划，也想出来了通过质因数分解来简化转化过程，但是囿于做题经验少，对于时间复杂度的感知能力不够强，导致在想思路的时候一直卡在 “如何去重” 上面，后面看了题解发现直接暴力使用容斥原理，复杂度常数只有 27=128 完全可以接受，唉唉，还好时间本来就来不及，不然又要后悔（

AC 代码 ​

cpp
#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

mt19937_64 rnd(time(0));

typedef long long ll;
typedef uint64_t ull;

const ll INF = 1e18, Mod = 998244353;

const ll MAXN = 1e6 + 1;

ll n;
ll mob[1000010], pr[1000010], a[200010], dp[1000010];

void init() {
    for (ll i = 1; i <= MAXN; i++)
        pr[i] = i, mob[i] = 1;
    for (ll i = 2; i <= MAXN; i++) {
        if (pr[i] == i) {
            for (ll j = i; j <= MAXN; j += i)
                pr[j] = min(pr[j], i);
            mob[i] = -1;
        }
    }
    mob[1] = 1;
    for (ll i = 2; i <= MAXN; i++) {
        if (pr[i] == pr[i / pr[i]])
            mob[i] = 0;
        else
            mob[i] = mob[i / pr[i]] * mob[pr[i]];
    }
    mob[1] = 0;
    //	for(ll i=1;i<=100;i++)
    //		cout<<i<<' '<<mob[i]<<endl;
}

ll DFS(vector<ll> &v, ll st, ll w) {

    if (w == v.size()) {
        if (st == 1)
            return 0;
        //		cout<<"!!"<<st<<' '<<dp[st]<<endl;
        return dp[st] * (-mob[st]);
    }

    return (DFS(v, st, w + 1) + DFS(v, st * v[w], w + 1)) % Mod;
}

void change(vector<ll> &v, ll st, ll w, ll ans) {
    if (w == v.size()) {
        if (st == 1)
            return;
        //		cout<<st<<' '<<ans<<endl;
        dp[st] = (dp[st] + ans) % Mod;
        return;
    }

    change(v, st, w + 1, ans);
    change(v, st * v[w], w + 1, ans);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    init();

    for (ll i = 1; i <= n; i++)
        cin >> a[i];

    for (ll i = 1; i <= n; i++) {
        ll x = a[i], ans = 0;
        vector<ll> v;
        while (x > 1) {
            if (v.empty() || *v.rbegin() != pr[x])
                v.emplace_back(pr[x]);
            x /= pr[x];
        }
        if (i == 1) {
            change(v, 1, 0, 1);
            continue;
        }
        ans = DFS(v, 1, 0);
        change(v, 1, 0, ans);

        //		cout<<">>>>>>"<<ans<<endl;
        if (i == n)
            cout << (ans + Mod) % Mod << endl;
    }
    return 0;

注意事项 ​

  • 经典的素数处理方法 —— 先离线处理其最小质因数，后在线按需求取对应数据（所有质因数，因子数等等）
  • DFS 处理遍历问题，传入参数不要省略，对于 vector 传入引用，注意终止条件的判断和无效状况的筛选
  • 不可在 vector 容器为空的时候访问其首尾指针，需要加一个特判