2024牛客寒假算法基础集训营1（视频讲解全部题目）

  • 开发
  • 28

2024牛客寒假算法基础集训营1（题目全解）

2024牛客寒假算法基础集训营1（视频讲解全部题目）
在这里插入图片描述

A

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
   
	int n; cin >> n;
	string s; cin >> s;
	bool f = false, F = false;
	for(int i = 0; i < n; i ++){
   
		if(s[i] == 'd'){
   
			for(int j = i + 1; j < n; j ++){
   
				if(s[j] == 'f'){
   
					for(int k = j + 1; k < n; k ++){
   
						if(s[k] =='s'){
   
							f = true; 
						}
					}
				}
			}
		}
	}
		for(int i = 0; i < n; i ++){
   
		if(s[i] == 'D'){
   
			for(int j = i + 1; j < n; j ++){
   
				if(s[j] == 'F'){
   
					for(int k = j + 1; k < n; k ++){
   
						if(s[k] =='S'){
   
							F = true; 
						}
					}
				}
			}
		}
	}
	cout << F << " " << f << endl;	
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}

B

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int> pii;
int dc[3] = {
   -1, 0, 1};
void solve()
{
   
	int n; cin >> n;
	int l = 2, r = 2;
	vector<pii>lp, rp;
	map<pii,bool>st;

	for(int i = 0; i < n; i ++){
   
		int r, c; cin >> r >> c;
		st[{
   c,r}] = true;
		if(c <= 0){
   
			lp.push_back({
   c, r});
		}else if(c > 0){
   
			rp.push_back({
   c, r});
		}
	}
	if(lp.size()){
   
		for(int i = 0; i < lp.size(); i ++){
   
			if(lp[i].first == 0 and lp[i].second == 2){
   
				if(!st[{
   -1, 1}]){
   
					l = min(1ll, l);
				}else{
   
					l = 0;
				}
				continue;
			}

			for(int j = 0; j < 3; j ++){
   
				int nc = lp[i].x + dc[j];
				int nr = 3 - lp[i].y;
				if(st[{
   nc, nr}]){
   
					l = 0;
				}else{
   
					l = min(l, 1ll);
				}
			}
		}
		
	}

	if((st[{
   -1, 1}] and l == 1)){
   
			st[{
   0, 2}] = true;
	}
	if(l == 2){
   
		st[{
   0, 2}] = true;
	}
	

	if(rp.size()){
   
		for(int i = 0; i < rp.size(); i ++){
   
			for(int j = 0; j < 3; j ++){
   
				int nc = rp[i].x + dc[j];
				int nr = 3 - rp[i].y;
				if(st[{
   nc, nr}]){
   
					r = 0;
				}else{
   
					r = min(r, 1ll);
				}
			}
		}
	}else{
   
		if(st[{
   0, 2}]){
   
			r = 1;
		}
	}
	int ans = l + r;
	cout << ans << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}

C

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

void solve()
{
   
	int n, q, tc; cin >> n >> q >> tc;
	vector<int>t(n + 1);
	vector<int>s(n + 1);
	vector<int>ss(n + 1);
	for(int i = 1; i <= n; i ++){
   
		cin >> t[i];
	}
	sort(t.begin() + 1, t.end());
	for(int i = 1; i <= n; i ++){
   
		s[i] = s[i - 1] + t[i];
	}
	for(int i = 1; i <= n; i ++){
   
		ss[i] = ss[i - 1] + s[i];
	}

	while(q--){
   
		int M; cin >> M;
		int l = 1, r = n;
		while(l < r){
   
			int mid = l + r >> 1;
			int cnt = n - mid + 1;
			if(cnt * tc <= M){
   
				r = mid;
			}else{
   
				l = mid + 1;
			}
		}
		if(l == n){
   
			if(tc > M){
   
				cout << s[n] + tc << endl;
				continue;
			} 
		}
		cout << s[l - 1] + tc << endl;
	}
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	//cin >> t;
	while(t--)
	solve();
}

D

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;

