T1 背包问题模板
比较套路的，我们考虑进行二进制拆分，对于数量 \(A\) ，我们首先从小到大拆分为 \(1,2,4...2^k\) ，对于剩余的 \(w\) ，我们直接按照它的二进制位拆分即可，这样问题转化为比较简单的 \(0/1\) 背包。
由于 \(b_i\) 的范围很小，如果将物体体积用二进制数表示，发现二进制上为 \(1\) 的个数很小，由于按照上面方法拆分后物品数量为 \(2\) 的整次幂，因此我们按照指数对物品进行分组，设 \(f_{i,j}\) 表示第 \(i\) 组内物体体积总和除以 \(2^i\) 小于等于 \(j\) 时的最大价值，考虑对每个组进行合并，设 \(g_{i,j}\) 表示当前考虑了前 \(i\) 组，第 \(i\) 位及以上的位状态为 \(j\) ，其他位与 \(m\) 对应位相同的最大价值，转移有 \(f_{i,j-k}+g_{i-1,2k+(m>>i-1\&1)}\to g_{i,j}\) 。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <ctime>
#include <cstring>
using namespace std;
const int max1 = 20, max_bit = 11, base = 1 << max_bit;
int n;
long long m;
long long a[max1 + 5], c[max1 + 5];
int b[max1 + 5];
struct Data
{
int bit;
__int128 val;
Data () {}
Data ( int __bit, __int128 __val )
{ bit = __bit, val = __val; }
};
vector <Data> d[max1 * 3 + 5];
__int128 f[max1 * 3 + 5][base + 5], g[max1 * 3 + 5][base + 5];
char s[105];
int top;
void Print ( __int128 x )
{
top = 0;
do
{ s[++top] = x % 10 + '0'; x /= 10; } while ( x );
while ( top )
putchar(s[top--]);
putchar('\n');
return;
}
int main ()
{
freopen("bag.in", "r", stdin);
freopen("bag.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
scanf("%lld%d%lld", &a[i], &b[i], &c[i]);
scanf("%lld", &m);
for ( int i = 1; i <= n; i ++ )
{
for ( int k = 0; ( 1LL << k ) <= a[i]; k ++ )
{
d[k].push_back(Data(b[i], (__int128) ( 1LL << k ) * c[i]));
a[i] -= 1LL << k;
}
for ( int k = 0; ( 1LL << k ) <= a[i]; k ++ )
if ( a[i] >> k & 1 )
d[k].push_back(Data(b[i], (__int128) ( 1LL << k ) * c[i]));
}
for ( int i = 0; i <= __lg(m); i ++ )
{
for ( auto v : d[i] )
{
for ( int k = base - 1; k >= v.bit; k -- )
f[i][k] = max(f[i][k], f[i][k - v.bit] + v.val);
}
}
for ( int k = 0; k < base; k ++ )
g[0][k] = f[0][k];
for ( int i = 1; i <= __lg(m) + 1; i ++ )
for ( int j = 0; j < base; j ++ )
for ( int k = 0; k <= j; k ++ )
g[i][j] = max(g[i][j], f[i][j - k] + g[i - 1][min(base - 1, ( k << 1 ) | (int)( m >> i - 1 & 1 ))]);
Print(g[__lg(m) + 1][0]);
return 0;
}
T2 南河泄露
设 \(f_{l,r,0/1}\) 表示当前考虑区间 \([l,r]\) ，起始点位于 \(l/r\) 时最优情况下代价和的最大值，转移有：
\[f_{l,r,0}=\max_{i=l+1}^{r-1}(\min(f_{l,k,1},f_{k,r,0})+d_k+(s_k-s_l)^2)\\ f_{l,r,1}=\max_{i=l+1}^{r-1}(\min(f_{l,k,1},f_{k,r,0})+d_k+(s_r-s_k)^2)\\ \]以 \(f_{l,r,0}\) 的转移为例，考虑进行优化，首先容易发现当 \(l\) 固定时， \(f_{l,r,0/1}\) 随 \(r\) 的增大而增大，当 \(r\) 固定时， \(f_{l,r,0/1}\) 随 \(l\) 的减小而增大，因此存在分界点 \(mid\) 满足 \(f_{l,mid,1}\le f_{mid,r,0}\) 并且 \(f_{l,mid+1,1}>f_{mid+1,r,0}\) ，因此 dp 转移方程可以写作：
\[f_{l,r,0}=\max(\max_{k=l+1}^{mid}(f_{l,k,1}+d_k+(s_k-s_l)^2),\max_{k=mid+1}^{r-1}(f_{k,r,0}+d_k-(s_k-s_l)^2) \]对于第一部分，发现只与 \(l\) 和 \(k\) 有关，当我们固定 \(l\) 进行维护时，由于 \(r\) 单调右移，因此 \(mid\) 单调右移，也就是有贡献的值只增不减，直接维护即可，对于第二部分，发现这是一个斜率优化形式，假设 \(k<t\) ，简单推导：
\[\begin{aligned} f_{k,r,0}+d_k+(s_k-s_l)^2&<f_{t,r,0}+d_t+(s_t-s_l)^2\\ (f_{k,r,0}+d_k+s_k^2)-(f_{t,r,0}+d_t+s_t^2)&<2s_l(s_k-s_t)\\ 2s_l&<\tfrac{(f_{k,r,0}+d_k+s_k^2)-(f_{t,r,0}+d_t+s_t^2)}{(s_k-s_t)} \end{aligned} \]考虑固定 \(r\) 进行维护，由于 \(l\) 单调左移， \(mid\) 单调左移，因此我们需要向凸包中加点，容易发现维护一个斜率单调递增的凸包时，切点为最优决策点，由于 \(s_k\) 单调递减，因此切点会向前移动，那么当前切点以后的决策点一定不会成为最优决策点，将它们从凸包中删去即可。
\(f_{l,r,1}\) 的转移同理。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 3000;
int n, s[max1 + 5];
long long d[max1 + 5];
long long f[max1 + 5][max1 + 5][2];
int mid[max1 + 5][2];
long long Max[max1 + 5][2];
int convex[max1 + 5][2][max1 + 5], cnt[max1 + 5][2];
long long Y0 ( int r, int k )
{ return f[k][r][0] + d[k] + 1LL * s[k] * s[k]; }
long long X0 ( int r, int k )
{ return s[k]; }
long long Y1 ( int l, int k )
{ return f[l][k][1] + d[k] + 1LL * s[k] * s[k]; }
long long X1 ( int l, int k )
{ return s[k]; }
void Trans0 ( int l, int r, long long up, long long &F, int &cnt, int *convex )
{
while ( cnt > 1 && 2LL * s[l] * ( s[convex[cnt]] - s[convex[cnt - 1]]) >= ( f[convex[cnt]][r][0] + d[convex[cnt]] + 1LL * s[convex[cnt]] * s[convex[cnt]] ) - ( f[convex[cnt - 1]][r][0] + d[convex[cnt - 1]] + 1LL * s[convex[cnt - 1]] * s[convex[cnt - 1]] ) )
--cnt;
F = max(up, f[convex[cnt]][r][0] + d[convex[cnt]] + 1LL * ( s[convex[cnt]] - s[l] ) * ( s[convex[cnt]] - s[l] ));
return;
}
void Trans1 ( int l, int r, long long up, long long &F, int &cnt, int *convex )
{
while ( cnt > 1 && 2LL * s[r] * ( s[convex[cnt]] - s[convex[cnt - 1]]) >= ( f[l][convex[cnt]][1] + d[convex[cnt]] + 1LL * s[convex[cnt]] * s[convex[cnt]] ) - ( f[l][convex[cnt - 1]][1] + d[convex[cnt - 1]] + 1LL * s[convex[cnt - 1]] * s[convex[cnt - 1]] ) )
--cnt;
F = max(up, f[l][convex[cnt]][1] + d[convex[cnt]] + 1LL * ( s[r] - s[convex[cnt]] ) * ( s[r] - s[convex[cnt]] ));
return;
}
void Insert0 ( int r, int k, int &cnt, int *convex )
{
while ( cnt > 1 && ( Y0(r, k) - Y0(r, convex[cnt - 1]) ) * ( X0(r, convex[cnt]) - X0(r, convex[cnt - 1]) ) <= ( Y0(r, convex[cnt]) - Y0(r, convex[cnt - 1]) ) * ( X0(r, k) - X0(r, convex[cnt - 1]) ) )
--cnt;
convex[++cnt] = k;
return;
}
void Insert1 ( int l, int k, int &cnt, int *convex )
{
while ( cnt > 1 && ( Y1(l, k) - Y1(l, convex[cnt - 1]) ) * ( X1(l, convex[cnt]) - X1(l, convex[cnt - 1]) ) >= ( Y1(l, convex[cnt]) - Y1(l, convex[cnt - 1]) ) * ( X1(l, k) - X1(l, convex[cnt - 1]) ) )
--cnt;
convex[++cnt] = k;
return;
}
int main ()
{
freopen("leak.in", "r", stdin);
freopen("leak.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &s[i]);
s[0] = 0, s[n + 1] = 114514;
for ( int i = 1; i <= n; i ++ )
scanf("%lld", &d[i]);
for ( int i = 0; i <= n; i ++ )
mid[i][1] = i, mid[i + 1][0] = i + 1;
for ( int len = 1; len <= n + 1; len ++ )
{
if ( len > 1 )
for ( int l = 0, r; ( r = l + len ) <= n + 1; l ++ )
Trans0(l, r, Max[l][1], f[l][r][0], cnt[r][0], convex[r][0]), Trans1(l, r, Max[r][0], f[l][r][1], cnt[l][1], convex[l][1]);
for ( int l = 0, r; ( r = l + len ) <= n; l ++ )
{
while ( mid[l][1] + 1 <= r && f[l][mid[l][1] + 1][1] <= f[mid[l][1] + 1][r + 1][0] )
{
++mid[l][1];
Max[l][1] = max(Max[l][1], f[l][mid[l][1]][1] + d[mid[l][1]] + 1LL * ( s[mid[l][1]] - s[l] ) * ( s[mid[l][1]] - s[l] ));
Insert1(l, mid[l][1], cnt[l][1], convex[l][1]);
}
}
for ( int r = n + 1, l; ( l = r - len ) >= 1; r -- )
{
while ( mid[r][0] - 1 >= l && f[mid[r][0] - 1][r][0] <= f[l - 1][mid[r][0] - 1][1] )
{
--mid[r][0];
Max[r][0] = max(Max[r][0], f[mid[r][0]][r][0] + d[mid[r][0]] + 1LL * ( s[r] - s[mid[r][0]] ) * ( s[r] - s[mid[r][0]] ));
Insert0(r, mid[r][0], cnt[r][0], convex[r][0]);
}
}
}
printf("%lld\n", f[0][n + 1][0]);
return 0;
}
T3 最短路问题模板
直接用线段树 + 树剖模拟 Dijikstra 算法即可。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <utility>
using namespace std;
const int max1 = 2e5, max2 = 5e5;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector < pair <int, int> > vec[max1 + 5];
int siz[max1 + 5], deep[max1 + 5], father[max1 + 5], son[max1 + 5];
int dfn[max1 + 5], rk[max1 + 5], top[max1 + 5], dfs_clock;
struct Node
{ int next, v1, v2, w; } edge[max2 + 5];
int head[max1 + 5], total;
long long ans[max1 + 5];
void Add ( int u, int v1, int v2, int w )
{
edge[++total].v1 = v1;
edge[total].v2 = v2;
edge[total].w = w;
edge[total].next = head[u];
head[u] = total;
return;
}
void Find_Heavy_Edge ( int now, int fa, int depth )
{
siz[now] = 1, deep[now] = depth, father[now] = fa, son[now] = 0;
int max_siz = 0;
for ( auto v : vec[now] )
{
if ( v.first == fa )
continue;
Find_Heavy_Edge(v.first, now, depth + 1);
siz[now] += siz[v.first];
if ( max_siz < siz[v.first] )
max_siz = siz[v.first], son[now] = v.first;
}
return;
}
void Connect_Heavy_Edge ( int now, int ancestor )
{
dfn[now] = ++dfs_clock;
rk[dfs_clock] = now;
top[now] = ancestor;
if ( son[now] )
Connect_Heavy_Edge(son[now], ancestor);
for ( auto v : vec[now] )
{
if ( v.first == father[now] || v.first == son[now] )
continue;
Connect_Heavy_Edge(v.first, v.first);
}
return;
}
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
struct Struct_Segment_Tree
{ long long min_val, lazy; bool vis; } tree[max1 * 4 + 5];
void Push_Up ( int now )
{
tree[now].min_val = inf;
if ( !tree[lson(now)].vis )
tree[now].min_val = min(tree[now].min_val, tree[lson(now)].min_val);
if ( !tree[rson(now)].vis )
tree[now].min_val = min(tree[now].min_val, tree[rson(now)].min_val);
tree[now].vis = tree[lson(now)].vis && tree[rson(now)].vis;
return;
}
void Update ( int now, long long x )
{
if ( !tree[now].vis )
{
tree[now].min_val = min(tree[now].min_val, x);
tree[now].lazy = min(tree[now].lazy, x);
}
return;
}
void Push_Down ( int now )
{
if ( tree[now].lazy != inf )
{
Update(lson(now), tree[now].lazy);
Update(rson(now), tree[now].lazy);
tree[now].lazy = inf;
}
return;
}
void Build ( int now, int l, int r )
{
tree[now].lazy = inf;
if ( l == r )
{
if ( rk[l] == 1 )
tree[now].min_val = 0;
else
tree[now].min_val = inf;
tree[now].vis = false;
return;
}
int mid = l + r >> 1;
Build(lson(now), l, mid);
Build(rson(now), mid + 1, r);
Push_Up(now);
return;
}
void Update ( int now, int l, int r, int ql, int qr, long long x )
{
if ( l >= ql && r <= qr )
{ Update(now, x); return; }
Push_Down(now);
int mid = l + r >> 1;
if ( ql <= mid )
Update(lson(now), l, mid, ql, qr, x);
if ( qr > mid )
Update(rson(now), mid + 1, r, ql, qr, x);
Push_Up(now);
return;
}
pair <int, long long> Query ( int now, int l, int r )
{
if ( l == r )
{
tree[now].vis = true;
return make_pair(rk[l], tree[now].min_val);
}
Push_Down(now);
int mid = l + r >> 1;
pair <int, long long> ans;
if ( !tree[lson(now)].vis && tree[lson(now)].min_val == tree[now].min_val )
ans = Query(lson(now), l, mid);
else
ans = Query(rson(now), mid + 1, r);
Push_Up(now);
return ans;
}
bool Empty ()
{ return tree[1].vis; }
void Print ( int now, int l, int r )
{
if ( l == r )
{ ans[rk[l]] = tree[now].min_val; return; }
Push_Down(now);
int mid = l + r >> 1;
Print(lson(now), l, mid);
Print(rson(now), mid + 1, r);
return;
}
}Tree;
void Dijikstra ()
{
Tree.Build(1, 1, n);
while ( !Tree.Empty() )
{
pair <int, long long> now = Tree.Query(1, 1, n);
fflush(stdout);
for ( auto v : vec[now.first] )
Tree.Update(1, 1, n, dfn[v.first], dfn[v.first], now.second + v.second);
for ( int i = head[now.first]; i; i = edge[i].next )
{
int v1 = edge[i].v1, v2 = edge[i].v2, w = edge[i].w;
if ( !v2 )
Tree.Update(1, 1, n, dfn[v1], dfn[v1] + siz[v1] - 1, now.second + w);
else
{
while ( top[v1] != top[v2] )
{
if ( deep[top[v1]] < deep[top[v2]] )
swap(v1, v2);
Tree.Update(1, 1, n, dfn[top[v1]], dfn[v1], now.second + w);
v1 = father[top[v1]];
}
if ( deep[v1] > deep[v2] )
swap(v1, v2);
Tree.Update(1, 1, n, dfn[v1], dfn[v2], now.second + w);
}
}
}
Tree.Print(1, 1, n);
return;
}
int main ()
{
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
int opt, u, v1, v2, w;
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n - 1; i ++ )
{
scanf("%d%d%d", &u, &v1, &w);
vec[u].push_back(make_pair(v1, w));
vec[v1].push_back(make_pair(u, w));
}
for ( int i = 1; i <= m; i ++ )
{
scanf("%d", &opt);
if ( opt == 1 )
scanf("%d%d%d%d", &u, &v1, &v2, &w);
else
scanf("%d%d%d", &u, &v1, &w), v2 = 0;
Add(u, v1, v2, w);
}
Find_Heavy_Edge(1, 0, 1);
Connect_Heavy_Edge(1, 1);
Dijikstra();
for ( int i = 1; i <= n; i ++ )
printf("%lld\n", ans[i]);
return 0;
}