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)$。
每次移动按照下面的顺序操作：
- 选择一条直线，要求直线经过现在的位置和至少两个景点（如果现在在某个景点那里，也算一个）如果有多条直线满足要求，等概率选择一条。
-
在选择的这条直线中，等概率选择一个直线覆盖了的景点移动过去，如果目前在景点上，也有可能停住不动。
酥室会进行若干次询问，第 $i$ 次询问从一个你选的任意点出发（可以不是景点），然后连续移动 $m_i$ 步，最后到达 $t_i$ 的最大概率是多少。
思路
代码
car
题目描述
作为申国的学生，你正在进行时事政治学习。
- 美国前国务卿是
A.希拉前 B. 希拉后 C.希拉里 D.希拉外
- 现任日本首相是
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;
}