巅峰赛#22 全题解

亚洲卷王 AK IOI

2025-06-23 05:42:53

发布于：北京

128阅读

0回复

0点赞

T1-未出现的人

可以想到，对于 $n$ 个人中的每一个， $O(m)$ 遍历查找是否在 $m$ 个出席者中，这样是 $O(nm)$ 的，可以通过本题。

当然，也有更好的做法，比如字符串哈希，可以做到线性，这里我使用的是又快又好写的 set。把 $m$ 个出席者加入到 set 中，再判断 $n$ 个人是否在 set 里，如果不在则输出。

时间复杂度： $O((n+m) \log m)$ .

空间复杂度： $O(n+m)$ .

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
string s;
string a[105];
set<string> sets;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>s;
        sets.insert(s);
    }
    for(int i=1;i<=n;i++){
        if(sets.count(a[i])) continue;
        cout<<a[i]<<'\n';
    }
    return 0;
}

T2-gcd

思考一个问题：已知一个 $g$ ，那么能否快速判断是否有子序列，让其最大公约数为 $g$ ？容易想到计算所有 $g$ 的倍数的最大公约数 $g'$ ，再判断 $g'$ 是否等于 $g$ 即可。 $g$ 可以枚举得到。显然， $a_i \leq 5000$ ，所以 $g$ 最多是 $5000$ 而且卡不满，这样我们就解决了如何选择子序列。

而且，选择所有 $g$ 的倍数作为子序列是最优的（比较简单不再赘述）。此时，子序列的最大公约数应该是 $g+1$ ，非子序列中的最大公约数直接计算即可。最后取最大值。

虽然 $\gcd$ 带有一只 $\log$ 有概率超时，但是刚才说了， $g$ 是卡不满的，所以不用担心。

时间复杂度：卡不满的 $O(n^2 \log n)$ .

空间复杂度： $O(n)$ .

Code:

#include<bits/stdc++.h>
using namespace std;
int n,g,gg,ans;
int a[5005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=5000;i++){
        g=0;
        for(int j=1;j<=n;j++){
            if(a[j]%i) continue;
            g=__gcd(a[j],g);
        }
        if(i==g){
            gg=0;
            for(int j=1;j<=n;j++){
                if(a[j]%i) gg=__gcd(a[j],gg);
                else gg=__gcd(g+1,gg);
            }
            ans=max(gg,ans);
        }
    }
    cout<<ans;
    return 0;
}

T3-a + b

~~我是不会告诉你本来想暴力骗分结果不小心过了的~~

直觉告诉我们如果较小的数据下没有答案，较大数据中也不太可能有。所以枚举 $a,b$ 到 $1000$ 即可。

时间复杂度： $O(10^6 \log 10^6)$ .

空间复杂度： $O(1)$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string sa,sb,sc;
bool a[10],b[10],c[10];
inline bool can(ll x, bool* arr){
    if(x==0) return arr[0];
    while(x){
        if(!arr[x%10]) return false;
        x/=10;
    }
    return true;
}
int main(){
    cin>>sa>>sb>>sc;
    for(auto &i:sa) a[i^48]=true;
    for(auto &i:sb) b[i^48]=true;
    for(auto &i:sc) c[i^48]=true;
    for(ll i=0;i<1000;i++){
        if(!can(i,a)) continue;
        for(ll j=0;j<1000;j++){
            if(!can(j,b)) continue;
            ll k=i+j;
            if(can(k,c)){
                cout<<i<<' '<<j<<' '<<k;
                return 0;
            }
        }
    }
    cout<<"impossible";
    return 0;
}

T4-礼物

首先 $O(n^2m)$ 的暴力转移 DP 非常好写，不再说明。考虑优化 DP。

容易想到，每一次购买是独立的，相互不依赖、不影响。所以可以预处理一下。

预处理出进行一次购买，花费为 $i$ 时候，小 P 所能拿到的最大价值。这个过程 $O(n^2)$ 枚举即可。

然后就是朴实无华的完全背包了。

时间复杂度： $O(n^2+m^2)$ .

