首页 > 编程语言 >2024牛客寒假算法基础集训营6 题解 ( A,B,C,D,E,I)

2024牛客寒假算法基础集训营6 题解 ( A,B,C,D,E,I)

时间:2024-02-28 17:14:42浏览次数:27  
标签:cout int 题解 ll cin long 2024 集训营

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

相关文章

  • 2024-02-28:用go语言,有一个由x轴和y轴组成的坐标系, “y下“和“y上“表示一条无限延伸
    2024-02-28:用go语言,有一个由x轴和y轴组成的坐标系,"y下"和"y上"表示一条无限延伸的道路,"y下"表示这个道路的下限,"y上"表示这个道路的上限,给定一批长方形,每一个长方形有(x1,x2,y1,y2),4个坐标可以表示一个长方形,判断这条道路整体是不是可以走通的。以下为正式题目:图片在计算......
  • 2024-02-29-Linux高级网络编程(1-计算机网络概述)
    1.计算机网络概述1.1计算机发展简史最早的广域网:在通信双方或多方之间,通过电路交换建立电路连接的网络。1.1.1电路交换特点建立链接->使用链接->释放链接物理通路被通信双方独占1.1.2电路交换适用于电话网​计算机数据是突发式出现在数据链路上的,而电路交......
  • 2024.02.22
    1.原始jsp模板查看初始jsp创建模板:File---Setting---Editor---FileandCodeTemplates---Other---Jspfiles---JspFile.jsp,可在⑤处重新定义jsp模板,编写完成后,Apply,OK,下次在新建jsp文件时,即可建立所定义模板的jsp页面。 2.重新定义jsp页面模板    File---Sett......
  • 2024.2.14
    HomeView.vue<template><el-containerstyle="min-height:100vh"><el-asidewidth="sideWidth+'px'"style="background-color:rgb(255,255,255)"><!--width="sideWidth+'px'&......
  • 2024.1.25
    想要使用IDEA去连接mysql等数据库需要先IDEA里先下载驱动,一般当你去配置的IDEA连接数据库这个过程,IDEA会提示你没有安装驱动,并问你需不需要自动下载这里如果你们遇到自动下载的途中,下载到一半进度条卡住了,或者直接下载失败,可以先到maven中导入相应的包,然后再回到上图重新下载驱......
  • 题解 NKOJ2929 【[THUSC2014] 函数求解】
    代码:#include<iostream>#include<queue>#include<cstdio>#include<cmath>usingnamespacestd;typedefstruct{ intnxt; intend; intdis; doublecost;}Edge;constintN=2e3,M=400+7,K=80800+7;constdoubleep......
  • ABC294 EFG 题解
    E-2xNGrid题意给你一个\(2\timesL\)的网格,但是\(L\)很大,所以用以下形式压缩:将同一个颜色的连续段视为一个整体,那么每一行就可以用若干个二元组\((a_i,b_i)\)表示,其中\(a_i\)为颜色,\(b_i\)为连续段的长度。保证长度\(\le10^5\)。输入以上述形式压缩,现在让你求出......
  • P1110 [ZJOI2007] 报表统计 题解
    考察点:STL的熟练运用。记:\(l_i\)表示序列中不超过\(a_i\)的最大数,\(r_i\)表示序列中超过\(a_i\)的最小数。开一个vectorinsert[N]存储\(a_i\)后面插入的所有数字。首先,我们使用一个multisets1来存储相邻元素的差的绝对值,然后再开一个multisets2来存储当前出......
  • CodeChef Chef and Churus 题解
    对给出的\(n\)个区间分块,设块长为\(B\)。每个块内计算每个位置的贡献(被覆盖次数)。具体地,记\(f_{i,j}\)表示第\(i\)个块第\(j\)个数被覆盖了多少次,这个可以用差分轻松维护。预处理复杂度\(O(\frac{n^2}{B})\)。现在考虑修改。记\(ans_i\)表示块\(i\)的贡献,那么对于......
  • ABC303 G 题解
    区间DP。设\(f_{l,r}\)表示只考虑\([l,r]\),先手得分减后手得分的最大值(并不关心谁是先手谁是后手),区间长度\(len=r-l+1\)。然后对三种情况分别讨论:使用操作一,此时取掉左/右端点的部分先手后手互换,对答案的贡献为\(\max(a_l-f_{l+1,r},a_r-f_{l,r-1})\)。使用操作二,继......