[supplementary question] 2021 Niuke summer multi school training camp 1-3

NO.1

H.Hash Function

The question ：

n Different numbers , Find the smallest number , Make this n The results of all the mathematical models are different

Ideas ：

We found that $a\equiv b\mathrm{m}\mathrm{o}\mathrm{d}m$ If and only if $\mid a-b\mid$ Can be $m$ to be divisible by .

In this way, the problem becomes to find a minimum $m$ , Its satisfaction he is not any one $\mid a_i-a_j\mid$ The divisor of .

We found that $1\le |a_i-a_j|\le 5e5$, Consider transforming to find

$(x^{a_1}+x^{a_2}+...+x^{a_n})\ast (x^{-a_1}+x^{-a_2}+...+x^{-a_n})$ The expanded results , The existing coefficient is the result of subtracting any two terms of the original array .

Add negative numbers N Make it a positive number , Last FFT after , Judge when processing N+i Whether the coefficient of the term exists or not .

#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,  Input b Is power ,1 Is the coefficient a 
        B[Bs-b].x=1;// use Bs-b A negative number  
    }
    int bit=20;
    limit=1<<20;//limit Must be greater than the maximum number of times  
    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);// The coefficient , Because it's subtraction , Added Bs, Greater than Bs And meet the requirements , Determine whether there is a modified power  
    
    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

Yes n A station , The opening hours of each station are $[u_i,v_i]$ , The vehicle passes through the i From the first station to the i + 1 The time for each station is $cost[i]$ , If you arrive at a station in advance, you can wait , If you reach the i There are more than stations in the world $v_i$ You can't stop at this station , Yes q operations

0 l r : : Power on l Station departure stops at each station and finally arrives at r Station , Can output Yes, Otherwise output No

1 pos c : Will be the first pos The time from the station to the next station is modified to c

2 pos : Will be the first pos The opening hours of the station are changed to $[l,r]$

Ideas ：

Segment tree interval merging ,

#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{
    
//  Get to the next station at the earliest   Arrive at the latest   After spending time   Can we get to  
	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;// to update 
	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.

Give a n ∗ m Matrix , It's all white at first , Can spend $cost[i][j]$ Put the grid $(i,j)$ Blacken , You can also select two lines by magic $x1,x2$ And two columns $y1,y2$, If three of the four points in the mark are black , Then the fourth point can be dyed black directly

Ideas ：

Analyze the options n+m-1 Just a little bit , Of course, it's not optional , Think of rows and columns as points , Point as edge , Make a new picture , Just find the smallest spanning tree

#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);
}