2022-11-11总结

序列

Description

小 Y 酷爱的接龙游戏正是这样。玩腻了成语接龙之后，小 决定尝试无平方因子二元合数接龙，规则如下： 现有 $n$ 个不超过 $10^6$ 的合数，每个均可表示为 $a=pq$ ( $p,q$ 为两个互异素数)。 若 $a=p_1 q_1 (p_1 < q_1)$ , $b=p_2 q_2(p_2 < q_2)$ ，当且仅当 $q_1 = p_2$ 时 $b$ 能接在 $a$ 后面。 请问从给定的这 $n$ 个数中选数接龙，最长可以形成一个包含多少数的接龙序列？

Input

第一行输入一个正整数 $n$, 意义如题干所述。

第二行输入 $n$ 个不超过 $10^6$ 的合数。

Output

输出一个整数表示答案。

Hint

$n \le 5 \times 10^4$。

Solution

把一个数 $a = p q$ 看成 $p \rightarrow q$ 的连边，然后跑 DAG 上的 DP 求出最长链即可。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("chain.in", "r", stdin);
        freopen("chain.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 1e6+10;

namespace sieve {
    bool vis[N];
    int prime[N], pcnt;
    int d[N];
    void main(int n)
    {
        for(int i = 2; i <= n; i++)
        {
            if(!vis[i]) prime[++pcnt] = i;
            for(int j = 1; j <= pcnt and i*prime[j] <= n; j++)
            {
                vis[i*prime[j]] = true;
                if(i%prime[j] == 0) break;
                else d[i*prime[j]] = prime[j];
            }
        }
    }
}
using namespace sieve;

int n, A[N], f[N];
vector<int> ver[N];

int main()
{
    read(n);
    sieve::main(1e6);
    for(int i = 1; i <= n; i++)
    {
        read(A[i]);
        int x = d[A[i]], y = A[i]/d[A[i]];
        ver[x].push_back(y);
    }
    
    
    int ans = 0;
    for(int i = 2; i <= 1e6; i++)
    {
        ans = max(ans, f[i]);
        for(auto y : ver[i])
            f[y] = max(f[y], f[i]+1);
    }
    
    print("{}", ans);
}

生成最小树

Description

你有一个含 $n$ 个点，$m$ 条边的图。现在选出一棵生成树，你每次可以选择树上一条边使其边权 $-1$，问至少需要操作多少次之后这棵树会成为图的最小生成树？保证图完全连通且不含重边。

Input

第一行输入两个数 $n, m$，分别表示图的点数和边数。

之后 $m$ 行，每行三个数 $u,v,w$，表示从点 $u$ 到点 $v$ 的连边权值为 $w$。

之后 $n-1$ 行，每行两个数 $a,b$，表示选定生成树的每条边。

Output

输出一个数，表示最少的操作次数。

Hint

$n \le 10^4, m \le 10^5, 1 \le w \le 10^6$。

Solution

考虑什么时候给定的树可以成为最小生成树：不存在一条边 $(x,y)$，用 $(x,y)$ 替换树上 $x \sim y$ 路径上一条边可以使生成树权值和更小，也就是所有非树边 $(x,y)$ 的权值都要大于等于树上 $x \sim y$ 路径上的最大值。

我们可以用树剖和线段树维护给定的树，枚举每条非树边，用每条非树边的权值在 $x \sim y$ 的路径上取 $\min$，最后把树上所有边的原权值和取完 $\min$ 的权值的差加起来就是答案。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("mintree.in", "r", stdin);
        freopen("mintree.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 1e5+10;
const int INF = 0x3f3f3f3f;

namespace HLD {
    int fa[N], dep[N], siz[N];
    int dfn[N], rk[N], dft;
    int big[N], top[N];
    int val[N], val2[N];
    void dfs1(int x, int dad);
    void dfs2(int x, int tp);
    void assign_min(int x, int y, int val);
}
namespace tr {
    struct node {
        int l, r;
        int min = INF;
    } a[N*4];
    
    void build(int l, int r, int i = 1);
    void assign_min(int ql, int qr, int val, int i = 1);
    void getans(int i = 1);
}
using namespace HLD;
using namespace tr;

typedef pair<int,int> pir;

struct edge{ int a, b, w; };

int n, m;
edge e[N];
vector<int> ver[N];
map<pir, int> mp;
set<pir> on;

int main()
{
    read(n, m);
    for(int i = 1; i <= m; i++)
    {
        read(e[i].a, e[i].b, e[i].w);
        mp[{e[i].a, e[i].b}] = mp[{e[i].b, e[i].a}] = e[i].w;
    }
    for(int i = 1; i <= n-1; i++)
    {
        int a, b; read(a, b);
        ver[a].push_back(b);
        ver[b].push_back(a);
        on.insert({a, b});
        on.insert({b, a});
    }
    
    HLD::dfs1(1, 0);
    HLD::dfs2(1, 1);
    tr::build(1, n);
    
    for(int i = 1; i <= m; i++)
    {
        if(on.count({e[i].a, e[i].b})) continue;
        HLD::assign_min(e[i].a, e[i].b, e[i].w);
    }
    
    tr::getans();
    
    
    ll sum = 0;
    for(int i = 2; i <= n; i++)
        sum += val[i]-val2[i];
    print("{}", sum);
}


namespace HLD {
    void dfs1(int x, int dad)
    {
        siz[x] = 1;
        fa[x] = dad;
        dep[x] = dep[dad]+1;
        for(auto y : ver[x])
        {
            if(y == dad) continue;
            val[y] = mp[{x,y}];
            dfs1(y, x); siz[x] += siz[y];
            if(siz[y] > siz[big[x]]) big[x] = y;
        }
    }
    void dfs2(int x, int tp)
    {
        top[x] = tp;
        dfn[x] = ++dft; rk[dft] = x;
        if(big[x]) dfs2(big[x], tp);
        for(auto y : ver[x])
            if(y != fa[x] and y != big[x])
                dfs2(y, y);
    }
    void assign_min(int x, int y, int val)
    {
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            tr::assign_min(dfn[top[x]], dfn[x], val);
            x = fa[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        if(x != y) tr::assign_min(dfn[x]+1, dfn[y], val);
    }
}
namespace tr {
    #define ls (i<<1)
    #define rs (i<<1|1)
    void pushdown(int i)
    {
        a[ls].min = min(a[i].min, a[ls].min);
        a[rs].min = min(a[i].min, a[rs].min);
    }
    void build(int l, int r, int i)
    {
        a[i].l = l, a[i].r = r;
        if(l == r)
        {
            a[i].min = val[rk[l]];
            return void();
        }
        int mid = (l+r)>>1;
        build(l, mid, ls);
        build(mid+1, r, rs);
    }
    void assign_min(int ql, int qr, int val, int i)
    {
        if(ql <= a[i].l and a[i].r <= qr)
            return void(a[i].min = min(a[i].min, val));
        pushdown(i);
        if(ql <= a[ls].r) assign_min(ql, qr, val, ls);
        if(qr >= a[rs].l) assign_min(ql, qr, val, rs);
    }
    void getans(int i)
    {
        if(a[i].l == a[i].r)
        {
            val2[rk[a[i].l]] = a[i].min;
            return void();
        }
        pushdown(i);
        getans(ls);
        getans(rs);
    }
}

互质序列

Description

给出两个数 $A,B (A \le B)$，问有多少个序列满足以下条件：

1. 序列是严格递增的。

2. 所有数字属于区间 $[A,B]$。

3. 序列中的所有数字两两互质。

Input

一行两个整数 $A,B$。

Output

输出一个整数表示答案。

Hint

$1 \le A \le B \le 10^{18}, B-A \le 100$。

Solution

考虑一个简单的问题： 如果 $A,B \le 100$ 怎么做，我们可以筛出来 $100$ 以内的质数，一共 $25$ 个，然后跑状压 DP 就行了，但是 $2^{25}$ 没法直接跑，可以把在 $[A,B]$ 中只出现过一次的质数给忽略掉，然后就变成 $2^{23} \sim 2^{24}$ 了，可以跑过去。

现在变成了 $A,B \le 10^{18}$，考虑哪些质数可能会出现两次，很明显只有 $p \le 100$ 的质数才可能出现两次以上，用上面的方法直接做就行了。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("rlprime.in", "r", stdin);
        freopen("rlprime.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 105;

namespace sieve {
    bool vis[105];
    int prime[30], pcnt;
    void main(int n)
    {
        for(int i = 2; i <= n; i++)
        {
            if(!vis[i]) prime[++pcnt] = i;
            for(int j = 1; j <= pcnt and i*prime[j] <= n; j++)
            {
                vis[i*prime[j]] = true;
                if(i%prime[j] == 0) break;
            }
        }
    }
} using namespace sieve;


ll A, B;
int st[N];
ll f[1<<24];

#define pos(i) (1<<(i-1))
#define ALL ((1<<pcnt)-1)

int main()
{
    read(A, B);
    sieve::main(B-A);
    
    for(int i = 1; i <= pcnt; i++)
    {
        int cnt = 0;
        for(ll x = A; x <= B; x++)
            if(x%prime[i] == 0) cnt++;
        if(cnt<=1) prime[i] = 114514;
    }
    sort(prime+1, prime+pcnt+1);
    pcnt = lower_bound(prime+1, prime+pcnt+1, 114514)-prime-1;
    
    for(ll i = A; i <= B; i++)
        for(int j = 1; j <= pcnt; j++)
            if(i%prime[j] == 0) st[i-A] |= pos(j);
    
    for(ll i = A; i <= B; i++)
    {
        int tmp = ALL^st[i-A];
        for(int j = tmp; j; j = (j-1)&tmp)
            f[j|st[i-A]] += f[j];
        f[st[i-A]] += f[0];
        
        f[st[i-A]]++;
    }
    
    ll ans = 0;
    for(int j = 0; j <= ALL; j++)
        ans += f[j];
    printv(ans);
}

鬼鬼的序列

Description

鬼鬼是一个十四岁的少女，她特别喜欢等差数列。出于对等差数列的喜欢，她想找这种序列：向这个序列 $a$ 中加上不多于 $k$ 个数，使这个新的数列排序后可以得到一个公差为 $d$ 的等差序列。

鬼鬼给你了一个由 $n$ 个整数组成的数列 。你的任务是找到它的最长子串，使它是鬼鬼想找的序列。鬼鬼会十分感谢你的！

Input

第一行三个整数 $n, k, d$。

第二行输入 $n$ 个整数，表示数列 $a$。

Output

输出两个整数 $l, r$，描述这个最长字串的左右边界，如果有多个最长子串，输出 $l$ 最小的。

Hint

$n,k \le 2 \times 10^5, 0 \le d \le 10^9, -10^9 \le a_i \le 10^9$。

Solution

考虑什么样的序列可以通过添加一些数重排成公差为 $d$ 的等差数列，我们先将所有 $a_i$ 按 $\bmod d$ 的值分类，设 $x_i = a_i \bmod d$，设 $y_i = \lfloor \frac{a_i}{d} \rfloor$，首先序列里不能出现 $x_i$ 不相同的数，否则一定无法构成等差数列，也不能出现相等的数，这样的序列就可以通过添加数来构成等差数列。

考虑满足条件的序列最少需要添加多少个数，首先构成的等差数列首项一定是 $a =\min\{y_i\}$，尾项一定是 $b=\max\{y_i\}$，所以这个等差数列应该有 $b-a+1$ 个数，而我们现在已经有了 $r-l+1$ 个数，只需要把剩下的空位填满即可，也就是需要填 $(b-a+1)-(r-l+1)$ 个数。

直接暴力枚举区间是 $O(n^2)$ 的，但是可以看到式子里有个非常套路的东西：极差；我们可以枚举每个右端点 $r$，用线段树维护每个左端点 $l$ 最少需要填多少个数，其实就是维护 $极差-区间长度$，这个直接用单调栈就行了，如果 $[l,r]$ 里出现了 $x_i$ 不相等的数，就直接把 $l$ 的答案赋值为 $\infty$。

查询每个右端点 $r$ 的答案可以直接线段树二分找到第一个满足 $\le k$ 的左端点，所以线段树需要支持区间加、区间赋值(赋 $\infty$)，然后维护区间 $\min$。

时间复杂度 $O(n \log n)$。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("seq.in", "r", stdin);
        freopen("seq.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 2e5+10;
const int INF = 0x3f3f3f3f;

namespace tr {
    struct node {
        int l, r, min;
        int lz_add, lz_asn;
    } a[N*4];
    
    void build(int l, int r, int i = 1);
    void add(int ql, int qr, int val, int i = 1);
    void assign(int ql, int qr, int val, int i = 1);
    int query(int i = 1);
    int get(int pos, int i = 1);
}

int n, k, d;
int val[N], x[N], y[N];
unordered_map<int,int> last;

struct Stack : vector<int> {
    int a[N], tp = 0;
    int size() { return tp; }
    bool empty() { return tp == 0; }
    void push(int x) { a[++tp] = x; }
    void pop() { tp--; }
    int top() { return a[tp]; }
    int sec() { return a[tp-1]; }
    void clear() { tp = 0; }
} st1, st2;

int main()
{
    int ansl = 0, ansr = -1;
    
    cin >> n >> k >> d;
    for(int i = 1; i <= n; i++)
    {
        cin >> val[i];
        if(d != 0)
        {
            x[i] = (val[i]%d+d)%d;
            y[i] = floor(val[i]*1.0/d);
        }
    }
    val[0] = INF;
    
    if(d == 0)
    {
        for(int l, r = 1; r <= n; r++)
        {
            if(val[r] != val[r-1]) l = r;
            if(r-l > ansr-ansl)
                ansl = l, ansr = r;
            else if(r-l == ansr-ansl and l < ansl)
                ansl = l, ansr = r;
        }
    }
    else
    {
        tr::build(0, n);
        
        for(int r = 1; r <= n; r++)
        {
            if(x[r] != x[r-1])
            {
                tr::assign(1, r-1, INF);
                st1.clear(), st2.clear();
            }
            
            if(last.count(val[r]))
                tr::assign(1, last[val[r]], INF);
            last[val[r]] = r;
            
            tr::add(0, r-1, -1);
            
            while(!st1.empty() and y[st1.top()] < y[r])
                tr::add(st1.sec()+1, st1.top(), y[r]-y[st1.top()]), st1.pop();
            while(!st2.empty() and y[st2.top()] > y[r])
                tr::add(st2.sec()+1, st2.top(), y[st2.top()]-y[r]), st2.pop();
            st1.push(r), st2.push(r); // 区间极差
            tr::assign(r, r, 0);
            
            int l = tr::query();
            if(r-l > ansr-ansl)
                ansl = l, ansr = r;
            else if(r-l == ansr-ansl and l < ansl)
                ansl = l, ansr = r;
        }
    }
    
    print("{} {}", ansl, ansr);
}


namespace tr {
    #define ls (i<<1)
    #define rs (i<<1|1)
    
    void add(node &i, int val)
    {
        i.min += val;
        i.lz_add += val;
    }
    void assign(node &i, int val)
    {
        i.min = val;
        i.lz_asn = val;
        i.lz_add = 0;
    }
    
    void pushdown(int i)
    {
        if(a[i].lz_asn != 0)
        {
            assign(a[ls], a[i].lz_asn);
            assign(a[rs], a[i].lz_asn);
        }
        if(a[i].lz_add != 0)
        {
            add(a[ls], a[i].lz_add);
            add(a[rs], a[i].lz_add);
        }
        a[i].lz_add = a[i].lz_asn = 0;
    }
    void pushup(int i)
    {
        a[i].min = min(a[ls].min, a[rs].min);
    }
    void build(int l, int r, int i)
    {
        a[i].min = INF;
        a[i].l = l, a[i].r = r;
        if(l == r) return void();
        int mid = (l+r)>>1;
        build(l, mid, ls);
        build(mid+1, r, rs);
    }
    void add(int ql, int qr, int val, int i)
    {
        if(ql > qr) return void();
        if(ql <= a[i].l and a[i].r <= qr)
            return add(a[i], val);
        pushdown(i);
        if(ql <= a[ls].r) add(ql, qr, val, ls);
        if(qr >= a[rs].l) add(ql, qr, val, rs);
        pushup(i);
    }
    void assign(int ql, int qr, int val, int i)
    {
        if(ql > qr) return void();
        if(ql <= a[i].l and a[i].r <= qr)
            return assign(a[i], val);
        pushdown(i);
        if(ql <= a[ls].r) assign(ql, qr, val, ls);
        if(qr >= a[rs].l) assign(ql, qr, val, rs);
        pushup(i);
    }
    int query(int i)
    {
        if(a[i].min > k) return n+1;
        if(a[i].l == a[i].r) return a[i].l;
        pushdown(i);
        if(a[ls].min <= k) return query(ls);
        else return query(rs);
    }
    int get(int pos, int i)
    {
        if(a[i].l == a[i].r) return a[i].min;
        pushdown(i);
        if(pos <= a[ls].r) return get(pos, ls);
        else return get(pos, rs);
    }
}