牛客小白月赛100（A,B,C,D,E,F三元环计数）

本文主要是介绍牛客小白月赛100（A,B,C,D,E,F三元环计数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛链接

官方讲解

这场比较简单，ABC都很签到，D是个不太裸需要预处理的 $BFS$ 搜索，E是调和级数暴力枚举，F是三元环计数。三元环考的比较少，没见过可能会偏难。

---

A ACM中的A题

思路：

就是枚举每个边变成原来的两倍，然后看看两短边之和是否大于第三边即可。

不能只给最短边乘 $2$，比如 1 4 8 这组数据，也不能只给第二短边乘 $2$，比如 2 3 4 这组数据。不过可以不给最长边乘 $2$，因为最长边乘 $2$ 后，边的长度的顺序没有改变，而原本两短边之和却更不容易大于第三边了。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;ll a[3];
bool check(){ll b[3];memcpy(b,a,sizeof(b));b[0]*=2;sort(b,b+3);if(b[0]+b[1]>b[2])return true;memcpy(b,a,sizeof(b));b[1]*=2;sort(b,b+3);if(b[0]+b[1]>b[2])return true;memcpy(b,a,sizeof(b));b[2]*=2;sort(b,b+3);if(b[0]+b[1]>b[2])return true;else return false;
}int main(){cin>>a[0]>>a[1]>>a[2];sort(a,a+3);if(check())cout<<"Yes";else cout<<"No";return 0;
} 

---

B ACM中的C题

思路：

我们交换位置只有两种策略，一种是一个已交换的数和一个未交换的数交换，另一种是两个未交换的数交换。显然第二种策略可以让未交换的数量减少的更快，所以从贪心的角度出发，我们每次选择两个未交换的数交换，剩最后一个的时候才用第一种策略。

这样交换的话，交换次数就是 $\lceil \frac{n}{2}\rceil$ 了。不过需要注意 $n=1$ 的话这个数是不可能交换到其他位置的，这时候无解。

code：

#include <iostream>
#include <cstdio>
using namespace std;int n;int main(){cin>>n;for(int i=1,t;i<=n;i++)cin>>t;if(n==1)cout<<-1<<endl;else cout<<(n+1)/2;return 0;
}

---

C ACM中的M题

思路：

多了一个只能同类别之间的数可以互换，和上一题其实没什么太大差别，我们对每一个类别分别用上题的策略来换即可。如果某个类别只有一个数，就说明这个数没法换到其他位置，这时候就无解了。

code：

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;int n;
map<int,int> mp;int calc(){int ans=0;for(auto [x,t]:mp)if(t==1)return -1;else ans+=(t+1)/2;return ans;
}int main(){cin>>n;for(int i=1,t;i<=n;i++)cin>>t;for(int j=1,t;j<=n;j++){cin>>t;mp[t]++;}cout<<calc();return 0;
}

---

D ACM中的AC题

思路：

通过人数比 $E$ 少一半，大伙都不喜欢傻逼搜索啊（摊手）。

我们先两人对称走，其中一个人走到终点后，留下另一个人，另一个人再单独走出终点。所以这题一个比较直观的思路就是跑两次 $BFS$，把前面两人对称走和一个人单独走分别 $BFS$ 一下就行了。

不过这样比较难写。还有就是前一个 $BFS$ 找到的最短路径 如果再加上后一个 $BFS$ 的答案 就不一定是最小的了，所以我们前一个 $BFS$ 不能只看找到的第一个答案，而是需要遍历到所有情况，这样的话第二段的 $BFS$ 就要跑好几次，有可能会超时。

考虑到我们只需要找到最少的步数，而不需要知道中间过程，所以第二段我们只需要知道某个位置到出口最短的距离是多少，这可以直接从所有终点 $BFS$ 到整个地图预处理出来。第一个 $BFS$ 比较好写，就是一个简单的 $BFS$，不过走到下一个位置的时候需要推出对称位置，再把限制条件再写一遍（比如不能出界，不能走到陷阱，不能走到已经走过的点）。

