AtCoder Beginner Contest 319

F - Fighter Takahashi

给定一棵树，除根节点外每个节点有一个敌人或一颗药，同时有初始能力值 $1$。每当访问一个节点时，如果该节点是敌人，那么若能力值小于敌人的能力值 $s_i$，则失败，否则能力值加上 $g_i$；如果该节点是药，那么能力值乘上 $g_i$。问是否能够击败所有敌人。

首先策略非常明显：先打败所有能打败的敌人，然后吃一颗药，继续打败敌人，依此类推。决策点在当有多颗药可以吃的时候，选择吃拿一颗。这似乎无法贪心，注意到药的数量非常少，所以可以进行状压。

记 $f_i$ 为状态 $i$ 下能够获得的最大能力值。每次转移时枚举吃哪颗药，新击败的敌人要么是 $s_i$ 大于之前状态的最大能力值，要么是敌人位于这颗药的子树内。同时，需要维护每个状态接下来可以吃哪颗药。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
const ll inf=0x3f3f3f3f;
int p[N],t[N];
ll s[N],g[N];
int m,idx[N],xdi[N];
ll f[(1<<10)+5];
bool nxt[(1<<10)+5][10];
struct node
{
    ll mx;
    int mask;
}nodes[N];
vector<int> g0[N];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> q;
bool contains(int x,int y)
{
    return ((x^y)&y)==0;
}
void dfs(int u,ll mx,int mask)
{
    if(t[u]==1) mx=max(mx,s[u]);
    if(t[u]==2) mask=mask|(1<<idx[u]);
    nodes[u]={mx,mask};
    for(auto v:g0[u]) dfs(v,mx,mask);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>p[i]>>t[i]>>s[i]>>g[i];
        g0[p[i]].push_back(i);
        if(t[i]==2) 
        {
            xdi[m]=i;
            idx[i]=m++;
        }
    }
    dfs(1,0,0);
    f[0]=1;q.push({0,1});
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(s[u]>f[0]) continue;
        f[0]=min(f[0]+g[u],inf);
        for(auto v:g0[u])
            if(t[v]==1) q.push({s[v],v});
            else if(t[v]==2) nxt[0][idx[v]]=1;
    }
    for(int i=0;i<(1<<m);i++)
        for(int j=0;j<m;j++)
        {
            if(!nxt[i][j]) continue;
            ll cur=min(inf,g[xdi[j]]*f[i]);
            q.push({0,1});
            while(!q.empty())
            {
                int u=q.top().second;q.pop();
                if(nodes[u].mx>cur) continue;
                if(t[u]==1&&(nodes[u].mx>f[i]||!contains(i,nodes[u].mask)))
                    cur=min(inf,cur+g[u]);
                for(auto v:g0[u])
                {
                    if(t[v]==1)
                    {
                        if(contains(i|(1<<j),nodes[v].mask))
                            q.push({s[v],v});
                    }
                    else
                    {
                        if((i|1<<j)>>idx[v]&1) q.push({s[v],v});
                        else nxt[(i|1<<j)][idx[v]]=1;
                    }
                }
            }
            f[i|(1<<j)]=max(f[i|(1<<j)],cur);
        }
    bool flag=true;
    for(int i=1;i<=n;i++)
        if(s[i]>f[(1<<m)-1]) flag=false;
    cout<<(flag?"Yes":"No")<<'\n';
    return 0;
}

G - Counting Shortest Paths

求补图上点 1 到点 n 的最短路计数。

首先回顾一下补图最短路和最短路计数。

补图最短路

考虑 bfs，使用 set 维护未访问点的集合。每当访问一个点时，枚举所有未访问点。如果之间有边，那么把未访问点入队；如果之间没有边，则不管。第一种情况发生 $O(n)$ 次，第二种情况发生 $O(m)$ 次。

void bfs(int x)
{
    queue<int> q;
    dis[x]=0;s.erase(x);q.push(x);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        queue<int> tmp;
        for(auto v:s)
            if(g[u].find(v)==g[u].end()) tmp.push(v);
        while(!tmp.empty())
        {
            int v=tmp.front();tmp.pop();
            dis[v]=dis[u]+1;s.erase(v);q.push(v);
        }
    }
}

最短路计数

改改 dijkstra，点 $v$ 的路径数从满足 $dis_v=dis_u+1$ 的点 $u$ 转移来。

if(dis[v]>dis[u]+1) 
{
    dis[v]=dis[u]+1;
    num[v]=num[u];
    q.push(v);
}
else if(dis[v]==dis[u]+1)
{
    num[v]=(num[v]+num[u])%p;
}

那么回到这道题目，可以分两步来做：

1. 求出点 1 到所有点的距离 $dis_1,dis_2,\cdots,dis_n$。
2. 基于 $dis$ 进行最短路计数。

第一步就是补图最短路。

第二步的转移方程为

$$f_v=\sum_{dis_v=dis_u+1}f_u$$

直接转移边的数量是 $O(n^2)$ 的。可以反过来做：对每个 $dis$ 维护所有点的路径数总和，在转移时扣除那些不与 $v$ 相连的点，这些点的个数的级别是 $O(m)$ 的。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int p=998244353;
set<int> g[N];
int dis[N],sum[N],ans[N];
vector<int> vec[N];
set<int> s;
void bfs(int x)
{
    queue<int> q;
    dis[x]=0;s.erase(x);q.push(x);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        queue<int> tmp;
        for(auto v:s)
            if(g[u].find(v)==g[u].end()) tmp.push(v);
        while(!tmp.empty())
        {
            int v=tmp.front();tmp.pop();
            dis[v]=dis[u]+1;s.erase(v);q.push(v);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        g[u].insert(v),g[v].insert(u);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;i++) s.insert(i);
    bfs(1);
    if(s.find(n)!=s.end()) cout<<-1<<'\n';
    else
    {
        for(int i=1;i<=n;i++) 
        {
            if(dis[i]>n) continue;
            vec[dis[i]].push_back(i);
        }
        sum[0]=ans[1]=1;
        for(int i=1;i<=n;i++)
        {
            for(auto u:vec[i])
            {
                ans[u]=sum[i-1];
                for(auto v:g[u])
                    if(dis[v]+1==dis[u]) ans[u]=(ans[u]-ans[v]+p)%p;
                sum[i]=(sum[i]+ans[u])%p;
            }
        }
        cout<<ans[n]<<'\n';
    }
    return 0;
}