A.牛牛的mex

题目传送门

牛牛的mex

题目大意

给你一个长度为n的序列a1~an（0<=ai<n且ai互不相同），有q次询问，每次想询问区间[l,r]中最小的未出现的自然数。

思路

由于每个0~n-1每个数字都只出现了一次，于是我们可以记下每个数字出现的位置，然后每次询问都从小到大进行遍历，如果该数不在询问范围内，那么它就是答案。

AC Code

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,q,a[N],b[N]; int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%d",&a[i]);          b[a[i]]=i; } while(q--) { int l,r; int flag=0; scanf("%d%d",&l,&r); for(int i=0;i<n;i++) { if(b[i]>r||b[i]<l) {                 flag=1; printf("%dn",i); break; } } if(flag==0) printf("%dn",n); } system("pause"); return 0; } 

B.牛牛的算术

题目传送门

牛牛的算术

题目大意

题目简洁清晰，截图贴上

思路

推一下式子

我们可以发现当n>=199999时，因为是连乘，所以取模后答案肯定是0，所以只需要考虑n<199999的情况。

然后计算这个式子只需维护两个前缀和即可
1、1+2+3+…+j==j(j+1)/2

2、j * j(j+1)/2

AC Code

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod=199999,N=2e5+10; LL sum[N],res[N]; char str[N]; int main() { int T; scanf("%d",&T); getchar();     sum[1]=1; for(int i=2;i<=N;i++)         sum[i]=(sum[i-1]+i)%mod;     LL ans=1;     res[1]=1; for(int i=2;i<=mod;i++) {         res[i]=res[i-1]*(ans+sum[i]*i%mod)%mod*i%mod;         ans=(ans+sum[i]*i%mod)%mod; } while(T--) { gets(str); int len=strlen(str); if(len>6||(len==6&&str[0]>='2')) printf("0n"); else { int k=0; for(int i=0;i<len;i++)                 k=k*10+str[i]-'0'; if(k==199999) printf("0n"); else printf("%dn",res[k]); } } system("pause"); return 0; } 

C.牛牛的无向图

题目传送门

牛牛的无向图

题目大意

有一张n个点，m条边的无向图，每条边有边权wi。定义一条路径的权值是这条路径上边的最大值。定义d(u,v)是点u到点v的所有路径中权值最小的路径。多次询问，每次给出一个L，问有多少无序点对的d不超过L。

思路

(比赛中没有做出，赛后参照了别人的想法)
由定义，d(u,v)等于最小瓶颈生成树上(我也是第一次接触这个名词，如果你也不知道，可以自行百度一下)，u到v路径上权值最大的边。而最小生成树是最小瓶颈生成树。所以问题就转化为：对于每个L，有多少最小生成树上的点对，满足点对路径上权值最大的边的权值不超过L。

由于最小生成树至多n-1条边，权值至多n-1种。因此可以按照树上边权从小到大的顺序维护点对个数的前缀和。这个可以用并查集统计，即在跑Kruskal的时候维护连通块大小，如果要用权值为w的把A，B两个连通块合并，那么A中的每个点和B 中的每个点间路径上权值最大的边的权值恰为w，即w产生的点对个数贡献为A*B。
处理出前缀和，每次进行二分就可以快速找到答案。

AC Code

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10,M=5e5+10; unsigned int SA, SB, SC; int n, m, q, LIM;//n个点，m条边，q个询问 LL L[M]; struct node{     LL u,v,w; }line[M]; LL num[M],ans[N],fa[N]; LL choose[N],th=n,sh=0; bool cmp(node a,node b) { return a.w<b.w; } LL find(LL x) {//并查集 if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } unsigned int rng61(){     SA ^= SA << 16;     SA ^= SA >> 5;     SA ^= SA << 1; unsigned int t = SA;     SA = SB;     SB = SC;     SC ^= t ^ SA; return SC; } void gen(){ scanf("%d%d%d%u%u%u%d", &n, &m, &q, &SA, &SB, &SC, &LIM); for(int i = 1; i <= m; i++){         line[i].u = rng61() % n + 1;         line[i].v = rng61() % n + 1;         line[i].w = rng61() % LIM; } for(int i = 1; i <= q; i++){         L[i] = rng61() % LIM; } } LL solve(LL k) {//二分函数     LL l=0,r=sh; while(l<r) {         LL mid=(l+r+1)/2; if(choose[mid]>k) r=mid-1; else l=mid; } return num[l]; } int main() { gen(); sort(line+1,line+1+m,cmp);//按边权从小到大排序 for(int i=1;i<=n;i++) {         ans[i]=1;//每个集合的点的数量         fa[i]=i;//并查集数组初始化 }     num[0]=0;     th=n,sh=0; for(int i=1;i<=m&&th>1;i++) { int du=find(line[i].u),dv=find(line[i].v); if(du==dv) continue; else {             th--;             sh++;             fa[dv]=du;//合并             num[sh]=num[sh-1]+1LL*ans[du]*ans[dv];//加上以这条边为路径权值的点集             ans[du]+=ans[dv];             choose[sh]=line[i].w; } }     LL res=0; for(int i=1;i<=q;i++)         res^=solve(L[i]); printf("%lldn",res); system("pause"); return 0; }