T1 天地一抹红
容易想到使用 dp 解决问题，设 \(f_{i, j}\) 表示初始法力值为 \(0\) ，从 \((i, j)\) 走到点 \((n, m)\) 后的最大法力值。
转移显然有：
\[f_{i, j} = \max(f_{i + 1, j}, \max_{k > j}(f_{i, k} + a_{i, k}\times \max_{j\le w\le k - 1}(h_{i, w})))
\]
这个式子看起来非常能够斜率优化，由于 \(\max_{j\le w\le k - 1}(h_{i, w})\) 的部分可以使用单调栈找到每个 \(h_{i, w}\) 控制的范围，因此将 \(f_{i, k}\) 看做截距，将 \(a_{i, k}\) 看做斜率，上述式子就可以使用李超线段树维护了。
然而不是所有人都有幸拥有脑子（比如现在写博客的笔者）。
于是思考一种不使用李超线段树的做法，一种比较邪恶的想法是，将 \(f_{i, j}\) 看做纵坐标，将 \(a_{i, k}\) 看做横坐标建立凸包，查询可以二分斜率等于 \(\max_{j\le w\le k - 1}(h_{i, w})\) 的点，然而由于凸包上每个位置查询的 \(\max_{j\le w\le k - 1}(h_{i, w})\) 并不相同，因此这个做法假掉了，继续深入思考，一种比较套路的想法是使用线段树维护凸包，当线段树一个节点满后暴力建出凸包，此时可以将斜率相同的询问分成 \(\log m\) 个区间，直接在这些区间的凸包上二分即可。
实际上由于线段树上每个区间的查询斜率具有单调性，可以做到 \(O(nm\log m)\) 。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int max1 = 100, max2 = 20000;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n, m, F, w[max1 + 5][max2 + 5], h[max1 + 5][max2 + 5], a[max1 + 5][max2 + 5];
long long f[max1 + 5][max2 + 5];
struct Point
{
int x;
long long y;
Point () {}
Point ( int __x, long long __y )
{ x = __x, y = __y; }
};
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
vector <Point> tree[max2 * 4 + 5], tmp;
int convex[max2 + 5], len;
void Build ( int now, int L, int R )
{
tree[now].clear();
if ( L == R )
return;
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
return;
}
void Build ( vector <Point> &v )
{
tmp.clear();
for ( auto val : v )
{
if ( tmp.empty() || tmp.back().x != val.x )
tmp.push_back(val);
else
tmp.back().y = max(tmp.back().y, val.y);
}
v.clear(); len = 0;
int siz = tmp.size() - 1;
for ( int i = 0; i <= siz; i ++ )
{
while ( len > 1 && ( tmp[i].y - tmp[convex[len]].y ) * ( tmp[i].x - tmp[convex[len - 1]].x ) > ( tmp[i].y - tmp[convex[len - 1]].y ) * ( tmp[i].x - tmp[convex[len]].x ) )
--len;
convex[++len] = i;
}
for ( int i = 1; i <= len; i ++ )
v.push_back(tmp[convex[i]]);
reverse(v.begin(), v.end());
return;
}
void Insert ( int now, int L, int R, int pos, const Point &v )
{
tree[now].push_back(v);
if ( pos == L )
Build(tree[now]);
if ( L == R )
return;
int mid = L + R >> 1;
if ( pos <= mid )
Insert(lson(now), L, mid, pos, v);
else
Insert(rson(now), mid + 1, R, pos, v);
return;
}
long long Query ( int now, int L, int R, int ql, int qr, int k )
{
if ( L >= ql && R <= qr )
{
while ( tree[now].size() > 1 )
{
int siz = tree[now].size() - 1;
if ( tree[now][siz].y + 1LL * k * tree[now][siz].x > tree[now][siz - 1].y + 1LL * k * tree[now][siz - 1].x )
break;
tree[now].pop_back();
}
return tree[now].back().y + 1LL * k * tree[now].back().x;
}
int mid = L + R >> 1;
long long res = -inf;
if ( ql <= mid )
res = max(res, Query(lson(now), L, mid, ql, qr, k));
if ( qr > mid )
res = max(res, Query(rson(now), mid + 1, R, ql, qr, k));
return res;
}
}Tree;
int s[max2 + 5], top;
multiset <long long> Set;
int main ()
{
freopen("red.in", "r", stdin);
freopen("red.out", "w", stdout);
scanf("%d%d%d", &n, &m, &F);
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
scanf("%d", &w[i][j]);
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
scanf("%d", &h[i][j]);
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
scanf("%d", &a[i][j]);
for ( int i = n; i >= 1; i -- )
{
if ( i == n )
f[i][m] = 0;
else
f[i][m] = f[i + 1][m] - w[i][m];
Tree.Build(1, 1, m);
Tree.Insert(1, 1, m, m, Point(a[i][m], f[i][m]));
top = 1; s[0] = m + 1; s[top] = m;
Set.clear();
Set.insert(Tree.Query(1, 1, m, m, m, h[i][m - 1]));
for ( int j = m - 1; j >= 1; j -- )
{
f[i][j] = *--Set.end();
if ( i != n )
f[i][j] = max(f[i][j], f[i + 1][j]);
f[i][j] -= w[i][j];
if ( j != 1 )
{
while ( top && h[i][j - 1] > h[i][s[top] - 1] )
{
Set.erase(Set.find(Tree.Query(1, 1, m, s[top], s[top - 1] - 1, h[i][s[top] - 1])));
--top;
}
Tree.Insert(1, 1, m, j, Point(a[i][j], f[i][j]));
Set.insert(Tree.Query(1, 1, m, j, s[top] - 1, h[i][j - 1]));
s[++top] = j;
}
}
}
if ( f[1][1] + F >= 0 )
printf("%lld\n", f[1][1] + F);
else
printf("-1\n");
return 0;
}
T2 最简根式
实际上我们需要求解满足 \(\gcd(a, b)\) 中含有平方因子的数对 \((a, b)\) 的个数，考虑枚举 \(\gcd(a, b)\) 的平方因子 \(x ^ 2\) ，如果 \(x\) 中含有平方因子，我们直接略过，否则，容易发现存在 \(\lfloor \tfrac{n}{x ^ 2} \rfloor ^ 2\) 个数对含有 \(x\) 这个平方因子，发现一种 \(\gcd(a, b)\) 会在其所有次数大于 \(2\) 的所有质因子所组成的集合的任意子集中被统计，因此考虑使用莫比乌斯函数作为容斥系数，由于 \(\sum _{d | n}\mu(d) = [n = 1]\) ，因此所有含有平方因子的数对的贡献系数为 \(0\) ，其余数对贡献系数为 \(1\) ，那么我们计算出了不合法的数对的个数，这样很容易计算答案。
因此需要计算 \(\sum _ {d = 1} ^ n \mu(d) \lfloor \tfrac{n}{d ^ 2} \rfloor ^ 2\) ，对于 \(\le n ^ {\tfrac{1}{3}}\) 的 \(d\) ，直接暴力枚举计算，对于剩余 \(d\) ，由于 \(\lfloor \tfrac{n}{d ^ 2} \rfloor \le n ^ \tfrac{1}{3}\) ，因此枚举 \(\lfloor \tfrac{n}{d ^ 2} \rfloor\) 的值计算，复杂度 \(O(T n ^ {\tfrac{1}{3}})\) 。
code
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <bitset>
using namespace std;
const int max1 = 1e8;
const int mod = 998244353;
bitset <max1 + 5> is_not_prime;
int prime[max1 + 5], total;
int mu[max1 + 5];
unordered_map <long long, int> Map;
int T;
long long n;
void Get_Prime ()
{
mu[1] = 1;
for ( int i = 2; i <= max1; i ++ )
{
if ( !is_not_prime[i] )
{
prime[++total] = i;
mu[i] = mod - 1;
}
for ( int j = 1; j <= total && i * prime[j] <= max1; j ++ )
{
int k = i * prime[j];
is_not_prime[k] = true;
if ( !( i % prime[j] ) )
{ mu[k] = 0; break; }
mu[k] = mod - mu[i];
}
}
for ( int i = 1; i <= max1; i ++ )
mu[i] = ( mu[i - 1] + mu[i] ) % mod;
return;
}
int Get_Mu ( long long x )
{
if ( x <= max1 )
return mu[x];
else if ( Map.find(x) != Map.end() )
return Map[x];
int res = 1;
for ( long long L = 2, R; L <= x; L = R + 1 )
{
R = x / ( x / L );
res = ( res - ( R - L + 1 ) % mod * Get_Mu(x / L) % mod + mod ) % mod;
}
Map[x] = res;
return res;
}
void Work ()
{
int ans = 0;
scanf("%lld", &n);
if ( n <= max1 )
{
for ( int i = 1; i <= n; i ++ )
ans = ( ans + 1LL * ( Get_Mu(i) - Get_Mu(i - 1) + mod ) * ( n / i / i ) % mod * ( n / i / i ) % mod ) % mod;
}
else
{
int B = pow(n, 0.36);
for ( int i = 1; i <= B; i ++ )
{
int v = n / i / i % mod;
ans = ( ans + 1LL * ( mu[i] - mu[i - 1] + mod ) * v % mod * v % mod ) % mod;
}
for ( long long i = n / B / B; i >= 1; i -- )
{
long long L = n / ( i + 1 ) + 1, R = n / i;
L = sqrt(L - 1) + 1;
R = sqrt(R);
L = max(L, B + 1LL);
R = max(R, B + 0LL);
if ( L > R )
continue;
ans = ( ans + 1LL * ( Get_Mu(R) - Get_Mu(L - 1) + mod ) * i % mod * i % mod ) % mod;
}
}
ans = ( ans - n % mod * ( n % mod ) % mod ) % mod;
ans = ( mod - ans ) % mod;
printf("%d\n", ans);
return;
}
int main ()
{
freopen("math.in", "r", stdin);
freopen("math.out", "w", stdout);
Get_Prime();
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}
T3 图床
考虑枚举图片数量 \(n\) ，设随机 \(m\) 次得到的图片种类数为 \(k\) ，那么实际上这个事件发生的概率为 \(\tfrac{\binom{n}{k}(k ^ m - (k - 1) ^ m)}{n ^ m}\) ，发现概率关于 \(n\) 是单峰函数，而我们需要求解整个函数的峰值，因此考虑二分，只需要判断 \(P(k)\) 与 \(P(k+1)\) 的大小关系，容易发现这等价于 \((n - k + 1)(n + 1) ^ m < (n + 1)n ^ m\) ，由于直接计算会产生很大的精度误差，取 \(\log\) 计算即可。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
const int SZ = 1 << 23;
char buf[SZ], *p1, *p2;
inline char gc()
{
if (__builtin_expect(p1 == p2, false))
{
p1 = buf;
p2 = buf + fread(buf, 1, SZ, stdin);
if (p2 != (buf + SZ))
*p2++ = EOF;
}
return *p1++;
}
int reads() {
int x = 0;
char c = gc();
while (c < '.') c = gc();
do {
x = x * 26 + c - 'a';
c = gc();
} while (c >= '.');
return x;
}
const int max1 = 1e5, max2 = 308915776;
int T, nmax, nmin, m;
double A, B, C, D;
int val[max1 + 5];
bitset <max2 + 5> bit;
void Work ()
{
char s[15]; int k = 0;
for ( int i = 1; i <= m; i ++ )
{
val[i] = reads();
if ( !bit[val[i]] )
{
bit.set(val[i]);
++k;
}
}
int L = max(k, nmin), R = nmax;
while ( L < R )
{
int mid = L + R >> 1;
if ( log2(mid - k + 1) + log2(mid + 1) * m < log2(mid + 1) + log2(mid) * m )
L = mid + 1;
else
R = mid;
}
for ( int i = 1; i <= m; i ++ )
bit.reset(val[i]);
printf("%d\n", L);
return;
}
int main ()
{
freopen("pic.in", "r", stdin);
freopen("pic.out", "w", stdout);
scanf("%d%lf%lf%lf%lf%d%d%d", &T, &A, &B, &C, &D, &nmin, &nmax, &m);
while ( T -- )
Work();
return 0;
}