2023河南萌新联赛第（六）场：河南理工大学

目录

A 简单的异或

题目：

解析：

B 这是dp题吗

题目链接：https://ac.nowcoder.com/acm/contest/63602/B

解析：

D 买饼干的小Y

题目：https://ac.nowcoder.com/acm/contest/63602/D

解析：

E 不爱吃早饭的小Y

题目：https://ac.nowcoder.com/acm/contest/63602/E

解析：

H 左右横跳

题目：https://ac.nowcoder.com/acm/contest/63602/H

解析：

I 简单的组合

题目：https://ac.nowcoder.com/acm/contest/63602/I

解析：

J 线代高手

题目：https://ac.nowcoder.com/acm/contest/63602/J

解析：

L 阴晴不定的大橘学长

题目：https://ac.nowcoder.com/acm/contest/63602/L

解析：

A 简单的异或

题目：

  小Y学过异或后觉得这太简单了，但小H认为小Y太天真了，决定考验一下他，出了一道题：
    给出一个数组a，长度为n，分别为a1​,a2​,a3​,...an−1​,an​。以及q次访问，每次给出两个整数 l，r表示区间的左右端点。

    对于每次访问，给出一个整数 x(x<2^31) 使∑i=l r​(x⊕ai​)最大 

输入描述:

第一行一个整数N (1≤N≤10^5)，表示序列的长度
第二行N个整数，表示序列内的元素(1≤ai​<2^31)
第三行一个整数q，表示询问的个数(1≤q≤10^5)

接下来q行，每行两个整数 L,R，表示询问的区间

保证L≤R

输出描述:

对于每次访问输出一个对应的x，若有多个解则输出最小的解

示例1

输入

5
1 2 3 4 5
3
1 2
2 4
3 5

输出

2147483644
2147483645
2147483642

说明

第一个样例中，

第一次访问区间[1,2]

区间内的值为1,2

当x取2147483644即1111111111111111111111111111100（31位二进制）时

x^1+x^2的值最大

解析：

题意就是求一个x , 使得区间内每一个元素与 x异或后的总和最大
先考虑单个元素与 x异或后最大，根据异或的性质，容易得到x 应该和 a的每一位都相反，才能
使得异或值最大。
考虑区间大小大于等于2 ，假如区间内每个元素的二进制第 i位相同 ( 从右往左数 ) ，比如全为1 ，那么
当 x的第 i位取相反值 0时，该位对于最后的总和贡献就是n*2^(i-1)
( 表示元素的个数 ) ，每有一个元素
的二进制第 i位为0 ，该位的贡献就会减少 2^(i-1)
，当有超过n/2的元素该位上为 0时， 的该位上取1 贡献更大
所以贪心考虑 x上每一位取值 0/1的贡献的多少，选择贡献大的即可
区间内第 i 位上 0 的个数与 1 的个数，当 1多时 x的第 i位上取0 ， 0多则取 1。
特别的当 0和 1的数量相同时，因为题目要求输出较小值，取0 即可
暴力计算区间内第 i 位上的 1 个数求解复杂度 利用前缀和优化求解复杂度 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010][40],sum[100010][40];
void solve()
{
	int n,q,l,r;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i][0];
		for(int j=1;j<=31;j++)
		{
			a[i][j]=a[i][0]>>(j-1)&1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=31;j++)
		{
			sum[i][j]+=a[i][j]+sum[i-1][j];
		}
	}
	cin>>q;
	while(q--)
	{
		int x=0;
		int ans;
		cin>>l>>r;
		for(int i=1;i<=31;i++)
		{
			ans=sum[r][i]-sum[l-1][i];
			if(ans<r-l+1-ans)
			x+=1<<(i-1);
		}
		cout<<x<<endl;
	}
}
signed main()
{
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

B 这是dp题吗

题目链接：https://ac.nowcoder.com/acm/contest/63602/B

解析：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=1e3+7;
int a[N][N];
void solve(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) 
	{
		for(int j=0;j<=2*n;j++) 
		a[i][j]=-1e18;
		for(int j=n-i+1;j<=n+i-1;j++)
		cin>>a[i][j];
	}
	for(int i=1;i<=n;i++) 
	{
		for(int j=n-i+1;j<=n+i-1;j++) 
		{
			a[i][j]+=max(a[i-1][j],max(a[i-1][j-1],a[i-1][j+1]));
		}
	}
	int ans=-1e18;
	for(int j=n-k;j<=n+k;j++) 
	ans=max(ans,a[n][j]);
	cout<<ans<<endl;
}
signed main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

D 买饼干的小Y

题目：https://ac.nowcoder.com/acm/contest/63602/D

解析：

