【题解】牛客小白月赛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
前排资瓷~~~
2 回复
分享
发布于 2020-02-22 22:10
联易融
校招火热招聘中
官网直投
J好像这样写更简单一点(eval ORZ!)
2 回复
分享
发布于 2020-02-22 22:55
D题收集纸片,每次开始前memset了所有的点坐标,只过了70%,去掉就100%了。一脸懵逼
1 回复
分享
发布于 2020-02-22 23:20
D数据输入格式有问题,现在已经订正了,不好意思
1 回复
分享
发布于 2020-02-22 23:31
请问A题真的保证t是正整数吗,我算出的t,然后assert(t>=1)failed了
1 回复
分享
发布于 2020-02-22 23:39
好像破案了,t并没有保证>=1,题解代码都failed了。出题人出来挨打
1 回复
分享
发布于 2020-02-22 23:58
能看数据吗?我用java有两个题目都说数组越界,好奇怪不知道错在哪里了
点赞 回复
分享
发布于 2020-02-22 22:18
  D题 先求各个点之间最短哈密顿距离,然后累加,然后再求起点到远的哈密顿距离,就是出发距离+结束距离,这样可以吗?wa了,不知道思路对不对,感觉没问题
点赞 回复
分享
发布于 2020-02-22 22:29
stO xiao_hei_hei
点赞 回复
分享
发布于 2020-02-22 22:35
B题里面 f(i) 指的是什么啊?
点赞 回复
分享
发布于 2020-02-22 23:11
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
G题暴力真的不会炸?不是数据不强?。。。。
点赞 回复
分享
发布于 2020-02-23 08:38
I题 已知本轮病毒的具***置,并且若病毒距离牛能激光射线的距离不大于d就会被消灭 那么消灭病毒的范围不应该是一个矩形+两个半圆嘛,题解的三角形内指的是什么
点赞 回复
分享
发布于 2020-02-23 09:32
这样的两个三角形
点赞 回复
分享
发布于 2020-02-23 09:54
请问下大佬,b的这个“最大链”的意思是类似于一个树的直径从头到尾的权值和,而不是从输入时候的根节点到尾节点的最大权值和么。。。😂😂
点赞 回复
分享
发布于 2020-02-23 14:27
请问一下,B题我照着题解写,几乎都是一模一样了,通过率90%,看了好久不知道哪有问题
点赞 回复
分享
发布于 2020-02-24 17:11
G题官方题解时间复杂度是O(T*n^2*m^2),极限情况下是1e9的数据量,居然这也能过吗...... 如果把行列分开来求和,预处理一下,可以使时间复杂度降为O(T*n*m*max(n,m)),极限情况正好1e7的数据量可以通过。
点赞 回复
分享
发布于 2020-03-01 15:00

相关推荐

点赞 评论 收藏
转发
点赞 7 评论
分享
牛客网
牛客企业服务