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

A.茕茕孑立之影

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

#include<bits/stdc++.h>

using namespace std;

int main(){

int n,t,x;

cin >> n;

while(n--){

cin >> t;

int ans=1e9+7;

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

cin >> x;

if(x==1)ans=-1;

}

cout << ans <<endl;

}

}

题解思路:题目要求为一个数不为该数组任何数倍数，也不允许该数组任何数为该数倍数。当该数组存在1时,必不可能满足即必然输出-1;当数组不存在1时,一个极大的素数必定满足条件,则输出任意一个极大的素数即可。

B.一气贯通之刃

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

#include<bits/stdc++.h>

using namespace std;

int main(){

int n,s1,s2,f=0;

cin >> n;

vector<int>a(n+1);

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

cin >> s1 >> s2;

a[s1]++;a[s2]++;

}

vector<int>b;

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

if(a[i]==1)b.push_back(i);

else if(a[i]>2)f=1;

}

if(f==1)cout << -1;

else cout << b[0] << " " << b[1];

}

题解思路:题目要求寻找一条简单路径通过所有节点,即一条链,则选择获取每个数字出现的频率,如果为一条链则存在首尾两个数出现频率为1,其余数皆为2,如果存在出现频率大于2的数则无法通过所有节点

C.兢兢业业之移

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

D.双生双宿之决

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

#include<bits/stdc++.h>

using namespace std;

int main(){

int n,t;

cin >> t;

while(t--){

cin >> n;

vector <int> a(n);

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

cin >> a[i];}

if(n%2!=0){cout<<"No"<<endl;continue;}

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

int j=1;

while(a[0]==a[j]){

j++;

}

int w=n-2;

while(a[n-1]==a[w]){

w--;

}

w++;

if(j==w&&j==n/2)cout << "Yes"<<endl;

else cout << "No"<<endl;

}

}

题解思路:题目要求数组中仅有两个出现次数相同的数字,那就顺题意分别从前往后和从后往前清点数字出现的次数,然后计算两个数字是否为数组的一半即可。

E. 双生双宿之错

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

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

int T;

cin >> T;

while(T--){

ll n,ans=0,l,r,l1,r1,ans1=0;

cin >> n;

vector<ll>a(n+1);a[0]=-2e9;

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

cin >> a[i];

}

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

int half=n/2;

if(half%2==0){

l=(a[(n/2)/2]+a[(n/2)/2+1])/2;

r=(a[((n/2)+n)/2]+a[((n/2)+n)/2+1])/2;}

else{

l=(a[(half+1)/2]);

r=(a[(half+(half+1)/2)]);

}

if(l!=r){

for(int i=1;i<=n/2;i++)ans+=abs(a[i]-l);

for(int i=n/2+1;i<=n;i++)ans+=abs(a[i]-r);

}

else{

l1=l-1;r1=r;

for(int i=1;i<=n/2;i++)ans1+=abs(a[i]-l1);

for(int i=n/2+1;i<=n;i++)ans1+=abs(a[i]-r1);

r=r1+1;

for(int i=1;i<=n/2;i++)ans+=abs(a[i]-l);

for(int i=n/2+1;i<=n;i++)ans+=abs(a[i]-r);

ans=min(ans,ans1);

}

cout << ans <<endl;

}

}

题解思路:由题意可知通过任意次-1,+1的操作将数组变为双生数组,将数组分为左右数组其最小操作次数则,将所有数变为其中位数。当左右数组中位数相等时,枚举左边为中位数-1和右边为中位数+1,取其最小

F.双生双宿之探

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

G.井然有序之衡

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

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main(){

ll n,sum=0,num=0;

cin >> n;

vector<ll>a(n+1);

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

cin >> a[i];

}

a[0]=-2e9;

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

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

sum+=a[i]-i;

if(i>a[i])num+=i-a[i];

}

if(sum)num=-1;

cout << num << endl;

}

题解思路:题目要求通过+1,-1将数组变为排列,即变为(1-n)的形式,那先将无序数组进行排列,由于最终数列内的值之和不变,所以通过计算数组的和可以知道是否能变为排列,将数组和目标值相减,sum为相差之和,num仅计算+1部分,可算得操作次数

H.井然有序之窗

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

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

int n,num=0;

cin >> n;

deque<array<int,3>>a(n);

set<array<int,3>>st;

for(auto& [l,r,i] : a){

cin >> l >> r;

i=++num;

}

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

vector<ll>ans(n+1);

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

while(a.size() && a[0][0] <= i){

auto[l,r,i]=a[0];

st.insert({r,l,i});

a.pop_front();

}

if(!st.size()){

cout << -1 <<endl;

return 0;

}

auto[r,l,j]=*st.begin();

st.erase(st.begin());

if(r < i){

cout << -1 << endl;

return 0;

}

ans[j]=i;

}

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

cout << ans[i]<<" ";

}

}

题解思路:题目给出数组中每个数字的区间,这段代码先设定一个set和一个双端队列,先对deque<int>a进行l,r从小到大排序,将满足左端点条件的点加入set中,并更换l,r位置使得右端点更小的值更早被使用掉,i作为记录位置的值将ans按位置输出答案;

I.井然有序之桠

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

J.硝基甲苯之袭

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

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

int n;

cin >> n;

vector<ll>a(n+1);map<ll,ll>s;

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

cin >> a[i];

s[a[i]]++;

}

ll num=0;

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

unordered_set<ll>c;

for(int j=1;j*j<=a[i];j++){

if(a[i]%j==0){

int x1=j,x2=a[i]/j;

if(__gcd(x1^a[i],a[i])==x1 && !c.count(x1^a[i])){

num+=s[x1^a[i]];

c.insert(x1^a[i]);

}

if(__gcd(x2^a[i],a[i])==x2 && !c.count(x2^a[i])){

num+=s[x2^a[i]];

c.insert(x2^a[i]);

}

}

}

}

cout << num/2 << endl;

}

题解思路:题目要求数组中两个数满足x^y=gcd(x,y)到底有多少组,根据异或性质,y=gcd(x,y)^x,那么从x的因子中寻找gcd并且推出y,再将值带回上式,若满足则查找数组中有几个满足条件的数字并加入num并输出.

M.数值膨胀之美

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

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

int n;

cin >> n;

pair<int,int>a[100001];

vector<ll>b;

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

cin >> a[i].first,b.push_back(a[i].first);

a[i].second=i;

}

a[n].first=2e9;

sort(a,a+n);

ll ma=max(a[0].first*2,a[n-1].first),l=a[0].second,r=a[0].second;

ll ans=ma-min(a[0].first*2,a[1].first);

b[l]=b[l]*2;

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

while(a[i].second<l){

l--;

ma=max(ma,b[l]*2);

}

while(a[i].second>r){

r++;

ma=max(ma,b[r]*2);

}

ans=min(ans,ma-min(a[i+1].first,a[0].first*2));

}

cout << ans;

}

题解思路:题目要求从数组中取一个非零区间进行全部乘2,那就从最小值开始,一一遍历次小值并将其乘2,并在最小值往次小值遍历的时候查找最大值是否发生变化,记录下每次往次小值遍历过程中的极差并取其最小。