牛客练习赛92

练习赛92"/>

牛客练习赛92

a.链接：登录—专业IT笔试面试备考平台_牛客网

总结：求平均数的时候，尽量不直接输出sum/n。习惯性输出前面几个aaaaa，然后输出最后一个sum-a*5。这样可以保证输出的一定是int，而不是小数强制转换之后的int。

int main()
{ll a,b,n;cin>>n>>a>>b;for(int i=1;i<n;i++){cout<<a<<' ';}cout<<b*n-a*n+a<<endl;
}

b.链接：登录—专业IT笔试面试备考平台_牛客网

总结：遇到需要将N个数字分成几组的这种情况，直接将前几个数字，每一个划分成一个组。该题在倒数第二组的时候把（sum-列队中即将出列的数字）如果不为0，则直接划分为一组，然后把后面的数字划分为最后一组。如果为0，则简单的换一下顺序输出即可。

c.链接：登录—专业IT笔试面试备考平台_牛客网
总结：遇见这种情况其实是组合问题，该问题划分为三个组合，第一个点数与能够组成Cn2条线，第二个是a与总条数的组合问题CCn2a，第三个是a与b条数的组合问题Cab，学习的两点是卢卡斯（lucas）定理，代码：C(a%mod,b%mod)*lucas(a/mod,b/mod)%mod;逆元里的费马小定理：amodp（p为素数时成立），a逆元是a的p-2次方。

需要注意的一点是：不可直接输出最后的Cab，而是需要求出总数，减去不存在的数字

ans = C(n*(n-1)/2, a)*C(n*(n-1)/2, b)%mod+mod;
ans -= C(n*(n-1)/2, a)*C(n*(n-1)/2 - a, b)%mod;

d.链接：登录—专业IT笔试面试备考平台_牛客网
总结：在图论里面，就这道题，选择逆向思考，如果有一个点有两条线路的话，那么就算是一个可以成功逃出的点，于是逃出点可以慢慢往前面挪动，直到接近1.最后如果1也被认定成可以逃出的点的话，那么则是yes。

比较有意思的是可以用数组模拟出数组指针指向上一个点的操作。而上一个点如果之前没有点存在的话则指向0。

for(int i=1;i<=m;i++){int v,u;cin>>v>>u;add_e(v,u);add_e(u,v);
}
void add_e(int v,int u){e[++tot].to=u;e[tot].next=head[v];head[v]=tot;
}

把每个点压进队列中：

queue <int > q;
for(int i=1;i<=k;i++){int x;cin>>x;vis[x]=1;q.push(x);
}

然后通过列队来进行模拟前推可逃出点的操作

while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(vis[v]==1)continue;du[v]++;if(du[v]>1){vis[v]=1;q.push(v);}}
}

e.链接：登录—专业IT笔试面试备考平台_牛客网

这道题感谢：坂井泉水唯一指定女友。过题代码的注释，万分感谢。

思路：

//题意：对n个数a[i]（sum<=1e13）,选定j和k使得满足a[i]%j==k的数最多

//思路：a[i]%2==0or1,所以至少(n+1)/2个答案

//随机x和y,1/4的可能性在答案内，x%j==y%j,(x-y)%j=0

//d=x-y,对d质因数分解,这些都是可能的j，加入集合s

//对s的每个元素j随机x,1/2的可能性a[x]在答案内，a[x]%j就是可能的k

//如果a[x]%j=k的次数大于某个数，说明是可能的答案

//按以上流程选定j和k进行计算:枚举a[1]~a[n],统计a[i]%j==k的个数ansnow

//对于每个选定的j和k,ans=max(ans,ansnow)

总结：先用一个质数筛，筛出质数数组。很关键的一点是：x%j==y%j,(x-y)%j=0，d=x-y,对d质因数分解。用随机筛出的x,y相减，用之前的质数数组挨个对d取模，若存在d%p[i]==0的话那么p[i]就是可能存在的一个点，然后对d操作while(d%p[i]==0)d=d/p[i];这样再次取出一个数字d存入set里面。之后用随机的方式去取答案

s.insert((ll)2); //2很有可能是答案，保底//下面对每种可能的因子进行答案计算,复杂度o(s.size()*t*n*10)ll ans=0,ansnow,k;map<ll,ll>mp; //记录a[i]%k的个数,越多是答案的可能性越大for(auto j:s){mp.clear(); //每个不同t=2000;     //随机a[i]/j,有1/2的可能a[i]在答案内while(t--){x=rand()%n+1;k=a[x]%j;mp[k]++;if(mp[k]==200) //出现次数较多，才会进行计算{ansnow=0;for(i=1;i<=n;i++){if(a[i]%j==k)ansnow++;}ans=max(ans,ansnow);}}}

总结完毕，时间：2021/12/10 22：11