空间复杂度： $O(n+m)$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll c[5005],v[5005],a[5005],pre[5005],dp[5005];
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>c[i]>>v[i];
    for(ll i=1;i<=n;i++){
        for(ll j=i+1;j<=n;j++){
            if(c[i]+c[j]>m) continue;
            a[c[i]+c[j]]=max(min(v[i],v[j]),a[c[i]+c[j]]);
        }
    }
    for(ll i=2;i<=m;i++) pre[i]=max(a[i],pre[i-1]);
    for(ll i=2;i<=m;i++) for(ll j=i;j<=m;j++) dp[j]=max(dp[j-i]+pre[i],dp[j]);
    cout<<dp[m];
    return 0;
}

T5-聊天室

如果开始聊天的时刻 $l'$ 确定，那么最早结束时间 $r'$ 是多少？显然为 $l'+d-1$ 。

那么开始聊天的时刻是什么时候呢？显然是 $u_i$ 或者 $l_j$ 中的一个。

如果网友上线比 Alice 晚，也就是 $l_j \geq u_i$ 的时候。不难想到按照 $r_j-l_j$ 从大到小排序，再按照 $d_i$ 从大到小排序，然后双指针求解。（这样就需要我们离线处理）当我们找到了一个满足条件的区间 $[l_j,r_j]$ 的时候，记录 $l_i$ ，最后判断 $[u_i,v_i]$ 中是否有记录即可。

这个过程暴力做是 $O(nm)$ 的，可以使用树状数组，将 $l_i$ 这个点增加 $1$ ，最后查询 $[u_i,v_i]$ 范围内的和是否为正数。这样是 $O((m+q) \log n)$ 的。

如果网友上线比 Alice 早，也就是 $l_j<u_i$ 的时候，不难想到按照 $l_j$ 和 $u_i$ 从小到大排序，也可以双指针求解。如果区间 $[l_j,r_j]$ 满足 $l_j<u_i$ ，那么记录 $r_j$ ，最后判断记录中， ${r_j}_{\max}$ 是否满足 ${r_j}_{\max} \geq u_i+d_i-1$ 即可。同样地，暴力做是 $O(nm)$ ，我使用的是大根堆优化，时间复杂度是 $O((m+q) \log m)$ 的复杂度。

能想到，如果这两种讨论中，满足任意一种，就是 Yes。这样就做完了。

时间复杂度： $O((m+q) \log n+(m+q) \log m)$ .

