2021“MINIEYE杯”中国大学生算法设计超级联赛1

2021/7/21 22:22:20

本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2021“MINIEYE杯”中国大学生算法设计超级联赛1

1001 Mod, Or and Everything

题目大意
求 \(\sum_{i=1}^{n-1}n\ mod\ i\)
\(n<=10^{12}\)
打表找规律n的答案是小于n的第一个\(2^x\)再减去1。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
int read(){
    int sum=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
int work(int x){
    int num=0;
    x>>=1;
    while(x){
        x>>=1;
        num=num<<1|1;
    }
    return num;
}
signed main(){
    int T=read();
    while(T--){
        int ans=0;
        int n=read();
        cout<<work(n-1)<<endl; 
    }
    return 0; 
}

1005

求2~n组成边权为\(lcm(u[i],v[i])\)生成树的边权之和的最小值。
为使答案最小,质数连2,合数连一个约数。统计答案即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
#define MAXN 1e7
#define N 10000000
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
int vis[N],phi[N],pri[N],cnt,ans[N]; 
void init() {
  phi[1] = 1;//0是质数 
  for (int i = 2; i < MAXN; ++i) {
    if (!vis[i]) {
      phi[i] = i - 1;
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] >= MAXN) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j]) {
        phi[i * pri[j]] = phi[i] * (pri[j] - 1);
      } else {
        phi[i * pri[j]] = phi[i] * pri[j];
        break;
      }
    }
  }
}
void pre_work(){
    ans[2]=0;
    for(int i=3;i<=N;i++){
        if(vis[i]==0)ans[i]=ans[i-1]+i*2;
        else ans[i]=ans[i-1]+i;
    }
}
signed main(){
    int T=read();
    init();
    pre_work();
    while(T--){
        int n=read();
        cout<<ans[n]<<endl;
    }
}

1006

给一个数列,求一个最短的区间使其区间异或和大于k
\(n<=100000\)
01trie上维护子树中出现过的前缀异或和在数列中最大位置。然后对于每一个r判断从1~r找到最优答案。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 2147483647
#define N 500100
int ch[N*50][2],mx_pos[N*50],root,tot,sum[N];
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
void update(int now){
	if(ch[now][0])mx_pos[now]=max(mx_pos[ch[now][0]],mx_pos[now]);
	if(ch[now][1])mx_pos[now]=max(mx_pos[ch[now][1]],mx_pos[now]);
}
void add(int tall,int pos,int x,int &now){
	if(now==0)now=++tot;
	if(tall==0){mx_pos[now]=pos;return;}
	int bit=x>>tall-1&1;
	add(tall-1,pos,x,ch[now][bit]); 
	update(now);
}
int check(int tall,int x,int k,int now){
	int bit_k=k>>tall-1&1;
	int bit_x=x>>tall-1&1;
	if(tall==0)return mx_pos[now];
	if(bit_k==0)return max(check(tall-1,x,k,ch[now][bit_x]),mx_pos[ch[now][bit_x^1]]);
	else return mx_pos[ch[now][bit_x^1]]==-1?-1:check(tall-1,x,k,ch[now][bit_x^1]);
}
void init(){
	while(tot){
		mx_pos[tot]=-1;
		ch[tot][0]=ch[tot][1]=0;
		tot--;
	}
	root=0;
}
int main(){
	int T=read();
	memset(mx_pos,-1,sizeof(mx_pos));
	while(T--){
		init(); 
		int ans=INF,ansl=INF,ansr=INF;
		int n=read(),k=read();
		add(31,0,0,root);
		for(int i=1;i<=n;i++){
			sum[i]=sum[i-1]^read();
			int l=check(31,sum[i],k,root)+1;
			add(31,i,sum[i],root);
			if(l==0)continue;
			int tmp=i-l+1;
			if(tmp<ans)ans=tmp,ansl=l,ansr=i;
		}
		if(ans==INF)printf("-1\n");
		else printf("%d %d\n",ansl,ansr);
	}
	return 0;
}

1007

打表然后发现\(f[i]=f[i-1]*(n-1)+(-1)^x(n-1)\)
推一推式子得到\(\frac{n-1}{n}[(n-1)^{t-1}+(-1)^t]=x\)
然后对于t的奇偶讨论,用BSGS求答案就好。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define N 40000
#define int long long
unordered_map<int,int> Map1,Map2;
int p,m;
int ksm(int x,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*x%p;
		b>>=1;
		x=x*x%p;
	}
	return ans;
}
int BSGS(int n,int x1,int x2){
	int tmp=1;
	for(int i=1;i<=m;i++){
		tmp=tmp*n%p;
		Map1[tmp*x1%p]=i;
		Map2[tmp*x2%p]=i;
	}
	n=ksm(n,m);tmp=1;
	for(int i=1;i<=m+1;i++){
		tmp=tmp*n%p;
		int w1=Map1.count(tmp);
		int w2=Map2.count(tmp);
		if(w2)return (i*m-Map2[tmp]+p)*2%p;
		if(w1)return ((i*m-Map1[tmp]+p)*2+1)%p;
	}
	return -1;
} 
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
signed main(){
	p=998244353;m=sqrt(p)+1;
	int T=read();
	while(T--){
		int n=read(),x=read();
		if(x==1){
			printf("0\n");
			continue;
		}
		if(x==0){
			printf("1\n");
			continue;
		}
		x=x*n%p*ksm(n-1,p-2)%p;
		int base=(n-1)*(n-1)%p; 
		Map1.clear();
		Map2.clear();
		int f1=(x+1)%p;
		int f2=(x-1+p)*(n-1)%p;
		int ans=BSGS(base,f1,f2);
		printf("%lld\n",ans);
	}
	return 0;
}

