巅峰赛#21 全题解！【7k+字数】
2025-05-25 22:46:59
发布于：广东
T1：模拟题
由数学知识得，凸 边形有如下特征：
-
内角和等于 。
-
任一内角小于 。
直接判断即可。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;
int n,m,a[N];
signed main(){
ios::sync_with_stdio(false);
cin>>n;
int sum = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>=180){
cout<<"No";
return 0;
}
sum += a[i];
}
if(sum==(n-2)*180){
cout<<"Yes";
}
else{
cout<<"No";
}
return 0;
}
T2：Nim游戏模板题
由Nim游戏结论，一个状态是必败状态当且仅当 ，其中 表示异或。
因此首先判断：
-
如果上述异或和为 ，则当前为必败状态，怎么走都赢不了，答案 。
-
否则，设上述异或和为 。枚举 ，判断能否通过减少 使得操作后异或和为 ，即将 换成 后， 与剩下的数异或和为 。由异或性质得充要条件为 。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6+10;
int n,m,a[N];
int tmp;
signed main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
tmp ^= a[i];
}
if(tmp==0){
cout<<0;
return 0;
}
int ans = 0;
for(int i=1;i<=n;i++){
if((a[i]^tmp)<a[i]){
ans++;
}
}
cout<<ans;
return 0;
}
T3：思维题
由于原问题是在一棵树上，由树的性质，每一个限制对应的边必然是一个割边（即去掉它后剩下两部分（或称为两个半区）不连通）。考虑若设定 这条边中 是父节点，那么相当于根节点只能在 所在半区。
因此我们考虑这样的策略：对每一个限制，把限制边割掉，给子节点所在半区打上“不可能存在根节点”的标记，最后在没被打上标记的连通区域（显然只可能有一个）统计它的数量。
实现方式很多，可以直接模拟，当然我比赛时使用的是并查集。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6+10;
int n,m,a[N];
int fa[N],flag[N],siz[N];
int rec[N];
int q;
struct node{
int u,v;
}no[N],qu[N];
inline bool cmp(node x,node y){
if(x.u==y.u) return x.v<y.v;
return x.u<y.u;
}
inline int find(int x){
if(fa[x]==x) return x;
return fa[x] = find(fa[x]);
}
inline int bound(int x,int y){
int l = 1,r = n-1;
while(l<=r){
int mid = (l+r)>>1;
if(no[mid].u<x) l = mid+1;
else if(no[mid].u==x){
if(no[mid].v<y) l = mid+1;
else if(no[mid].v==y) return mid;
else r = mid-1;
}
else{
r = mid-1;
}
}
return -1;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++){
fa[i] = i;
siz[i] = 1;
}
int q1,q2;
for(int i=1;i<n;i++){
cin>>q1>>q2;
no[i] = {q1,q2};
}
sort(no+1,no+n,cmp);
for(int i=1;i<=q;i++){
cin>>q1>>q2;
qu[i] = {q1,q2};
int pos = bound(q1,q2);
if(pos>=0){
rec[pos] = 1;
}
else{
pos = bound(q2,q1);
rec[pos] = 2;
}
}
for(int i=1;i<n;i++){
int fx = find(no[i].u),fy = find(no[i].v);
if(rec[i]==1){
flag[fy] = 1;
}
else if(rec[i]==2){
flag[fx] = 1;
}
else{
flag[fy] = max(flag[fy],flag[fx]);
fa[fx] = fy;
siz[fy] += siz[fx];
}
}
for(int i=1;i<=n;i++){
if(fa[i]==i && !flag[i]){
cout<<siz[i];
return 0;
}
}
return 0;
}
T4：组合题
首先将所有选手按实力从小到大排序，接着考虑对于排名为 的选手（由于从小到大，最弱的排名为 ），倘若他进入第 轮，简单推导得到他必定是这个位置对应的 个人中最强的，因此我们必须要安排 （减去那个人自己）名实力比他弱的选手填充掉这个位置，剩下的对他没有影响。
因此，这个排名为 人最高能进入的轮数 是满足 的最大的 ，设 ，则有这个位置的答案为 。
表示的是：在第 轮对应的 个不同的区域内随便选一个，在可以被选的 个人中选出需要的 个进行全排列，其中这一区域的 人需要全排，剩下与之无关的 个人也要全排。
套公式即可。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e6+10;
int n,m,a[N];
int inv[N],jc[N];
const int M = 998244353;
struct node{
int id,v;
}no[N],ans[N];
inline bool cmp(node x,node y){
return x.v<y.v;
}
inline int C(int x,int y){
if(x==0) return 1;
return jc[x]*inv[y]%M*inv[x-y]%M;
}
signed main(){
ios::sync_with_stdio(false);
inv[0] = 1;
inv[1] = 1;
jc[0] = 1;
for(int i=1;i<=2e6;i++){
jc[i] = jc[i-1]*i%M;
}
for(int i=2;i<=2e6;i++){
inv[i] = (M-M/i)*inv[M%i]%M;
}
for(int i=2;i<=2e6;i++){
inv[i] = inv[i-1]*inv[i]%M;
}
cin>>n;
n = pow(2,n);
for(int i=1;i<=n;i++){
no[i].id = i;
cin>>no[i].v;
//no[i].v = i;
}
sort(no+1,no+n+1,cmp);
int now = 1,nid = 1;
for(int i=1;i<=n;i++){
if(i==now*2){
now *= 2;
nid++;
}
ans[no[i].id] = {nid,C(i-1,now-1)*jc[now]%M*jc[n-now]%M*(n/now)%M};
}
for(int i=1;i<=n;i++){
cout<<ans[i].id<<' '<<ans[i].v<<endl;
}
return 0;
}
T5：思维题。
首先注意到随着 的增加，答案必定单调不增。这启示我们预处理出每一个 对应的 的最大值，其中双指针维护当前的最大答案。
我们考虑 时，答案必定是其中的最大值。当 更大时，答案只可能比它更小，而可能的答案只有 个。因此我们可以尝试能否 判断第 大的数能否作为长度为 的连续序列的最小值。
因此我们先钦定某一个数为连续序列的最小值，那么我们一定不能取比它更小的值，因此我们可以维护这个数左边和右边第一个比它小的值的位置（分别设为 ），那么只要左端点大于 ，右端点小于 ，就一定可以以这个点作为最小值。极限情况下，我们分别取它们的相邻位置，就可以得到长度为 的以这个数为最小值的连续区间。
上述维护的值可以用单调栈实现。这样我们只需要判断 是否大于等于当前的 即可判断这个答案成不成立。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6+10;
int n,m,a[N];
int s[N],top;
int l[N],r[N];
int ans[N];
int q;
struct node{
int id,v;
}no[N];
inline bool cmp(node x,node y){
return x.v>y.v;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
no[i] = {i,a[i]};
}
sort(no+1,no+n+1,cmp);
for(int i=1;i<=n;i++){
while(top && a[s[top]]>=a[i]) top--;
l[i] = s[top]+1;
s[++top] = i;
}
top = 0;
for(int i=n;i>=1;i--){
while(top && a[s[top]]>=a[i]) top--;
if(!top) r[i] = n;
else r[i] = s[top]-1;
s[++top] = i;
}
int now = 1;
ans[1] = no[1].v;
for(int i=2;i<=n;i++){
while(now<=n && r[no[now].id]-l[no[now].id]+1<i){
now++;
}
ans[i] = no[now].v;
}
int q1,q2;
for(int i=1;i<=q;i++){
cin>>q1>>q2;
if(ans[q1]>=q2){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
return 0;
}
T6：博弈论
首先看题，很明显这个游戏符合公平博弈游戏的经典特点（双方都知道全部信息，双方进行的操作相同，具有明确的终止状态）。这种游戏的特点是：每一个状态都必定是必胜态和必败态的其中之一。其中必胜态指的是游戏进行到这个状态时先手有必胜策略，必败态指的是这个时候先手无论怎么操作都必败（双方智商足够高的情况下）。且必胜态必定有一个策略能在下一步转移至必胜态，必胜态也必定有一个策略能在下一步转移至必败态（不懂的可以学一下博弈论）。
回到这个题，首先我们注意到一个性质：若在某个状态下，存在一个节点连有两个以上的叶子节点，那么这个状态必定是必胜态。这是很显然的。比如我们规定其中一个叶子节点是S，那么我可以选择只删除S这个节点，那么如果之后的状态是必胜态，那我就必胜了。否则如果是必败态，我们发现在剩下这个树能进行的操作和我现在保留S这个叶子结点能进行的操作完全相同，根据我上面提到的性质，必定存在一种同时删除S和剩下一些叶子节点的策略，使得下一步还是必胜态。也就是说，我们可以先判断初始状态是否有一个点连有2个以上叶子结点，如果有，那么直接判Alice赢。
那如果没有呢？这样我们可以把问题转化为：找到一种策略使得在我先手时可以使某个点连有两个以上叶子结点。这和原问题是等价的，因为至少有一个人可以实现这一目标，而能实现这个目标的必定赢。于是容易想到维护初始时每个节点至第一个连有两个以上子节点且是这个节点祖先的节点的最短距离（也就是从这个地方一直删除到满足要求最少需要多少步），第 个设为 。考虑若有叶子节点的 是 ，就等价于满足了这个需求，即必胜。否则，若所有叶子节点的 都是 ，那么他无论怎样操作下一步都必定出现一个 的点，即必败。此时若又存在若干个 ，那么他需要把必败留给对方，就可以把所有 的都删掉，即必胜。若又又又存在 ，那么他第一步可以把所有 全部删除，只剩下 的。这样另外一个人只能删 的将其变为 ，而此时转回来后又必胜了。我们注意到这些策略都是以先手删除 为奇数的点为基础，这样就不难猜出这样一个策略：
-
若存在叶子结点 为奇数，则将所有 为奇数的叶子节点 ，这样所有叶子节点 都是偶数。
-
否则，由于你必须删除一个叶子结点，故你怎样操作都会使后一步出现 为奇数的叶子结点。而且你还不能删除 的叶子结点，因为这样对面直接就赢了。
因此，这样进行若干次后，必然会剩下一个叶子结点 均为 的情况，此时谁先手谁输，而这种情况必定是由存在 为奇数的对手状态转移而来。这样，我们只需要判断是否存在叶子结点 为奇数，就可以判断谁赢。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5+10;
int n,m,a[N];
int t;
vector<int> vec[N],g[N];
int son[N],f[N];
inline void dfs(int x,int fa){
for(auto v:vec[x]){
if(v==fa) continue;
son[x]++;
dfs(v,x);
}
}
inline void calc(int x,int fa){
f[x] = (son[x]>1)?0:f[fa]+1;
for(auto v:vec[x]){
if(v==fa) continue;
calc(v,x);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--){
cin>>n;
int q1,q2;
bool flag = 0;
for(int i=1;i<n;i++){
cin>>q1>>q2;
vec[q1].push_back(q2);
vec[q2].push_back(q1);
}
if(n==1){
cout<<"Alice\n";continue;
}
dfs(1,0);calc(1,0);
int ans = 0;
for(int i=1;i<=n;i++){
if(!son[i] && f[i]%2){
ans = 1;
break;
}
}
if(ans==1) cout<<"Alice\n";
else cout<<"Bob\n";
for(int i=1;i<=n;i++){
f[i] = son[i] = 0;
vec[i].clear();
}
}
return 0;
}
有帮助，赞一个