题解(自记录) | 牛客寒假集训营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,并在最小值往次小值遍历的时候查找最大值是否发生变化,记录下每次往次小值遍历过程中的极差并取其最小。
Momenta公司福利 584人发布