void solve()
{
   
	int n, m; cin >> n >> m;
	vector<int>a(n);
	map<int,int>cnt;
	set<int>ans;
	ans.insert(0);

	for(int i = 0; i < n; i ++){
   
		cin >> a[i];
		cnt[a[i]] += 1;
	}
	if(n >= 30){
   
		//一定要减少绝对值不等于1的数字个数。
		for(auto [x, y]: cnt){
   
			if(n - cnt[x] - cnt[x - 2] > 30)
				continue;

			int mul = 1;
			bool flag = true;
			for(int i = 0; i < n; i ++){
   
				mul = mul * (a[i] - (x - 1));
				if(abs(mul) > 1e9){
   
					flag = false;
					break;
				}
			}
			if(flag)
				ans.insert(mul);

			mul = 1, flag = true;
			for(int i = 0; i < n; i ++){
   
				mul = mul * (a[i] - (x + 1));
				if(abs(mul) > 1e9){
   
					flag = false;
					break;
				}
			}
			if(flag)
				ans.insert(mul);
		}
	}else{
   
		//如果n <= 30
		sort(a.begin(), a.end());
		int tmp = a[0];
		for(int i = 0; i < n; i ++){
   
			a[i] -= tmp;
		}
		for(int i = -1e6; i <= 1e6; i ++){
   
			int mul = 1;
			bool flag = true;
			for(int j = 0; j < n; j ++){
   
				mul = mul * (a[j] + i);
				if(abs(mul) > 1e9){
   
					flag = false;
					break;
				}
			}
			if(flag)
				ans.insert(mul);
		}

		
		reverse(a.begin(), a.end());
		tmp = a[0];
		for(int i = 0; i < n; i ++){
   
			a[i] -= tmp;
		}
		
		for(int i = -1e6; i <= 1e6; i ++){
   
			int mul = 1;
			bool flag = true;
			for(int j = 0; j < n; j ++){
   
				mul = mul * (a[j] + i);
				if(abs(mul) > 1e9){
   
					flag = false;
					break;
				}
			}
			if(flag)
				ans.insert(mul);
		}
	}

	while(m--){
   
		int x; cin >> x;
		if(ans.count(x)){
   
			cout << "Yes" << endl;
		}else{
   
			cout << "No" << endl;
		}
	}

}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	//cin >> t;
	while(t--)
	solve();
}

E

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;

void solve()
{
   
	int n, m; cin >> n >> m;
	vector<int>a(n);
	vector<pii>b(m);
	for(int i = 0; i < n; i ++){
   
		cin >> a[i];
	}
	for(int i = 0; i < m; i ++){
   
		int u, v; 
		cin >> u >> v;
		u --, v --;
		b[i] = {
   u, v};
	}
	int ans = 11;

	function<void(int)> dfs = [&](int u)->void{
   
		
		if(u >= m){
   
			int sc = a[0];
			int top = 1;
			for(int i = 1; i < n; i ++){
   
				if(a[i] > sc){
   
					top ++;
				}
			}

			ans = min(ans, top);
			return;
		}
	
		int x = b[u].first, y = b[u].second;

		a[x] += 3;
		dfs(u + 1);
		//回溯
		a[x] -= 3;

		a[y] += 3;
		dfs(u + 1);
		
		a[y] -= 3;

		a[x] += 1, a[y] += 1;
		dfs(u + 1);
		a[x] -= 1, a[y] -= 1;
	};


	dfs(0);
	cout << ans << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}

