<!-- wp:heading {"level":1} -->
<h1>牛客编程巅峰赛S2第1场 - 青铜&白银&黄金</h1>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>https://ac.nowcoder.com/acm/contest/9004
2020-11-17 20:00:00 至 2020-11-17 21:00:00
时长: 1小时
AC 1/3
Rank 459/853
罚时 00:26:10
A (719/3034) 00:16:10 (-2)
B (222/1915) (-8)
C (173/523)</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>本来人就菜，还好久好久没有做过题了，只通过了一道，问题很多。复盘一下。</p>
<!-- /wp:paragraph -->
<!-- wp:heading -->
<h2>A 最小差值</h2>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>https://ac.nowcoder.com/acm/contest/9004/A
给你一个数组a，请你求出数组a中任意两个元素间差的绝对值的最小值。$latex (2\leq len(a) \leq 10^3)$</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>A.1 比赛时AC (现已不能AC，测试数据被改了)</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求最小差值
* @param a int整型vector 数组a
* @return int整型
*/
int minDifference(vector<int>& a) {
// write code here
vector<int> v(a);
sort(v.begin(),v.end());
int d=abs(a[0]-a[1]);
for(vector<int>::iterator i=v.begin();i!=v.end()-1;i++){
int t=abs(i-(i+1));
if(t<d)d=t;
}
return d;
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>比赛时可以AC，但后来测试数据改了，比赛结束后已经不能通过，只能90.91。
问题1. 输入的a是引用，而不是const，没必要再复制一份才排序。
问题2. 最小值的初值当然可以取abs(a[0]-a[1])，但对于int更简单的方式是INT_MAX。
问题3. vector容器不用非得用迭代器，当数组用就行了。
问题4. 虽然返回值是int但计算中可能会溢出，后面测试数据改了就暴露了这个问题。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>A.2 听讲解后写的 （未来以这个为准即可）</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求最小差值
* @param a int整型vector 数组a
* @return int整型
*/
typedef long long LL;
int minDifference(vector<int>& a) {
// write code here
sort(a.begin(),a.end());
LL m=LLONG_MAX;
for(int i=1;i<a.size();i++){
m=min(m,1ll*abs(a[i]-a[i-1]));
}
return (int)m;
}
};<!-- /wp:code -->
<!-- wp:list {"ordered":true} -->
- 为了解决问题4，换用long long，为了简便可以用typedef起个别名。
- 与 INT_MAX 类似 long long 的上限为 LLONG_MAX。
- 不用写if判断谁小，直接用min函数一步到位。
- 写1的话，参与运算还是会出错，long long 中要写 1ll。
- 返回的时候再把 long long 转回int
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求最小差值
* @param a int整型vector 数组a
* @return int整型
*/
int minDifference(vector<int>& a) {
// write code here
vector<int> v(a);
sort(v.begin(),v.end());
long long d=abs(a[0]-a[1]);
for(vector<int>::iterator i=v.begin();i!=v.end()-1;i++){
long long t=abs((long long)(i)-(long long)((i+1)));
if(t<d)d=t;
}
return (int)d;
}
};<!-- /wp:code -->
<!-- wp:list {"ordered":true} -->
- 主要是为了避免溢出，把d,t类型设置成long long还有读取的 i (i+1) 转换成 long long。
- 返回时转换成int。
给出一棵有$latex n$个结点的标准的完全二叉树（即，若父结点编号为$latex x$，则它的两个子结点的编号分别为$latex x \times 2$和$latex x \times 2 + 1$），定义每个结点的价值为$latex xdep_x$，即每个点的编号乘以每个点的深度（深度即为从根结点到这一结点最短路径经过的点的个数，定义根结点1的深度为1）。</p> <!-- /wp:paragraph --> <!-- wp:paragraph --> <p>请你求解这棵树中每个结点的价值和（由于答案可能会很大，请你对998244353取模），即$latex \sum\limits_{i=1}^{n}idep_i \ mod\ 998244353 $</p> <!-- /wp:paragraph --> <!-- wp:paragraph --> <p>完全二叉树：若设二叉树的深度为$latex k$，除第 $latex k$ 层外，其它各层 $latex (1～k-1)$ 的结点数都达到最大个数，第 $latex k$ 层所有的结点都连续集中在最左边。
例如（图为一棵标准的完全二叉树）：
</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>B.1 比赛时一直有错</h3>
<!-- /wp:heading -->
<!-- wp:code -->class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n long长整型 表示标准完全二叉树的结点个数
* @return long长整型
*/
long long tree4(long long n) {
// write code here
long long m=n;
long long l=1;
while(m>1){
m=m>>1;
l++;
}
long long excess=n-(1<<l);
long long sum=0;
for(long long i=1;i<=l;i++){
if(i<=l-1){
sum+=(i(((1<<(i-1))+((1<<i)-1))(1<<(i-1))/2))%998244353;
}else{
sum+=(i(((1<<(i-1))+n)(n-((1<<(i-1))-1))/2))%998244353;
}
sum=sum%998244353;
}
return sum;
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>问题1. excess用到了n，但excess本身没用到，也就不用把n再复制成一个m了。啊后面用到了，没问题，excess删了就行。
问题2. long long 可以像A题一样，typedef起个别名。
问题3. l其实用不到long long 但也没问题吧。
问题4. 计算每层最左最右节点编号时，太不直观了，不如定义两个变量出来，也可以更方便的处理不完全的层数。
问题5. sum累加的取余了，累加后的结果没有取余，会导致溢出。啊后面也取余了，没问题。
问题6. 可以把取余用到的大整数定义成常量啊。
问题7. i*等差数列求和可能溢出了，不如先取个余。
问题8. 1<<i 不对 得 1ll<<i。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3>B.2 听讲解后写的</h3>
<!-- /wp:heading -->
<!-- wp:code -->
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n long长整型 表示标准完全二叉树的结点个数
* @return long长整型
*/
typedef long long LL;
const LL Mod=998244353;
long long tree4(long long n) {
// write code here
LL layer=0,sum=0,x,y,dep=1;
for(LL i=1;i<=n;i*=2){
x=i;
if(i*2<=n){
y=i*2-1;
}else{
y=n;
}
layer=((x+y)(y-x+1))/2%Moddep%Mod;
sum=(sum+layer)%Mod;
dep++;
}
return sum;
}
};<!-- /wp:code -->
<!-- wp:list {"ordered":true} -->
- typedef const 更直观。
- for 循环的结构，不用单独计算层数，一个计数器累计深度即可，更直观。
- 注意等差数列先乘起来保证是偶数再除2，不然就按整除法会出错。
- 乘深度前先取个余防止溢出。
- 等差数列先乘起来取余再除2貌似会出错，有人说是精度打折了，不是很懂。？？？
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n long长整型 表示标准完全二叉树的结点个数
* @return long长整型
*/
long long tree4(long long n) {
// write code here
long long m=n;
long long l=1;
while(m>1){
m=m>>1;
l++;
}
long long excess=n-(1<<l);
long long sum=0;
for(long long i=1;i<=l;i++){
if(i<=l-1){
sum+=((((1ll<<(i-1))+((1ll<<i)-1))(1ll<<(i-1))/2))%998244353i%998244353;
}else{
sum+=((((1ll<<(i-1))+n)(n-((1ll<<(i-1))-1))/2))%998244353i%998244353;
}
sum=sum%998244353;
}
return sum;
}
};<!-- /wp:code -->
<!-- wp:list {"ordered":true} -->
- 换成1ll。
- 注意取余问题，很有意思，这里除2再取余就没问题。？？？
比如n=3的字符串x为“121”
如果k=3，那么组成k个数只有{1,1,2}这一种可能,和只有一种可能为4
如果k=2，那么组成k个数的方案有{11,2},{12,1},{21,1}三种可能，和最大为21+1=22
如果k=1，那么组成k个数的方案有{112},{121},{211}三种可能，和最大为211</p> <!-- /wp:paragraph --> <!-- wp:heading {"level":3} --> <h3>C.1 比赛时的代码</h3> <!-- /wp:heading --> <!-- wp:code -->
太惨了，比赛就没做到这道题。class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回最大和的字符串
* @param x string字符串 即题目描述中所给字符串
* @param k int整型 即题目描述中所给的k
* @return string字符串
*/
string Maxsumforknumers(string x, int k) {
// write code here
int num[100010]={0};
int tong[10]={0};
for(int i=0;i<x.size();i++){
tong[x[i]-'0']++;
}
int p=9;
for(int i=x.size()-k;i>=0;i--){
while(p>=0&&!tong[p])p--;
if(tong[p]){
num[i]=p;
tong[p]--;
}
}
while(p>=0){
if(tong[p]){
num[0]+=p;
tong[p]--;
}else{
p--;
}
}
int i;
for(i=0;i<100010;i++){
int tmp=num[i];
num[i]=tmp%10;
num[i+1]+=tmp/10;
if(tmp==0)break;
}
string str;
for(i--;i>=0;i--){
str+=('0'+num[i]);
}
return str;
}
};<!-- /wp:code -->
<!-- wp:paragraph -->
<p>听了讲解所以直接写出来了。贪心法。
各位数字由大到小，拆成一个最长的数和一堆小的一位数。
原来总共n位数，拆成k个数。
最大的数只要留n-k+1位就好了，刚好是x.size-k到0。
剩下的全加到个位数上进位即可。
28行一开始，从桶里取数，桶中剩下的忘记--了，所以进了死循环，改了就对了。
讲解的思路很流畅，不用直接存到数组中再排序，用桶就会简单很多。
从高位开始存数据的思路很重要。
进位计算很经典，得记一下。</p>
<!-- /wp:paragraph -->
