牛客编程巅峰赛S2赛季第2场题解与参考代码
比赛链接：
初级场A题 热心的牛牛：
不妨设牛牛获得x枚糖果，那么牛牛的朋友每人需要至少获得x+1枚糖果。那么这种情况下需要的总糖果数为x+n(x+1)，这个总数需要小于等于k。因此有x+n(x+1)<=k。整理得到(1+n)x+n<=k，合法的x值满足x<=(k-n)/(n+1)，因此输出该式下取整就是答案。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回牛牛能吃到的最多糖果数
* @param n long长整型
* @param k long长整型
* @return long长整型
*/
long long Maximumcandies(long long n, long long k) {
return (k-n)/(n+1);
}
}; 初级场B题&高级场A题 牛牛切木棒：
这是比较经典的题目，使用斐波那契数列作为边长，可以使得任意三个数字不能作为一个三角形的边长。从小到大使用斐波那契数列的各项，就可以将木棒拆成若干个小木棒，任意三条木棒不能构成三角形。
class Solution {
public:
/**
*
* @param a long长整型 木棒的长度
* @return int整型
*/
long long f[100];
int stick(long long a) {
f[1]=1;
f[2]=1;
for(int i=3;f[i-1]<=1e18;++i){
f[i]=f[i-1]+f[i-2];
}
for(int i=1;;++i){
if (a<f[i]) return i-1;
a-=f[i];
}
}
}; 根据完全k叉数的性质可以推导出，或者可以观察出bfs序为i(i>0)的点，其父结点在bfs序中的编号为(i-1)/k。利用这个性质扫描一遍即可完成统计。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param k int整型 表示完全k叉树的叉数k
* @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
* @return long长整型
*/
long long tree2(int k, vector<int>& a) {
long long ans=0;
for(int i=1;i<a.size();++i) ans+=a[i]^a[(i-1)/k];
return ans;
}
}; 高级赛C题 数据分析：
这题我用了稍微复杂的方法，当做是抛砖引玉提供了另一种思路。思路大致是，（假设题目给定的输入是数组numbers）按照numbers中的数字大小从小到大考虑并维护答案。一开始不妨先当做numbers中所有数字都被拿掉了，然后按数字从小到大的顺序逐个放回numbers中的数字，那么某一时刻，numbers中只会存在一部分元素，在numbers中形成若干个连续段。假设现在从小到大考虑完的元素是numbers[i]，那么该时刻numbers中只会存在所有<=numbers[i]的所有数，之后考虑放入将numbers中所有数排序后的后继x，那么放入x后，可能会将其左右的两段连接成一个连续段。注意到目前放入numbers中的数都不大于x，因此当前numbers中存在的数形成的任何一个子区间最大值都不会大于x。考虑x所在的那么连续段，不妨设这个连续段的长度为l，那么x可以更新长度小于等于l的区间的区间最大值的答案，也就是说长度小于等于l的区间的区间最大值的最小值小于等于x。因此从小到大插入numbers中的元素，可以得到若干个上述ans[1..l]<=x的信息。最后利用这些信息就可以计算出ans。插入元素与合并段的代码具体实现可以采用并查集，或者也可以直接采用类似链表的方式维护。
struct nod{
int v,x;
inline bool operator <(const nod &a)const{
return v<a.v;
}
};
class Solution {
public:
/**
* 找到所有长度子数组中最大值的最小值
* @param numbers int整型vector 牛牛给出的数据
* @return int整型vector
*/
int f[110000],l[110000],r[110000];
nod g[110000];
int ans[110000];
bool b[110000],hans[110000];
int father(int x){
if (f[x]!=x) f[x]=father(f[x]);
return f[x];
}
void merge(int x,int y){
int fx=father(x);
int fy=father(y);
if (fx!=fy){
f[fx]=fy;
if (l[fx]<l[fy]) l[fy]=l[fx];
if (r[fx]>r[fy]) r[fy]=r[fx];
}
}
vector<int> getMinimums(vector<int>& numbers) {
// write code here
//if (numbers.size()==1) return numbers;
int n=numbers.size();
for(int i=1;i<=n;++i){
f[i]=l[i]=r[i]=i;
g[i]=(nod){numbers[i-1],i};
b[i]=hans[i]=0;
}
b[0]=b[n+1]=0;
sort(g+1,g+n+1);
for(int i=1;i<=n;++i){
int &x=g[i].x;
b[x]=1;
if (b[x-1]) merge(x,x-1);
if (b[x+1]) merge(x,x+1);
int fx=father(x);
int len=r[fx]-l[fx]+1;
if (!hans[len]){
hans[len]=1;
ans[len]=g[i].v;
}
}
for(int i=n-1;i>=1;--i){
if (!hans[i]) ans[i]=ans[i+1];
if (ans[i+1]<ans[i]) ans[i]=ans[i+1];
}
vector<int> v;
for(int i=1;i<=n;++i) v.push_back(ans[i]);
return v;
}
};
