[数据结构与算法]牛客练习赛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