boxmoe_header_banner_img

Hello! 欢迎来到DRheEheAM的blog!

加载中

文章导读

Nov. 2th 总结


avatar
DRheEheAM_Gary憨毛怪 2026-11-03 72

AI Summary

NOIP Day9题解:T1笛卡尔树加树状数组,T2用Z函数性质质因数分解二分,T4答案为n减众数频次,T3略。

NOIP 二十连测 Day 9

T1 最值(tree)

题目本身已经写的很明确了,就是求出对于树上每个 uu,求出 ∑av\sum a_v ,其中, uu 到 vv 的路径中 uu 是编号最大的而 vv 是最小的。

考虑建立两颗小根/大根笛卡尔树 T1,T2T_1,T_2,那么题目条件转换为 vv 在 T1T_1 上是 uu 的祖先,而 vv 在 T2T_2 中 uu 的子树上。

直接考虑在 T2T_2 上 dfs 求欧拉序,然后在 T1T_1 上用树状数组维护权值即可。

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

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
typedef long long intl;
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e6+10;
#ifdef CLANGD_
#define N 10
#endif
int n,a[N];
struct edge {
    int to,nxt;
}e[N<<3];
int hd[N],ecnt=0;
int hd1[N],hd2[N];
void addedge (int u,int v) {
    e[++ecnt]={v,hd[u]},hd[u]=ecnt;
    e[++ecnt]={u,hd[v]},hd[v]=ecnt;
}
void addedge1 (int u,int v) {
    e[++ecnt]={v,hd1[u]},hd1[u]=ecnt;
} 
void addedge2 (int u,int v) {
    e[++ecnt]={v,hd2[u]},hd2[u]=ecnt;
}
int fa[N];
int find (int x) {
    if (x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
int tin[N],tout[N],tcnt=0;
void dfs2 (int u) {
    tin[u]=++tcnt;
    for (int i=hd2[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) dfs2(v);
    tout[u]=++tcnt;
}
intl res[N];
class Fenwick {
    intl tr[N<<1];
    inline int lb (int x) {return x&(-x);}
    public:
    void update (int x,int k) {
        while (x<(N<<1)) {
            tr[x]+=k;
            x+=lb(x);
        }
    }
    intl query (int x) {
        intl res=0;
        while (x) {
            res+=tr[x];
            x-=lb(x);
        }
        return res;
    }
    inline intl query (int l,int r) {return query(r)-query(l-1);}
}bit;
void dfs1 (int u) {
    res[u]=bit.query(tin[u],tout[u]);
    bit.update(tin[u],a[u]);
    for (int i=hd1[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) dfs1(v);
    bit.update(tin[u],-a[u]);
}
signed main() {
    Cios;
    // freopen("tree.in","r",stdin);
    // freopen("tree.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        addedge(u,v);
    }
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int u=n;u>=1;u--) {
        for (int i=hd[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) {
            if (v>u) addedge1(u,v=find(v)),fa[v]=u;
        }
    }
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int u=1;u<=n;u++) {
        for (int i=hd[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) {
            if (v<u) addedge2(u,v=find(v)),fa[v]=u;
        }
    }
    dfs2(n);
    dfs1(1);
    for (int i=1;i<=n;i++) cout<<res[i]<<" \n"[i==n];
    return 0;
}

/*
g++ -g tree.cpp -o tree.exe -std=c++14 -O2 -static; echo "finish"; .\tree.exe; rm tree.exe
cd $work/ZhengRui/Competition/noip20/9/tree && g++ tree.cpp -o tree -std=c++14 -O2 && echo "finish" && ./tree && rm tree
*/

T2 周期(period)

题意大致为,对于一个字符串 SS 对应的 Z 函数 ZZ ,求出这个 ZZ 所有对应的字符串 S′S’ 中 S′S’ 重复节数量最多的数量大小。

考虑 Z 函数的性质,可以得到,若 Zi+i=nZ_{i}+i=n ,并且 n|in|i 时,存在字符串 S′S’ 重复节长度为 ii 。

那么直接对 nn 进行质因数分解,并且对每个质因子的幂次进行单独的二分询问即可。

因为 n≤106n\le 10^6 范围内本质不同的质因子个数最多只有 77 个,并且单个质因子的幂次不超过 2020 ,二分次数不会大于 44,完全可以通过 q=9q=9 的限制。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
typedef long long intl;
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#include "period.h"
int qpow (int a,int b) {
    int res=1;
    while (b>0) {
        if (b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
vector <pair<int,int>> prim;
int solve(int n, int q) { 
    int temp=n;
    for (int i=2;i*i<=temp;i++) {
        if (temp%i==0) {
            int cnt=0;
            while (temp%i==0) temp/=i,cnt++;
            prim.push_back({i,cnt});
        }
    }
    if (temp>1) prim.push_back({temp,1});
    int res=1;
    for (auto [pr,cnt]:prim) {
        int l=1,r=cnt,resp=0;
        while (l<=r) {
            int mid=(l+r)>>1;
            int len=n/qpow(pr,mid);
            if (query(len)==n-len) l=mid+1,resp=mid;
            else r=mid-1;
        }
        res*=qpow(pr,resp);
    }
    return res;
}
/*
g++ -g period.cpp -o period.exe -std=c++14 -O2 -static; echo "finish"; .\period.exe; rm period.exe
cd $work/ZhengRui/Competition/noip20/9/period && g++ period.cpp implementer.cpp -o period -std=c++14 -O2 && echo "finish" && ./period && rm period
*/

T3 (不考虑补)

T4 重排(reorder)

自定义表情 不那么容易的可以发现,答案即为 nn 减去序列中众数出现次数。因为考虑将 aia_i 排序,设众数次数为 kk ,最优策略显然是 aia_i 与 ai−ka_{i-k} 匹配。因为此时配对中 ai<bia_i<b_i 的数量显然最大。

那么使用 STL map 维护出现次数,用 STL multiset 维护次数的集合就可以在 O(log⁡n)O(\log n) 的复杂度上求众数的数量。

时间复杂度 O(qlog⁡n)O(q\log n)。

/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
typedef long long intl;
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+10;
int n,q,a[N];
map <int,int> cnt;
multiset <int> cts;
signed main() {
    Cios;
    // freopen("reorder.in","r",stdin);
    // freopen("reorder.out","w",stdout);
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
    for (auto [a,ct]:cnt) cts.insert(ct);
    cout<<n-*cts.rbegin()<<"\n";
    while (q--) {
        int p,x;
        cin>>p>>x;
        cts.erase(cts.find(cnt[a[p]]));
        cts.insert(--cnt[a[p]]);
        auto it=cts.find(cnt[x]);
        if (it!=cts.end()) cts.erase(it);
        cts.insert(++cnt[x]);
        a[p]=x;
        cout<<n-*cts.rbegin()<<"\n";
    }
    return 0;
}

/*
g++ -g reorder.cpp -o reorder.exe -std=c++14 -O2 -static; echo "finish"; .\reorder.exe; rm reorder.exe
cd $work && g++ reorder.cpp -o reorder -std=c++14 -O2 && echo "finish" && ./reorder && rm reorder
*/



评论(0)

查看评论列表

暂无评论


发表评论

DRheEheAM_Gary Blog