F 题有循环节，一看就有 KMP，比较难，太晚了，早上起来再补。
C - Tak and Cards
\(n\) 个整数 \(a_1\sim a_n\)，问有多少种选数方案，使得选出来的数平均值为 \(A\)。
\(1\le n,a_i,A\le 50\)
背包即可。时间复杂度 \(\mathcal O(n^4)\)
Code
// Problem: C - Tak and Cards
// Contest: AtCoder - AtCoder Regular Contest 060
// URL: https://atcoder.jp/contests/arc060/tasks/arc060_a
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using i64 = long long;
const int maxn = 55;
const int maxm = 3005;
int n,m,a[maxn];
i64 dp[maxn][maxm];
int main() {
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;++ i) {
scanf("%d",&a[i]);
}
dp[0][0] = 1;
for(int i = 1;i <= n;++ i) {
for(int j = i;j >= 1;-- j) {
for(int k = j * 50;k >= a[i];-- k) {
dp[j][k] += dp[j - 1][k - a[i]];
}
}
}
i64 ans = 0;
for(int i = 1;i <= n;++ i)
ans += dp[i][i * m];
printf("%lld",ans);
return 0;
}
D - Digit Sum
定义 \(f(b,n)\)：
\(f(b,n)=n(n\lt b)\)
\(f(b,n)=f(b,\lfloor\frac{n}{b} \rfloor)+n\bmod b(n\ge b)\)
给定 \(n,s\)，求出最小的满足 \(f(b,n)=s(b\ge 2)\) 的 \(b\)
\(1\le n,s\le 10^{11}\)
非常简单的数论题。
直接求解显然不可能，我们可以枚举 \(f\) 的取值，当然，并不是暴力。
观察到若 \(b\gt \sqrt{n}\)，那么 \(f(b,n)\) 可以直接求出来，考虑根号分治：
-
\(b\le \sqrt{n}\)：直接暴力跑 \(f(b,n)\)，时间复杂度 \(\mathcal O(\sqrt{n}\log \sqrt{n})\)
-
\(b\gt \sqrt{n}\)：此时 \(f(b,n)=\lfloor\frac{n}{b} \rfloor+n\bmod b=\lfloor\frac{n}{b} \rfloor+n-b\times \lfloor\frac{n}{b} \rfloor\)，用数论分块求出所有 \(\lfloor\frac{n}{b} \rfloor\) 及其范围 \([l,r]\)，代入 \(f(b,n)=s\) 求解，判断解是否在 \([l,r]\) 间即可。时间复杂度 \(\mathcal O(\sqrt{n})\)
综上，时间复杂度为 \(\mathcal O(\sqrt{n}\log \sqrt{n})\)
Code
// Problem: D - Digit Sum
// Contest: AtCoder - AtCoder Regular Contest 060
// URL: https://atcoder.jp/contests/arc060/tasks/arc060_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using i64 = long long;
i64 n,s;
i64 f(i64 b,i64 n) {
if(n < b)return n;
return f(b , n / b) + (n % b);
}
int main() {
scanf("%lld %lld",&n,&s);
if(s > n) {
puts("-1");
return 0;
}
if(s == n) {
printf("%lld\n",n + 1);
return 0;
}
for(i64 i = 2;i <= 1e6;++ i) {
if(f(i , n) == s) {
printf("%lld\n",i);
return 0;
}
}
for(i64 l = 1e6 + 1,r = 0;l <= n;l = r + 1) {
r = n / (n / l);
i64 g = n / l;
i64 x = (n - s) / g + 1;
if(x >= l&&x <= r&&g + n - g * x == s) {
printf("%lld\n",x);
return 0;
}
}
puts("-1");
return 0;
}
E - Tak and Hotels
一条数轴上有 \(n\) 个点，第 \(i\) 个点坐标为 \(a_i\)。
一个人从某个点出发，他一步能迈出的距离不超过 \(L\) 且终点必须为给出的点。
\(Q\) 次询问，每次询问他从 \(a_x\) 走到 \(a_y\) 最少需要多少步。
\(1\le n,Q\le 10^5,1\le a_i,L\le 10^9,1\le a_{i+1}-a_i\le L\)
很老的 trick。
显然，从一个点出发一定要尽可能走得更远，这样肯定不劣。
用双指针求出每个点最远能到的点，倍增预处理，每次回答询问即可。
时间复杂度 \(\mathcal O((n+Q)\log n)\)
Code
有点小坑，要特判 \(x=y\)，并且因为我把倍增预处理循环边界打成了 ST 表，狂 WA 了好几发 QAQ
// Problem: E - Tak and Hotels
// Contest: AtCoder - AtCoder Regular Contest 060
// URL: https://atcoder.jp/contests/arc060/tasks/arc060_c
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int maxm = 20;
int n,a[maxn],m,f[maxn][20];
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
scanf("%d",&m);
for(int l = n,r = n;l;-- l) {
for(;r > l&&a[r] - a[l] > m;-- r);
f[l][0] = r;
}
for(int k = 1;k < 20;++ k)
for(int i = 1;i <= n;++ i)
f[i][k] = f[f[i][k - 1]][k - 1];
int Q;
scanf("%d",&Q);
while(Q --) {
int x,y,ans = 0;
scanf("%d %d",&x,&y);
if(x == y) {
puts("0");
continue ;
}
if(x > y)std::swap(x , y);
for(int k = 19;~ k;-- k)
if(f[x][k] < y)x = f[x][k],ans += 1 << k;
printf("%d\n",ans + 1);
}
return 0;
}