首页 > 编程语言 >2024牛客寒假算法基础集训营5 题解 （ A,C,G,H,I,L,M ）

2024牛客寒假算法基础集训营5 题解 （ A,C,G,H,I,L,M ）

时间：2024-02-27 21:12:41浏览次数：21  
标签：prime cout int 题解 质数 pos long 2024 集训营

2024牛客寒假算法基础集训营5 题解 （ A,C,G,H,I,L,M ）

A mutsumi的质数合数

题意

有一个由 \(n\) 个正整数组成的数组，她想知道数组中质数和合数共有几个。

思路

由质数和合数的定义可知，正整数范围内除 \(1\) 外，要么是质数要么是合数，本题直接统计不是 \(1\) 的正整数的个数即可

代码

#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;
	int cnt = 0;
	for(int i = 0;i < n;i++){

		int a;
		cin >> a;

		if(a != 0 && a != 1)cnt++;

	}

	cout << cnt;
			
	return 0;
}

C anon的私货

题意

在一个正数数组中夹带一些 0，只要数组的除全 0 连续子数组外的每个连续子数组的平均数都大于等于 1，最多可以夹带多少个 0

思路

如果在两数之间插入 \(0\) 的话，插入的位置左右两侧的数都会受影响
所以数组的第一个元素和最后一个元素要重点考虑，在数组前插 \(0\) ，只有第一个元素会受影响，最后一个元素同理。

除此之外，设数组第 \(i\) 个元素为 \(a_i\)，可以把本题看作从第 \(1\) 位开始，每次对第 \(i\) 和 \(i+1\) 位（ $ 1 \le i \lt n$），同时自减 \(min(a_i-1,a_{i+1}-1)\)，然后整个数组一共减去的值就是答案。

特别注意第一位和最后一位是否有剩余

代码

