IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 牛客练习赛96 (A - C)题解 -> 正文阅读

[C++知识库]牛客练习赛96 (A - C)题解

牛客练习赛96比赛地址

A – 小y的平面

签到题,将所有的坐标按照左端点排序,然后遍历一遍查有没有纵坐标递减的情况,如果没有答案为YES, 有答案为NO (这题数据应该是出水了,不用排序也能过)

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e6 + 10;
 
struct Node{
    int x, y;
}a[N];
 
bool cmp(Node u, Node v)
{
    if(u.x != v.x) return u.x < v.x;
    else return u.y < v.y;
}
 
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i].x >> a[i].y;
    }
     
    sort (a + 1, a + 1 + n, cmp);
     
    for (int i = 1; i < n; i ++ ){
        if(a[i].y > a[i + 1].y){
            cout << "NO" << endl;
            return 0;
        }
    }
     
    cout << "YES" << endl;
}

B – 小y的树

最容易想到的应该是按层枚举每层提供的权值,但是这样太复杂了。这里提供一种更简单的方法 – 计算每条边经过的次数,即位答案。

用最简单的四层满二叉树来举例子:
在这里插入图片描述要计算一条边的经过次数, 即为 该边以下所有节点的个数 * 除了该边以下的所有节点的个数

例如 :
第二层所有边经过次数 = 7 * 8 * 2 = 112
第三层所有边经过次数 = 12 * 3 * 4 = 144
第四层所有边经过次数 = 1 * 14 * 8 = 112

用sum数组记录一个前缀和 表示前i层所有节点的个数
用cnt数组记录每一层的节点个数

而我们可以观察到 第i层的边以下所有的点就等于sum[n - i + 1]
所以每一层所有边提供的权值为 : cnt[i] * (sum[n] - sum[n - i + 1]) * sum[n - i + 1]

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;
ll cnt[N] ,sum[N];

int main()
{
	int n, k;
	cin >> n >> k;
	cnt[1] = 1, sum[1] = 1;
	for (int i = 2; i <= n; i ++ ){
		cnt[i] = (cnt[i - 1] * k) % mod;
		sum[i] = (sum[i - 1] + cnt[i]) % mod;
	}
	
	long long ans = 0;
	for (int i = 2; i <= n; i ++ ){
		ans += cnt[i] % mod * (sum[n] - sum[n - i + 1] + mod) % mod * sum[n - i + 1];
        ans %= mod;
	}
	
	cout << ans << endl;
}

C – 小y的序列

一道RMQ二分查询的题目,将RMQ算法掌握之后这题就很简单

该题的一个性质:固定左端点后,右端点往后移,区间内最大值减最小值是单调递增的

我们遍历固定每个左端点 i,去查找从左端点开始, 二分查找最大值减最小值为k的右端点r,然后r - i就为区间个数

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, k;
int a[N];
int fx[N][30], fi[N][30];

void init()
{	
	for (int j = 1; j < 22; j ++ ){
		for (int i = 1; i + (1 << j) - 1 <= n; i ++ ){
			fx[i][j] = max(fx[i][j - 1], fx[i + (1 << (j - 1))][j - 1]);
			fi[i][j] = min(fi[i][j - 1], fi[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int check(int l, int r)
{
	int p = log2(r - l + 1);
	int s = max(fx[l][p], fx[r - (1 << p) + 1][p]) - min(fi[l][p], fi[r - (1 << p) + 1][p]);
    return s;
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i ++ ){
		cin >> a[i];
		fx[i][0] = a[i], fi[i][0] = a[i];
	} 
	
    init();
    
	long long ans = 0;
	for (int i = 1; i <= n; i ++ ){
		int l = i, r = n;
		while (l < r){
			int mid = l + r >> 1;
			if(check(i, mid) < k) l = mid + 1;
			else r = mid;
		}
		
		int left = l;
		if(check(i, left) != k) continue;
		
		l = i, r = n;
		while (l < r){
			int mid = l + r + 1 >> 1;
			if(check(i, mid) <= k) l = mid;
			else r = mid - 1;
		}
		ans += l - left + 1;
	}
	
	cout << ans << endl;
}
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-02-28 15:10:05  更:2022-02-28 15:12:05 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/24 8:03:03-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码