第五届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−1b>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)}x4x3x2x1(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