先暴力找到力气大于等于1的，之后加上剩下的（不足一的按1计算）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int a[202000];
void solve()
{
	int n,m,x,y,sum=0;
	cin>>n>>m;
	x=n;
	y=m;
	x-=m;
	while(x>0)
	{
		x-=ceil((double)y/2);
		sum++;
		y=ceil(double(y)/2);
		if(y<=2&&x>0)
		{
			sum+=x;
			x=0;
		}
	}
	cout<<sum<<endl;
	return ;
}
signed main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

E 不爱吃早饭的小Y

题目：https://ac.nowcoder.com/acm/contest/63602/E

解析：

对于单堆饼干暴力或者递归求出该堆的SG函数值，如果为0 ，先手必败，反之先手必胜。对于n 堆游戏，总游戏的合就是每个单堆的SG函数的异或和 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
	int n,a,b;
	cin>>n>>a>>b;
    int res=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        x%=(a+b);
        res^=x/a;
    }
    cout<<(res?"C":"Y");
	return ;
}
signed main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

H 左右横跳

题目：https://ac.nowcoder.com/acm/contest/63602/H

解析：

简单的动态规划，题目可以理解为一个 n*m 大小的点阵，每个点上有不同的分数，而一个点上能得 到的分数或积累的分数需要通过操作一直接继承正下方的点的分值，或者通过操作二继承下方任意一列 的间隔 k 行的点的分数并加上所在位置上点的分数 ，因为通过操作二转移得到的分数需要比较 m 列所有的分数，所以每操作一行就记录当前一行所能获得的分数的最大值 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int a[100010],dp[100010];
void solve()
{
	int n,m,k,sum=0,x,num=0,j=1;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
	    {
		cin>>x;
		a[i]=max(a[i],x);
	    }
	}
	dp[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		dp[i]=dp[i-1];
		if(i-k>0)
		dp[i]=max(dp[i],dp[i-k]+a[i]);
	}
	cout<<dp[n]<<endl;
	
}
signed main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

I 简单的组合

题目：https://ac.nowcoder.com/acm/contest/63602/I

解析：

string模拟排序，输出值即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
bool cmp(string x,string y)
{
	return x>y;
}
void solve()
{
	int n,sum=0,num=0;
	cin>>n;
	string a,b,c,d;
	string z[5];
	for(int i=31;i>=0;i--)
	{
		int k=n>>i&1;
		sum++;
		if(sum<=8)
		z[0]+=(k+'0');
		else if(sum<=16)
		z[1]+=(k+'0');
		else if(sum<=24)
		z[2]+=(k+'0');
		else
		z[3]+=(k+'0');
	}
	sort(z,z+4,cmp);
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<8;j++)
		{
			num=num*2+(z[i][j]-'0');
		}
	}
	cout<<num<<endl;
}
signed main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

J 线代高手

题目：https://ac.nowcoder.com/acm/contest/63602/J

解析：

数据范围较小，直接暴力枚举左上角和右下角，如果该子矩阵合法，更新答案即可 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
signed main() {
	IOS
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    vector<int> B(m);
    for (int i = 0; i < m; ++i) {
        cin >> B[i];
    }
    int x;
    cin >> x;
    int maxArea = 0;
    vector<int> prefixSumA(n + 1, 0);
    vector<int> prefixSumB(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefixSumA[i] = prefixSumA[i - 1] + A[i - 1];
    }
    for (int i = 1; i <= m; ++i) {
        prefixSumB[i] = prefixSumB[i - 1] + B[i - 1];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = i; k <= n; ++k) {
                for (int l = j; l <= m; ++l) {
                    int sumA = prefixSumA[k] - prefixSumA[i - 1];
                    int sumB = prefixSumB[l] - prefixSumB[j - 1];
                    int sum = sumA * sumB;
                    if (sum <= x) {
                        int area = (k - i + 1) * (l - j + 1);
                        maxArea = max(maxArea, area);
                    }
                }
            }
        }
    }
    cout << maxArea << endl;
    return 0;
}

L 阴晴不定的大橘学长

题目：https://ac.nowcoder.com/acm/contest/63602/L

解析：

前缀和变形加树状数组维护

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll n,x;
ll a[N],b[N],c[N],s[N];
void add(int x,int d){
	while(x<N){
		c[x]+=d;
		x+=x&-x;
	}
}
ll sum(int x){
	ll res=0;
	while(x){
		res+=c[x];
		x-=x&-x;
	}
	return res;
}
int main(){
	scanf("%lld%lld",&n,&x);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=s[i]=s[i-1]+a[i];
	}
	sort(b,b+n+1);
	ll ans=0;
	for(int i=0;i<=n;i++){
		int k;
		if(i>0){
			k=upper_bound(b,b+n+1,s[i]-x)-b+1-1;
			ans+=sum(k);
		}
		k=lower_bound(b,b+n+1,s[i])-b+1;
		add(k,1);
	}
	printf("%lld\n",ans);
}

