当前位置：网站首页>【补题】2021牛客暑期多校训练营1-3

【补题】2021牛客暑期多校训练营1-3

2022-06-25 06:43:00 【mfy的1号小迷弟】

NO.1

H.Hash Function

题意：

n个互不相同的数，找一个最小的数，使得这n个数模它的结果都不一样

思路：

我们发现 a ≡ b m o d    m a\equiv b\mod m a≡bmodm 当且仅当 ∣ a − b ∣ ∣ a − b ∣ ∣a−b∣ 能被 m m m 整除。

这样问题就转化成求一个最小的 m m m ，其满足他不是任何一个 ∣ a i − a j ∣ ∣ a_i − a_j ∣ ∣ai​−aj​∣ 的约数。

我们发现 1 ≤ ∣ a i − a j ∣ ≤ 5 e 5 1\leq|a_i-a_j|\leq5e5 1≤∣ai​−aj​∣≤5e5，考虑转化求

( x a 1 + x a 2 + . . . + x a n ) ∗ ( x − a 1 + x − a 2 + . . . + x − a n ) (x^{a_1} +x^{a_2}+...+x^{a_n})*(x^{-a_1} +x^{-a_2}+...+x^{-a_n}) (xa1​+xa2​+...+xan​)∗(x−a1​+x−a2​+...+x−an​)展开后的结果，存在的系数即为原数组任意两项相减的结果。

把负数加N使其变成正数，最后FFT后，处理时判断N+i项的系数是否存在即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=(1<<20)+5;
const double PI=acos(-1);
struct Complex
{
    
    double x,y;
    Complex operator+(const Complex &o) const{
    return{
    x+o.x,y+o.y};}  
    Complex operator-(const Complex &o) const{
    return{
    x-o.x,y-o.y};}  
    Complex operator*(const Complex &o) const{
    return{
    x*o.x-y*o.y,x*o.y+y*o.x};} 
}A[maxn],B[maxn];
int rev[maxn];
int limit=1;
void FFT(Complex *a,int inv){
    
    for(int i=0;i<limit;i++)
	    if(i<rev[i])swap(a[i],a[rev[i]]);

    for(int mid=1;mid<limit;mid<<=1){
    
        Complex Wn=Complex({
    cos(PI/mid),inv*sin(PI/mid)});

        for(int i=0;i<limit;i+=mid*2){
    
            Complex w=Complex({
    1,0});
            for(int j=0;j<mid;j++,w=w*Wn){
    
                Complex x=a[i+j],y=w*a[i+j+mid];
                a[i+j]=x+y,a[i+j+mid]=x-y;
            }
        }
    }
    if(inv==-1) for(int i=0;i<limit;i++) A[i].x/=limit;
}
// --------FFT
int n;
const int Bs=500000;
int vis[maxn];
int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        int b;
        cin>>b;
        A[b].x=1;//ax^b, 输入的b是次方，1为系数a 
        B[Bs-b].x=1;//用Bs-b表示负数 
    }
    int bit=20;
    limit=1<<20;//limit要大于最高次数 
    for(int i=1;i<limit;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1); 
    FFT(A,1),FFT(B,1);
    for(int i=0;i<limit;i++) A[i]=A[i]*B[i];
    FFT(A,-1);
    for(int i=0;i<=Bs;i++) vis[i]=int(A[i+Bs].x+0.5);//表示系数，因为是减法，加过Bs，大于Bs的符合要求，进行判断是否存在改次方 
    
    for(int i=n;;i++)
    {
    
        bool ok=1;
        for(int j=i;j<=Bs;j+=i)
            if(vis[j]) {
    ok=0;break;}
        if(ok) return cout<<i<<'\n',0;
    }
    return 0;
}

J.Journey among Railway Stations

有 n 个车站，每个车站开放时间为 [ u i , v i ] [ u_i , v_i ] [ui​,vi​] ，车辆经过第 i 个车站到第 i + 1 个车站的时间为 c o s t [ i ] cost[i] cost[i] ，如果提前到达一个车站可以等待，如果到达第 i 个车站的世界超过 v i v_i vi​ 则不能在这个车站停车，有 q 次操作

0 l r : :能否从 l 车站出发经停每个车站最后到达 r 车站，可以输出 Yes，否则输出 No

1 pos c :将第 pos 车站到下一个车站的时间修改为 c

2 pos :将第 pos 车站的开放时间改为 [ l , r ] [l,r] [l,r]

思路：

