当前位置：首页 > news >正文

2026寒假牛客2.5

news 2026/5/12 17:54:54

考试的时候体感上感觉有点难.......敲完后其实感觉还行

有点cf分格的一场，难度分界特别明显

赛时ac 7

A签到

B:需要注意的是，如果最大值是奇数个，那么只有最大值能够获胜，如果最大值有偶数个，那最大值必不可能获胜，但最大值可以通过和其他任意值相抵消的情况消掉任意值，最后再自己相互抵消，从而实现比最大值小的数都可以获胜

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
const int N=2e4+10,mod=998244353,M=1e6+10;
int lowbit(int x){
return x&(-x);}
void solve(){
int n;
cin>>n;
vector<int>a(n+1),b(n+1);
int num=-inf;
//vector<bool>st(n+1,0);
//unordered_map<int,int>mp;
fr(i,1,n){
cin>>a[i];
//mp[a[i]]++;
}
b=a;
sort(a.begin()+1,a.end(),greater<int>());
int maxx=a[1];
int maxo=-1;
fr(i,1,n){
int j=i;
while(j<n&&a[j]==a[i]){
j++;
}
int cnt=j-i;
if(cnt&1){
maxo=a[i];
break;
}
i=j;
}
fr(i,1,n){
if(maxo==-1)cout<<0;
else{
if(b[i]==maxo){
cout<<1;
}
else if(b[i]>maxo&&b[i]<maxx){
cout<<1;
}
else cout<<0;
}
}
cout<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}

C/D UNKNOWN

我们令初始矩阵为

111110

111100

111000

110000

100000

000000

该矩阵满足条件1，2

接下来考虑如何满足条件3
在不破坏原有行列构造数字集合的前提下拆分连通块，考虑偶数行的 1 变
成列，从右边依次往左放置即可

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
const int N=2e4+10,mod=998244353,M=1e6+10;
int lowbit(int x){
return x&(-x);}
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
int l=1;
int r=n;
fr(i,1,n){
if(i&1){
a[i]=l++;
}
else{
a[i]=r--;
}
}
vector<vector<int>>ans(n+1,vector<int>(n+1));
fr(i,1,n){
fr(j,1,n){
if(a[i]<a[j])ans[i][j]=1;
else ans[i][j]=0;
}
}
fr(i,1,n){
fr(j,1,n){
cout<<ans[i][j];
}
cout<<"\n";
}
}
signed main(){
GG;
int _t=1;
//cin>>_t;
while(_t--){
solve();
}

}

n=gcd(x,y)<=|x-y|<=x^y====>x^y min =n

题目给了n的范围2^31,x的范围2^63,所以我们可以之间把x左移，直到x1与x没有重合，在令y=x1+x,x=x1,这样x^y=n;

G UNKNOWN

先翻译一下代码，求s的所有前缀中不同字符个数的累加

一般这种题的套路都是，考虑每一个字符对最终答案的贡献

对于s=......a(1)......a(2)......

我们考虑a2的贡献，很显然，只有当起点为a1+1--a2时，a2才有贡献

我们记a2的上一次出现为pre,很显然，有贡献的起点个数为i-prei

接下来考虑终点，很显然终点是a2-n(n-i+1)

也就是a2的贡献长度是1-n-i+1,显然贡献=贡献长度，所以每一个起点的贡献就是1-n-i+1的累加

ans=(sum)(i-prei)*(i-n+1)*(i-n+2)/2

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
const int N=2e4+10,mod=998244353,M=1e6+10;
int lowbit(int x){
return x&(-x);}
void solve(){
int n;
cin>>n;
vector<int>a(n+1,0);
//vector<int>np(N,0);
unordered_map<int,int>np;
vector<int>pre(n+1,0);
fr(i,1,n){
cin>>a[i];
if(!np.count(a[i])){
np[a[i]]=i;
}
else{
pre[i]=np[a[i]];
np[a[i]]=i;
}
}
int ans=0;
fr(i,1,n){
ans+=((i-pre[i])*((n-i+1)*(n-i+2))/2);
}
cans;
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}

卡B,想着先看I，看到这么个玩意.....

当时的感觉是我以急哭。。。

脑子超级混乱，最后想着直接爆搜写，考完一想好像确实是check题

对于一个0/1字符，如果矩阵里面有相同字符，则一定可以

1出发，遇到1一定能够形成回文串，100000.....1

0同理

然后就解决了.......

这个反而是写下来感觉最简单的题之一？

低维求的是到任意高维的最短路，那我们可以直接从高维往低维写，每降一维判断当前节点的dist是不是被跟新过，没有出-1，有出答案，然后把这一层的点压进去做多源最短路就行，因为是逐层更新，所以保证当前答案一定最优

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
const int N=2e4+10,mod=998244353,M=1e6+10;
int lowbit(int x){
return x&(-x);}
void solve(){
int n,m;
cin>>n>>m;
vector<vector<int>>g(n+1);
vector<int>d(n+1,0);
vector<vector<int>>dj(n+1);
vector<int>ans(n+1,-1);
fr(i,1,m){
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
d[v]++;
d[u]++;
}
/*
fr(i,1,n){
cout<<d[i]<<" ";
}
*/
fr(i,1,n){
dj[d[i]].pb(i);
}
vector<int>dist(n+1,inf);
for(int i=n;i>=1;i--){
if(dj[i].empty())continue;
for(int x:dj[i]){
if(dist[x]==inf)ans[x]=-1;
else ans[x]=dist[x];
}
queue<int>q;
for(int x:dj[i]){
dist[x]=0;
q.push(x);
}
while(!q.empty()){
int tot=q.front();
q.pop();
for(int x:g[tot]){
if(dist[x]>dist[tot]+1){
dist[x]=dist[tot]+1;
q.push(x);
}
}
}
}
fr(i,1,n){
cout<<ans[i]<<" ";
}

}
signed main(){
GG;
int _t=1;
//cin>>_t;
while(_t--){
solve();
}

}