A. Add and Divide
不难想到，最优解一定是(b)先加到某个值(b')后再通过不断除而成。
答案即为(min {n + left lfloor log_{b + n} {a}
ight
floor + 1})，(n)为(b)加了几次。
可以想出答案不会超过(30)，枚举(n)即可。
# include <bits/stdc++.h>
using namespace std;
int t;
int a,b;
int qfind(int a,int b)
{
long long cur = 1;
if(a == 1) return 1;
if(b == 1) return 1e9 + 7;
for(int i = 1; i <= 31; i++)
{
cur *= b;
if(cur > a) return i;
else if(cur == a) return i + 1;
}
}
int main(void)
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
if(a < b)
{
printf("1
");
continue;
}
if(a == b)
{
printf("2
");
continue;
}
int ans = 31;
for(int n = 0; n <= 30; n++)
{
int P = qfind(a,b + n);
ans = min(ans,P + n);
// printf("n = %lld,b + n = %lld,P = %lld
",n,b + n,P);
}
printf("%d
",ans);
}
return 0;
}
B. Replace and Keep Sorted
考虑对于第(i)个位置上可以改成几个数是合法的。
- 对于(i = 1)，则整数(x)满足(x in [1,a_2))是合法的。
- 对于(i = n)，则整数(x)满足(x in (a_{n - 1},k])是合法的。
- 对于(1 < i < n)，则整数(x)满足(x in (a_{i - 1},a_{i + 1}))是合法的。
令(b_i)为第(i)个位置上能够修改的数的个数，减一下就珂以了，别忘了减一（不能和(a_i)一样）
然后(sum_i)维护一下(b_i)前缀和，对于每个询问(l_i,r_i)，答案为(Sum(l_i + 1,r_i - 1))再加上两边的个数，因为两边不受限制了。
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,q,k;
int a[N];
int b[N];
long long sum[N];
int Get1(int l,int r)
{
if(l > r) return 0;
return r - l + 1;
}
long long Get2(int l,int r)
{
return sum[r] - sum[l - 1];
}
int main(void)
{
scanf("%d%d%d",&n,&q,&k);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
}
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
b[i] = Get1(1,a[i + 1] - 1);
}
else
{
if(i == n)
{
b[i] = Get1(a[i - 1] + 1,k);
}
else b[i] = Get1(a[i - 1] + 1,a[i + 1] - 1);
}
--b[i];
// printf("b[%d] = %d
",i,b[i]);
}
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + b[i];
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
if(l == r)
{
printf("%d
",k - 1);
continue;
}
if(l + 1 == r)
{
long long ans = Get1(1,a[r] - 1) - 1 + Get1(a[l] + 1,k) - 1;
printf("%lld
",ans);
continue;
}
long long ans = Get2(l + 1,r - 1);
ans += Get1(1,a[l + 1] - 1) - 1;
ans += Get1(a[r - 1] + 1,k) - 1;
printf("%lld
",ans);
}
return 0;
}
C. Floor and Mod
这题有点恶心，虽然只有*1700。
考虑固定住(b)。
很容易想到(left lfloor frac{a}{b}
ight
floor)的答案是一块一块的，然后就会联想到：
对于(a in [1,b),left lfloor frac{a}{b}
ight
floor = 0)
对于(a in [b,2b),left lfloor frac{a}{b}
ight
floor = 1)
对于(a in [2b,3b),left lfloor frac{a}{b}
ight
floor = 2)
(cdots)
对于(a in [(k - 1)b,kb),left lfloor frac{a}{b}
ight
floor = k - 1 space (k le b))
然后我们会发现，除了第一组，其它每一组对答案都有(1)的贡献。
对于第(k)块，对答案有贡献（即(left lfloor frac{a}{b}
ight
floor = a mod b)）的(a_k = (k - 1)b + k - 1 = (k - 1)(b + 1))。同时(a)还得要满足(a le x)的性质，而我们的目标，就是找到最大的这个(k)，然后对于每一个(b)，求出其最大值(k)，其对答案贡献为(k - 1)。
考虑对于每个(b)如何求出(k)最大值。
根据上面的东西列不等式：
[egin{aligned}
(k - 1)(b + 1) &le x\
k - 1 &le dfrac{x}{b + 1}\
k &le dfrac{x}{b + 1} + 1\
end{aligned}
]
然后取个整即可。不过要和(b)取(min)。
通过分析，我们发现我们要求
[sum_{b = 1} ^ y min left(left lfloor dfrac{x}{b + 1}
ight
floor,b - 1
ight)
]
单次询问复杂度(mathcal{O}(b))，然而(b le 10^9)
我们发现了下取整符号，考虑分块，但是得先把(min)去掉。
列不等式
[egin{aligned}
b - 1 &le dfrac{x}{b + 1}\
(b - 1)(b + 1) &le x\
b^2 - 1 &le x\
b^2 &le x + 1\
b &le sqrt{x + 1}\
end{aligned}
]
对于([1,sqrt{x + 1}])直接等差数列求和，对于([sqrt{x + 1} + 1,y])使用数论分块。
# include <bits/stdc++.h>
using namespace std;
int t;
long long x,y;
# define min(x,y) x < y ? x : y
long long solve(void)
{
long long ans = 0;
bool flag = 0;
for(int b = 1; b <= y; b++)
{
ans += min(b - 1,int(x / (b + 1)));
if(b - 1 > x / (b + 1) && !flag)
{
printf("flag = %d
",b);
flag = 1;
}
}
return ans;
}
long long dc(int l,int r)
{
return (l + r) * (r - l + 1) / 2;
}
long long solve2(void)
{
long long ans = 0;
int SQ = int(sqrt(x + 1));
ans = dc(0,min(SQ - 1,y - 1)); // [1,SQ]
// printf("SQ = %d
",SQ
for(int l = SQ + 2,r = 0; l <= y + 1; l = r + 1)
{
int s = x / l;
if(!s) break;
r = min(x / s,y + 1);
ans += (r - l + 1) * s;
}
return ans;
}
int main(void)
{
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&x,&y);
printf("%lld
",solve2());
}
return 0;
}
D. Multiples and Power Differences
构造题。
若(i + j)为偶，填(720720)。
若(i + j)为奇，填(720720 + a_{i,j}^4)
E. Move and Swap
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int t;
int n;
long long a[N],dp[N];
vector <int> g[N],G[N];
int f[N],dep[N];
const long long inf = 1e10;
// # define max(a,b) a > b ? a : b
int d;
void dfs(int x,int fa)
{
G[dep[x]].push_back(x);
d = max(d,dep[x]);
for(int i = 0; i < (int)g[x].size(); i++)
{
int v = g[x][i];
if(v != fa)
{
f[v] = x;
dep[v] = dep[x] + 1;
dfs(v,x);
}
}
return;
}
int main(void)
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
dep[i] = 0;
f[i] = 0;
G[i].clear();
g[i].clear();
dp[i] = 0;
}
for(int i = 2; i <= n; i++)
{
int v;
scanf("%d",&v);
g[i].push_back(v);
g[v].push_back(i);
}
for(int i = 2; i <= n; i++)
{
scanf("%lld",&a[i]);
}
dep[1] = 0;
dfs(1,0);
// printf("d = %d
",d);
// // dp[0] = 0;
// for(int i = 1; i <= n; i++)
// {
// printf("dep[%d] = %d
",i,dep[i]);
// }
// putchar('
');
for(int i = 1; i <= d; i++)
{
long long Max = -inf,Min = inf,Max1 = -inf,Max2 = -inf;
for(int j = 0; j < (int)G[i].size(); j++)
{
int v = G[i][j];
Max = max(Max,a[v]);
Min = min(Min,a[v]);
Max1 = max(Max1,a[v] + dp[f[v]]);
Max2 = max(Max2,dp[f[v]] - a[v]);
}
// printf("i = %d,Max = %lld,Min = %lld,Max1 = %lld,Max2 = %lld
",i,Max,Min,Max1,Max2);
for(int j = 0; j < (int)G[i].size(); j++)
{
int v = G[i][j];
dp[v] = max(abs(Min - a[v]),abs(Max - a[v])) + dp[f[v]];
dp[v] = max(dp[v],max(Max1 - a[v],Max2 + a[v]));
}
}
long long ans = 0;
for(int i = 1; i <= n; i++)
{
ans = max(ans,dp[i]);
}
printf("%lld
",ans);
}
return 0;
}