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

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

  • 视频链接
  • A
  • B
  • C
  • D
  • E
  • F
  • G、H（下面是hard版本的代码两个都可以过）

视频链接

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

A

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

void solve()
{
	int a, b ,k;
	cin >> a >> b >> k;
	if(a >= k * b){
		cout << "good" << endl;
	}else{
		cout << "bad" << 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
using namespace std;

void solve()
{
	int n; cin >> n;
	vector<int>a(n);
	int x = 0;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		x += (a[i] - 1);
	}
	if(x % 2){
		cout << "gui" << endl;
	}else{
		cout << "sweet" << 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 deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;
void solve()
{
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	x -- ,y --;
	vector<string> g(n + 10);
	for(int i = 0; i < n; i ++){
		cin >> g[i];
	}
	int p, q; cin >> p >> q;

	vector<pii>ops(q);
	
	for(int i = 0; i < q; i ++){
		cin >> ops[i].first >> ops[i].second;
	}
	while(p--){
		for(int j = 0; j < q; j ++){
			int op = ops[j].first, z = ops[j].second - 1;
			if(op == 1){
				char s = g[z][m - 1];
				for(int i = m - 1; i >= 1; i --){
					g[z][i] = g[z][i - 1];
				}
				g[z][0] = s;
			}else{
				char s = g[n - 1][z];
				for(int i = n - 1; i >= 1; i --){
					g[i][z] = g[i - 1][z];
				}
				g[0][z] = s;
			}
		}
	}

	cout << g[x][y] << 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; cin >> n;
	vector<int>a(n);
	for(int i = 0; i < n; i ++){
		cin >> a[i];
	}
	if(n == 1){
		cout << 1 << endl;
		return;
	}
	int s = 0;
	for(int i = 0; i < n; i ++){
		s += a[i];
	}
	int ans = 0;
    
	for(int i = 1; i <= s / i; i ++){
		if(s % i){
			continue;
		}
        int a = i, b = s / i;
        if(s / a >= n){
            ans ++;
        }
        if(a != b and s / b >= n){
            ans ++;
        }
	}
	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();
}

E

#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, k; cin >> n >> k;
	vector<int>a(n + 1), s(n + 1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	int ans = 0;
	map<int,int>st;
	st[0] = 1;

	for(int i = 1; i <= n; i ++){
		int p = s[i] % k;
		if(st[p]){
			ans += st[p];
			st.clear();
		}
		st[p] ++;
	}

	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 deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long 
using namespace std;
const int N = 1e3 + 10;
int a[N];
int f[N][10], g[N][10], dp[N];
int has[N][N][2];
int cal(int x, int y){
	if(y - x + 1 < 6){
		return 0;
	}

	if(has[x][y - 1][0] != INF and has[x][y - 1][1] != INF){
		int res = max(has[x][y - 1][1], has[x][y - 1][0] - a[y]);
		return res;
	}

	for(int i = x; i <= y + 1; i ++){
		for(int j = 0; j <= 6; j ++){
			f[i][j] = -INF;
			g[i][j] = INF;
		}
	}
	for(int i = x; i <= y; i ++){

		if(i != x)
		{
			f[i][1] = max(f[i - 1][1], a[i]);
			g[i][1] = min(g[i - 1][1], a[i]);
		}
		else
		{
			f[i][1] = a[i];
			g[i][1] = a[i];
		}


		if(i - x + 1 >= 2)
		{
			g[i][2] = min(g[i - 1][2], g[i - 1][1] - a[i]);
			f[i][2] = max(f[i - 1][2], f[i - 1][1] - a[i]);
		}
		else
			continue;

		if(i - x + 1 >= 3){
			if(g[i - 1][2] != INF){
				f[i][3] = max(f[i - 1][3], max(g[i - 1][2] * a[i], f[i - 1][2] * a[i]));
			}else{
				f[i][3] = max(f[i - 1][3], f[i - 1][2] * a[i]);
			}
			if(f[i - 1][2] != -INF)
				g[i][3] = min(g[i - 1][3], min(g[i - 1][2] * a[i], f[i - 1][2] * a[i]));
			else
				g[i][3] = min(g[i - 1][3], g[i - 1][2] * a[i]);
		}else
			continue;
		
		if(i - x + 1 >= 4)
		{
			f[i][4] = max(f[i - 1][4], f[i - 1][3] - a[i]);
			g[i][4] = min(g[i - 1][4], g[i - 1][3] - a[i]);
		}
		else
			continue;

		
		if(i - x + 1 >= 5){
			if(g[i - 1][4] != INF)
				f[i][5] = max(f[i - 1][5], max(g[i - 1][4] * a[i], f[i - 1][4] * a[i]));
			else
				f[i][5] = max(f[i - 1][5], f[i - 1][4] * a[i]);

			if(f[i - 1][4] != -INF)
				g[i][5] = min(g[i - 1][5], min(g[i - 1][4] * a[i], f[i - 1][4] * a[i]));
			else
				g[i][5] = min(g[i - 1][5], g[i - 1][4] * a[i]);
		}else
			continue;

		if(i - x + 1 >= 6)
			f[i][6] = max(f[i - 1][6], f[i - 1][5] - a[i]);

	}
	int res = 0;
	int xx = 0;
	for(int i = x; i <= y; i ++){
		res = max(res, f[i][6]);
		xx = max(xx, f[i][5]);
	}
	has[x][y][1] = res;//选6个数字的最大值
	has[x][y][0] = xx;//选5个数字的最大值
	return res;
}
void solve()
{
	int n; scanf("%lld", & n);
	for(int i = 1; i <= n; i ++){
		scanf("%lld", a + i);
	}

	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++){
				has[i][j][0] = has[i][j][1] = INF;
		}
	}
	
	for(int i = 1; i <= n; i ++){
		dp[i] = dp[i - 1];
		for(int j = 1; j <= i; j ++){
			dp[i] = max(dp[i], dp[j - 1] + cal(j, i));
		}
	}
	printf("%lld", dp[n]);
}

signed main()
{
	int t = 1;
	while(t--)
	solve();
}

G、H（下面是hard版本的代码两个都可以过）

#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
const int N = 3e3 + 10;
char g[N][N];
int ul[N][N], ur[N][N], ls[N][N], rs[N][N];

class BIT{
private:
    vector<long long>tre;
    int n;
public:
    BIT(int size): n(size), tre(size + 1, 0) {};

public:
    int lowbit(int x){
        return x & -x;
    }

    void add(int pos, long long x){
        for(int i = pos; i <= n; i += lowbit(i))
            tre[i] = tre[i] + x;
    }

    long long sum(int pos){
        long long res = 0;
        for(int i = pos; i; i -= lowbit(i))
            res = res + tre[i];
        return res;
    }

};
void solve()
{
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		string s; cin >> s;
		for(int j = 1; j <= m; j ++){
			g[i][j] = s[j - 1];
		}
	}

	for(int i = n; i >= 1; i --){
		for(int j = 1; j <= m; j ++){
			if(g[i][j] == '*'){
				ul[i][j] = ul[i + 1][j - 1] + 1;
				ur[i][j] = ur[i + 1][j + 1] + 1;
				ls[i][j] = ls[i][j - 1] + 1;
			}else{
				ul[i][j] = ur[i][j] = ls[i][j] = 0;
			}
		}
		for(int j = m; j >= 1; j --){
			if(g[i][j] == '*'){
				rs[i][j] = rs[i][j + 1] + 1;
			}else{
				rs[i][j] = 0;
			}
		}
	}
	long long ans = 0;
	for(int j = 1; j <= m; j ++){
		BIT t(n);//记录合法点的个数
		vector<vector<int>>del(n + 1);//记录在v这个点需要删除的点。
		for(int i = n; i >= 1; i --){
			
			if(g[i][j] == '*'){
				int v = i - min(ls[i][j], rs[i][j]) + 1;
				if(v >= 1){
					del[v].push_back(i);
				}
				int low = i + min(ul[i][j], ur[i][j]) - 1;
				ans += t.sum(low);
				t.add(i, 1);
			}
			
			for(auto x: del[i]){
				t.add(x, -1);
			}
		}
	}
	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();
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/399351.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

在Win系统部署WampServer并实现公网访问本地服务【内网穿透】

在Win系统部署WampServer并实现公网访问本地服务【内网穿透】

目录 推荐 前言 1.WampServer下载安装 2.WampServer启动 3.安装cpolar内网穿透 3.1 注册账号 3.2 下载cpolar客户端 3.3 登录cpolar web ui管理界面 3.4 创建公网地址 4.固定公网地址访问 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0…
阅读更多...
Windows系统安全策略设置之本地NTLM重放提权

Windows系统安全策略设置之本地NTLM重放提权

经安全部门研究分析&#xff0c;近期利用NTLM重放机制入侵Windows 系统事件增多&#xff0c;入侵者主要通过Potato程序攻击拥有SYSTEM权限的端口伪造网络身份认证过程&#xff0c;利用NTLM重放机制骗取SYSTEM身份令牌&#xff0c;最终取得系统权限&#xff0c;该安全风险微软并…
阅读更多...
vue3 用xlsx 解决 excel 低版本office无法打开问题

vue3 用xlsx 解决 excel 低版本office无法打开问题

需求背景解决思路解决效果将json导出为excel将table导为excel导出样式 需求背景 原使用 vue3-json-excel &#xff0c;导致在笔记本office环境下&#xff0c;出现兼容性问题 <vue3-json-excel class"export-btn" :fetch"excelGetList" :fields"js…
阅读更多...
国际贸易报关需要向海关提交哪些资料 | 全球数字贸易发展联盟 | 箱讯科技

国际贸易报关需要向海关提交哪些资料 | 全球数字贸易发展联盟 | 箱讯科技

1、进出口货物报关单。一般进口货物应填写一式二份;需要由海关核销的货物&#xff0c;如加工贸易货物和保税货物等&#xff0c;应填写专用报关单一式三份;货物出口后需国内退税的&#xff0c;应另填一份退税专用报关单。 2、货物发票。要求份数比报关单少一份&#xff0c;对货…
阅读更多...
OpenProject 安装迁移

OpenProject 安装迁移

文章目录 1、概要2、备份3、新服务器安装OpenProject4、新服务器安装Postgresql5、旧服务器数据转移到新服务器5.1、转移attachments附件5.2、转移conf配置文件5.3、转移存储库5.4、导入Postgres数据库 6、openproject配置 1、概要 注意&#xff1a;本文仅适用于 DEB/RPM 包安…
阅读更多...
高品质定制线缆厂家推荐：精工电联-打造智能智造的线缆解决方案（线缆定制流程）

高品质定制线缆厂家推荐：精工电联-打造智能智造的线缆解决方案（线缆定制流程）

高品质定制线缆厂家&#xff1a;精工电联-打造智能智造的线缆解决方案&#xff08;定制线缆定制流程&#xff09; 精工电联 在百年未有之大变局的当下&#xff0c;科技发展日新月异的今天&#xff0c;智能制造正在改变着各行各业的生产及人们的生活方式。作为线缆制造领域的领先…
阅读更多...
0220作业

0220作业

C语言实现LED1闪烁 led.h #ifndef __LED_H__ #define __LED_H__//RCC寄存器封装 #define RCC_MP_AHB4_ENSETR (*(volatile unsigned int*)0x50000A28) //寄存器封装//GPIO寄存器封装 typedef struct{volatile unsigned int MODER; //00volatile unsigned int OTYPER; //04vol…
阅读更多...
c++：蓝桥杯中的基础算法1（枚举，双指针）

c++：蓝桥杯中的基础算法1（枚举，双指针）

枚举 基础概念&#xff1a; 枚举&#xff08;Enum&#xff09;是一种用户定义的数据类型&#xff0c;用于定义一个有限集合的命名常量。在C中&#xff0c;枚举类型可以通过关键字enum来定义。 下面是一个简单的枚举类型的定义示例&#xff1a; #include <iostream>enum…
阅读更多...
Spring Bean 的生命周期了解么?

Spring Bean 的生命周期了解么?

Spring Bean 的生命周期基本流程 一个Spring的Bean从出生到销毁的全过程就是他的整个生命周期, 整个生命周期可以大致分为3个大的阶段 : 创建 使用 销毁 还可以分为5个小步骤 : 实例化(Bean的创建) , 初始化赋值, 注册Destruction回调 , Bean的正常使用 以及 Bean的销毁 …
阅读更多...
leetcode 105. 从前序与中序遍历序列构造二叉树【构造二叉树】

leetcode 105. 从前序与中序遍历序列构造二叉树【构造二叉树】

原题链接&#xff1a;105. 从前序与中序遍历序列构造二叉树 题目描述&#xff1a; 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 输入输出描述&…
阅读更多...
ETL快速拉取物流信息

ETL快速拉取物流信息

我国作为世界第一的物流大国&#xff0c;但是在目前的物流信息系统还存在着几大的痛点。主要包括以下几个方面&#xff1a; 数据孤岛&#xff1a;有些物流企业各个部门之间的数据标准不一致&#xff0c;难以实现数据共享和协同&#xff0c;容易导致信息孤岛。 操作繁琐&#x…
阅读更多...
小程序--loading和toast

小程序--loading和toast

一、loading wx.showLoading({})显示loading提示框。wx.hideLoading({})隐藏loading提示框。 title&#xff1a;文字提示内容 mask&#xff1a;是否显示透明蒙层&#xff0c;防止触摸穿透。 更多属性参考showLoading官方文档。 wx.showLoading({title: 加载中...,mask: true }…
阅读更多...
HTML学习笔记——08：表单＜form＞

HTML学习笔记——08：表单＜form＞

HTML <form> 元素表示文档中的一个区域&#xff0c;此区域包含交互控件&#xff0c;用于向 Web 服务器提交信息。 例如&#xff1a;登录页面。 作用&#xff1a;搜集不同类型的用户输入&#xff0c;并向服务器传送数据。 注意&#xff1a;表单本身并不可见&#xff01;…
阅读更多...
Git基本操作（2）

Git基本操作（2）

Git基本操作&#xff08;2&#xff09; 上交文件之后&#xff0c;git文件的变化git cat-file HEAD指针里面有啥文件被修改git statusgit diff 文件名 版本回退&#xff08;git reset&#xff09;撤销回退git reflog 撤销的三种情况还没有addgit checkout -- [file] 已经add还没…
阅读更多...
全志 T527 适配 I2S

全志 T527 适配 I2S

一、背景概念 在 T5 系列芯片中&#xff0c;内置了一个 AudioHub 模块&#xff0c;使用的 是I2S 接口&#xff0c;都跟 AudioHub 关联在一起&#xff0c;此时外挂的声卡若想正常工作&#xff0c;还需要配置 AudioHub 的路由信息。&#xff08;AudioHub 是全志 T527 特有的模块&…
阅读更多...
【Java程序员面试专栏 数据结构】三 高频面试算法题：栈和队列

【Java程序员面试专栏 数据结构】三 高频面试算法题：栈和队列

一轮的算法训练完成后，对相关的题目有了一个初步理解了，接下来进行专题训练，以下这些题目就是汇总的高频题目，因为栈和队列这两哥们结构特性比较向对应，所以放到一篇Blog中集中练习 题目题干直接给出对应博客链接，这里只给出简单思路、代码实现、复杂度分析 题目关键字…
阅读更多...
高考杂志高考杂志社高考编辑部2023年第32期目录

高考杂志高考杂志社高考编辑部2023年第32期目录

高考论坛 高中数学课堂教学中创设有效情境的策略探究 黄进生; 3-5 核心素养为导向的高中物理教学探究 王丽萍; 6-8 高中化学“教、学、评”一体化教学模式的有效应用 陈燕; 9-11《高考》投稿&#xff1a;cn7kantougao163.com 新高考背景下高中英语阅读理解教学…
阅读更多...
xshell安装社区(免费)版本

xshell安装社区(免费)版本

xshell安装社区(免费)版本 官方网址&#xff0c;点击直接跳转&#xff1a;https://www.xshell.com/zh/free-for-home-school/ 1.打开链接之后&#xff0c;先选择 家庭/学校免费 &#xff0c;然后输入名字和邮箱&#xff0c;勾选需要下载的资源&#xff1a; 2.然后邮箱就会收到…
阅读更多...
Dockerfile文件中只指定挂载点会发生什么？

Dockerfile文件中只指定挂载点会发生什么？

当你在VOLUME指令中只指定容器内的路径&#xff08;挂载点&#xff09;而不指定宿主机的目录时&#xff0c;Docker会为该挂载点自动生成一个匿名卷。这个匿名卷存储在宿主机的某个位置&#xff0c;但这个具体位置是由Docker自动管理的&#xff0c;用户通常不需要关心这个存储位…
阅读更多...
JavaScript 设计模式之组合模式

JavaScript 设计模式之组合模式

组合模式 在我们日常中肯呢个会将一个表单用这种模式来创建 const Car function () { } Car.prototype.getName function () { throw new Error("需要重写该方法") } Car.prototype.getPrice function () {throw new Error("需要重写该方法") } const…
阅读更多...
最新文章

Copyright @ 2022~2023