• 周日. 5月 26th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

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

admin

11月 28, 2021

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

1002 Rocket land

题解说是K-Dtree裸题,APIO2018D1T1?

但是我的K-Dtree T了?

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long
#define mid (L+R>>1)
const int N=501000;
const int K=2;
const double e=0.75;
int sum[N],ch[N][2],val[N],mx[N][K],mn[N][K],d[N][K],size[N];
int now_D,stack[N],top,tot,root;
int a[N],b[2][K];
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 x){
    int l=ch[x][0],r=ch[x][1];
    sum[x]=sum[l]+sum[r]+val[x];
    size[x]=size[l]+size[r]+1;
    if(l)mx[x][0]=max(mx[x][0],mx[l][0]),mn[x][0]=min(mn[x][0],mn[l][0]);
    if(r)mx[x][0]=max(mx[x][0],mx[r][0]),mn[x][0]=min(mn[x][0],mn[r][0]);
    if(l)mx[x][1]=max(mx[x][1],mx[l][1]),mn[x][1]=min(mn[x][1],mn[l][1]);
    if(r)mx[x][1]=max(mx[x][1],mx[r][1]),mn[x][1]=min(mn[x][1],mn[r][1]);
}
bool cmp(int x,int y){
    return d[x][now_D]<d[y][now_D];
}
int build(int L,int R,int D){
    if(L>R)return 0;
    now_D=D;
    nth_element(stack+L,stack+mid,stack+R+1,cmp);
    int now=stack[mid];
    sum[now]=val[now];
    mx[now][0]=mn[now][0]=d[now][0];
    mx[now][1]=mn[now][1]=d[now][1];
    ch[now][0]=build(L,mid-1,(D+1)%K);
    ch[now][1]=build(mid+1,R,(D+1)%K);
    update(now);
    return now;
}
void recycle(int now){
    if(ch[now][0])recycle(ch[now][0]);
    stack[++top]=now;
    if(ch[now][1])recycle(ch[now][1]); 
} 
void rebuild(int &now,int D){
    top=0;recycle(now);
    now=build(1,top,D);
}
bool check(int now){
    return size[ch[now][0]]>e*size[now]||size[ch[now][1]]>e*size[now];
}
void ins(int &x,int w,int D){
    if(!x){
        x=++tot;
        size[x]=1;sum[x]=val[x]=w;
        ch[x][0]=ch[x][1]=0;
        mx[x][0]=mn[x][0]=d[x][0]=a[0];
        mx[x][1]=mn[x][1]=d[x][1]=a[1];
        return;
    }
    if(a[D]<d[x][D])ins(ch[x][0],w,(D+1)%K);
    else ins(ch[x][1],w,(D+1)%K);
    update(x);
    if(check(x))rebuild(x,D);
}
bool judge_all(int x,int y,int r,int now){
    if(!now)return false;
    LL tmp=0,cnt=0;
    if(1ll*(mn[now][0]-x)*(mn[now][0]-x)+1ll*(mn[now][1]-y)*(mn[now][1]-y)<=1ll*r*r)cnt++;
    if(1ll*(mx[now][0]-x)*(mx[now][0]-x)+1ll*(mn[now][1]-y)*(mn[now][1]-y)<=1ll*r*r)cnt++;
    if(1ll*(mn[now][0]-x)*(mn[now][0]-x)+1ll*(mx[now][1]-y)*(mx[now][1]-y)<=1ll*r*r)cnt++;
    if(1ll*(mx[now][0]-x)*(mx[now][0]-x)+1ll*(mx[now][1]-y)*(mx[now][1]-y)<=1ll*r*r)cnt++;
    if(cnt==4)return true;
    return false;
}
bool judge_node(int x,int y,int r,int now){
    if(!now)return false;
    LL tmp=1ll*(d[now][0]-x)*(d[now][0]-x)+1ll*(d[now][1]-y)*(d[now][1]-y);
    if(tmp<=1ll*r*r)return true;
    else return false;
}
bool judge(int x,int y,int r,int now){
    if(!now)return false;
    int x_1=x-r,x_2=x+r,y_1=y-r,y_2=y+r;
    int x_mid=(x_1+x_2),y_mid=(y_1+y_2),X_mid=(mn[now][0]+mx[now][0]),Y_mid=(mn[now][1]+mx[now][1]);
    if(1LL*abs(x_mid-X_mid)<=1LL*x_2-x_1+mx[now][0]-mn[now][0]&&1LL*abs(y_mid-Y_mid)<=1LL*y_2-y_1+mx[now][1]-mn[now][1])return true;
    else return false;    
}
LL check(int x,int y,int r,int now){
    LL ans=0;
    if(judge_all(x,y,r,now))return sum[now];
    if(!judge(x,y,r,now))return 0;
    if(judge_node(x,y,r,now))ans+=val[now];
    if(judge(x,y,r,ch[now][0]))ans+=check(x,y,r,ch[now][0]);
    if(judge(x,y,r,ch[now][1]))ans+=check(x,y,r,ch[now][1]);
    return ans;
}
int main(){
//    freopen("1.in","r",stdin);
//    freopen("xdx.out","w",stdout);
    int T=read();
    while(T--){
        int n=read();
        for(int i=1;i<=n;i++){
            for(int j=0;j<K;j++)a[j]=read();
            int w=read();
            ins(root,w,0);
            printf("%lld
",check(a[0],a[1],read(),root));
        }
        tot=root=0;
    }
    return 0;
}

1005 Minimum spanning tree

求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 Xor sum

给一个数列,求一个最短的区间使其区间异或和大于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
");
		else printf("%d %d
",ansl,ansr);
	}
	return 0;
}

1007 Pass!

打表然后发现(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
");
			continue;
		}
		if(x==0){
			printf("1
");
			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
",ans);
	}
	return 0;
}

1008 Maximal submatrix

洛谷原题,《月蟾宫》

#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
",ans);
    }
    return 0;
}

1009 KD-Graph

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

#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
",ans);
    }
    return 0;
}

1010 zoto

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
",ans[i]);
    }
    return 0; 
}

《2021“MINIEYE杯”中国大学生算法设计超级联赛1》有2个想法
  1. Wow, awesome blog layout! How lengthy have you
    been blogging for? you make blogging look easy. The total glance of your site is great, let alone the content material!
    You can see similar here ecommerce

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注