下一篇：牛客周赛 Round 7

推荐音乐：呓语

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

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

相关文章

Redisson 分布式锁

Redisson 分布式锁

Redis是基础客户端库&#xff0c;可用于执行基本操作。 Redisson是基于Redis的Java客户端&#xff0c;提供高级功能如分布式锁、分布式集合和分布式对象。 Redisson提供更友好的API&#xff0c;支持异步和响应式编程&#xff0c;提供内置线程安全和失败重试机制。 实现步骤…
阅读更多...
【算法】活用双指针完成复写零操作

【算法】活用双指针完成复写零操作

Problem: 1089. 复写零 文章目录 题目解析算法原理分析找到最后一个复写的位置从后往前进行复写操作 代码展示 题目解析 首先我们来分析一下本题的题目意思 可以看到题目中给到了一个数组&#xff0c;意思是让我们将数组中的零元素都复写一遍&#xff0c;然后将其余的元素向后平…
阅读更多...
云计算在IT领域的发展和应用

云计算在IT领域的发展和应用

文章目录 云计算的发展历程云计算的核心概念云计算在IT领域的应用1. 基础设施即服务&#xff08;IaaS&#xff09;&#xff1a;2. 平台即服务&#xff08;PaaS&#xff09;&#xff1a;3. 软件即服务&#xff08;SaaS&#xff09;&#xff1a; 云计算的拓展应用结论 &#x1f3…
阅读更多...
无涯教程-PHP - 全局变量函数

无涯教程-PHP - 全局变量函数

全局变量 与局部变量相反,可以在程序的任何部分访问全局变量。通过将关键字 GLOBAL 放置在应被识别为全局变量的前面,可以很方便地实现这一目标。 <?php$somevar15;function addit() {GLOBAL $somevar;$somevar;print "Somevar is $somevar";}addit(); ?> …
阅读更多...
NineData中标移动云数据库传输项目（2023）

NineData中标移动云数据库传输项目（2023）

近日&#xff0c;玖章算术NineData智能数据管理平台成功中标《2023年移动云数据库传输服务软件项目》&#xff0c;中标金额为406万。这标志着玖章算术NineData平台已成功落地顶级运营商行业&#xff0c;并在数据管理方面实现了大规模应用实践。 NineData中标2023移动云数据库传…
阅读更多...
LabVIEW硬件在环仿真模拟电路故障分析和特征提取

LabVIEW硬件在环仿真模拟电路故障分析和特征提取

LabVIEW硬件在环仿真模拟电路故障分析和特征提取 与数字电路相比&#xff0c;模拟电路故障分析是一项具有挑战性的任务。这主要是由于模拟分立元件的非线性特性&#xff0c;以及其他因素&#xff0c;包括噪声和内部可访问性的限制。参数故障和灾难性故障是模拟电路中发生的两种…
阅读更多...
使用IDEA把Java程序打包成jar

使用IDEA把Java程序打包成jar

点击左上角File,选择Project Structure 左侧选中Artifacts,点击右侧的号 选择JAR->From modules with dependencies 选择你要运行的main方法所在的类,选好了点击OK Artifacts添加完成后点击右下角OK 在工具栏中找到Build,选择Build Artifacts 刚才创建好的Artifacts,选择Bui…
阅读更多...
阿里云使用WordPress搭建个人博客

阿里云使用WordPress搭建个人博客

手把手教你使用阿里云服务器搭建个人博客 一、免费创建服务器实例 1.1 点击试用 点击试用会需要你创建服务器实例&#xff0c;直接选择默认的操作系统即可&#xff0c;点击下一步 1.2 修改服务器账号密码 二、创建云数据库实例 2.1 免费获取云数据库使用 2.2 实例列表页 在…
阅读更多...
ORB-SLAM系列算法演进

ORB-SLAM系列算法演进

ORB-SLAM算法是特征点法的代表&#xff0c;当前最新发展的ORB-SLAM3已经将相机模型抽象化&#xff0c;适用范围非常广&#xff0c;虽然ORB-SLAM在算法上的创新并不是很丰富&#xff0c;但是它在工程上的创新确实让人耳目一新&#xff0c;也能更好的为AR、机器人的算法实现落地。…
阅读更多...
【笔记】MySQL行转列函数

【笔记】MySQL行转列函数

GROUP_CONCAT()函数 创建表person_info&#xff0c;并插入数据 CREATE TABLE person_info (id bigint(20) NOT NULL AUTO_INCREMENT,name varchar(100) DEFAULT NULL,family varchar(100) DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB AUTO_INCREMENT8 DEFAULT CHARSETutf8;…
阅读更多...
测试驱动开发（TDD）