F

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int b, int p){
   
	int res = 1;
	while(b){
   
		if(b & 1)
			res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

void init(){
   
	fact[0] = infact[0] = 1;
	for(int i = 1; i < N; i ++){
   
		fact[i] = fact[i - 1] * i % mod;
		infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
	}
}

void solve()
{
   
	int n, m; cin >> n >> m;
	int res = 0;
	for(int i = 0; i <= m; i ++){
   
		if((m - i) % 2){
   
			res = ((res - (qmi(i, n, mod) * infact[i] % mod * infact[m - i] % mod)) % mod + mod) % mod;
		}else{
   
			res = (res + (qmi(i, n, mod) * infact[i] % mod * infact[m - i] % mod)) % mod;
		}
	}
	cout << res << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	init();
	while(t--)
	solve();
}

G

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define x first
#define y second
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;

void solve()
{
   
	int n, m; cin >> n >> m;
	vector<pii>a(n + 1);
	for(int i = 1; i <= n; i ++){
   
		cin >> a[i].x >> a[i].y;
	}
	sort(a.begin(), a.end());
	vector<int>s(n + 1);
	for(int i = 1; i <= n; i ++){
   
		s[i] = s[i - 1] + a[i].y;
	}
	int ans = m;
	for(int i = n; i >= 1; i --){
   
		int dis = a[i].x - s[i];
		if(dis > m){
   
			continue;
		}
		ans = max(ans, m + s[i]);
	}
	cout << ans << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}

H

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
   
	int n, m; cin >> n >> m;
	vector<int>v(n), w(n);
	for(int i = 0; i < n; i ++){
   
		cin >> v[i] >> w[i];
	}
	int ans = 0, pre = 0;
	for(int i = 31; i >= 0; i --){
   
		int x = pre;
		if((m >> i) & 1){
   
			x += (1 << i) - 1;
			pre += (1 << i);
		}

		int sum = 0;
		for(int j = 0; j < n; j ++){
   
			if((x | w[j]) == x){
   
				sum += v[j];
			}
		}
		ans = max(ans, sum);
	}


	int sum = 0;
	for(int j = 0; j < n; j ++){
   
		if((m | w[j]) == m){
   
			sum += v[j];
		}
	}
	
	ans = max(ans, sum);

	cout << ans << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}

I

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
uniform_int_distribution<int> u1(-99,99);//生成圆心
uniform_int_distribution<int> u2(1,100);//生成半径
default_random_engine e;

void test()
{
   
	int n = 1e5;
	double r1 = 0;
	for(int i = 1; i <= n; i ++){
   

		int x = u1(e), y = u1(e);
		while(1){
   
			int r = u2(e);
			if(x + r > 100 || x - r < -100 || y + r > 100 || y - r < -100){
   
				continue;
			}else{
   
				r1 += (r);
				break;
			}
		} 
		
	}
	double r2 = 0;
	for(int i = 1; i <= n; i ++){
   
		while(1){
   
			int x = u1(e), y = u1(e);
			int r = u2(e);
			if(x + r > 100 || x - r < -100 || y + r > 100 || y - r < -100){
   
				continue;
			}else{
   
				r2 += (r);
				break;
			}
		} 
	}
	r1 = r1 / n;
	r2 = r2	/ n;
	cout << r1 << " " << r2 << endl;
}
void solve(){
   
	int n; cin >> n;
	double sum = 0;
	for(int i = 0; i < n; i ++){
   
		int x, y, r; cin >> x >> y >> r;
		sum += r; 
	}
	sum /= n;
	if((int)sum == 17){
   
		cout << "bit-noob" << endl;
	}else{
   
		cout << "buaa-noob" << endl;
	}
}
signed main()
{
   
	e.seed(time(NULL));

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	// solve();
		test();
}

J

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
   
	int n, x, y; cin >> n >> x >> y;
	vector<int>a(n);
	for(int i = 0; i < n; i ++){
   
		cin >> a[i];
	}

	auto check = [&](int dis)->bool{
   
		// cout << dis << endl;
		set<int>st;
		st.insert(x), st.insert(y);
		if(abs(x - y) > dis){
   
			return false;
		}

		for(int i = 0; i < a.size(); i ++){
   
			
			while(st.size() and abs(*st.begin() - a[i]) > dis){
   
				st.erase(st.begin());
			}
			while(st.size() and abs(*st.rbegin() - a[i]) > dis){
   
				st.erase(*st.rbegin());
			}
			
			if(!st.size()){
   
				return false;
			}
			st.insert(a[i]);
		}
		return true;
	};

	int l = 0, r = 1e9;
	while(l < r){
   
		int mid = l + r >> 1;
		if(check(mid)){
   
			r = mid;
		}else{
   
			l = mid + 1;
		}
	}
	cout << l << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while(t--)
	solve();
}

