最近练车+过年，补题时间不太多。
A. Add and Divide
题意
给出两个整数a和b，在一次操作中，你可以选择让a=a/b或b++，问使得a=0的最小操作次数。
题解
直接枚举即可，最坏情况下时间复杂度O(nlog（n))，不过因为每次只能+1，所以大部分情况下还是很快的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll max(ll a, ll b) {
if (a > b) return a;
return b;
}
ll min(ll a, ll b) {
if (a < b) return a;
return b;
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll a,b;
cin>>a>>b;
ll a2=a,b2=b;
int re=imax,num=0,i=0;
for(int j=b;j<max(a,b)+3;j++){
if(j==1) {
i++;
continue;
}
num=i;
a2=a,b2=b+i;
while(a2/b2!=0){
a2=a2/b2;
num++;
}
if(re<num) {
break;
}
//cout<<num<<" "<<j<<endl;
re=num;
i++;
}
cout<<re+1<<endl;
}
return 0;
}
B. Replace and Keep Sorted
题意
给出一个递增数组和一个区间，输出对应区间“相似数组”的个数。
相似数组也需要递增，长度相同，每个元素均为1-k，只有一个地方不同。
题解
因为相似数组只能有一个元素不同，所以除了num[l]和num[r]可以取的个数分别是num[l+1]-2和k-num[r-1]-1，剩下的都是num[i+1]-num[i-1]-2，然后将可以取的个数累加起来。普通的累加一定不行，需要用到线段树等快速求区间和的东西。
这题用线段树可能小题大作，也能用前缀和的方式得出结果。
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
ll n, a[100005], d[270000], b[270000];
void build(ll s, ll t, ll p) {
if (s == t) {
d[p] = a[s];
return;
}
ll m = (s + t) / 2;
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[(p * 2) + 1];
}
ll getsum(ll l, ll r, ll s, ll t, ll p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return d[p];
ll m = (s + t) / 2, sum = 0;
//throw 100;
if (b[p]) {
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),
b[p * 2] += b[p], b[p * 2 + 1] += b[p];
b[p] = 0;
}
if (l <= m) sum = getsum(l, r, s, m, p * 2);
// cout << sum << " " << s << " " << t << endl;
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
//cout << sum <<" "<<s<<" "<< t<< endl;
return sum;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,q,k,l,r;
cin>>n>>q>>k;
int num[n+2];
for(int i=1;i<=n;i++){
cin>>num[i];
if(i==1) continue;
else if(i==2){
a[i-1]=num[i]-2;
}
else if(i==n){
a[i-1]=num[i]-num[i-2]-2;
a[i]=k-num[i-1]-1;
}
else a[i-1]=num[i]-num[i-2]-2;
}
build(1, n, 1);
//for(int i=1;i<=n;i++) cout<<a[i]<<" ";
//cout<<endl;
for(int i=0;i<q;i++){
cin>>l>>r;
if(l==r){
cout<<k-1<<endl;
continue;
}
ll sum=0;
sum+=num[l+1]-2;
sum+=k-num[r-1]-1;
//cout<<" "<<sum<<endl;
if(r-l>1) sum+=getsum(l+1,r-1,1,n,1);
cout<<sum<<endl;
}
return 0;
}
C. Floor and Mod
题意
题解
