【Fortuna OJ】10/16 Contest / 题解
轻功
题目描述
一共有 n 个木桩，要求从起点（0）开始，经过所有梅花桩，恰好到达终点 n,尊者神高达一共会 k 种门派的轻功，不同门派的轻功经过的梅花桩数不同，花费时间也不同。但是尊者神高达一次只能使用一种轻功，当他使用别的门派的轻功时，需要花费 W 秒切换（开始时可以是任意门派,不需要更换时间）。由于尊者神高达手残，所以经过某些梅花桩（包括起点和终点）时他不能使用一些门派的轻功。尊者神高达想知道他最快多久能到达终点。如果无解，则输出-1。
思路
我们可以写一个 $O(nk)$ 的 DP。$f_{i,j}$ 表示经过第 $i$ 个梅花桩结束使用门派 $j$，那么它可以从 $f_{i-cost_j,p}$ 转移过来。发现 $p$ 的具体数值对转移没有影响，只需要特判 $p==j$ 的情况，所以处理 $f_{i,p}$ 的最小值，O(1) 转移。限制条件只需要前缀和判断即可。
代码
#include
#define inf 0x77777777
#define ll long long
#define maxn 510
using namespace std;
int n,k,W,Q;
int a[maxn],v[maxn];
ll f[maxn][maxn],s[maxn][maxn];
ll ans=inf;
int main(){
freopen("qinggong.in","r",stdin);
freopen("qinggong.out","w",stdout);
scanf("%d%d%d",&n,&k,&W);
for (int i=1;i<=k;i++) scanf("%d%d",a+i,v+i); scanf("%d",&q); for (int i="1,xi,ki;i<=Q;i++)" scanf("%d%d",&xi,&ki), s[xi][ki]++; j="1;j<=k;j++)" s[i][j]+="s[i-1][j];" memset(f,inf,sizeof(f)); f[0][i]="0;" if (a[j]<="i&&s[i][j]-s[max(i-a[j]-1,0)][j]==0){" f[i][j]="min(f[i][j],f[i-a[j]][j]+v[j]);" f[i][0]="min(f[i][0],f[i][j]);" } ans="min(ans,f[n][i]);" printf("%lld",ans="=inf?-1:ans);" }< code>开荒
题目描述
(太长了以下是我的精简版)
给定一棵树，点有权值，支持修改。询问某 $k$ 个点的最小联通块权值和。
思路
首先我们不考虑修改，如何计算答案。发现将 $k$ 个点按 $DFS$ 序升序以后，点 $i$ 到自己和前一个点 $i-1$ 的最近公共祖先深度一定递增，并且到 $LCA$ 的路径的集合就是最小联通块，注意第一个点要和所有点的 $LCA$ 相连。将点权转移到连接父亲的边上，计算答案的时候可以做到不重复，但是会遗漏所有点的 $LCA$，单独计入即可。
代码
#include
#define ll long long
#define maxn 1000100
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1]; int head[maxn],w[maxn],cnt,ind; dfn[maxn<<2],tag[maxn][2]; dep[maxn],lca[maxn<<1][21]; n,q; ll dis[maxn]; void add(int x,int y){ l[++cnt]="Edge(y,head[x]);" head[x]="cnt;" } struct bt{ t[maxn<<1]; while(x<="ind){" t[x]+="y;" x+="(x&-x);" sum(int x){ r="0;" while(x){ r+="t[x];" x-="(x&-x);" return r; }pat; dfs(int u,int f){ dis[u]="dis[f]+w[u],dep[u]=dep[f]+1;" dfn[++ind]="u,tag[u][0]=ind;" for (int i="head[u];i;i=l[i].next){" v="l[i].to;" if (v="=f)" continue; dfs(v,u); tag[u][1]="ind;" init(){ lca[i][0]="dfn[i];" j="1;j<21;j++){" (i+(1<r) swap(l,r);
int k=log(r-l+1.0)/log(2.0);
if (dep[lca[l][k]]跑商
题目描述
给定一个 $n$ 个点，$m$ 条边的简单无向图，支持修改点权。每次询问路径上点权最小值。