线段树区间合并，

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=2e6+5;
struct node{
    
// 最早到下一站 最晚到达 经过花费时间 能否到达 
	int u,v,cost,f;
}tr[maxn<<2];
int u[maxn],v[maxn],cost[maxn],t,n,m;
node merge(node a,node b){
    
	node tmp;
	tmp.f=a.f&b.f;
	if(a.u>b.v)tmp.f=0;
	tmp.cost=a.cost+b.cost;//更新
	tmp.u=max(b.u,a.u+b.cost);
	tmp.v=min(a.v,b.v-a.cost);
	return tmp;
}
void build(int rt,int l,int r){
    
	if(l==r){
    
		tr[rt]={
    u[l]+cost[l],v[l],cost[l],1};
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
void update(int rt,int l,int r,int x){
    
	if(l==r){
    
		tr[rt]={
    u[l]+cost[l],v[l],cost[l],1};
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(lson,x);
	else update(rson,x);
	tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
}
node query(int rt,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[rt];
	int mid=(l+r)>>1;
	if(y<=mid)return query(lson,x,y);
	if(x>mid)return query(rson,x,y);
	return merge(query(lson,x,y),query(rson,x,y));
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		    scanf("%d",&u[i]);
		for(int i=1;i<=n;i++)
		    scanf("%d",&v[i]);
		for(int i=1;i<n;i++)
		    scanf("%d",&cost[i]);
		build(1,1,n);
		scanf("%d",&m);
		while(m--){
    
			int op,l,r,q;
			scanf("%d%d%d",&op,&l,&r);
			if(op==0){
    
				if(query(1,1,n,l,r).f)printf("Yes\n");
				else printf("No\n");
			}
			else if(op==1){
    
				cost[l]=r;
				update(1,1,n,l);
			}
			else if(op==2){
    
				scanf("%d",&q);
				u[l]=r,v[l]=q;
				update(1,1,n,l);
			}
		}
	}
}

NO2.

L.

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,q;
vector<int>mp[maxn];
vector<vector<pair<int,int>>>vx(maxn);
int main(){
    
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1,x,y;i<=m;i++){
    
		scanf("%d%d",&x,&y);
		mp[x].push_back(y);
		mp[y].push_back(x);
	}
	for(int i=1,x,y;i<=q;i++){
    
		scanf("%d%d",&x,&y);
		vx[x].push_back({
    y,i});
	}
	for(int i=1;i<=n;i++){
    
		for(int j=1;j<vx[i].size();j++){
    
			vx[i][j].first+=vx[i][j-1].first;
		}
	}
	int tmp=400;
	for(int i=1;i<=n;i++){
    
		int ans=0;
		if(mp[i].size()<=tmp){
    
			for(int j=0;j<vx[i].size();j++){
    
				int t=q;
				int x=vx[i][j].first,y=vx[i][j].second;
				if(j!=vx[i].size()-1)t=vx[i][j+1].second;
				for(auto d:mp[i]){
    
				    auto it=lower_bound(vx[d].begin(),vx[d].end(),(pair<int ,int>){
    x,0});
				    if(it!=vx[d].end()){
    
				    	t=min(t,(*it).second);
					}
				}
				ans+=max(0,t-y);
			}
		}
		else{
    
			vector<int>tor(2e4,2e5+1);
			for(auto j:mp[i]){
    
				for(auto d:vx[j]){
    
					tor[d.first]=min(tor[d.first],d.second);
				}
			}
			for(int j=9999;j;j--)tor[j]=min(tor[j],tor[j+1]);
			for(int j=0;j<vx[i].size();j++){
    
				int x=vx[i][j].first,y=vx[i][j].second,t=q;
				if(j!=vx[i].size()-1)t=vx[i][j+1].second;
				t=min(t,tor[x]);
				ans+=max(0,t-y);
			}
		}
		printf("%d\n",ans);
	}
}

NO.3

B.

给出一个 n ∗ m 的矩阵，初始时都是白色，可以花费掉 c o s t [ i ] [ j ] cost[i][j] cost[i][j] 将格子 ( i , j ) (i,j) (i,j) 染黑，也可以通过魔法选择两行 x 1 , x 2 x1,x2 x1,x2 和两列 y 1 , y 2 y1,y2 y1,y2，如果标记中的四个点有三个点是黑色的，那么第四个点可以直接被染黑

思路：

分析出选择n+m-1个点就可以了，当然不是任意选的，把行和列看成点，点看成边，构成新图，找最小生成树就可以了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll n,m,a,b,c,d,p,ans,fa[maxn];
vector<pair<int,int>>mp[maxn];
int find(int x){
    
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    
	scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&d,&p);
	for(int i=1;i<=n;i++){
    
		for(int j=1;j<=m;j++){
    
			a=(a*a*b+a*c+d)%p;
			mp[a].push_back({
    i,j+n});
		}
	}
	for(int i=1;i<=n+m;i++)fa[i]=i;
	for(int i=0;i<p;i++){
    
		for(auto j:mp[i]){
    
			int x=j.first,y=j.second;
			int fx=find(x),fy=find(y);
			if(fx!=fy){
    
				ans+=i;
				fa[fx]=fy;
			}
		}
	}
	printf("%lld\n",ans);
}
原网站

版权声明
本文为[mfy的1号小迷弟]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_45722843/article/details/119986154

边栏推荐

猜你喜欢

随机推荐