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

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

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

一个四位的三进制整数，从低到高位，标为 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元起，快前往官网查看详情吧