/*******************************
| Author:  AlwaysBeShine
| Problem: anon的私货
| Contest: NowCoder
| URL:     https://ac.nowcoder.com/acm/contest/67745/C
| When:    2024-02-21 15:48:37
| 
| 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;	
    cin >> n;
    std::vector<ll> a(n+3,LLONG_MAX);
    for(int i = 1; i <= n;i++){

    	cin >> a[i];

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

    	if(a[i] >= 2 && a[i+1] >= 2){
    		
    		if(a[i] >= a[i+1]){
    			cnt += a[i+1] - 1;
    			a[i] -= (a[i+1] - 1);
    			a[i+1] = 1;


    		}else{

    			cnt += a[i] - 1;
    			a[i+1] -= (a[i] - 1);
    			a[i] = 1;

    		}

    	}

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

    	// 	cout << a[i] << " \n"[i==n];

    	// }

    }

    if(a[1] >= 2)cnt += a[1] - 1;
    cout << cnt;
			
	return 0;
}

G sakiko的排列构造（easy）

题意

构造一个长度为 \(n\) 的排列 \(p\) ，使得每一个 \(p_i+i\ (1\leq i\leq n)\) 都是质数。

思路

通过打表可发现规律
设第 \(i\) 位应该放的值为 \(a_i\)，当前使用的质数为 \(z_k\) （第 \(k\) 个质数）
倒着构造，提前预处理出小于等于 \(10^3\) 以内的所有质数，用第一个大于等于 \(n\) 的质数从最后一位开始倒着构造。

因为要构造一个排列，所以数字不能重复，也不能大于 \(n\)
所以要求 \(z_k - i\) 必须没有出现过，并且 \(z_k - i \le n\) 如果满足条件，那么 \(a_i = z_k - i\)
否则 \(k\) 自减（就是再往小找最大的满足 \(z_k - i\) 没出现过的质数）再循环这个情况

如果构造过程中 \(k \lt 1\) （也就是质数不够用了），那么就构造不出来，否则就构造的出来

代码

/*******************************
| Author:  AlwaysBeShine
| Problem: sakiko的排列构造（easy）
| Contest: NowCoder
| URL:     https://ac.nowcoder.com/acm/contest/67745/G
| When:    2024-02-21 16:49:29
| 
| 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(10100);
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 <= 10000;i++){

		if(isNotPrime[i] == false){

			prime.push_back(i);
			
		}
		for(int j = 1;prime[j] * i <= 10000;j++){
			int temp = prime[j] * i;
			isNotPrime[temp] = true;
			
			if(i % prime[j] == 0)break;

		}
	}

    int pos;
    int n;
    cin >> n;
    for(int i = 1;i <= prime.size();i++){

    	if(prime[i] > n){

    		pos = i;
    		break;
    	}

    }
    vector<int>ans(n+5);
    map<int,int>mp;
    for(int i = n;i >= 1;i--){ //倒着来

    	if(pos < 1){

    		cout << "-1";
    		return 0;
    	}

    	while(pos >= 1 && (prime[pos] - i > n || mp[prime[pos] - i] == 1)){

    		pos--;

    	}

    	if(mp[prime[pos] - i] == 0){ //如果没出现过这个数

    		if(prime[pos] - i <= n){ //必须要小于等于 n
    			ans[i] = prime[pos] - i;
    			mp[prime[pos] - i] = 1; 

    		}else{ //如果大于等于n了或者出现过了

    			while(pos >= 1 && (prime[pos] - i > n || mp[prime[pos] - i] == 1)){

    				pos--;

    			}

    			if(pos < 1){

    				cout << -1;

    			}else{

    				ans[i] = prime[pos] - i;
    				mp[prime[pos] - i] = 1;

    			}

    		}
    	}

    }

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

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

    }

    return 0;
}

H sakiko的排列构造（hard）

题意

同 easy 版，只有数据范围扩大到了 \(10^6\)

思路

同 easy 版

代码

/*******************************
| Author:  AlwaysBeShine
| Problem: sakiko的排列构造（easy）
| Contest: NowCoder
| URL:     https://ac.nowcoder.com/acm/contest/67745/G
| When:    2024-02-21 16:49:29
| 
| 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(1000010);
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 <= 1000010;i++){

		if(isNotPrime[i] == false){

			prime.push_back(i);
			
		}
		for(int j = 1;prime[j] * i <= 1000010;j++){
			int temp = prime[j] * i;
			isNotPrime[temp] = true;
			
			if(i % prime[j] == 0)break;

		}
	}

    int pos;
    int n;
    cin >> n;
    for(int i = 1;i <= prime.size();i++){

    	if(prime[i] > n){

    		pos = i;
    		break;
    	}

    }
    vector<int>ans(n+5);
    map<int,int>mp;
    for(int i = n;i >= 1;i--){ //倒着来

    	if(pos < 1){

    		cout << "-1";
    		return 0;
    	}

    	while(pos >= 1 && (prime[pos] - i > n || mp[prime[pos] - i] == 1)){

    		pos--;

    	}

    	if(mp[prime[pos] - i] == 0){ //如果没出现过这个数

    		if(prime[pos] - i <= n){ //必须要小于等于 n
    			ans[i] = prime[pos] - i;
    			mp[prime[pos] - i] = 1; 

    		}else{ //如果大于等于n了或者出现过了

    			while(pos >= 1 && (prime[pos] - i > n || mp[prime[pos] - i] == 1)){

    				pos--;

    			}

    			if(pos < 1){

    				cout << -1;

    			}else{

    				ans[i] = prime[pos] - i;
    				mp[prime[pos] - i] = 1;

    			}

    		}
    	}

    }

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

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

    }

    return 0;
}

I rikki的最短路

题意

rikki 在找 anon ，她准备去找 tomorin 问一下 anon 在哪。 （以下tomorin简称 \(T\) ，anon简称 \(A\) ）
寻找过程：找到 \(A\) ，将 \(A\) 带回 \(T\) 的位置，可以简单的理解为先找到 \(A\) 再去找 \(T\) 。
我们把寻找过程简化为一条数轴， rikki 在数轴上的坐标为 0 ， \(T\) 在数轴上的坐标为 \(t\) ， \(A\) 在数轴上的坐标为 \(a\) 。
初始时 rikki 只知道 \(T\) 的坐标，而不知道 \(A\) 的坐标，因此 rikki 会先前往 \(T\) 的坐标。
而当 rikki 到达 \(T\) 的坐标时，就可以知道 \(A\) 的坐标。
rikki 的视野为 \(k\) ，若rikki当前坐标为 \(u\) ，则她可以看到 \([u-k,u+k]\) 区间内的东西，即 rikki 可能可以在移动到 \(T\) 所在坐标的过程中直接看到 \(A\) ，去找到 \(A\) ，省略先去找 \(T\) 的过程。
rikki 想知道她将 \(A\) 带回 \(T\) 的坐标最少需要移动多少距离。

思路

分类讨论

  1. 当 \(A\) 和 \(T\) 同向时，如果 \(\lvert A \rvert \le \lvert T \rvert\)，那么在找 \(T\) 的过程中就找到了 \(A\) 直接带走，不需要多走，答案就是 \(\lvert T \rvert\)
  2. 当 A 和 \(T\) 同向时，如果 \(\lvert A \rvert \gt \lvert T \rvert\)，那就得比上面那种情况，多走 \(2 * (\lvert A \rvert - \lvert T \rvert)\)
  3. 当 \(A\) 和 \(T\) 反向时，如果\(\lvert A \rvert \le \lvert k \rvert\)，一开始就知道 \(A\) 在哪，所以可以先找 \(A\) ，再带到 \(T\) 处
  4. 当 \(T = 0\) 时，同上理。
  5. 当 \(A\) 和 \(T\) 反向时，如果\(\lvert A \rvert \gt \lvert T \rvert\) ，得先去找 \(T\) 再去找 \(A\) ，再找 \(T\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
			
int main(){
			
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
			
	ll t,a,k;
	cin >> t >> a >> k;
    if((t > 0 && a > 0) || (t < 0 && a < 0)){ //同向
		ll la = abs(a),lt = abs(t);
		if(la <= lt){ //去t路上能看见a

			cout << lt;

		}else{ //看不见a

			cout << la + la - lt;

		}

	}else if(a == 0){ //带着a去找t

		cout << abs(t);

	}else if(t == 0){ //直接知道a在哪 把他带回来

		cout << 2 * abs(a);

	}else{ //反向

		if(abs(a) > k){

			cout << 3*abs(t) + 2*abs(a);

		}else{

			cout << 2*abs(a) + abs(t);

		}

	}
			
	return 0;
}

L anon的星星

题意

玩一个游戏，胜利一局会获得一颗星星，失败一局会失去一颗星星，没有平局。 只知道自己玩了 \(n\) 局游戏，共获得了 \(x\) 颗星星。
求胜利了几局，失败了几局？

思路

设胜利了 \(i\) 局，则输了 $ n - i$ 局，判断 \(1 \le i \le n\) 是否存在 \(i - (n-i) = x\) 即可

代码

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    for (int i = 0; i <= n; ++i) {
        int j = n - i;
        if (i - j == x) {
            cout << i << " " << j << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
    return 0;
}

M mutsumi的排列连通

题意

有两个排列，放置在一个 \(2 \times n\) 的矩形中，每次你可以选择一个数字 \(x\) ，将两个排列内的 \(x\) 所在的单元格删除。
删除尽可能少的数字，使得矩形至少被分成两个连通块（不一定是矩形），
请输出最小的删除次数。若无法通过删除使得矩形被分成至少两个连通块，则输出 -1。
连通块：块内任意两点（可以是同一点）都可以找到至少一条只由上下左右组成的路径相连。
长度为 \(n\) 的排列为：\(1-n\) 中，每个数字恰好出现一次。

思路

很容易思考出，答案只有 \(-1,1,2\) 三种可能

当 \(n = 1\) 时，无解

当 \(n = 2\) 时，如果两排列完全相同，无解；如果两排列不同，操作一次即可

当 \(n \ge 3\) 时，判断第 \(2\) 位到第 \(n-1\) 位之间，两排列是否存在两个相同的元素在两排列种各自的下标之差为 \(1\)

​ 如果存在，则操作一次即可，否则要操作两次。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){

    map<int,int>a;

	map<int,int>b;		
	int n,temp;
	cin >> n;
	vector<int>A(n+1,0);
	vector<int>B(n+1,0);
	for(int i = 1;i <= n;i++){

		
		cin >> temp;
		a[temp] = i;
		A[i] = temp;
	}
	bool ck = false;
	for(int i = 1;i <= n;i++){

		cin >> temp;
		b[temp] = i;
		B[i] = temp;
		if(abs(i - a[temp]) == 1 || i == a[temp] && i != n && i != 1){

			ck = true;

		}

	}

	if(n == 1){

		cout << "-1\n";

	}else if(n == 2){

		if(A[1] == B[1] && A[2] == B[2])cout << "-1\n";
		else{

			cout << "1\n";

		}
	}else{

		if(ck){

			cout << "1\n";

		}else{

			cout << "2\n";

		}

	}

}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while(T--){

       solve();

    }

    return 0;
}

标签：prime,cout,int,题解,质数,pos,long,2024,集训营
From： https://www.cnblogs.com/AlwaysBeShine/p/18038356

相关文章

  • 2024.02.19 测试
    BeforewritingAlltheproblemsin2024.02.18测试and2024.02.19测试inhere:linkT1素数Linkgxyzoj:#3598素数Luogu:UVA1210连续素数之和UVa:1210-SumofConsecutivePrimeNumbersDescriptionSomepositiveintegerscanberepresentedbyasumofo......
  • USACO 2024年2月月赛
    S2把一个颜色段看作一个球。现在有三个栈。初始\(1,2\)有球，\(3\)空。依次判断。如果\(1,2\)中都只有一种颜色且\(3\)空，结束。若\(1,2\)的栈顶元素不一样且\(3\)为空时，把\(1,2\)中球数量多的那个栈的栈顶放到\(3\)里。否则先判断是否三个栈都非空。若......
  • 题解 CF963E Circles of Waiting
    令\(f_{i,j}\)表示\((i,j)\)走出以\((0,0)\)为圆心，半径为\(R\)的期望步数，显然所有在圆外的点\((i,j)\)满足\(f_{i,j}=0\)。有\(f_{i,j}=p_1f_{i-1,j}+p_2f_{i,j-1}+p_3f_{i+1,j}+p_4f_{i,j+1}\)。这东西很套路，高斯消元就行，但状态数是\(O(R^2)\)的，复杂度\(O(R^......
  • 题解 CF725G Messages on a Tree
    updateon2023.8.9修正了一些错误。\(\texttt{link}\)第\(i\)条信息的传输可以表示成\(x_i\)走到\(x_i\)的某一祖先再走回\(x_i\)的路径。所以答案只和\(x_i\)的这一祖先有关，记为\(f_i\)，则\(ans_i=t_i+2\timesdep_{x_i}-2\timesdep_{f_i}\)。若\(x_i\)在\(f......
  • 题解 CF1781G Diverse Coloring
    \(\texttt{link}\)题意给定一棵\(n\)个点的二叉树，现对其每个点染成黑色或白色。一种合法的染色方案满足：对于所有黑色的点，都存在白色的点与之相邻。对于所有白色的点，都存在黑色的点与之相邻。一种染色方案的权值是染成黑色的点数与染成白色的点数之差的绝对值。\(\foral......
  • 题解 CF1523H Hopping Around the Array
    \(\texttt{link}\)题意数轴上有\(n\)个点，每个点有属性\(a_i\)，在第\(i\)个点可以花费\(1\)的步数移动至\([i,i+a_i]\)中任意一个点。定义一次操作为选出一个\(i\)，使\(a_i\getsa_i+1\)。\(q\)组询问，每次给出\(l,r,k\)，求有\(k\)次操作机会时，从第\(l\)个点走到......
  • 题解 CF983D Arkady and Rectangles
    \(\texttt{link}\)题意平面直角坐标系上给定\(n\)个矩形，第\(i\)个矩形颜色为\(i\)，颜色大的矩形将覆盖颜色小的矩形，问最后能看到几种颜色。\(1\len\le10^5,|x_i|,|y_i|\le10^9\)题解首先离散化，考虑扫描线如何维护序列上的颜色。一个区间\([l,r]\)投射到线段树上\(......
  • AT_arc117_c [ARC117C] Tricolor Pyramid 题解
    [ARC117C]TricolorPyramid博客阅读体验（也许）更佳题意给一个金字塔的底部颜色组成和生长规律，问顶部的颜色是什么。分析试几次就可以很容易得到的一种构造：令颜色B为\(0\)，W为\(1\)，R为\(2\)。设左右两个方块的颜色分别为\(col_l\)和\(col_r\)，则生长规则可以描......
  • P5605 小 A 与两位神仙 题解
    推销博客P5605小A与两位神仙题意给定\(x\)、\(y\)和\(m\)，其中\(m=p^n,n\in\mathbb{N+},p\ge3\)，问同余方程\(x^a\equivy\pmodm\)是否有非负整数解。分析前置芝士Pollard_rho原根化简对这种指数型的同余方程是很难解决的，我们要先把它转化成线性的同余方......
  • GDOI2024 AFO寄
    Day-4怎么说呢……因为这次考不好就会AFO，而我又铁定考不好（个人估分两天加起来\(150\)分）。如果真的要进省队的话，以我\(\text{NOIP233}\)分的垃圾分数，假设省选最高分\(450\)分的情况下，我需要至少考\(200+140=340\)分，再想想\(\text{GDKOI}\)考的\(90\)分的“好成绩......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99