牛客小白月赛99(A-F)

2024-08-27 12:04
文章标签 牛客 99 小白月赛

本文主要是介绍牛客小白月赛99(A-F),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

牛客小白月赛99_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A

签到题,不解释

#include<iostream>
using namespace std;
using ll = long long;
int main()
{int t; cin >> t;while(t--){ll a, b, x, y; cin >> a >> b >> x >> y;ll res = b * y;if(x < y) res += a * x;else res += a * y;cout << res << endl;}return 0;
}

B

n % b = c   \Rightarrow   n - \left \lfloor \frac{n}{b} \right \rfloor * b = c  , 令 \left \lfloor \frac{n}{b} \right \rfloor * b = k,  k 属于 [ b, n ],c 属于 [ 0, b), [0, k)

  n - k = c, k \in \left ( \frac{n}{2}, n \right ],每次 c 若取最大值,那么 k 取最小, k  每次取 n / 2 + 1.

#include<iostream>using namespace std;
using ll = long long;void slove()
{ll n; cin >> n;ll ans = 0;while(n){ll k = n / 2 + 1;n %= k;ans++;}cout << ans << endl;
}int main()
{int t; cin >> t;while(t--) slove();return 0;
}

C

起点是否能达终点,取决于终点属于的连通块周围是否可以被激光清除。对于终点的每一块连通块,将该点的上下左右 行 和 列标记,若起点可达这些标记行 列,即可达终点。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n, m;
int sx, sy, ex, ey;
int dy[] = {0, 1, 0, -1}, dx[] = {-1, 0, 1, 0};
char g[N][N];
bool stx[N], sty[N], st1[N][N], st2[N][N];
void bfs()
{cin >> n >> m;for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)cin >> g[i][j];for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)if(g[i][j] == 'S') { sx = i, sy = j; }else if(g[i][j] == 'E') { ex = i, ey = j; }queue<PII> q1;q1.push({ex, ey});st1[ex][ey] = true;while(q1.size()){PII t = q1.front(); q1.pop();int x = t.first, y = t.second;stx[x] = stx[x - 1] = stx[x + 1] = true;sty[y] = sty[y + 1] = sty[y - 1] = true;for(int i = 0; i < 4; i++){int a = x + dx[i], b = y + dy[i];if(a < 1 || a > n || b < 1 || b > m) continue;  if(g[a][b] == '#' || st1[a][b]) continue;st1[a][b] = true;q1.push({a, b});}}queue<PII> q2;q2.push({sx, sy});st2[sx][sy] = true;while(q2.size()){PII t = q2.front(); q2.pop();int x = t.first, y = t.second;if(stx[x] || sty[y]) {cout << "YES" << endl;return;}for(int i = 0; i < 4; i++){int a = x + dx[i], b = y + dy[i];if(a < 1 || a > n || b < 1 || b > m) continue;if(g[a][b] == '#' || st2[a][b]) continue;st2[a][b] = true;q2.push({a, b});}}cout << "NO" << endl;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);bfs();return 0;}

D

每个人眨眼的时刻为 ai 的倍数,确保每个人不眨眼,那么应该是不能被 ai 整除。

答案是质数还是合数?答案为质数。

设 x 为答案,且 x 为合数,那么 ai 不整除 x,令 y 为 x 的质因子,因为 x 为合数,所以一定存在一个小于它的质因子。y < x, 且 ai 不整除 x,那么 ai 也不整除 y。因为 y 小于 x,所以 y 更优。而y是质数,所以答案为质数。

所以可以先将所有的质数筛出来,并去除 ai,剩余的最小的质数即为答案。

#include<iostream>
#include<set>
using namespace std;const int N = 2e5 + 10,  M = 3e6 + 10;
int a[N];
int primes[N];
bool st[M];
int count;
int get_primes(int n)  // 线性筛
{int cnt = 0;for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i;if(cnt > count) break;  // 只筛 n + 1 个for(int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true;if(i % primes[j] == 0) break;  // pj 一定是i的最小质因子}}return cnt;
}
void slove()
{cin >> count;for(int i = 0; i < count; i++) cin >> a[i];int cnt = get_primes(3e6);  // 1~3e6 的质数有 216816set<int> S;for(int i = 0; i < cnt; i++) S.insert(primes[i]);  for(int i = 0; i < count; i++)if(S.count(a[i])) S.erase(a[i]); cout << *S.begin() << endl;
}int main()
{int t; cin >> t;while(t--) slove();return 0;
}

