第五届B组传智杯初赛题解-创新互联

第一题: 题目背景:

在宇宙射线的轰击下,莲子电脑里的一些她自己预定义的函数被损坏了。

创新互联是一家专业提供南岔企业网站建设,专注与网站设计、做网站H5响应式网站、小程序制作等业务。10年已为南岔众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。

对于一名理科生来说,各种软件在学习和研究中是非常重要的。为了尽快恢复她电脑上的软件的正常使用,她需要尽快地重新编写这么一些函数。

题目描述

具体而言,给定两个整数 a,ba,b,保证 b\neq 0b=0。莲子要实现这样一个函数 \operatorname{fun}(a,b)fun(a,b) 来将 bb 的符号转移到 aa 上。

具体而言,\operatorname{fun}(a,b)=\operatorname{sgn}(b)\times |a|fun(a,b)=sgn(b)×∣a∣。其中,\operatorname{sgn}(b)=\begin{cases}1&b>0\\-1&b<0\end{cases}sgn(b)={1−1​b>0b<0​

换而言之:

  • 如果 bb 是正数,那么 \operatorname{fun}(a,b)=+|a|=|a|fun(a,b)=+∣a∣=∣a∣;
  • 如果 bb 是负数,那么 \operatorname{fun}(a,b)=-|a|fun(a,b)=−∣a∣。
输入格式
  • 共一行两个整数 a,ba,b。
输出格式
  • 共一行一个整数 \operatorname{fun}(a,b)fun(a,b) 的值。
输入输出样例

输入 #1复制

-1 2

输出 #1复制

1

输入 #2复制

0 -4

输出 #2复制

0

输入 #3复制

-12345 -54321

输出 #3复制

-12345
说明/提示

对于全部数据,保证 a,ba,b 在 3232 位有符号整型范围内,并且 b \neq 0b=0。

思路:

这个题签到题,没有什么思路,直接写,就注意一个方面,32位无符号型,最后一个数超过了int类型,需要用long long

代码:
#includeusing namespace std;
typedef long long ll;
int main()
{
	ll a,b;
	cin>>a>>b;
	if(b>0)
	{
		if(a<0)
		a=-a;
	}
	else
	{
		if(a>0)
		a=-a;
	}
	cout<
第二题:  题目背景

【题目背景和题目描述的两个题面是完全等价的,您可以选择阅读其中一部分。】

专攻超统一物理学的莲子,对机械结构的运动颇有了解。如下图所示,是一个三进制加法计算器的(超简化)示意图。

一个四位的三进制整数,从低到高位,标为 x_1,x_2,x_3,x_4x1​,x2​,x3​,x4​。换言之,这个数可以写成 \overline{x_4x_3x_2x_1}_{(3)}x4​x3​x2​x1​​(3)​。把它放在这四个齿轮里,对应箭头指向的数字就是现在这位的数值。

在这种机械式计算机里,我们通过齿轮的啮合来实现数位间的连接。通过不同齿轮半径的比例来确定进制。图中所有浅灰色的小齿轮的半径,比上使用皮带相接的较大齿轮的半径,都是 1:31:3。那么小齿轮每转动一圈,大齿轮就转动 \dfrac{1}{3}31​ 圈,也就是刚好一个数码的角度。

于是,我们通过控制齿轮的半径实现了 33 进制的进位。

如果需要实现三进制加法,则只需要在对应数位拨动对应的数码长度即可。

如下是个例子,实现 \overline{1021}_{(3)}+\overline{0021}_{(3)}=\overline{1112}_{(3)}1021(3)​+0021(3)​=1112(3)​

初始时齿轮的状态如上。

把第一个齿轮拨动一个单位长度,变为如上图所示。

把第二个齿轮拨动两个单位长度,变为如上图所示。读数,得到结果 \overline{1112}_{(3)}1112(3)​。


现在莲子设计了如下图所示的机械结构。对于从左往右数的第 ii 枚齿轮,它上面的浅色小齿轮与第 i+1i+1 枚齿轮上的深色小齿轮的半径之比为 1:(i+2)1:(i+2)。也就是说,第 ii 枚齿轮每转动 11 圈,第 i+1i+1 枚齿轮转过的角度恰好为它上面的一个数码。

莲子想要知道,在这样的特别的进制表示下,给定 a,ba,b,那么计算出的 a+ba+b 的结果是多少。

题目描述

题目背景的问题可以转化为如下描述:

给定两个长度分别为 n,mn,m 的整数 a,ba,b,计算它们的和。

但是要注意的是,这里的 a,ba,b 采用了某种特殊的进制表示法。最终的结果也会采用该种表示法。具体而言,从低位往高位数起,第 ii 位采用的是 i+1i+1 进制。换言之,相较于十进制下每一位的「逢 1010 进 11」,该种进制下第 ii 位是「逢 i+1i+1 进 11」。

下图所示,左边是十进制的竖式加法;右边是这种特殊进制的竖式加法。图中的红色加号表示上一位发生了进位。

输入格式
  • 第一行有两个整数 n,mn,m,分别表示 aa 和 bb 的位数。
  • 第二行有 nn 个整数,中间用空格隔开,从高到低位描述 aa 的每个数码。
  • 第三行有 mm 个整数,中间用空格隔开,从高到低位描述 bb 的每个数码。
输出格式
  • 输出有若干个整数,从高到低位输出 a+ba+b 在这种特殊表示法下的结果。
输入输出样例

输入 #1复制

5 4
3 3 2 1 1
3 2 2 1

输出 #1复制

4 2 1 1 0

输入 #2复制

10 1
10 9 8 7 6 5 4 3 2 1
0

输出 #2复制

10 9 8 7 6 5 4 3 2 1
说明/提示

对于全部数据,保证 1\le n,m\le 2\times 10^51≤n,m≤2×105,从低位往高位数起有 a_i\in[0,i]ai​∈[0,i],b_i\in[0,i]bi​∈[0,i]。请使用 Java 或 Python 语言作答的选手注意输入输出时的效率。

思路: 

就是高精度加法,我这里有个小技巧,让两个数组的位数相同,不够的位数补零,很好理解,直接看代码吧

代码:
#includeusing namespace std;
const int N=1e6;
int a[N],b[N],c[N];
int main()
{
	int n,m;
	cin>>n>>m;
	int maxx=max(m,n);
	for(int i=0;i=0;i--)
	{
		a[i]+=b[i]+ct;
		ct=a[i]/ans;
		c[k++]=a[i]%ans;
		ans++;
	}
	while(ct)
	{
		
		c[k++]=ct%ans;
		ct=ct/ans;
		ans++;
	}
	for(int i=k-1;i>=0;i--)
	printf("%d ",c[i]);
	return 0;
}
第三题:  题目背景

莲子正在研究分子的运动。

每个分子都有一个速度,约定正方向为正,负方向为负。分子的数量极多,速度又并不一致,看上去杂乱无章。于是莲子希望调整部分分子的速度,使得最终分子们看上去整齐。

题目描述

莲子给定了 nn 个整数 a_1,a_2,\cdots a_na1​,a2​,⋯an​,描述每个分子。现在她可以进行至多 mm 次操作(也可以一次也不进行),每次操作可以执行以下两条之一:

  • 选择 ii,满足 a_i=\min_j\{a_j\}ai​=minj​{aj​},然后将 a_iai​ 变为 \max_j\{a_j\}maxj​{aj​}。
  • 选择 ii,满足 a_i=\max_j\{a_j\}ai​=maxj​{aj​},然后将 a_iai​ 变为 \min_j\{a_j\}minj​{aj​}。

现在莲子希望需要最小化最终序列的极差(大值减去最小值的差)。请求出最小的极差。


例如,对于序列 a=\{5,1,4\}a={5,1,4},可以进行如下几次操作:

  • 选择 i=1i=1,满足 a_1=5a1​=5 是当前的大值 55,可以将 a_1a1​ 修改成当前的最小值 11,此时序列变成 \{1,1,4\}{1,1,4};
  • 再选 i=2i=2,满足 a_2=1a2​=1 是当前的最小值 11,可以将 a_2a2​ 修改成当前的大值 44,此时序列变成 \{1,4,4\}{1,4,4}。

这两次操作后得到的序列为 \{1,4,4\}{1,4,4}。大值减去最小值的差为 |4-1|=3∣4−1∣=3。

当然,这种操作方式得到的极差并非最小。最优策略是,先将大值 a_1=5a1​=5 变成目前的最小值 11,再把此时的大值 a_3=4a3​=4 变成目前的最小值 11。此时序列为 \{1,1,1\}{1,1,1},得到的极差 |1-1|=0∣1−1∣=0 是所有策略中最小的。

输入格式
  • 第一行有两个正整数 n,mn,m,分别表示序列的长度和你最多可以进行的操作次数。
  • 第二行有 nn 个整数 aa,描述给定的序列。
输出格式
  • 输出共一行一个整数,表示最优策略下能得到的最小极差。
输入输出样例

输入 #1复制

3 2
5 1 4

输出 #1复制

0

输入 #2复制

8 0
1 2 3 4 5 6 7 8

输出 #2复制

7

输入 #3复制

8 3
1 5 5 5 6 6 9 10

输出 #3复制

4
说明/提示 样例解释

样例 11:\{5,1,4\}\to\{1,1,4\}\to\{1,1,1\}{5,1,4}→{1,1,4}→{1,1,1},极差为 00。
样例 22:\{1,2,3,4,5,6,7,8\}{1,2,3,4,5,6,7,8},什么也做不了,极差为 77。
样例 33:\{1,5,5,5,6,6,9,10\}\to\{10,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,5\}{1,5,5,5,6,6,9,10}→{10,5,5,5,6,6,9,10}→{5,5,5,5,6,6,9,10}→{5,5,5,5,6,6,9,5},极差为 44。

数据范围及约定

对于全部数据,保证 1\le n \le 10^51≤n≤105,0\le m\le10^90≤m≤109,|a_i|\le 10^9∣ai​∣≤109。

思路:

贪心很容易想到,就是进行m次操作,首先当n-1<=m时,这时候你肯定可以把这n个数变成一个一样的数,其次但n-1>m时,你记得你只能处理最小的和大的数,这样想,假如你改变了前i个数,和前j个数,你是怎么改的呢,就是可以先把前i个数改成大的数,然后把这i+1的数改成第二个大的数,依次递加,总共操作了i+j+min(i,j)次。说的过于抽象,可以自己实验几下。考试时,思路我想到了,但是一直运行超时,还因为服务器问题,这道题wa了六次,就在刚刚突然想到了,双指针啊。

代码:
#include#include
using namespace std;
const int N=1e5+10;
typedef long long ll;
int a[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i=i;j--)//为什么让j=y,这样考虑,你的i增加了,你的j肯定要在上一次的y的基础上减小 
            {
                if(i+min(i,j)+j<=m)
                {
                    minn=min(minn,(ll)a[n-j-1]-a[i]);
                    y=j;
                    break;
                }
            }
        }
        printf("%lld",minn);
        
    }return 0;
}
第四题:  题目背景

梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析,为此她时常抱怨自己学不会,想退课。

但是如果现在退掉的话这学期的学分就不够啦,因此她根据“梦中”的经历,“胡诌”了一个简单到不现实的市场模型,并依据这个模型编起了 essay。为了方便地编出图表,她需要写一个程序来查询每个时刻的市场贸易差。

题目描述

市场每一天的贸易差可以视为一个有周期性规律的数列 aa:\color{red}[0],\color{blue}[0,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak 0],\color{red}[0,\allowbreak 1,\allowbreak 2,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak -2,\allowbreak -1,\allowbreak 0],\allowbreak \color{blue}[0,\allowbreak 1,\allowbreak 2,\allowbreak 3,\allowbreak 2,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak -2,\allowbreak -3,\allowbreak -2,\allowbreak -1,\allowbreak 0]\dots[0],[0,1,0,−1,0],[0,1,2,1,0,−1,−2,−1,0],[0,1,2,3,2,1,0,−1,−2,−3,−2,−1,0]… 具体而言,aa 可以被分为无穷段,第 ii 段的内容为 \{0,\allowbreak 1,\allowbreak \cdots,\allowbreak i,\allowbreak i-1,\allowbreak \cdots,0,\allowbreak -1,\allowbreak \cdots,\allowbreak -i,\allowbreak -i+1,\allowbreak \cdots 0\}{0,1,⋯,i,i−1,⋯,0,−1,⋯,−i,−i+1,⋯0}。如下图所示,是将 aa 数列内的前一些点绘制在坐标轴上的情况:

