qbxt刷题营day1
长春花
通过暴力，我们可以发现答案通常很小。通过对范围内所有的p 进行验证，答案的最大值为 31。因此，我们首先维护出 v[i]表示是否存在 x满足x^2三i(modp) 。随后，我们直接暴力枚举a 的值并 check 即可。时间复杂度为O（ans*p） ，其中在p<=10^5时ans<=31 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int v[100005],g[100005];
int ans=0;
signed main(){
int p=read();
memset(v,-1,sizeof(v));
for(int i=0;i<p;i++){
if(v[(i*i)%p]==-1){
v[(i*i)%p]=i;
}
}
for(int i=0;i<p;i++){
for(int j=0;j<p;j++){
if(v[(((i-j*j)%p)+p)%p]!=-1){
ans=max(ans,j);
break;
}
}
}
cout<<ans<<endl;
}
紫罗兰
统计无项不带权图中的最小环个数。
考虑BFS，以每一个点为起点，第一次访问到某个节点时更新对应的最短路，如果是第二次访问，那么dis[u]+dis[v]+1一定是一个环。
对于一个无向图的BFS生成树，我们可以发现在搜索时找到的边只有以下两种：横插边和前向边。
当前搜索到的节点如果已经被搜索过，那么该节点在BFS生成树上的深度一定和当前节点相等或比当前节点大一，（其实也有小1的情况，只是这种情况下这条边一定已经被遍历过了。当然，等于的情况也有可能已经被遍历过，所以奇数环的个数要额外/2）因为BFS生成树上除了队列中的节点以外的节点的邻边一定已经被搜索完毕，所以搜到的节点要么从未搜到，要么在队列中还未搜索。
如果搜到的节点v的深度比当前节点u大一，那么v的最短路径条数加上u的最短路径条数。
所以当我们找到v时，我们找到的不只是一个环，而是way[u]*way[v]个。
找到的也有可能不是一个简单环，而是一个有公共部分的环...不过它的简单环部分一定会被计数，而其本身也不是最小环，所以可以不考虑。（也可以通过记录由原点的某一个邻边扩展而来来避免此类问题）
对于计数部分，可以注意到：
1.以环上任意一点均会将环统计一次，所以答案要/len;
2.奇数环的每条边被重复计数两次，要额外/2;
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn=1e6+10;
int ans=0x3f3f3f3f,cnt=0;
int head[maxn],nxt[maxn],to[maxn],tot;
int vis[maxn],way[maxn];
int dis[maxn];
queue<int>q;
void add(int u,int v){
nxt[++tot]=head[u],to[head[u]=tot]=v;
}
int main(){
int n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[j]=0x3f3f3f3f;
way[j]=0;
}
// for(int j=1;j<=tot;j++)vis[j]=0;
dis[i]=0;
way[i]=1;
q.push(i);
while(!q.empty()){
int u=q.front();
q.pop();
for(int k=head[u];k;k=nxt[k]){
int v=to[k];
//cout<<v<<" "<<dis[v]<<endl;
if(dis[u]+1==dis[v]||dis[u]==dis[v]){
int len=dis[u]+dis[v]+1;
if(len<ans){
ans=len;
cnt=way[u]*way[v];
}
else if(len==ans){
cnt+=way[u]*way[v];
}
}
if(dis[v]>dis[u]+1) {
way[v]=way[u];
dis[v]=dis[u]+1;
q.push(v);
}
else if(dis[v]==dis[u]+1){
way[v]+=way[u];
}
}
}
}printf("%d\n",ans%2?cnt/ans/2:cnt/ans);
}
天竺葵
当n=m-1 时，问题转化成有 m个变量，第i变量的取值为 [li,ri]，且任意两个变量不相等，构造 一组方案。我们可以将所有区间按照左端点排序，随后扫 li时贪心的选择 ri最小的来放置。
当m>n-1 时，每条非树边会有额外的限制：非树边(u,v) 的边权必须严格大于路径u->v 的边权 最小值。因此，对于一条非树边，我们只有在这条路径上所有的边均被赋值后，才可以赋非树边的值。 因此我们仍然按照 Li排序，但在合并两个联通块时，更新这一轮所联通的非树边，如果一个非树边的两 端点联通，则将其加入堆中即可。
具体的实现我们可以把u到v的边分别挂在这两个端点上，然后在合并两个集合时找到两个集合重合的边，然后合并两个集合。
具体可以用set启发式合并实现。
标签：ch,int,day1,qbxt,maxn,way,dis,节点,刷题 From： https://www.cnblogs.com/Hushizhi/p/16897977.html