「THOI」THOI Round1 赛后题解

2024-04-14 03:18

文章标签 题解赛后 round1 thoi

本文主要是介绍「THOI」THOI Round1 赛后题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. 出题

题目传送门

该题正解 dp，数据略水，暴力都过了。

完全背包问题，只不过要求刚好装满，所以 $f$ 数组可以全部赋值为一个特殊的数，只有刚好装到这个容量时才能转移。

代码实现：

#include <bits/stdc++.h>
using namespace std;int f[4005];
int n,s[4];
int main(){cin>>n>>s[1]>>s[2]>>s[3];fill(f+1,f+n+1,INT_MIN);//赋值为特殊的数f[0]=0;//0可以达到，所以是0for(int i=1;i<=3;i++){for(int j=s[i];j<=n;j++){if(f[j-s[i]]!=INT_MIN)f[j]=max(f[j],f[j-s[i]]+1);//f[j-s[i]]可以达到才能状态转移}}cout<<f[n];return 0;
}

B. 导航

题目传送门

最长路+高精度。这题数据出了问题（我的锅），代码不放了。

C. 秘密

题目传送门

很多人想用并查集，其实不然，因为题目中规定：

每行 $2$ 个整数 $u$ ， $v$ ，表示 $u$ 认识 $v$ 。

但是 $v$ 不认识 $u$ ！所以这是一道 Tarjan 缩点题。

我们先跑一遍 Tarjan 缩点，然后维护每个强连通分量的入度。显然，入度为 $0$ 的强连通分量需要通知，因为没有别的人来通知它。

代码实现如下：

#include <bits/stdc++.h>
using namespace std;inline int read(){int x=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x;
}int n;
struct edge{int to,nxt;
}e[200005]; 
int head[200005];int idx;
void link(int x,int y){e[++idx]={y,head[x]};head[x]=idx;
}int dfn[200005],low[200005];
stack <int> stk;bool ins[200005];
int ans,tot;
int scc[200005],in[200005];
void tarjan(int x){dfn[x]=low[x]=++tot;stk.push(x);ins[x]=true;for(int i=head[x];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(ins[v]){low[x]=min(low[x],dfn[v]);}}if(dfn[x]==low[x]){int v;ans++;do{v=stk.top();stk.pop();scc[v]=ans;ins[v]=false;}while(v!=x);}
}int main(){int m;n=read();m=read();for(int i=1;i<=m;i++){int x=read();int y=read();link(x,y);}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=n;i++){for(int j=head[i];j;j=e[j].nxt){int v=e[j].to;if(scc[i]!=scc[v]){in[scc[v]]++;}}}int cnt=0;for(int i=1;i<=ans;i++){if(in[i]==0)cnt++;}cout<<cnt;return 0;
}

D. 轰炸

题目传送门

被曝很像 P1656炸铁路，但真的是原创题目。

要炸断 $1$ 条铁路使图不连通，显然是求图的桥。

注意要按字典序输出。

#include <bits/stdc++.h>
using namespace std;int m,n;
struct edge{int to,nxt;
}e[100005<<1];
int head[100005],idx;
void link(int x,int y){e[++idx]=edge{y,head[x]};head[x]=idx;
}bool flag;
int ans1=INT_MAX,ans2=INT_MAX;int dfn[100005],low[100005],tot;void tarjan(int x,int fa){dfn[x]=low[x]=++tot;for(int i=head[x];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){tarjan(v,x);low[x]=min(low[x],low[v]);if(low[v]>dfn[x]){flag=true;if(x<ans1){ans1=x;ans2=v;}else if(x==ans1){if(v<ans2){ans1=x;ans2=v;}}}}else if(v!=fa)low[x]=min(low[x],dfn[v]);}
}int main(){cin>>m>>n;for(int i=1,x,y,w;i<=m;i++){cin>>x>>y>>w;link(x,y);link(y,x);}for(int i=1;i<=n;i++)if(!dfn[i]){tarjan(i,i);}if(ans1>ans2)swap(ans1,ans2);if(flag)cout<<ans1<<' '<<ans2;else cout<<-1;//system("pause");return 0;
}