1008

洛谷原题,《月蟾宫》

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s[2010],l[2010],ans,a[2010][2010],num[2010][2010];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        ans=0;
        memset(a,0,sizeof(a));
        memset(num,0,sizeof(num));
        memset(s,0,sizeof(s));
        memset(l,0,sizeof(l));
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j){
                scanf("%d",&num[i][j]);
                if(num[i][j]>=num[i-1][j]) a[i][j]=a[i-1][j]+1;
                else a[i][j]=1;
            }
        for(int top,len,i=1;i<=n;++i){
            top=0; len=0; s[top]=0; l[top]=0;
            for(int j=1;j<=m;++j){
                if(a[i][j]>=s[top]){
                    s[++top]=a[i][j];
                    l[top]=1;
                }else{
                    len=0;
                    while(top&&s[top]>a[i][j]){
                        len+=l[top];
                        ans=max(ans,len*s[top]);
                        --top;
                    }
                    s[++top]=a[i][j];
                    l[top]=len+1;
                }
            }
            len=0;
            while(top){
                len+=l[top];
                ans=max(ans,len*s[top]);
                --top;
               }
           }
           printf("%d\n",ans);
    }
    return 0;
}

1009

二分权值用并查集维护连通块即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 101000
#define M 501000
int fa[N],x[M],w[M],y[M],col[N],n,m,k;
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
int check(int W){
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        if(w[i]<=W){
            int fx=find(x[i]);
            int fy=find(y[i]);
            fa[fx]=fy;
        }
    }
    for(int i=1;i<=n;i++)col[i]=0;
    for(int i=1;i<=n;i++)col[find(i)]=1;
    int ans=0;
    for(int i=1;i<=n;i++)ans+=col[i];
    return ans;
}
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
int main(){
    int T=read();
    while(T--){
        n=read(),m=read(),k=read();
        for(int i=1;i<=m;i++)x[i]=read(),y[i]=read(),w[i]=read();
        int l=0,r=1000000001;
        int ans=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            int tmp=check(mid);
            if(tmp<=k){
                if(tmp==k)ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

1010

HH项链原题,就是询问一个区间的某个值域有多少不同的数。
离线然后树状数组套权值线段树。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 101000
#define mid (L+R>>1)
int sum[N*400],ch[N*400][2],tot,n,m,root[N*20];
int a[N],pre[N],pos[N],ans[N];
struct qu{
    int x0,x1,y0,y1,num;
}q[N];
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
void update(int now){
    sum[now]=sum[ch[now][0]]+sum[ch[now][1]];
}
void add(int L,int R,int x,int w,int &now){
    if(now==0)now=++tot;
    if(L==R){
        sum[now]+=w;
        return;
    }
    if(x>mid)add(mid+1,R,x,w,ch[now][1]);
    else add(L,mid,x,w,ch[now][0]);
    update(now);
}
int check(int L,int R,int l,int r,int now){
    if(now==0)return 0;
    if(L==l&&R==r)return sum[now];
    if(l>mid)return check(mid+1,R,l,r,ch[now][1]);
    else if(r<=mid)return check(L,mid,l,r,ch[now][0]);
    else  return check(L,mid,l,mid,ch[now][0])+check(mid+1,R,mid+1,r,ch[now][1]);
}
bool cmp(qu a,qu b){
    return a.x1<b.x1;
}
int lowbit(int x){
    return x&-x;
}
void ADD(int x,int val,int w){
    for(int i=x;i<=n;i+=lowbit(i)){
        add(1,100001,val,w,root[i]);
    }
}
int query(int x,int l,int r){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        ans+=check(1,100001,l,r,root[i]);
    }
    return ans;
}
int main(){
    int T=read();
    while(T--){
        while(tot){
            ch[tot][0]=ch[tot][1]=sum[tot]=0;
            tot--;
        }
        n=m=0;
        memset(ans,0,sizeof(ans));
        memset(pos,0,sizeof(ans));
        memset(pre,0,sizeof(ans));
        memset(a,0,sizeof(ans));
        memset(root,0,sizeof(ans));
        n=read(),m=read();
        for(int i=1;i<=n;i++){
            a[i]=read()+1;
            pre[i]=pos[a[i]]+1;
            pos[a[i]]=i;
        }
        for(int j=1;j<=m;j++)q[j].x0=read(),q[j].y0=read()+1,q[j].x1=read(),q[j].y1=read()+1,q[j].num=j;
        sort(q+1,q+1+m,cmp);
        for(int now=0,i=1;i<=m;i++){
            while(now<q[i].x1){
                now++;
                ADD(pre[now],a[now],+1);
                ADD(now+1,a[now],-1);
            }
            ans[q[i].num]=query(q[i].x0,q[i].y0,q[i].y1);
        }
        for(int i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    return 0; 
}


这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程