K

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
int nex[N];
string choice[N];
int p[N], in[N];
bool st[N];
char t[N];
set<int> root;
int nums;

int find(int x){
   
	if(x != p[x])
		p[x] = find(p[x]);
	return p[x];
}

void init(int x){
   
	for(int i = 1; i <= x; i ++){
   
		p[i] = i;
		root.insert(i);
	}
}

void merge(int x, int y){
   
	int px = find(x);
	int py = find(y);
	if(px != py){
   
		if(in[px])
		{
   
			p[px] = py;
			root.erase(px);
		}
		else
		{
   
			p[py] = px;
			root.erase(py);
		}
	}
}

void dfs(int u, char answer){
   
	if(st[nex[u]]){
   
		if(answer == t[nex[u]]){
   
			nums ++;
		}
		return;
	}
	
	char nex_answer = choice[nex[u]][answer - 'A'];
	t[nex[u]] = answer;
	st[nex[u]] = true;
	dfs(nex[u], nex_answer);	
	st[nex[u]] = false;
}

void solve()
{
   
	int n; cin >> n;
	init(n);

	for(int i = 1; i <= n; i ++){
   
		int x; string s;
		cin >> x >> s;
		choice[i] = s;
		nex[i] = x;
		in[x] ++;
		merge(x, i);
	}

	int ans = 1;
	for(auto x: root){
   
		for(int i = 0; i < 5; i ++){
   
			t[x] = ('A' + i);
			st[x] = true;
			dfs(x, choice[x][i]);
		}
		ans = nums * ans % mod;
		nums = 0;
	}
	cout << ans << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while(t--)
	solve();
}

L

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
   
	int c, d, h, w;
	cin >> c >> d >> h >> w;
	cout << 3 * w * c << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}

M

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;

void solve()
{
   
	int n; cin >> n;
	if(n % 6)
		cout << (n / 6) * 2 << endl;
	else
		cout << (n / 6) << endl;
}

signed main()
{
   
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//t = 1;
	cin >> t;
	while(t--)
	solve();
}
阅读全部

相关推荐

  10. 【持续更新】2024牛客寒假算法基础集训营4 题解 | JorbanS

    2024-02-05 09:32:01       30 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-02-05 09:32:01       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-02-05 09:32:01       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-02-05 09:32:01       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-02-05 09:32:01       18 阅读

热门阅读

  2. session和cache的区别

    2024-02-05 09:32:01       32 阅读

  3. Shell脚本是一种用来自动化执行一系列命令的文本文件

    2024-02-05 09:32:01       31 阅读

  4. 5、SHAP 值的高级用法

    2024-02-05 09:32:01       31 阅读

  8. PyTorch中的nn.Embedding的使用、参数及案例

    2024-02-05 09:32:01       30 阅读

  10. python 解析多层级的json数据

    2024-02-05 09:32:01       33 阅读

  11. MySQL分区的优缺点

    2024-02-05 09:32:01       29 阅读

  12. 详解 Spring Boot 条件装配

    2024-02-05 09:32:01       27 阅读

  13. 在CentOS 7中使用Python 3执行系统命令

    2024-02-05 09:32:01       33 阅读

  18. Adobe Illustrator CEP插件开发入门指南

    2024-02-05 09:32:01       30 阅读

  20. C++设计模式-简单工厂模式，工厂方法模式，抽象工厂模式

    2024-02-05 09:32:01       31 阅读

  21. 字符串拼接+和+=的执行过程

    2024-02-05 09:32:01       33 阅读

  22. 手机常亮屏不自动灭屏

    2024-02-05 09:32:01       90 阅读

  28. 【Golang】exec.command命令日志输出示例

    2024-02-05 09:32:01       30 阅读