推出对称点用的是中点坐标公式，假设两个点坐标分别为 $(x_1,y_1)(x_2,y_2)$，中点坐标为 $(x,y)$，那么就有 $x=\frac{x_1+x_2}{2},y=\frac{y_1+y_2}{2}$。而对于中心对称来说，原点和对称点就是上面的两点，对称中心点就是中点，知道中点坐标 $(x,y)$，知道原点坐标 $(x_1,y_1)$，那么对称点坐标就是 $(x_2,y_2)=(2x-x_1,2y-y_1)$。我是这样想的：两点坐标加起来就是两倍中点坐标，所以两倍中点减去一个点就是另一个点。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <array>
using namespace std;
const int maxn=2e3+5;
const int inf=1e9;int n,m,sx,sy;
int fx[]={1,-1,0,0},fy[]={0,0,1,-1};
string mp[maxn];
int dis[maxn][maxn];void init(){vector<vector<bool> > vis(n+1,vector<bool>(m+1,false));memset(dis,0x3f,sizeof(dis));queue<array<int,3> > q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='@'){q.push({i,j,0});vis[i][j]=true;}while(!q.empty()){auto [ux,uy,d]=q.front();q.pop();dis[ux][uy]=d;for(int i=0,x,y;i<4;i++){x=ux+fx[i];y=uy+fy[i];if(x<1 || x>n || y<1 || y>m)continue;if(mp[x][y]=='#')continue;if(vis[x][y])continue;q.push({x,y,d+1});vis[x][y]=true;}}
}
int bfs(int sx,int sy){int ans=inf;vector<vector<bool> > vis(n+1,vector<bool>(m+1,false));queue<array<int,3> > q;q.push({sx,sy,0});vis[sx][sy]=true;while(!q.empty()){auto [ux,uy,d]=q.front();q.pop();if(mp[ux][uy]=='@'){ans=min(ans,d+dis[2*sx-ux][2*sy-uy]);}for(int i=0,x,y,rx,ry;i<4;i++){x=ux+fx[i];y=uy+fy[i];rx=sx*2-x;ry=sy*2-y;if(x<1 || x>n || y<1 || y>m)continue;if(rx<1 || rx>n || ry<1 || ry>m)continue;if(mp[x][y]=='#' || mp[rx][ry]=='#')continue;if(vis[x][y])continue;q.push({x,y,d+1});vis[x][y]=true;}}return ans==inf?-1:ans;
}int main(){cin>>n>>m>>sx>>sy;for(int i=1;i<=n;i++){cin>>mp[i];mp[i]=" "+mp[i];}init();cout<<bfs(sx,sy);return 0;
}

---

E ACM中的CM题

思路1（三分）：

其实能不能算正解我也不清楚，总感觉很悬，非常粗糙的做法。

可以想到我们一定先提高能力，准备好了之后再排雷，不然你先排雷再提高能力，总次数没有减少，排雷的范围还小，不划算。

我们把能力提高到 $m$，然后算最少的排雷次数，把提高能力和排雷次数加起来就是总共花费的时间。

这个算最少排雷次数可以 $O(n)$ 来算，也可以 $O(n\log n)$。

$O(n)$ 写法就是从小到大枚举有雷的位置，假设上次排雷的范围是 $[l,r]$，如果这个雷在范围内就跳过（因为在范围内就说明这个雷被排过了），如果不在范围内，就以它的位置为左端点 $l$，开始新一轮的排雷，数一下中间重置了几次 $l$ 就是排雷次数。

$O(n\log n)$ 的写法是用 $set$，把雷的位置存入，每次以未被排过的位置最小的雷开始排，用 $uppe{r}_{b}ound$ 找到下一个未被排过的雷，跳到最后，跳的次数就是排雷次数。这个方法的时间复杂度准确来说应该是 排雷次数乘以 $\log n$。

我们把能力提高到 $m$ 的 $m$ 看成自变量，总共花费的时间看成是因变量，这个函数就是一个类似 “单谷” 的函数，因为我们能力设的太小或者太大都会导致花费的时间大大增加，只有处在中间的某个位置的时候花费时间才少。可以想到用三分来解决。

不过这不是一个单纯的单谷函数，而是一个大致形状类似单谷，在局部上可能会“抖动”，那么我们可以把范围缩小到一定程度，然后在一个小范围内暴力地计算答案。

code：

