【Fortuna OJ】10/20 Contest / 题解

flow

题目描述

你是申国的一个地方长官,你手下有n个城市。

为了加强基础设施建设,在2020全面建成小康社会,统筹推进经济建设、政治建设、文化建设、社会建设、生态文明建设,坚定实施科教兴国战略、人才强国战略、创新驱动发展战略、乡村振兴战略、区域协调发展战略、可持续发展战略、军民融合发展战略,突出抓重点、补短板、强弱项,特别是要坚决打好防范化解重大风险、精准脱贫、污染防治的攻坚战,使全面建成小康社会得到人民认可、经得起历史检验。你认为本省的水利调配非常有问题,这导致部分地区出现严重的缺水,而部分地区却全年洪灾泛滥。

于是你打算将原有的但是已经废弃了的 $m$ 条水管重新使用。第 $i$ 条水管连接城市 $x_i$ 和 $y_i$。这些水管联通了所有城市。每座城市对水的需求不同设为$a_i$,部分城市处于缺水状态,$a_i$为正,缺水量刚好为 $a_i \text{mol}$。部分城市因为有水库,$a_i$ 为负,它需要向外输送$-a_i \text{mol}$的水才能不形成洪灾。对于每条水管,你需要决定它的输送量 $f_i$,若 $f_i$ 为正则表示从 $x_i$ 向 $y_i$ 输送 $f_i \text{mol}$的水,$f_i$ 为负则表示从 $y_i$ 向 $x_i$ 输送 $-f_i \text{mol}$ 的水。

你需要做到每个城市都刚好满足它的需求,即缺 $a_i \text{mol}$ 水的城市需要刚好输入 $a_i$ 的水,而多出 $-a_i \text{mol}$ 水的城市需要刚好输出 $-a_i \text{mol}$ 水。

你需要判断能否满足要求,若满足,你还需要输出所有的 $f$。

思路

这道题看上去要缩点 + 拓扑排序,涉及三套不同的编号转换,令人窒息。尽管我考试的时候是这么写的,但作为聪明人的读者一定早发现了更好的方案。随意地找出原图地任意一个最小生成树,从叶子节点开始输水,一直向上推到根节点即可。如果根节点的水量不为 0,则判断为无法满足要求。

代码

