AtCoder Beginner Contest 218 个人题解
比赛链接：AtCoder Beginner Contest 218
更好的阅读体验：戳这里@不会飞的小飞龙
A题 Weather Forecast
题目大意：
给出一周天气，判断第 $i$ 天阴晴
思路解析：
直接判断
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int main(){
int n;
cin>>n;
string s;
cin>>s;
if(s[n-1]=='o')cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
B题 qwerty
题目大意：
给出字母排位，还原字母序列
思路解析：
直接输出
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int main(){
for(int i=1;i<=26;i++){
int x;
cin>>x;
char op='a'+x-1;
cout<<op;
}
}
C题 Shapes
题目大意：
判断两个 $n*n$ 图中的图形是否可以通过平移或 $90°$ 旋转来完全重合
思路解析：
很明显模拟，众所周知，模拟狗都不写！
我们可以求出每个图中最小包括图形的正方块，然后与旋转后的四种情况匹配即可
AC代码：
D题 Rectangles
题目大意：
给出平面内 $n$ 个点，判断可以形成多少个以这些点为顶点的矩形，矩形必须平行于坐标轴
思路解析：
枚举左下和右上的顶点，用 $map$ 判断左上和右下的点是否存在，最后统计答案，答案需要 $/4$
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
struct node{
int x,y;
}a[maxn];
map<int,map<int,int>>vis;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
vis[a[i].x][a[i].y]=1;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(a[i].x==a[j].x||a[i].y==a[j].y)continue;
if(vis[a[i].x][a[j].y]==1&&vis[a[j].x][a[i].y]==1){
ans++;
}
}
}
cout<<ans/4<<endl;
}
E题 Destruction
题目大意：
给出一个无向图，每一条边都有一个权值 $w$ ，$w>0$ 表示删掉这条边可以获得 $w$ ，$w<0$ 表示删掉这条边可以失去 $w$ ，可以删除任意条边，问可获得的最大权值
思路解析：
很显然这是一道最小生成树
很显然，权值为负的边一定不会删，因为删掉并不会让我们的答案更优
所以解法显然，我们首先把所有负边加入并查集，再对所有正边Kruskal贪心取，统计答案
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
struct node{
ll x,y,w;
}a[maxn],b[maxn];
int f[maxn];
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
bool cmp(node u,node v){
return u.w<v.w;
}
int t1,t2;
ll ans,top;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
if(z>=0){
a[++t1].x=x;
a[t1].y=y;
a[t1].w=z;
top+=z;
}
else {
b[++t2].x=x;
b[t2].y=y;
b[t2].w=z;
}
}
sort(a+1,a+t1+1,cmp);
for(int i=1;i<=t2;i++){
int x=find(b[i].x),y=find(b[i].y);
f[x]=y;
}
for(int i=1;i<=t1;i++){
int x=find(a[i].x),y=find(a[i].y);
if(x==y)continue;
f[x]=y;
ans+=a[i].w;
}
cout<<top-ans<<endl;
}
F题 Blocked Roads
题目大意：
给你一个有向图，给出 $m$ 条边，对于依次给出的每条边，我们需要输出删除这条边后 $1-n$ 的最短路，若删除后不可到达，输出 $-1$
当然每个询问是独立的，即删除这条边后在下一次询问是会重新恢复的
思路解析：
首先我们对原图跑 $dijkstra$ ，求出 $1-n$ 的最短路径，用 $map$ 记录 $1-n$ 的最短路径，记录最短距离
然后我们枚举每一条边，我们把这些边分为两类：
不经过原图中最短路径
经过原图中最短路径
对于第一种情况，我们删除这条边不会影响 $1-n$ 的最短路径的，所以答案即为原图最短路
对于第二种情况，我们删除这条边是会改变原图的最短路径的，但是由于 $2<=n<=400$ ,所以这种情况的边至多不会超过 $400$ 个，我们可以直接再对删掉这条边的图跑 $dijkstra$ ，输出此时的最短路
复杂度满足要求 $O(n*n*logn)$
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int n,m;
int e[maxn],nex[maxn],id,dis[maxn],h[maxn];
int vis[maxn];
void add(int a,int b){
e[++id]=b;
nex[id]=h[a];
h[a]=id;
}
int pre[maxn];
map<int,map<int,int>>st;
struct nodee{
int x,y;
}q[maxn];
void dij(int s,int x,int y){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[s]=0;
priority_queue<pii,vector<pii>,greater<pii> >q;
q.push({0,s});
while(!q.empty()){
pii t=q.top();
q.pop();
int now=t.second,d=t.first;
if(vis[now])continue;
vis[now]=1;
for(int i=h[now];i;i=nex[i]){
int j=e[i];
if(now==x&&j==y)continue;
if(dis[j]>d+1){
dis[j]=d+1;
q.push({dis[j],j});
pre[j]=now;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
q[i].x=x;
q[i].y=y;
add(x,y);
}
dij(1,0,0);
int nt=n;
while(pre[nt]){
st[pre[nt]][nt]=1;
nt=pre[nt];
}
int tt;
if(dis[n]>inf/2)tt=-1;
else tt=dis[n];
for(int i=1;i<=m;i++){
if(st[q[i].x][q[i].y]==1){
dij(1,q[i].x,q[i].y);
if(dis[n]>inf/2)cout<<-1<<endl;
else cout<<dis[n]<<endl;
}
else cout<<tt<<endl;
}
}
