【题解】牛客小白月赛 81
A. 小辰打比赛
题意就是要尽可能地赢，而赢的先后关系无影响。所以把所有比 x 小的数加起来即可。
#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
using namespace std;
const int N=5e5+10;
int a[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,i,x;
cin>>n>>x;
For(i,1,n) cin>>a[i];
int sum=0;
For(i,1,n) if(a[i]<x) sum+=a[i];
cout<<sum<<'\n';
return 0;
}
B. 小辰的圣剑
贪心地想，要尽可能多出战，每天应该只击杀一只怪物，并且圣剑不能不击杀怪物（会浪费耐久）。所以枚举连续出战的区间，判断 血量之和是否不超过 w ，声望之和是否不超过 u 即可。
#include<bits/stdc++.h>
#define int long long
#define ldb long double
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
using namespace std;
const int N=5e5+10;
int a[N],b[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m,u,i,j;
cin>>n>>m>>u;
For(i,1,n) cin>>a[i];
For(i,1,n) cin>>b[i];
int ans=0;
For(i,1,n){
int res1=0,res2=0;
For(j,i,n){
res1+=a[j];
res2+=b[j];
if(res1>m) break;
if(res2>u) break;
ans=max(ans,j-i+1);
}
}
cout<<ans<<'\n';
return 0;
}
C. 陶陶学算术
两种运算结果相同，当且仅当结果分解质因数后相同。因为只含乘法和除法，所以对每个数分解质因数后计算质数的指数即可。注意符号个数的判断。
#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
using namespace std;
const int N=1e6+10;
int num[N];
void divide(int x,int sign){
int i,cnt;
for(i=2;i<=x/i;i++){
cnt=0;
while(x%i==0) cnt++,x/=i;
num[i]+=sign*cnt;
}
if(x>1) num[x]+=sign;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int i,op,x;
int m1,m2,sign1=1,sign2=1;
cin>>m1;
For(i,1,m1){
cin>>op>>x;
if(!x) return 0;
if(x<0) sign1*=-1,x=-x;
if(op==1) divide(x,1);
if(op==2) divide(x,-1);
}
cin>>m2;
For(i,1,m2){
cin>>op>>x;
if(!x) return 0;
if(x<0) sign2*=-1,x=-x;
if(op==1) divide(x,-1);
if(op==2) divide(x,1);
}
if(sign1!=sign2) cout<<"NO\n";
else{
For(i,1,1e6) if(num[i]) break;
if(i<=1e6) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
D. 小辰的借钱计划
先要知道简单期望的计算。此题里，即所有情况下另一个盒子的钱数之和除以情况数就是更换盒子获得钱的期望。
枚举另一个盒子里的钱数，判断是否是 a 的倍数或是 a 的因数，注意之和不能超过 m 。
#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
using namespace std;
const int N=5e5+10;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int a,m,t,i;
cin>>t;
while(t--){
int tot=0,cnt=0;
cin>>m>>a;
m-=a;
For(i,1,m){
if(a%i==0) tot+=i,cnt++;
else if(i%a==0) tot+=i,cnt++;
}
if(tot>cnt*a) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
E. 小辰的智慧树
先将贡献的那个式子展开可以发现是公差为 1 的等差数列求和的一个变型。 而等差数列求和，满足结合律（就先砍一段，再砍一段和直接砍两段的长度是一样的） 而等差数列求和，满足结合律（就先砍一段，再砍一段和直接砍两段的长度是一样的）最后答案 后减去砍的树木长度即可。
或者直接得出：砍一棵树 x=x1+x2 时的贡献和 x=x1,x=x2 的贡献之和是一样的后直接维护也行。
或者直接看出树最后的最高高度具有单调性直接二分也行。
维护上面这个过程的方式比较多，也相对较经典。
解法一：
考虑暴力解法，每次取 max{hi} ，取 m 次，注意 hi=ci 时不能再取，时间复杂度 O(nm)。
使用优先队列 priority_queue 优化，可以做到 O(mlogn)。
继续优化。
观察发现，在进行优先队列取数时，取的高度一定是连续不增的。也就是满足“单调性”，这启发使用二分答案的方式，去找到能取到的最小高度，然后一次性把大于这个高度的所有高度的树全部取掉。
注意可能会存在一种情况是，并不是所有等于能取到的最小高度的高度的树都会被取。因为 m 可能会不够。所以二分答案 check 函数的标准是取完的次数 ≥m，且二分结束后，要计算一下 m 会不会不够，相差差的部分要减去。
解法二：
受解法一前部分启发，因为取的高度一定是连续不增的，所以不如直接连续取高度值，将相同高度的树一起取掉。这样就能严格递减，并且最坏情况是从 106 减到 1。直接使用优先队列 priority_queue 维护高度，每个高度只会被弹出放入一次，所以时间复杂度是 O(hi logn) 的。
此种解法需要注意一些细节。例如，当某一棵树达到下限高度时，应将其去掉；当剩余 m 不足以取完当前的高度的所有树时，要退出。
解法三：
受解法二思想启发，可以直接从值域入手，因为值域只有 106，所以直接用桶维护值域。然后从大到小贪心地取完 m 次为止即可。
这里用桶维护值域的方式有很多，因为一棵树的高度值域是 [ci+1,hi]。所以相当于是对桶执行区间加 1 操作。
此题只有一个询问，且没有修改。所以可以选择差分后维护桶，询问前进行前缀和即可。
解法三代码：
#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
PII a[N];
int num[2][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m,sum=0,i;
cin>>n>>m;
For(i,1,n) cin>>a[i].first>>a[i].second;
For(i,1,n) sum+=a[i].first-a[i].second;
For(i,1,n) num[0][a[i].first]++,num[1][a[i].second]++;
int cnt=0,res=0,tot=0;
FOR(i,1e6,1){
cnt+=num[0][i];
cnt-=num[1][i];
if(tot+cnt>=m){
res+=(m-tot)*i;
break;
}
tot+=cnt;
res+=cnt*i;
}
cout<<res*2-min(m,sum)<<'\n';
return 0;
}
F. 小辰刚学 gcd
首先，我们要知道 gcd 的一个性质：在集合的超集中，集合 gcd 只有 logn 级别的取值。因为最小的质因数为 2，所以若 gcd 变小，则至少会减小一半。
预处理出以每个位置为右端点的区间的后缀 gcd 集合。i 的集合可以通过 i-1 的集合中的元素和 ai 取 gcd 得到。这个集合大小为 logai 级别。同时根据 gcd 的势能均摊性质。预处理这个后缀 gcd 集合的时间复杂度为：O(nlogai )。
预处理过程中，同时处理出 p 集合，表示 p 的后缀 gcd 集合中每个 gcd 值第一次出现的位置。
处理询问时：在 p[r] 中 lower_bound 即可（直接遍历也是可以的）。
#include<bits/stdc++.h>
#define int unsigned int
#define pb push_back
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N=6e5+10;
int n,m,a[N],b[N],c[N];
vector<int> p[N],s[N];
void init(){
int i,j,cnt=0;
For(i,1,n){
cnt=0;
b[++cnt]=a[i];
c[cnt]=i;
int t=a[i];
For(j,1,p[i-1].size()){
t=__gcd(t,s[i-1][j-1]);
b[++cnt]=t;
c[cnt]=p[i-1][j-1];
}
b[cnt+1]=0;
For(j,1,cnt) if(b[j]!=b[j+1]) p[i].pb(c[j]),s[i].pb(b[j]);
}
}
int calc(int x,int y){
return p[y].end()-upper_bound(p[y].begin(),p[y].end(),x)+1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int i,l,r;
cin>>n>>m;
For(i,1,n) cin>>a[i];
init();
For(i,1,n) reverse(p[i].begin(),p[i].end());
For(i,1,m){
cin>>l>>r;
cout<<calc(l,r)<<'\n';
}
return 0;
}
