牛客编程巅峰赛S2第1场 - 青铜&白银&黄金
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)
本来人就菜，还好久好久没有做过题了，只通过了一道，问题很多。复盘一下。
A 最小差值
https://ac.nowcoder.com/acm/contest/9004/A
给你一个数组aa，请你求出数组a中任意两个元素间差的绝对值的最小值。
A.1 比赛时AC (现已不能AC，测试数据被改了)
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;
}
};比赛时可以AC，但后来测试数据改了，比赛结束后已经不能通过，只能90.91。
问题1. 输入的a是引用，而不是const，没必要再复制一份才排序。
问题2. 最小值的初值当然可以取abs(a[0]-a[1])，但对于int更简单的方式是INT_MAX。
问题3. vector容器不用非得用迭代器，当数组用就行了。
问题4. 虽然返回值是int但计算中可能会溢出，后面测试数据改了就暴露了这个问题。
A.2 听讲解后写的 （未来以这个为准即可）
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;
}
};- 为了解决问题4，换用long long，为了简便可以用typedef起个别名。
- 与 INT_MAX 类似 long long 的上限为 LLONG_MAX。
- 不用写if判断谁小，直接用min函数一步到位。
- 写1的话，参与运算还是会出错，long long 中要写 1ll。
- 返回的时候再把 long long 转回int
A.3 what if 强行修改比赛时的版本
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;
}
};- 主要是为了避免溢出，把d,t类型设置成long long还有读取的 *i *(i+1) 转换成 long long。
- 返回时转换成int。
B Tree IV
https://ac.nowcoder.com/acm/contest/9004/B
给出一棵有个结点的标准的完全二叉树（即，若父结点编号为
，则它的两个子结点的编号分别为
和
），定义每个结点的价值为
，即每个点的编号乘以每个点的深度（深度即为从根结点到这一结点最短路径经过的点的个数，定义根结点1的深度为1）。
请你求解这棵树中每个结点的价值和（由于答案可能会很大，请你对998244353取模），即
完全二叉树：若设二叉树的深度为，除第
层外，其它各层
的结点数都达到最大个数，第
层所有的结点都连续集中在最左边。
例如（图为一棵标准的完全二叉树）：
B.1 比赛时一直有错
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;
}
};问题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。
B.2 听讲解后写的
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%Mod*dep%Mod;
sum=(sum+layer)%Mod;
dep++;
}
return sum;
}
};- typedef const 更直观。
- for 循环的结构，不用单独计算层数，一个计数器累计深度即可，更直观。
- 注意等差数列先乘起来保证是偶数再除2，不然就按整除***出错。
- 乘深度前先取个余防止溢出。
- 等差数列先乘起来取余再除2貌似会出错，有人说是精度打折了，不是很懂。？？？
B.3 强行修改比赛时的代码
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))%998244353*i%998244353;
}else{
sum+=((((1ll<<(i-1))+n)*(n-((1ll<<(i-1))-1))/2))%998244353*i%998244353;
}
sum=sum%998244353;
}
return sum;
}
};- 换成1ll。
- 注意取余问题，很有意思，这里除2再取余就没问题。？？？
C 牛牛组数
https://ac.nowcoder.com/acm/contest/9004/C
牛牛现在有一个长度为n的只包含数字1-9的字符串x，牛牛想用这n个数字组成k个数。这k个数每个数至少要用字符串x中的一个数字，字符串x中的每个位置的字符要在这k个数中出现一次。牛牛想知道这k个数的和最大是多少。
组成数字的定义如下：
比如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
C.1 比赛时的代码
太惨了，比赛就没做到这道题。
C.2 听了讲解后的代码
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;
}
};听了讲解所以直接写出来了。贪心法。
各位数字由大到小，拆成一个最长的数和一堆小的一位数。
原来总共n位数，拆成k个数。
最大的数只要留n-k+1位就好了，刚好是x.size-k到0。
剩下的全加到个位数上进位即可。
28行一开始，从桶里取数，桶中剩下的忘记--了，所以进了死循环，改了就对了。
讲解的思路很流畅，不用直接存到数组中再排序，用桶就会简单很多。
从高位开始存数据的思路很重要。
进位计算很经典，得记一下。
京公网安备 11010502036488号