【题解】牛客小白月赛22

A - 操作序列

模拟题,因为是个模拟,所以就一模到底,索性将输入也变成字符串模拟了。
有一些细节的地方处理要小心,可以离线下来胡搞,也可以平衡树在线。

我的解法

B - 树上子链

树的直径
树的直径有很多种求法,先将这棵树改成有根树

代表从结点到以其为根的子树中任意一个点的路径最大值

节点的点权,节点的第个儿子的编号
则动态转移方程为

我的解法

C - 交换游戏

Dfs乱搞一下即可,可以将这个字符串看作是一个二进制串,把所有的情况先处理一下,然后对应询问直接输出即可。

我的解法

D - 收集制片

因为最多只有10片纸片,所以大可枚举所有的收集顺序,然后在其中取一个最小值。
状压就更好了。
我的数据造的有问题,我比赛结束后才发现这个问题,输入格式不对,现在已经订正了。

我的解法

E - 方块涂色

可以用总的个数,减去涂色的行数和列数,然后再加上重合的部分。

我的解法

F - 累乘数字

先输出n,然后紧跟着输出2d个0即可。

我的解法

G - 仓库选址

简要题意是找到一个位置,使得其它所有位置上的数乘以两个位置之间的距离的总和最小。
直接暴力枚举每一个位置然后取一个最小值即可。

我的解法

H - 货物种类

每次选择一段区间放入物品,问所有操作完成后物品种类最多的位置是几。
区间操作,只有在最后有一次询问
所以很显然可以用差分进行求解
差分对于每个位置维护一个数组,最后统计更新答案
当然,也可以用某些数据结构来解。

我的解法

I - 工具人

先计算从原点到该点线段的角度,以及从原点开始的一条线相对于该点<=d的角度应在哪个角度间隔(三角形)内。
对所有间隔进行排序创建循环列表,在所有可能的位置分解列表,使其变为线性,然后对每个线性列表用贪心的思想进行求解。
排序时,要注意浮点比较。

我的解法

J - 计算 A + B

没有和大家说清楚前导零的问题,对不起
这个题定位是签到题,简单的字符串模拟一下即可
还要注意一下高精

我的解法

全部评论
A的读入其实可以读入一个数后读入一个字符判断是不是空格
3 回复 分享
发布于 2020-02-22 22:15
J好像这样写更简单一点(eval ORZ!)
2 回复 分享
发布于 2020-02-22 22:55
前排资瓷~~~
2 回复 分享
发布于 2020-02-22 22:10
好像破案了,t并没有保证>=1,题解代码都failed了。出题人出来挨打
1 回复 分享
发布于 2020-02-22 23:58
请问A题真的保证t是正整数吗,我算出的t,然后assert(t>=1)failed了
1 回复 分享
发布于 2020-02-22 23:39
D数据输入格式有问题,现在已经订正了,不好意思
1 回复 分享
发布于 2020-02-22 23:31
D题收集纸片,每次开始前memset了所有的点坐标,只过了70%,去掉就100%了。一脸懵逼
1 回复 分享
发布于 2020-02-22 23:20
G题官方题解时间复杂度是O(T*n^2*m^2),极限情况下是1e9的数据量,居然这也能过吗...... 如果把行列分开来求和,预处理一下,可以使时间复杂度降为O(T*n*m*max(n,m)),极限情况正好1e7的数据量可以通过。
点赞 回复 分享
发布于 2020-03-01 15:00
请问一下,B题我照着题解写,几乎都是一模一样了,通过率90%,看了好久不知道哪有问题
点赞 回复 分享
发布于 2020-02-24 17:11
请问下大佬,b的这个“最大链”的意思是类似于一个树的直径从头到尾的权值和,而不是从输入时候的根节点到尾节点的最大权值和么。。。😂😂
点赞 回复 分享
发布于 2020-02-23 14:27
这样的两个三角形
点赞 回复 分享
发布于 2020-02-23 09:54
I题 已知本轮病毒的具***置,并且若病毒距离牛能激光射线的距离不大于d就会被消灭 那么消灭病毒的范围不应该是一个矩形+两个半圆嘛,题解的三角形内指的是什么
点赞 回复 分享
发布于 2020-02-23 09:32
G题暴力真的不会炸?不是数据不强?。。。。
点赞 回复 分享
发布于 2020-02-23 08:38
J题过0.0%好迷,大佬看看这是为啥 #include<bits/stdc++.h> using namespace std; string ff(string s1,string s2){     int idx1=s1.length()-1,idx2=s2.length()-1;     int res=0;     string ans="";     while(idx1>=0||idx2>=0){         int num1=idx1>=0?s1[idx1]-'0':0;         int num2=idx2>=0?s2[idx2]-'0':0;         int plus=num1+num2+res;         res=plus/10;         ans+=plus%10+'0';         idx1--;idx2--;     }     reverse(ans.begin(),ans.end());     int index=0;     while(ans[index]=='0') index++;//去前置0     if(index==ans.length()) return "0";     return ans.substr(index,ans.length()-index); } void Solve(){     string ss;cin>>ss;     int n=ss.length();     int idx=-1;     int cnt=0;     for(int i=0;i<n;i++)         if(ss[i]=='+') cnt++,idx=i;     if(idx==0||idx==n-1||cnt>1){         cout<<"skipped"<<endl;return;     }          string l=ss.substr(0,idx);//取加号左右     string r=ss.substr(idx+1,n-1-idx);     cout<<ff(l,r)<<endl;     return; } int main(){     int T;cin>>T;     while(T--) Solve(); }
点赞 回复 分享
发布于 2020-02-22 23:27
B题里面 f(i) 指的是什么啊?
点赞 回复 分享
发布于 2020-02-22 23:11
stO xiao_hei_hei
点赞 回复 分享
发布于 2020-02-22 22:35
  D题 先求各个点之间最短哈密顿距离,然后累加,然后再求起点到远的哈密顿距离,就是出发距离+结束距离,这样可以吗?wa了,不知道思路对不对,感觉没问题
点赞 回复 分享
发布于 2020-02-22 22:29
能看数据吗?我用java有两个题目都说数组越界,好奇怪不知道错在哪里了
点赞 回复 分享
发布于 2020-02-22 22:18

相关推荐

07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
7
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务