2021.11.18-NOIP模拟信心赛
前言
太蒟蒻了，信心赛打的都快没信心了，giao
T1\(\color{green}100\)题目
T1作为简单的签到题，直接先枚举所有的流量再用dijkstra跑这么多遍就可以了
#include<bits/stdc++.h>
#define M 2100
#define N 1100
#define inf 0x7f7f7f7f
using namespace std;
int n,m,maxx=-15;
int first[M],nex[M],to[M],w[M],f[M],tot;
int dis[N];
bool vis[N];
priority_queue<pair<int,int> >q;
//=======================================================
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
//========================================================
inline void add(int x,int y,int z,int q){
nex[++tot]=first[x];
first[x]=tot;
to[tot]=y;
w[tot]=z;
f[tot]=q;
}
//========================================================
inline void dijkstra(){
for(int x=1;x<=1000;x++){
for(int i=1;i<=n;i++){
dis[i]=inf;
vis[i]=0;
}
q.push(make_pair(0,1));
dis[1]=0;
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=first[u];i;i=nex[i]){
int v=to[i];
if(f[i]<x)continue;
if(dis[u]+w[i]<dis[v]){
dis[v]=dis[u]+w[i];
if(!vis[v]){
q.push(make_pair(-dis[v],v));
}
}
}
}
if(dis[n]!=inf)
maxx=max(maxx,x*1000000/dis[n]);
}
}
//========================================================
int main(){
n=read(),m=read();
int a,b,c,f;
for(int i=1;i<=m;i++){
a=read(),b=read(),c=read(),f=read();
add(a,b,c,f);
add(b,a,c,f);
}
dijkstra();
cout<<maxx<<endl;
return 0;
}
T2\(\color{red}0\)题目
明明第二天比第一题还简单简单我却做不出来
一开始在哪里想建图然后\(bfs\)然后小样例过了，大样例却挂了
结果直接用一个并查集分成两个集合就好了（有两种牛奶）
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,m;
char s[N];
int f[N];
int ans[N];
//=====================================================
inline int read(){
int p=0,f=1;
char c;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
//======================================================
int gf(int x){
if(x == f[x]) return x;
return f[x] = gf(f[x]);
}
//======================================================
void hb(int x, int y){
f[gf(x)] = gf(y);
}
//======================================================
int main(){
n=read(),m=read();
scanf("%s",s+1);
int x,y;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<n;i++){
x=read(),y=read();
if(s[x]==s[y])
hb(x,y);
}
for(int i=1;i<=m;i++){
char c;
x=read(),y=read(),cin>>c;
if(gf(x)==gf(y)&&s[x]!=c)ans[i]=0;
else ans[i]=1;
}
for(int i=1;i<=m;i++)cout<<ans[i];
return 0;
}
T3\(\color{red}0\)题目
第二题都没做出来自然第三题也做不出来
题意：
求一颗树\(u\)到\(v\)的路径上有无某颜色的点
先跑一遍dfs，再求出\(u\)和\(v\)的最近公共祖先，这样就可以得到\(u\)和\(v\)的路径，然后用结构体和vector存储查询的颜色，最近公共祖先以及该点的编号，
最后再来一遍dfs，这一遍相当于把颜色按照节点的深度进行赋值，然后枚举点因为刚才记录了该点所要查询的颜色以及最近公共祖先，而且\(u\)和\(v\)都记录了，所以如果该点颜色深度大于最近公共祖先的深度，就说明一定能够经过，就把\(ans[now.id]=1\)
第三题代码复杂度\(O\)（\(n\log n\)）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100,M = 2e5 + 100;
const int maxdep=24;
int n,m;
int first[M],to[M],nex[M],tot;
int val[N],dep[N],faz[N][maxdep+1],ans[N];
struct mpair{
int col,top,id;
};
vector<mpair> vec[N];
//==============================================================
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
//==============================================================
inline void add(int x,int y){
nex[++tot]=first[x];
first[x]=tot;
to[tot]=y;
}
//==============================================================
void dfs1(int u){
for(int i=1;i<=maxdep;i++)faz[u][i]=faz[faz[u][i-1]][i-1];
for(int i=first[u];i;i=nex[i]){
int v=to[i];
if(v==faz[u][0])continue;
dep[v]=dep[u]+1;
faz[v][0]=u;
dfs1(v);
}
}
//==============================================================
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=maxdep;i>=0;i--)
if(dep[faz[x][i]]>=dep[y])x=faz[x][i];
if(x==y)return x;
for(int i=maxdep;i>=0;i--)
if(faz[x][i]!=faz[y][i])x=faz[x][i],y=faz[y][i];
return faz[x][0];
}
//==============================================================
int tmp[N];
void dfs(int u){
int lst=tmp[val[u]];
tmp[val[u]]=dep[u];
for(int i=0;i<vec[u].size();i++){
mpair now=vec[u][i];
if(tmp[now.col]>=dep[now.top])
ans[now.id]=1;
}
for(int i=first[u];i;i=nex[i]){
int v=to[i];
if(v==faz[u][0])continue;
dfs(v);
}
tmp[val[u]]=lst;
}
//==============================================================
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)val[i]=read();
int x,y;
for(int i=1;i<n;i++){
x=read(),y=read();
add(x,y);
add(y,x);
}
dfs1(1);
int c;
for(int i=1;i<=m;i++){
x=read(),y=read(),c=read();
int l=lca(x,y);
vec[x].push_back(mpair{c,l,i});
vec[y].push_back(mpair{c,l,i});
}
memset(tmp,-1,sizeof(tmp));
dfs(1);
for(int i=1;i<=m;i++)cout<<ans[i];
return 0;
}