空间复杂度： $O(n+m+q)$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5e5+55;
struct node{
    ll l,r,d,id;
};
ll n,m,q,l,r;
ll bitr[MAXN];
bool vis[MAXN];
node a[MAXN],b[MAXN];
priority_queue<ll> pq;
inline ll lowbit(const ll &x){return x&-x;}
inline void update(const ll &q,const ll &c){
    for(ll i=q;i<=n;i+=lowbit(i)) bitr[i]+=c;
    return;
}
inline ll query(const ll &q){
    ll res=0;
    for(ll i=q;i;i-=lowbit(i)) res+=bitr[i];
    return res;
}
int main(){
    cin>>n>>m>>q;
    for(ll i=1;i<=m;i++) cin>>a[i].l>>a[i].r;
    for(ll i=1;i<=q;i++){
        cin>>b[i].l>>b[i].r>>b[i].d;
        b[i].id=i;
    }
    //网友上线比Alice晚
    sort(a+1,a+1+m,[](const node &a,const node &b){
        return a.r-a.l>b.r-b.l;
    });
    sort(b+1,b+1+q,[](const node &a,const node &b){
        return a.d>b.d;
    });
    l=r=1;
    while(r<=q){
        while(l<=m){
            if(a[l].r-a[l].l+1<b[r].d) break;
            update(a[l].l,1);
            l++;
        }
        if(query(b[r].r-b[r].d+1)-query(b[r].l-1)) vis[b[r].id]=true;
        r++;
    }
    //网友上线比Alice早
    sort(a+1,a+1+m,[](const node &a,const node &b){
        return a.l<b.l;
    });
    sort(b+1,b+1+q,[](const node &a,const node &b){
        return a.l<b.l;
    });
    l=r=1;
    while(r<=q){
        while(l<=m&&a[l].l<b[r].l) pq.push(a[l++].r);
        if(!pq.empty()&&pq.top()>=b[r].l+b[r].d-1) vis[b[r].id]=true;
        r++;
    }
    for(ll i=1;i<=q;i++){
        if(vis[i]) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

T6-BFS

题目是一棵树，还求方案数量，还求任意根的方案数量，这是明显的换根 DP 啊！

过程就是一般的换根 DP 的过程。定义 $dp_u$ 为对于树根节点为 $u$ 的时候，子树大小的乘积。状态转移也不是很难得到，如下：

$dp_v=\cfrac{dp_u \times (n-size_v)}{size_v} \bmod 998244353$

容易发现需要逆元处理。注意到 $998244353$ 是质数，且 $size_v$ 不可能是其倍数，所以直接运用费马小定理即可。用快速幂实现。

定义 $ans_i$ 为根节点为 $i$ 的随机 BFS 序数量。发现其刚好为有根树的拓扑序数量。得到结论： $ans_i=\cfrac{n!}{dp_i} \bmod 998244353$ .

预处理 $n!$ ，并使用快速幂计算逆元。

时间复杂度： $O(n \log 998244353)$ .

空间复杂度： $O(n)$ .

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e6+16,MOD=998244353;
struct node{
    ll nxt,to;
};
ll n,u,v,tot;
ll hd[MAXN],siz[MAXN],dp[MAXN],fac[MAXN],ans[MAXN];
node edge[MAXN<<1];
inline void add(const ll &u,const ll &v){
	edge[++tot]={hd[u],v};
	hd[u]=tot;
	return;
}
inline ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
inline void dfs1(const ll &u,const ll &fath){
    ll v;
	siz[u]=1;
	for(ll i=hd[u];i;i=edge[i].nxt){
		v=edge[i].to;
		if(v^fath){
            dfs1(v,u);
            siz[u]+=siz[v];
        }
	}
	return;
}
inline void dfs2(const ll &u,const ll &fath){
    ll v;
	for(ll i=hd[u];i;i=edge[i].nxt){
		v=edge[i].to;
		if(v==fath) continue;
		dp[v]=dp[u]*(n-siz[v])%MOD*qpow(siz[v],MOD-2)%MOD;
		dfs2(v,u);
	}
	return;
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<n;i++){
		scanf("%lld %lld",&u,&v);
		add(u,v);
        add(v,u);
	}
	dfs1(1,0);
	fac[0]=1;
	for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	dp[1]=1;
	for(ll i=1;i<=n;i++) dp[1]=dp[1]*siz[i]%MOD;
	dfs2(1,0);
	for(ll i=1;i<=n;i++) ans[i]=fac[n]*qpow(dp[i],MOD-2)%MOD;
	for(ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 8

arrowpoint
%%%

2025-06-23 来自广东
1
- 亚洲卷王 AK IOI
  回复arrowpoint
  nmnmn
  
  2025-06-24 来自北京
  0
复仇者_帅童
T5真的啥都能用啊……我的解法是栈+区间加区间查的线段树

2025-06-29 来自广东
0
AAA水泥批發白哥
%%%

2025-06-24 来自北京
0
- 亚洲卷王 AK IOI
  回复AAA水泥批發白哥
  nmnmn
  
  2025-06-25 来自北京
  0
说的道理
%%% Orz tql

2025-06-23 来自北京
0
AAA混泥土批发ppl哥
%%%

2025-06-23 来自浙江
0
AAA混泥土批发ppl哥
你不配当主播，我要取关你！（雾

2025-06-23 来自浙江
0
- AAA混泥土批发ppl哥
  回复AAA混泥土批发ppl哥
  ~~竟然不在昨天晚上早点发出来~~
  
  2025-06-23 来自浙江
  0
AAA水泥批發白哥
%%%

2025-06-23 来自北京
0
- AAA水泥批發白哥
  回复AAA水泥批發白哥
  充分发扬人类智慧（T3）
  
  2025-06-23 来自北京
  0
复仇者_帅童
膜膜膜哦日子

2025-06-23 来自广东
0
- 亚洲卷王 AK IOI
  回复复仇者_帅童
  n%%%orznmn
  
  2025-06-23 来自北京
  0

T1-未出现的人

T2-gcd

T3-a + b

T4-礼物

T5-聊天室

T6-BFS

全部评论 8

热门讨论