AI Summary
NOIP Day9题解:T1笛卡尔树加树状数组,T2用Z函数性质质因数分解二分,T4答案为n减众数频次,T3略。
NOIP 二十连测 Day 9
T1 最值(tree)
题目本身已经写的很明确了,就是求出对于树上每个 ,求出 ,其中, 到 的路径中 是编号最大的而 是最小的。
考虑建立两颗小根/大根笛卡尔树 ,那么题目条件转换为 在 上是 的祖先,而 在 中 的子树上。
直接考虑在 上 dfs 求欧拉序,然后在 上用树状数组维护权值即可。
时间复杂度 。
/*---------------------
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)
题意大致为,对于一个字符串 对应的 Z 函数 ,求出这个 所有对应的字符串 中 重复节数量最多的数量大小。
考虑 Z 函数的性质,可以得到,若 ,并且 时,存在字符串 重复节长度为 。
那么直接对 进行质因数分解,并且对每个质因子的幂次进行单独的二分询问即可。
因为 范围内本质不同的质因子个数最多只有 个,并且单个质因子的幂次不超过 ,二分次数不会大于 ,完全可以通过 的限制。
/*---------------------
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)
不那么容易的可以发现,答案即为 减去序列中众数出现次数。因为考虑将 排序,设众数次数为 ,最优策略显然是 与 匹配。因为此时配对中 的数量显然最大。
那么使用 STL map 维护出现次数,用 STL multiset 维护次数的集合就可以在 的复杂度上求众数的数量。
时间复杂度 。
/*---------------------
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)
暂无评论