E

一道简单的区间合并问题。每一块牌有一个倒塌范围,当后面的牌位于该范围之内,就能被推倒。计算每一个牌倒塌的范围,按照左端点升序排列,然后区间合并,存储一下每一次能推倒的个数。

#include<iostream>
#include<vector>
#include<algorithm>
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> PII;int n, m;void slove()
{cin >> n >> m;vector<int> h(n + 5, 0);vector<int> a(n + 5, 0);for(int i = 0; i < n; i++) cin >> h[i];for(int i = 0; i < n; i++) cin >> a[i];vector<PII> arr(n + 5, {2e9 + 10, 2e9 + 10});for(int i = 0; i < n; i++) arr[i] = {a[i], a[i] + h[i]};sort(arr.begin(), arr.begin() + n);vector<int> b;int res = 0;for(int i = 0; i < n; i++){int j = i + 1;int temp = arr[i]._2;while(j <= n && arr[j]._1 <= temp) {temp = max(temp, arr[j]._2);j++;}b.push_back(j - i);i = j - 1;}sort(b.begin(), b.end(), greater<int>());for(int i = 0; i < min(m, (int)b.size()); i++) res += b[i];cout << res << endl;
}int main()
{int t; cin >> t;while(t--) slove();return 0;
}

F

机器人从起点到终点的距离 n 为必要距离,也就是必须要走的长度。当这个长度大于 t,那么就会提前爆炸,造成伤害为 0。

对于中间的墙壁,需要时机器人在墙壁之间来回移动,从而增加移动时间,增加爆炸伤害,有多种开启和关闭的方案,但是对于每一个大区间墙壁的操作增加的时间,都可以由小区间墙壁操作得到,只不过需要多操作几次。所以可以将所有墙壁在位置升序排列,每两个墙壁之间的区间就是最小区间。

将该区间的长度 * 2 加入容器中,每一次操作墙壁,机器人会多走 区间长度 * 2 的时间。
将操作增加的时间排序去重,然后就可以转化为完全背包问题

为了达到最大的爆炸伤害 t ,那么需要操作墙壁增加的时间 d = t - n。
每一个墙壁区间可以操作无限次。每一次增加的时间为 v。

集合表示 f[i, j]:在前 i 个区间中选,体积(增加的时间)能否恰好为 j。

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;void slove()
{int n, m, t; cin >> n >> m >> t;vector<int> a(m, 0);for(int i = 0; i < m; i++) cin >> a[i];if(t < n) { cout << 0 << endl; return; }sort(a.begin(), a.end());vector<int> b(m - 1, 0);for(int i = 0; i <= m - 2; i++) b[i] = 2 * (a[i + 1] - a[i]);sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());int d = t - n;vector<int> f(d + 1, 0);f[0] = 1;for(auto& v : b)for(int j = v; j <= d; j++)f[j] |= f[j - v];for(int i = d; i >= 0; i--)if(f[i]) { cout << i + n << endl; return; }
}int main()
{int t; cin >> t;while(t--) slove();return 0;
}

这篇关于牛客小白月赛99(A-F)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1111616

相关文章

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

牛客《剑指Offer》 -- 数值的整数次方

题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 思路 特别注意负数的情况,出现负数,将其转化为正数然后求倒数。 class Solution {public:double Power(double base, int exponent) {double total = 1;bool flag = false

牛客网《剑指Offer》 二进制中1的个数

题目描述 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 思路 负数用补码,其实就是求一个数据在计算机中是存储是怎么样子的。用位运算,就能很好实现。 class Solution {public:int NumberOf1(int n) {int count = 0;int flag = 1;while (flag != 0) {if ((n & f

牛客网《剑指Offer》 矩形覆盖

题目描述 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? class Solution {public:int rectCover(int number) {if(number==0) return 0;if(number==1) return 1;if(number==2) return 2;retu

牛客《剑指Offer》 变态跳台阶

题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思路 根据 普通的跳台阶可以总结出 f(n) = f(n-1) + f(n-2) +f(n-3) + 。。。。+ f(1) +1 不妨设 f(0) = 1 , 则易得 class Solution {public:int jumpFloorII(int n

牛客《剑指Offer》 跳台阶

题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思路 递归思想,n阶梯子走法等于n-1 加上n-2的。 class Solution {public:int jumpFloor(int number) {if(number==1) return 1;if(number==2) return 2;return jumpFl