题解(自记录) | 牛客寒假集训营20250123第二场比赛

A.一起奏响历史之音！

题目:https://ac.nowcoder.com/acm/contest/95334/A

#include<bits/stdc++.h>

using namespace std;

int main(){

int a[5]={1,2,3,5,6};

int x;string l="YES";

for(int i=0;i<7;i++){

cin >> x;

if(find(a,a+5,x)==a+5){

l="NO";

}

}

cout << l;

}

题解思路:相当于判断输入数组中有没有除去1,2,3,5,6以外的其他元素,构建一个数组并查找输入过程中是否存在以外的数即可

B.能去你家蹭口饭吃吗

题目:https://ac.nowcoder.com/acm/contest/95334/B

#include<bits/stdc++.h>

using namespace std;

bool cmp(int x,int y){

return x>y;

}

int main(){

int n,ans;

cin >> n;

vector<int>a(n);

for(int i=0;i<n;i++){

cin >> a[i];

}

sort(a.begin(),a.end(),cmp);

if(n%2==0){

ans=a[n/2-1]-1;

}

else{

ans=a[n/2]-1;

}

cout << ans;

}

题解思路:依题意可知为求其中位数,排序后输出中间位即可。

C.字符串外串

题目:https://ac.nowcoder.com/acm/contest/95334/C

D.字符串里串

题目:https://ac.nowcoder.com/acm/contest/95334/D

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

string s;int n,ans=0;

cin >> n >> s;

s=" "+s;

set<int>a;

for(int i=n;i>=2;i++){

if(a.count(s[i]))ans=max(ans,i);

a.insert(s[i]);

}

a=set<int>();

for(int i=1;i<=n-1;i++){

if(a.count(s[i]))ans=max(ans,n-i-1);

a.insert(s[i]);

}

cout << ans << endl;

}

题解思路:需要连续数组a和不连续数组b相同,那么可以记录每个数字出现的频率,如果出现过则记录当前重复数字的下标,从前往后和从后往前各一次找出哪个最长

E.一起走很长的路！

题目:https://ac.nowcoder.com/acm/contest/95334/E

F.一起找神秘的数！

题目:https://ac.nowcoder.com/acm/contest/95334/F

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

int T;

cin >> T;

while(T--){

ll x,y;

cin >> x >> y;

cout << y-x+1 <<endl;

}

}

题解思路:(x&y)+(x|y)等同于x+y,那么当(x^y)==0时仅有x==y所以等同于区间之和

G.一起铸最好的剑！

题目:https://ac.nowcoder.com/acm/contest/95334/G

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main(){

ll T,n,m,res1,res2;

cin >> T;

while (T--) {

ll ans=1;

cin >> n >> m;

ll d=m;

res1=n-d;

d=d*m;

res2=n-d;

while(abs(res1)>abs(res2)){

ans++;res1=res2;

d=d*m;res2=n-d;

}

cout << ans <<endl;

}

}

题解思路:起始温度为m,添柴次数为1,每次添柴后乘上m,计算每次添柴后与目标温度的距离若小于添柴前,则输出当前添柴次数。

H.一起画很大的圆！

题目:https://ac.nowcoder.com/acm/contest/95334/H

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

int T;

cin>>T;

while(T--){

ll a,b,c,d;

cin >> a >> b >> c >> d;

if(b-a>d-c){

cout << a <<" " << d-1 << endl;

cout << b <<" " << d << endl;

cout <<b-1 << " "<< d <<endl;

}

else{

cout << b-1 <<" "<< d<<endl;

cout << b <<" "<<c<<endl;

cout << b <<" "<< c+1<< endl;

}

}

}

题解思路:首先输出为整数类型,那就不必考虑浮点数,随机在矩形上取三个点,取两个在长边上的点和一个短边上的点,由正弦定理和外切圆的定义可得长边上的两个点越接近,短边上的点越接近长边,且与另外两个点越远时外切圆最大

I.一起看很美的日落！

题目:https://ac.nowcoder.com/acm/contest/95334/I

J.数据时间？

题目:https://ac.nowcoder.com/acm/contest/95334/J

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

int n,h,m;

cin >> n >> h >>m;

set<string>A,B,C;

while(n--){

string id;int ye,mon,day,hou,min,s,num;

cin >>id;

scanf("%d-%d-%d %d:%d:%d",&ye,&mon,&day,&hou,&min,&s);

if(ye!=h||m!=mon)continue;

num=hou*3600+min*60+s;

if((25200<=num&&num<=32400)||(64800<=num&&num<=72000)){

A.insert(id);

}

else if(39600<=num&&num<=46800){

B.insert(id);

}

else if((79200<=num&&num<=86400)||(0<=num&&num<=3600)){

C.insert(id);

}

}

cout << A.size() <<" " << B.size() <<" "<<C.size()<<endl;

}

题解思路:按照题目同一个人的相同时间段仅算一次,开一个set容器,将输入进来的数据先判断年份和月份是否正确,在将时间全转换为秒进行分类。

K.可以分开吗？

题目:https://ac.nowcoder.com/acm/contest/95334/K

#include<bits/stdc++.h>

#define ll long long

using namespace std;

vector<vector<int>>vis;

vector<pair<int,int>>p={{-1,0},{1,0},{0,1},{0,-1}};

vector<string>a;

set<pair<int,int>>st;

int n,m;

int main() {

cin >> n >> m;

a=vector(n+2,string(m+2,'0'));

for(int i=0;i<n;i++){

cin >> a[i];

// a[i]='0'+a[i]+'0';

}

vis=vector(n+2,vector<int>(m+2));

int ans=1e9;

void dfs(int x,int y);

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(vis[i][j])continue;

if(a[i][j]=='0')continue;

st.clear();

dfs(i,j);

ans=min(ans,(int)st.size());

}

}

cout << ans <<endl;

}

void dfs(int x,int y){

int xx,yy;

vis[x][y]=1;

for(auto&[dx,dy]:p){

xx=dx+x;

yy=dy+y;

if(xx<0||xx>n-1||yy<0||yy>m-1)continue;

if(vis[xx][yy])continue;

if(a[xx][yy]=='0')st.insert({xx,yy});

else dfs(xx,yy);

}

}

题解思路:题目要求分离出一个蓝色极大联通块,那么先找出蓝色区块的位置,找出后通过dfs探测周边需要敲碎的灰色区块,并找出最小需要敲碎的数量

L.还会再见吗？

题目:https://ac.nowcoder.com/acm/contest/95334/L

M.那是我们的影子

题目:https://ac.nowcoder.com/acm/contest/95334/M