2025牛客寒假算法基础集训营1
A
1
2
3
4
5
6
7
8
9
10
| void solve(){
int n;cin>>n;
int ok=1;
while(n--){
int x;cin>>x;
if(x==1) ok=0;
}
if(ok) cout<<999999999999999989<<"\n";
else cout<<-1<<"\n";
}
|
B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void solve(){
int n;cin>>n;
vector<vector<int>>g(n+1);
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int>ans;
for(int i=1;i<=n;i++){
if(g[i].size()==1){
ans.push_back(i);
}
}
if(ans.size()!=2){
cout<<-1<<"\n";
}else{
cout<<ans[0]<<" "<<ans[1]<<"\n";
}
}
|
C
D
1
2
3
4
5
6
7
8
9
10
11
12
| void solve(){
int n;cin>>n;
map<int,int>mp;
int a=-1,b=-1;
for(int i=0;i<n;i++){
int x;cin>>x;
mp[x]++;
if(a==-1) a=x;
else if(b==-1&&x!=a) b=x;
}
cout<<((n%2==0&&mp.size()==2&&mp[a]==mp[b])?"Yes\n":"No\n");
}
|
E
好像挺典的,+1-1最小次数操作使得数组相等,就选中位数
所以选前半段中位数和后半段中位数，为了特判必须要为两个不同的数，在mid的基础上+-1
G
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| void solve(){
int n;cin>>n;
vector<int>a(n),p,need;
int sum=0;
map<int,int>mp;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
mp[a[i]]++;
if(a[i]<=0||a[i]>n){
p.push_back(a[i]);
}else if(a[i]>=1&&a[i]<=n&&mp[a[i]]==2){
mp[a[i]]--;
p.push_back(a[i]);
}
}
for(int i=1;i<=n;i++){
if(mp[i]==0){
need.push_back(i);
}
}
if(sum!=(n+1)*n/2){
cout<<-1<<"\n";
}else{
sort(p.begin(),p.end());
sort(need.begin(),need.end());
int mx=0;
for(int i=0;i<p.size();i++){
mx+=abs(p[i]-need[i]);
}
cout<<(mx+1)/2<<"\n";
}
}
|
H
对于[1,n]的每一个点i,都必须找到某个区间[l,r]，其中l<=i<=r
如果有多个区间满足,贪心思想就是找到一个一定不会使得答案变差的方法
每次遍历到点i时,我们将所有<=i的左端点都入队，选取其中最小的右端点，这样一定不会使得答案变差
因为如果所有待选的r都不同,下一个点一定还有的选；若存在相同r，i<r下一个数还是有解，i==r此时产生空选项,无答案,无论哪一种情况都不会使得答案变差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| void solve(){
int n;cin>>n;
vector<array<int,2>>a(n+1);
vector<vector<array<int,2>>>g(n+1);
for(int i=1;i<=n;i++){
cin>>a[i][0]>>a[i][1];
g[a[i][0]].push_back({a[i][1],i});
}
vector<int>p(n+1,0);
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
for(int i=1;i<=n;i++){
for(auto [x,y]:g[i]){
pq.push({x,y});
}
if(pq.empty()||pq.top()[0]<i){
cout<<-1;
return;
}
p[pq.top()[1]]=i;
pq.pop();
}
for(int i=1;i<=n;i++){
cout<<p[i]<<" ";
}
}
|
J
A和任意数的gcd一定在A的因子中
$a_i{XOR}a_j=gcd(a_i,a_j)$，等价于$a_j=gcd(a_i,a_j)XORa_i$
我们枚举数组a,同时枚举a的所有因子,如果因子XOR$a_i$存在的话,等价于$a_j$存在
为了避免重复,我们要求$a_i>a_j$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void solve(){
int n;cin>>n;
vector<int>a(n);
map<int,int>mp;
for(int i=0;i<n;i++){
cin>>a[i];
mp[a[i]]++;
}
sort(a.begin(),a.end());
int ans=0;
for(int i=0;i<n;i++){
for(int j=1;j*j<=a[i];j++){
int x=j^a[i];
if(a[i]%j) continue;
if(x>a[i]&&gcd(x,a[i])==j) ans+=mp[x];
if(j*j!=a[i]){
x=(a[i]/j)^a[i];
if(x>a[i]&&gcd(x,a[i])==a[i]/j) ans+=mp[x];
}
}
}
cout<<ans;
}
|
M