【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]++;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=k;j++)
            s[i][j]+=s[i-1][j];
    memset(f,inf,sizeof(f));
    for (int i=0;i<=k;i++)
        f[0][i]=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=k;j++){
            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][j]=min(f[i][j],f[i-a[j]][0]+v[j]+W);
                f[i][0]=min(f[i][0],f[i][j]);
            }
        }
    }
    for (int i=1;i<=k;i++)
        ans=min(ans,f[n][i]);
    printf("%lld",ans==inf?-1:ans);
}

开荒

题目描述

(太长了以下是我的精简版)

给定一棵树,点有权值,支持修改。询问某 $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;
int dfn[maxn<<2],tag[maxn][2];
int dep[maxn],lca[maxn<<1][21];
int n,q;
ll dis[maxn];
void Add(int x,int y){
    l[++cnt]=Edge(y,head[x]);
    head[x]=cnt;
}
struct Bt{
    ll t[maxn<<1];
    void add(int x,int y){
        while(x<=ind){
            t[x]+=y;
            x+=(x&-x);
        }
    }
    ll sum(int x){
        ll r=0;
        while(x){
            r+=t[x];
            x-=(x&-x);
        }
        return r;
    }

}pat;
void 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){
        int v=l[i].to;
        if (v==f) continue;
        dfs(v,u);
        dfn[++ind]=u;
    }
    tag[u][1]=ind;
}
void init(){
    for (int i=1;i<=ind;i++)
        lca[i][0]=dfn[i];
    for (int j=1;j<21;j++){
        for (int i=1;i<=ind;i++){
            if (i+(1<r) swap(l,r);
    int k=log(r-l+1.0)/log(2.0);
    if (dep[lca[l][k]]

跑商

题目描述

给定一个 $n$ 个点,$m$ 条边的简单无向图,支持修改点权。每次询问路径上点权最小值。

思路与代码

CodeForces 487E

Show Comments