2022-10-5总结

小D的序列

乱搞过的（

题目给了一个等比数列，我们可以用小学二年级就学过的等比数列求和公式 check 一下每个数作为公比的时候是否与真实的 sum 值相等。时间复杂度 $O(n \log n)$。

#include <cstdio>
#include <iostream>
#include <unordered_set>
using namespace std;
 
typedef long long ll;
const int N = 2e5+10;
 
int n, p;
ll a[N];
 
ll qpow(ll a, ll b);
 
int main()
{
    cin >> n >> p;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    ll sum = 0;
    for(int i = 1; i <= n; i++)
        (sum += a[i]) %= p;
    for(int i = 2; i <= n; i++)
    {
        ll chk = (qpow(a[i],n)-1) * qpow(a[i]-1, p-2)%p;
        if(chk == sum) { cout << a[i] << "\n"; break; }
    }
}
 
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%p)
        if(b&1) ans = ans*a%p;
    return ans;
}

小S排座位

肯定是一段前缀匹配一段后缀，直接维护即可，但我赛时写的二分。（我真傻，真的)

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
 
const int N = 1e6+10;
int n, k;
int a[N];
 
bool check(int x);
 
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
     
    int l = 0, r = n/2, mid;
    while(l < r)
    {
        mid = (l+r+1)>>1;
        if(check(mid))
            l = mid;
        else
            r = mid-1;
    }
    cout << l << "\n";
}
 
 
bool check(int x)
{
    vector<int> v;
    for(int i = x; i >= 1; i--)
        v.push_back(a[i]);
    for(int i = x+1; i <= n and v.size(); i++)
    {
        if(a[i]-v.back() >= k)
            v.pop_back();
    }
    return v.empty();
}

小K的外挂

如果没有向前连的边，这就是个倍增板子题。

然而有向前连的边，那就直接先取个前缀 $\max$ 再预处理倍增就行了。

但是这题有删边，考虑删一条边顶多变成次优解，预处理一个跳 $2^k$ 步能跳到的最大和次大距离。然后倍增的时候判一下编号即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const int LN = 17;

struct jump {
    int to, id;
    jump(int to = 0, int id = 0)
        : to(to), id(id) {}
};

struct node {
    jump max1, max2;
    void update(jump b)
    {
        if(b.to > max1.to)
            max2 = max1, max1 = b;
        else if(b.id != max1.id and b.to > max2.to)
            max2 = b;
    }
};

int n, m, q;
node a[N];
int l[N], r[N];
int f[N][LN+1][2];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> l[i] >> r[i];
        a[l[i]].update({r[i], i});
    }
    for(int i = 1; i <= n; i++)
    {
        a[i].update(a[i-1].max1);
        a[i].update(a[i-1].max2);
        f[i][0][0] = a[i].max1.to;
        f[i][0][1] = a[i].max2.to;
    }
    for(int j = 1; j <= LN; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            f[i][j][0] = f[ f[i][j-1][0] ][j-1][0];
            f[i][j][1] = f[ f[i][j-1][1] ][j-1][ a[f[i][j-1][1]].max1.id==a[i].max1.id ];
        }
    }
    
    cin >> q;
    for(int i = 1, id, s, t; i <= q; i++)
    {
        cin >> id >> s >> t;
        int ans = 0;
        if(t < l[id]) id = 0;
        if(s < l[id])
        {
            for(int i = LN; i >= 0; i--)
                if(f[s][i][0] < l[id])
                    ans += (1<<i), s = f[s][i][0];
            ans++, s = f[s][0][0];
        }
        if(s >= t)
        {
            cout << ans << "\n";
            continue;
        }
        for(int i = LN; i >= 0; i--)
            if(f[s][i][ a[s].max1.id==id ] < t)
                ans += (1<<i), s = f[s][i][ a[s].max1.id==id ];
        ans++, s = f[s][0][ a[s].max1.id==id ];
        if(s < t) cout << "-1\n";
        else cout << ans << "\n";
    }
}

小Z的作业

设 $f(r)$ 表示以 $r$ 为右端点，最小的满足答案为 Yes 的左端点。

显然 $f(i)$ 是单调递增的。

考虑每个位置开一个并查集，求 $f(i)$ 时，从 $i$ 开始不断向后加边，直到连通块数量小于 $k$ 停止即可。

但是这样时间复杂度太大，考虑先求出 $f(n)$，因为 $f(n-1) \le f(n)$，所以 $[f(n),n-1]$ 这一部分的边一定会在求 $f(n-1)$ 时用到，所以对于 $\forall i \in [f(n),n-1]$ ，在区间 $[i,n-1]$ 这个区间加入边 $i$ 即可。

可以用线段树分治维护这个过程，时间复杂度 $O(m \log^2 m + q)$。

#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

const int N = 2e5+10;

namespace dsu {
    int fa[N], siz[N], cnt;
    vector<pair<int,int>> opt;
    inline void init(int n)
    {
        for(int i = 1; i <= n; i++)
            fa[i] = i, siz[i] = 1;
    }
    inline int find(int x)
    {
        while(fa[x] != x)
            x = fa[x];
        return x;
    }
    inline bool check(int x, int y)
    {
        return find(x) == find(y);
    }
    inline bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y) return false;
        if(siz[x] < siz[y]) swap(x, y);
        opt.push_back({x, y});
        siz[x] += siz[y];
        fa[y] = x; cnt--;
        return true;
    }
    inline void undo()
    {
        int x = opt.back().first;
        int y = opt.back().second;
        opt.pop_back();
        siz[x] -= siz[y];
        fa[y] = y; cnt++;
    }
}

namespace tree {
    vector<int> opt[N*4]; int lim;
    void add(int ql, int qr, int id, int i = 1, int l = 1, int r = lim);
    void solve(int i = 1, int l = 1, int r = lim);
}

int n, m, k, tp, q;
int u[N], v[N];
int f[N];

int main()
{
    read(n, m, k, tp);
    for(int i = 1; i <= m; i++)
        read(u[i], v[i]);
    
    f[m+1] = m+1;
    dsu::init(n);
    dsu::cnt = n;
    tree::lim = m;
    tree::solve();
    
    read(q);
    unsigned int lans = 0;
    for(int i = 1, l, r; i <= q; i++)
    {
        read(l, r);
        if(tp == 1)
        {
            l = (l+lans)%m+1;
            r = (r+lans)%m+1;
            if(l > r) swap(l, r);
        }
        
        lans <<= 1;
        if(f[r] > l)
            print("Yes\n"), lans|=1;
        else
            print("No\n");
    }
}

namespace tree {
    #define ls (i<<1)
    #define rs (i<<1|1)
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    
    inline void solve(int i, int l, int r)
    {
        int tot = 0;
        for(auto x : opt[i])
            tot += dsu::merge(u[x], v[x]);
        if(l == r)
        {
            f[l] = f[l+1];
            while(f[l] > 1)
            {
                tot += dsu::merge(u[f[l]-1], v[f[l]-1]);
                if(dsu::cnt <= k) break;
                f[l]--;
                if(f[l] < l) tree::add(f[l], l-1, f[l]);
            }
        }
        else
        {
            solve(rs, rmid, r);
            solve(ls, l, lmid);
        }
        while(tot --> 0)
            dsu::undo();
    }
    
    void add(int ql, int qr, int id, int i, int l, int r)
    {
        if(ql <= l and r <= qr) return opt[i].push_back(id);
        if(ql <= lmid) add(ql, qr, id, ls, l, lmid);
        if(qr >= rmid) add(ql, qr, id, rs, rmid, r);
    }
}