2024牛客寒假算法基础集训营6 题解 ( A,B,C,D,E,I)
A 宇宙的终结
题意
找到\([l,r]\)区间中有多少数恰好等于三个不同素数的乘积
思路
数据范围很小,可以考虑暴力,遍历 \([l,r]\)区间内每个数,拿每个小于当前数的素数一直往下除,判断是否存在能被恰好 3 个素数整除的情况
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 宇宙的终结
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67746/A
| When: 2024-02-23 13:00:12
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
/*******************************
| Author: AlwaysBeShine
| Problem: B3716 分解质因子 3
| Contest: Luogu
| URL: https://www.luogu.com.cn/problem/B3716
| When: 2024-02-11 15:50:18
|
| Memory: 600 MB
| Time: 2500 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<bool> isNotPrime(100000010);
vector<int> prime;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
prime.push_back(2);
for(int i = 2;i <= 1000;i++){
if(isNotPrime[i] == false){
prime.push_back(i);
}
for(int j = 1;prime[j] * i <= 1000;j++){
int temp = prime[j] * i;
isNotPrime[temp] = true;
if(i % prime[j] == 0)break;
}
}
int l,r;
cin >> l >> r;
set<int>s;
for(int i = l;i <= r;i++){
int temp = i,cnt = 0, n = i;
for(int j = 1;prime[j] <= n;j++){
if(temp % prime[j] == 0){
cnt++;
temp /= prime[j];
}
if(cnt == 3 && temp == 1){
cout << i;
return 0;
}
}
}
cout << -1;
return 0;
}
B 爱恨的纠葛
题意
定义两个长度相等的数组的亲密度为:对于\(i∈[1,n],|a_i-b_i|\)的最小值。
例如,[1,2,3]和[3,3,1]的亲密度为 \(min(|1-3|,|2-3|,|3-1|)=1。\)
现在给定了两个长度为\(n\)的数组\(a\)和\(b\),
可以随意打乱\(a\)数组的元素顺序。希望最终两个数组的亲密度尽可能小。请你给出任意一个操作方案。
思路
在两个数组之间,分别取一个,使两个数的绝对值相差最小。
记录第二个数组中取的那个数的下标 \(x\),和第一个数组取的值 \(v\)。
输出第一个数组的时候,第 \(x\) 个输出 \(v\) ,其他元素的顺序随便。
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 爱恨的纠葛
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67746/B
| When: 2024-02-23 13:43:46
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
set<pair<int, int>>s;
std::vector<int> av;
vector<int>bv;
for(int i = 0;i < n;i++){
int temp;
cin >> temp;
av.push_back(temp);
s.insert({temp,1});
}
for(int i = 0;i < n;i++){
int temp;
cin >> temp;
bv.push_back(temp);
s.insert({temp,2});
}
int a = -1,b = -1;
pair<int,int>ans1,ans2;
int mini = 2000000000;
for(auto &[x,y]:s){
if(y == 1)a = x;
else b = x;
if(abs(a-b) < mini){
mini = abs(a-b);
ans1 = {a,1};
ans2 = {b,2};
}
//mini = min(mini,abs(a-b));
}
int pos1 = find(bv.begin(),bv.end(),ans2.first) - bv.begin(); //b中对应的位置
int pos2 = find(av.begin(),av.end(),ans1.first) - av.begin(); //a对应的位置
//cout << pos1 << " " << pos2;
for(int i = 0;i < n;i++){
if(i == pos1 && av[i] != av[pos2]){
swap(av[i],av[pos2]);
break;
}
}
for(auto &tx:av){
cout << tx << " ";
}
return 0;
}
C 心绪的解剖
题意
将一个正整数\(n\),分解为三个斐波那契数之和
思路
性质:任何正整数都可以拆分成 一个或若干个斐波那契数之和,且拆分方式一定
则只要判断是否答案恰好为 \(3\) 即可
每次拿 满足 \(x \le n\) 的最大的斐波那契数 \(x\),使 \(n\) 自减 \(x\) 即可,最后统计一共找到了多少个 \(x\)
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 心绪的解剖
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67746/C
| When: 2024-02-23 14:28:18
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> fib;
std::vector<ll> generateFibonacci(ll n) {
std::vector<ll> fibonacci;
if (n <= 0)
return fibonacci;
fibonacci.push_back(0);
if (n == 1)
return fibonacci;
fibonacci.push_back(1);
if (n == 2)
return fibonacci;
for (int i = 2; i < n; ++i) {
ll nextFib = fibonacci[i - 1] + fibonacci[i - 2];
fibonacci.push_back(nextFib);
}
return fibonacci;
}
void solve(){
vector<ll>ans;
ll n,cnt = 0;
cin >> n;
for(int i = 0;i < 3;i++){
if(upper_bound(fib.begin(),fib.end(),n) != fib.end() - 1){
ll res = *(upper_bound(fib.begin(),fib.end(),n) - 1);
cnt++;
n -= res;
//cout << res << " \n"[i == 2];
ans.push_back(res);
}
// ll res = ;
// n -=
}
if(ans.size() != 3 || (ans.size() == 3 && n != 0)){
cout << -1 << "\n";
}else{
cout << ans[0] << " " << ans[1] << " " << ans[2] << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fib = generateFibonacci(50);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
D 友谊的套路
题意
一场 BO5 的对战,已知小红队每一局获胜的概率为\(p\),请问最终这场对战出现让二追三的概率是多少?
思路
让二追三有两个情况,一个情况是 小红自己让二追三,第二个情况是 小红被让二追三,用 01分布 的期望即可
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 友谊的套路
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67746/D
| When: 2024-02-23 13:26:28
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
double p;
cin >> p;
cout << fixed<<setprecision(6) << pow(1-p,3) * pow(p,2) + pow(p,3) * pow(1-p,2);
return 0;
}
E 未来的预言
题意
在淘汰制游戏中,有一个比较常用的机制:BO 机制。一般 BO 后面接一个奇数\(x\),代表比赛的总局数,两个队伍谁的胜局先超过\(x\)的一半,谁就获胜了。例如,"BO3"代表三局两胜,"BO5"代表五局三胜,以此类推。 现在给定游戏规则为 BOx,以及红队和紫队两个队伍接下来若干局的的胜负情况(不一定比完,因为有可能没比完就结束了)。现在请你判断比赛得出胜负的时候,一共进行了多少局。
思路
模拟即可,判断谁的胜场数先大于等于 \(\frac{x}{2}\),如果读入 \(n\) 次后,还没有分出胜负就输出 "to be continued."。
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 未来的预言
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67746/E
| When: 2024-02-23 13:32:18
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
char c;
cin >> c;
cin >> c;
int n,cnt = 0;
cin >> n;
int a = 0,b = 0;
string s;
cin >> s;
for(int i = 0;i < s.size();i++){
if(s[i] == 'R')a++;
else b++;
if(a > n / 2){
cout << "kou!\n" << i+1;
break;
}else if(b > n / 2){
cout << "yukari!\n" << i+1;
break;
}else if(i == s.size()-1){
cout << "to be continued.\n" << i+1;
}
}
// cin >> c;
// }
return 0;
}
I 时空的交织
题意
小红拿到了一个 \(n\) 行 \(m\) 列的矩阵,矩阵中每个元素的权值由 \(a\) 数组和 \(b\) 数组决定。第 \(i\) 行第 \(j\) 列的元素为 \(a_i*b_j\)。 小红希望选择一个子矩形,使得该子矩形所有元素的和尽可能大。你能帮帮她吗?
思路
对 \(a\) 数组和 \(b\) 数组分别求两组 最大区间和以及最小区间和,然后 \(a\) 数组的最大/小区间和 分别乘 \(b\) 数组的最大/小区间和 输出这四个值中最大的一个
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 时空的交织
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67746/I
| When: 2024-02-27 21:08:32
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
vector<ll>a(n+5,0),b(m+5,0);
for(int i = 1;i <= n;i++)cin >> a[i];
for(int i = 1;i <= m;i++)cin >> b[i];
ll ans1 = -20000,ans2 = -20000,ans3 = 20000,ans4 = 20000,t1 = a[1],t2 = b[1],t3 = a[1],t4 = b[1];
for(int i = 2;i <= n;i++){
t1 = max(t1 + a[i],a[i]);
t3 = min(t3 + a[i],a[i]);
ans1 = max(t1,ans1);
ans3 = min(t3,ans3);
}
for(int i = 2;i <= m;i++){
t2 = max(t2 + b[i],b[i]);
t4 = min(t4 + b[i],b[i]);
ans2 = max(t2,ans2);
ans4 = min(t4,ans4);
}
cout << max(ans1 * ans2,max(ans1*ans4,max(ans2*ans3,ans3*ans4)));
return 0;
}
标签:cout,int,题解,ll,cin,long,2024,集训营
From: https://www.cnblogs.com/AlwaysBeShine/p/18041065