A - Add and Divide
可以发现，当 $b=2$ 的时候，直接除下去就行，答案不会超过 $\log_2(a)$，然后直接枚举 $b$ 加多少就行，反正不会太大。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
ll a, b;
inline void solve()
{
cin >> a >> b;
ll ans = 0;
if (b == 1)
ans = llinf;
else
{
ll x = a;
while (x)
x /= b, ans++;
}
ll now = ans;
for (int i = 1; i <= ans; ++i)
{
b++;
ll ret = i, x = a;
while (x)
x /= b, ret++;
ans = min(ans, ret);
}
cout << ans << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
B - Replace and Keep Sorted
因为只有一个位置不同，所以每个位置之间的贡献互不影响，设 $ans_i$ 表示第 $i$ 个位置的合法数的区间大小，那么答案就是 $\sum_{i=l}^{r}ans_i$，一个前缀和就搞定。
不过注意两头要特判一下，因为这个时候两头的限制各自少了一边。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n, q, k, a[N];
ll ans[N], sum[N];
inline void solve()
{
scanf(
for (int i = 1; i <= n; ++i)
scanf(
a[0] = 0, a[n + 1] = k + 1;
for (int i = 1; i <= n; ++i)
{
ans[i] = a[i + 1] - a[i - 1] - 1;
sum[i] = sum[i - 1] + ans[i];
}
while (q--)
{
int l, r;
scanf(
ll ansnow = sum[r - 1] - sum[l];
ansnow += a[l + 1] - 1;
ansnow += k - a[r - 1];
ansnow = max(0ll, ansnow - (r - l + 1));
cout << ansnow << '\n';
}
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
C - Floor and Mod
这个题还是有点烦的说实话（
其实可以先打个表找下规律（
这里就说规律吧：首先，$(a,a-1)$ 是肯定可以的，然后可以打个表发现对于任何 $(ak,a-1),1\le k \le a-2$ 都是可以的，于是就可以在这上面计算。
可以分成两部分：第一部分是带有 $k\le a-2$ 这个限制的，但是 $a(a-2)\le x$ 的话，$a$ 的上限基本上约等于 $\sqrt{x}$，所以这一部分可以直接 $\mathcal{O}(\sqrt{x})$ 爆算；第二部分的话就没有 $k\le a-2$ 的限制（其实本来也不可能超过上限了），但是有 $ak\le x$ 的限制。可以发现这个能变成 $k\le \lfloor\frac{x}{a}\rfloor$，右边是一个数论分块统计答案。
于是，上面两部分合起来，时间复杂度总的为 $\mathcal{O}(\sqrt{x})$。
但是，比赛的时候我居然不会这个数论分块卡了一个小时......
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
ll x, y;
ll cal(ll n)
{
ll ans = 0, k = x;
ll j;
for (ll i = 1; i <= n; i = j + 1)
{
if (!(k / i))
break;
j = std::min(k / (k / i), n);
ans += 1ll * (j - i + 1) * (k / i);
}
return ans;
}
inline void solve()
{
cin >> x >> y;
ll ans = 0;
y = min(x - 1, y);
ll upa = 0;
while ((upa + 1) * (upa - 1) <= x && upa <= y)
upa++;
for (int a = 3; a <= upa; ++a)
ans += a - 2;
if (upa == y + 1)
cout << ans << '\n';
else
{
ans += cal(y + 1) - cal(upa);
cout << ans << '\n';
}
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
D - Multiples and Power Differences
这个题挺有意思的（
实际上，构造方法很妙：$\mathrm{lcm}(1,2,3,...,16) = 720720$，这个时候全部变成同一个数了就很好办了：把棋盘黑白染色，黑色块加上原数的四次方即可。
很有意思
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 550;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n, m, k;
int a[N][N], b[N][N];
int _k[N];
inline void solve()
{
scanf(
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf(
for (int i = 1; i <= n; ++i, puts(""))
for (int j = 1; j <= m; ++j)
{
if ((i + j) & 1)
b[i][j] += _k[a[i][j]];
printf(
}
}
int main()
{
TIME__START = clock();
int Test = 1;
for (int i = 1;; ++i)
{
_k[i] = i * i * i * i;
if (_k[i] > 1e6)
{
k = i - 1;
break;
}
}
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
E - Move and Swap
不难发现 r 和 b 每轮操作结束后一定都在同一层，所以把树上这些点按照层来分类，每一层之间的答案其实没啥影响，设 $dp(u)$ 表示 r=u 时的最大值，接下来分成两种情况算答案：
第一种情况，不交换 r 和 b，那么 b 肯定是选这一层的最大值或者最小值，就在这两者种取 max 就行；
第二种情况，交换 r 和 b，那么可以看成到达 u 的点是 b，这个时候，就要加上上一层的贡献，即从上一层的某个红点到达这一层的红点，即需要满足 $\max{dp_{father_j} + |a_u-a_j|}$，其中 j 和 u 在同一层。这个东西可以维护这一层的 $dp_{father_j}+a_j$ 和 $dp_{father_j}-a_j$ 分别的最大值，这样就变成 $dp(v)=\max{dp(v), \max{dp_{father_j}+a_j-a_u, dp_{father_j}-a_j+a_u }}$（即把绝对值拆开）
最后，答案就是所有点的 dp 值的最大值。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmpfunction) (sort(vecall(v), cmpfunction))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n, dep[N], d;
ll a[N], dp[N], f[N], ans;
vector<int> e[N];
vector<int> vecdep[N];
bool cmp(const int &x, const int &y) { return a[x] < a[y]; }
void data_clear()
{
d = 0, ans = 0;
for (int i = 1; i <= n; ++i)
e[i].resize(0), vecdep[i].resize(0);
mem(dp, 0, n, ll);
}
void dfsdep(int u, int fa)
{
dep[u] = dep[fa] + 1, f[u] = fa;
vecdep[dep[u]].push_back(u), d = max(d, dep[u]);
for (auto v : e[u])
{
if (v == fa)
continue;
dfsdep(v, u);
}
}
queue<int> q;
bool vis[N];
int mxid1[N], mxid2[N];
ll mx1[N], mx2[N];
void work()
{
mem(vis, 0, d, bool);
mem(mxid1, -1, d, int), mem(mxid2, -1, d, int);
fill(mx1 + 1, mx1 + d + 1, -llinf);
fill(mx2 + 1, mx2 + d + 1, -llinf);
q.push(1);
int depth = 2;
while (!q.empty())
{
int u = q.front();
q.pop();
depth = dep[u] + 1;
if (!vis[depth])
{
vis[depth] = 1;
for (auto i : vecdep[depth])
{
if (dp[f[i]] + a[i] > mx1[depth])
mx1[depth] = dp[f[i]] + a[i], mxid1[depth] = i;
if (dp[f[i]] - a[i] > mx2[depth])
mx2[depth] = dp[f[i]] - a[i], mxid2[depth] = i;
}
}
for (auto v : e[u])
{
if (dep[v] < depth)
continue;
dp[v] = dp[u] + max(abs(a[v] - a[vecdep[depth][0]]), abs(a[v] - a[vecdep[depth].back()]));
dp[v] = max(dp[v], max(dp[f[mxid1[depth]]] + a[mxid1[depth]] - a[v], dp[f[mxid2[depth]]] - a[mxid2[depth]] + a[v]));
}
for (auto v : e[u])
if (dep[v] == depth)
q.push(v);
}
}
inline void solve()
{
scanf(
data_clear();
for (int i = 2; i <= n; ++i)
{
int v;
scanf(
e[i].push_back(v), e[v].push_back(i);
}
for (int i = 2; i <= n; ++i)
scanf(
dfsdep(1, 0);
for (int i = 1; i <= d; ++i)
veccmpsort(vecdep[i], cmp);
work();
for (int i = 1; i <= n; ++i)
{
ans = max(ans, dp[i]);
#ifdef VINGYING
printf(
#endif
}
#ifdef VINGYING
puts("");
#endif
printf(
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
F - Copy or Prefix Sum
转化一下，$a_i$ 有两种选择：一种是 $b_i$，另一种是 $b_i - \sum_{k=1}^{i-1}a_i$。如果 $\sum_{k=1}^{i-1}a_i = 0$ 的话意味着两种选择相同，我们就需要减去这种情况。
设 $dp(i,j)$ 表示到第 $i$ 个位置的前缀和为 $j$ 的个数，因为到第 $i$ 个位置时前缀和一共差不多有 $i$ 种，借助 map 的话复杂度为 $\mathcal{O}(n^2\log(n))$，因为有两种选择故有两种转移。
考虑优化：实际上，如果 $j=0$ 的话两种转移本质上是相同的，所以此时就需要禁止其中一种转移，这样才能不统计重复，比如禁止第一种转移。那么接下来就要考虑如何计算 $j=0$ 的情况数。
具体可以看代码。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
ll b[N];
inline void solve()
{
scanf(
for (int i = 1; i <= n; ++i)
scanf(
ll ans = 1;
map<ll, ll> dp;
dp[0] = 1;
ll sum = 0;
for (int i = 1; i <= n; ++i)
{
ll now = dp[sum];
dp[sum] = ans;sum -= b[i];
ans = (ans << 1) - now + MOD, ans = (ans + MOD)
}
cout << ans << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments NOTHING