现在梅莉对市场发起了 qq 次询问,每次她会给定一个 kk,希望求出 a_kak​ 是多少。

输入格式
  • 第一行有一个正整数 qq,表示询问次数。
  • 接下来 qq 行,每行一个正整数 kk,描述每次询问。
输出格式
  • 输出共 qq 行。对于每次询问,输出对应的结果。
输入输出样例

输入 #1复制

9
1
10
100
1000
10000
100000
1000000
10000000
100000000

输出 #1复制

0
1
6
-9
-11
-128
406
1629
5154
说明/提示

对于所有数据,1 \leq q \leq 10^51≤q≤105,1 \leq k \leq 4\times 10^{18}1≤k≤4×1018。

思路:

这题就是找规律吧,我试了几组数字,发现2*(n+1)**2-(n+1)的规律,然后根据二分找到n(记得用二分查找,刚开始没有用二分,成功超时,罚时加一),然后研究规律,直接上代码吧

代码:
#includeusing namespace std;
typedef long long ll;
int main()
{
	int q;
	cin>>q;
	while(q--)
	{
		ll x;
		scanf("%lld",&x);
		ll l=0,j=3e9;
		while(l>1;
			if(2*mid*mid-mid>=x)j=mid;
			else l=mid+1;
		}
		ll n=l-1;
		x=x-2*n*n+n;	
		if(2*n+1>=x)
			{
				if(x==1||x==2*n+1)
			     printf("0\n");
			    else if(n+1>=x)
			    {
			    	printf("%d\n",x-1);
				}
				else
				{
					x=2*n+1-x;
					printf("%d\n",x);
				}
			}
			else
			{
				if(x<=3*n+1)
				{
					printf("%d\n",-(x-2*n-1));
				}
				else
				{
					printf("%d\n",-(4*n+1-x));
				}
			}
		}
		
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页标题:第五届B组传智杯初赛题解-创新互联
分享网址:http://scyanting.com/article/dogcgh.html