#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;int n,a[maxn];int check(int m){//当排雷能力变为m时的花费时间int ans=m;for(int i=1,l,r=0;i<=n;i++){if(r<a[i]){l=a[i];r=l+m;ans++;}}return ans;
}int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int l=0,r=2e5,lm,rm;while(l+1000<r){lm=l*2/3+r/3;rm=l/3+r*2/3;if(check(lm)<check(rm))r=rm;else l=lm;
//		cout<<l<<" "<<r<<" "<<check(lm)<<" "<<check(rm)<<endl;}int ans=1e9;for(int i=l;i<=r;i++)ans=min(ans,check(i));cout<<ans<<endl;return 0;
}

思路2（调和级数）：

上面说过 $O(n\log n)$ 的写法的时间复杂度准确来说应该是 排雷次数乘以 $\log n$。而当 $m$ 比较大的时候，排雷次数就会变少，最坏情况下就是 $2e5$ 的位置里每个位置都有雷，那么时间复杂度就是 $\frac{20000}{m}\ast \log n$。

如果我们暴力地来枚举 $m$，时间复杂度一共是 $\frac{200000}{1}\ast \log n+\frac{200000}{2}\ast \log n+\cdots +\frac{200000}{200000}\ast \log n=200000\log n\ast (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{200000})$，括号内的数是调和级数，其和约等于 $\ln 200000\approx \log n$，因此时间复杂度变成 $=n{\log }^{2}n$。

所以我们如果用这所谓的 $O(n\log n)$ 的写法，就可以直接暴力地算。

code：

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=2e5+5;int n;
set<int> S;int check(int m){int ans=m;set<int>::iterator it=S.begin();while(it!=S.end()){it=S.upper_bound(*it+m);ans++;}return ans;
}int main(){cin>>n;for(int i=1,t;i<=n;i++){cin>>t;S.insert(t);}int ans=1e9;for(int i=0;i<=200000;i++)ans=min(ans,check(i));cout<<ans<<endl;return 0;
}

---

F ACM中的ACM题

思路：

三元环计数，虽然不是用来计数而是用并查集把边加入同一个集合，大体做法是差不多的。三元环计数的讲解可以看 OI wiki

首先可以想到如果有一条边连接了 $ux$，另一条边连接了 $uy$，如果想要这两条边同属一个集合，那就必须连接 $xy$。也就是必须是三元环才能让环上三边同属一个集合。

我们在三元环计数的时候，其实是比较暴力地枚举三元环上的三个点三条边，只是我们是通过按顺序不重复地枚举，导致时间复杂度降为了 $O(n\sqrt{n})$。因为我们枚举出了所有三元环的三边，所以我们用三元环计数的写法，把计数的部分改成用并查集将三边合并成同一个集合，最后看一下所有边是否被合并到了同一个集合即可。

三元环计数在 这场K题 也考过一次。

code：

#include <iostream>
#include <cstdio>
#include <array>
#include <vector>
using namespace std;
const int maxn=2e5+5;int T,n,m;int deg[maxn];
array<int,2> edge[maxn];int head[maxn],ent;
struct edge{int v,id,nxt;
}e[maxn];
void add(int u,int v,int id){e[++ent]={v,id,head[u]};head[u]=ent;
}int vis[maxn];int f[maxn];
void init(){for(int i=1;i<=n;i++)deg[i]=0;for(int i=1;i<=n;i++)head[i]=0;ent=0;for(int i=1;i<=m;i++)f[i]=i;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){int fx=find(x),fy=find(y);f[fy]=fx;
}int main(){cin>>T;while(T--){cin>>n>>m;init();for(int i=1;i<=m;i++){auto &[u,v]=edge[i];cin>>u>>v;deg[u]++;deg[v]++;}for(int i=1;i<=m;i++){auto &[u,v]=edge[i];if(deg[u]<deg[v] || (deg[u]==deg[v] && u>v))swap(u,v);add(u,v,i);}for(int u=1;u<=n;u++){for(int i=head[u];i;i=e[i].nxt)vis[e[i].v]=e[i].id;for(int i=head[u],v,id1;i;i=e[i].nxt){v=e[i].v;id1=e[i].id;for(int j=head[v],w,id2;j;j=e[j].nxt){w=e[j].v;id2=e[j].id;if(vis[w]){merge(vis[w],id1);merge(id1,id2);}}}for(int i=head[u];i;i=e[i].nxt)vis[e[i].v]=0;}int cnt=0;for(int i=1;i<=m;i++)if(f[i]==i)cnt++;puts((cnt==1)?"Yes":"No");}return 0;
}

这篇关于牛客小白月赛100（A,B,C,D,E,F三元环计数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---