测试驱动开发（TDD）

测试驱动开发&#xff08;TDD&#xff09; 本篇文章简单叙述一下什么是测试驱动开发&#xff0c;以及怎么进行测试驱动开发&#xff01; TDD &#xff08;Test Driven Development&#xff09;&#xff1a;&#xff08;源于极限编程&#xff08;XP&#xff09;&#xff09;在不…
阅读更多...
gitee远程仓库——Git常用远程仓库托管服务

gitee远程仓库——Git常用远程仓库托管服务

远程仓库 我们的代码不能总是放在本地&#xff0c;因为总是放在本地&#xff0c;一旦电脑出现故障&#xff0c;数据将丢失&#xff0c;怎么共享呢&#xff1f;这里我们需要一个服务器&#xff0c;我们可以把代码放到服务器上&#xff0c;然后让别人下载&#xff0c;这样我们既…
阅读更多...
【Apollo学习笔记】——规划模块TASK之PATH_BORROW_DECIDER

【Apollo学习笔记】——规划模块TASK之PATH_BORROW_DECIDER

文章目录 前言PATH_BORROW_DECIDER功能简介PATH_BORROW_DECIDER相关配置PATH_BORROW_DECIDER总体流程PATH_BORROW_DECIDER相关子函数IsNecessaryToBorrowLaneIsBlockingObstacleFarFromIntersectionIsNonmovableObstacleCheckLaneBorrow 参考 前言 在Apollo星火计划学习笔记—…
阅读更多...
微信小程序 echarts 画多个横向柱状图

微信小程序 echarts 画多个横向柱状图

然后是json {"usingComponents": {"ec-canvas": "../../common/ec-canvas/ec-canvas"},"navigationBarTitleText": "主题活动" } ec-canvas获取方式 在链接里下载代码 然后copy ec-canvas文件夹到自己的项目 https://gi…
阅读更多...
长胜证券：越南首富，又火了！旗下汽车股市值盘中超越比亚迪！

长胜证券：越南首富，又火了！旗下汽车股市值盘中超越比亚迪！

当地时刻8月22日&#xff0c;美股三大股指涨跌纷歧&#xff0c;其中&#xff0c;道指跌0.51%&#xff0c;标普500指数跌0.28%&#xff0c;纳斯达克指数涨0.06%。 异动股方面&#xff0c;8月22日周二&#xff0c;越南电动轿车出产商VinFast Auto ADR盘中上涨超越167%&#xff0c…
阅读更多...
Python 合并多个 PDF 文件并建立书签目录

Python 合并多个 PDF 文件并建立书签目录

今天在用 WPS 的 PDF 工具合并多个文件的时候&#xff0c;非常不给力&#xff0c;居然卡死了好几次&#xff0c;什么毛病&#xff1f;&#xff01; 心里想&#xff0c;就这么点儿功能&#xff0c;居然收了我会员费都实现不了&#xff1f;不是吧…… 只能自己来了&#xff0c;…
阅读更多...
职业学院物联网实训室建设方案

职业学院物联网实训室建设方案

一、概述 1.1专业背景 物联网&#xff08;Internet of Things&#xff09;被称为继计算机、互联网之后世界信息产业第三次浪潮&#xff0c;它并非一个全新的技术领域&#xff0c;而是现代信息技术发展到一定阶段后出现的一种聚合性应用与技术提升&#xff0c;是随着传感网、通…
阅读更多...
Googel Earth Engine 配置Python 环境

Googel Earth Engine 配置Python 环境

1. 安装并配置python环境 此处不再赘述 2. 安装 earthengine-api pip install earthengine-api C:\Users\xixi>pip install earthengine-api Collecting earthengine-apiUsing cached earthengine_api-0.1.363-py3-none-any.whl Requirement already satisfied: google-c…
阅读更多...
数据结构 - 线性表的定义和基本操作

数据结构 - 线性表的定义和基本操作

一、定义 线性表是具有相同特性的数据元素的一个有限序列。 线性表&#xff1a; 由n(n≥0)个数据元素&#xff08;结点&#xff09;组成的有限序列。线性表中数据元素是一对一的关系&#xff0c;每个结点最多有一个直接前驱&#xff0c;和一个直接后继 二、线性表的基本操作 …
阅读更多...
无涯教程-PHP - 条件判断

无涯教程-PHP - 条件判断

if... elseif ... else和switch语句用于根据不同条件进行判断。 您可以在代码中使用条件语句来做出决定&#xff0c; PHP支持以下三个决策语句- if ... else语句 - 如果要在条件为真时执行&#xff0c;而在条件不为真时执行另一个代码&#xff0c;请使用此语句 els…
阅读更多...
最新文章

Copyright @ 2022~2023