#include <bits/stdc++.h>
#define ll long long
#define maxn 400100
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],fa[maxn],inse[maxn];
ll ans[maxn<<1],w[maxn],sumai;
int out[maxn],cnt=1,n,m,vis[maxn];
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void Build(int u,int f){
    fa[u]=f;
    vis[u]=1;
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (vis[v]) continue;
        inse[v]=i;
        Build(v,u);
    }
}
void Solve(){
    for (int i=2;i<=n;i++)
        out[fa[i]]++;
    queue<int>q;
    for (int i=1;i<=n;i++)
        if (!out[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        ans[inse[u]]=w[u];
        w[fa[u]]+=w[u];
        out[fa[u]]--;
        if (!out[fa[u]]) q.push(fa[u]);
    }
}
void Print(){
    for (int i=2;i<=2*m+1;i+=2){
        if (ans[i]) printf("%d\n",ans[i]);
        else printf("%d\n",-1*ans[i^1]);
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lld",w+i),sumai+=w[i];
    if (sumai){
        printf("Impossible\n");
        return 0;
    }
    printf("Possible\n");
    scanf("%d",&m);
    for (int i=1,t1,t2;i<=m;i++)
        scanf("%d%d",&t1,&t2),
        Add(t1,t2),Add(t2,t1);
    Build(1,0),Solve(),Print();
}

moon

题目描述

作为申国的学者,你需要严格遵守三大基本原则:

战争即和平
自由即奴役
无知即力量

你正在对一本书进行审核,其中片段写道:

“少焉,月出于东山之上,徘徊于斗牛之间。白露横江,水光接天。纵一苇之所如,凌万顷之茫然。浩浩乎如冯虚御风,而不知其所止;飘飘乎如遗世独立,羽化而登仙。”

这种行为明显不符合三大原则,比如 “纵一苇之所如” 中自由的意思已经在新话中被删除了。

但是你在修改的同时,发现书中夹着一道问题:

酥室等人现在的位置是 $(x,y)$,同时还有 $n$个 景点,坐标分别为 $(x_i,y_i)$。

每次移动按照下面的顺序操作:

  1. 选择一条直线,要求直线经过现在的位置和至少两个景点(如果现在在某个景点那里,也算一个)如果有多条直线满足要求,等概率选择一条。

  2. 在选择的这条直线中,等概率选择一个直线覆盖了的景点移动过去,如果目前在景点上,也有可能停住不动。
    酥室会进行若干次询问,第 $i$ 次询问从一个你选的任意点出发(可以不是景点),然后连续移动 $m_i$ 步,最后到达 $t_i$ 的最大概率是多少。

思路

代码

car

题目描述

作为申国的学生,你正在进行时事政治学习。

  1. 美国前国务卿是

A.希拉前 B. 希拉后 C.希拉里 D.希拉外

  1. 现任日本首相是

A.安倍晋一 B. 安倍晋二 C. 安倍晋三 D. 安倍晋四

3.现任申国国家元首是

A.吸寿瓶 B. 吸权瓶 C. 吸金瓶 D. 帘刃瓶

由于题目太难你不会做,你只好思考几天后的旅行问题。

有若干个城市形成一棵树的形状。

有若干辆双向班车往返于两个城市(中途经过的城市都会停)。

有人要从城市x到城市y,问最少坐几趟班车。

如果到不了,输出-1。

思路

代码

#include <bits/stdc++.h>
#define mp(x,y) make_pair(x,y)
#define pi pair<int,int>
#define maxn 1000100
using namespace std;
int n,m,q,cnt,head[maxn];
int pos[maxn][2],ind,p[maxn][20],f[maxn][20];
int dep[maxn],ans[maxn],tmp[maxn],c[maxn];
vector<int> lic[maxn];
vector<pi> que[maxn];
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }   
}l[maxn];
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void dfs(int x){
    dep[x]=dep[f[x][0]]+1;pos[x][0]=++ind;p[x][0]=x;
    for (int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
    for (int i=head[x];i;i=l[i].next) dfs(l[i].to);
    pos[x][1]=ind;
}
int Getlca(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=18;~i;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=18;~i;i--)
        if (f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
    return f[x][0];
}
void build(){
    for (int i=n;i>=1;i--){
        p[i][0]=i;
        for (int j=head[i];j;j=l[j].next)
            p[i][0]=dep[p[l[j].to][0]]<dep[p[i][0]]?p[l[j].to][0]:p[i][0];
        for (int j=0;j<lic[i].size();j++){
            int lca=Getlca(i,lic[i][j]);
            p[i][0]=dep[lca]<dep[p[i][0]]?lca:p[i][0];
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=18;j++)
            p[i][j]=p[p[i][j-1]][j-1];
}
void ins(int x){while (x<=n)c[x]++,x+=x&(-x);}
int sum(int x){int r=0;while (x)r+=c[x],x-=x&(-x);return r;}
void solve(int x){
    for (int i=0;i<que[x].size();i++)
        tmp[que[x][i].second]=sum(pos[que[x][i].first][1])-sum(pos[que[x][i].first][0]-1);
    for (int i=0;i<lic[x].size();i++)
        ins(pos[lic[x][i]][0]);
    for (int i=head[x];i;i=l[i].next) solve(l[i].to);
    for (int i=0;i<que[x].size();i++)
        ans[que[x][i].second]+=(tmp[que[x][i].second]==sum(pos[que[x][i].first][1])-sum(pos[que[x][i].first][0]-1));
}
int main(){
    scanf("%d",&n);
    for (int i=2;i<=n;i++)
        scanf("%d",&f[i][0]),Add(f[i][0],i);
    scanf("%d",&m);
    for (int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        lic[x].push_back(y);
        lic[y].push_back(x);
    }
    dfs(1);
    build();
    scanf("%d",&q);
    for (int i=1,x,y;i<=q;i++){
        scanf("%d%d",&x,&y);
        int lca=Getlca(x,y);
        if (x==y){
            ans[i]=0;
            continue;
        }
        for (int j=18;j>=0;j--){
            if (dep[p[x][j]]>dep[lca]) x=p[x][j],ans[i]+=1<<j;
            if (dep[p[y][j]]>dep[lca]) y=p[y][j],ans[i]+=1<<j;
        }
        if (dep[p[x][0]]>dep[lca]||dep[p[y][0]]>dep[lca]) {ans[i]=-1;continue;}
        ans[i]++;
        if (x!=lca&&y!=lca) que[x].push_back(mp(y,i));
    }
    solve(1);
    for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}