2021HDU多校1
比赛地址
A题 Mod, Or and Everything 题目地址
题目大意:求(n mod 1) or (n mod 2) or ... or (n mod (n - 1)) or (n mod n).
打表轻松找到规律。
代码:
#include<bits/stdc++.h> using namespace std; long long a[100010]; int main() { long long t; cin>>t; long long n; a[0]=0; a[1]=0; for(int i=2;i<=100000;i++) { a[i]=a[i-1]*2+1; } while(t--) { scanf("%lld",&n); long long nn=1; int cnt=0; while(nn<n) { nn*=2; cnt++; } //cout<<cnt<<endl<<endl; cout<<a[cnt]<<endl; } /*for(int i=1;i<=100;i++) { int ans=0; for(int j=1;j<=i;j++) { ans=ans|(i%j); } cout<<i<<" "<<ans<<endl; }*/ } /* 2 0 2 1 4 3 8 7 16 15 64 31*/
E题 Minimum spanning tree 题目地址
题目大意:两点边权为LCM,求最小生成树。
求质数,每个数都和最小因子连,然后最小因子都和2连,答案为3-n的加和,再加上所有质数和。
代码
#include<bits/stdc++.h> using namespace std; int t; long long n; const int maxnum = 1e7; int prime[maxnum]; void getPrime(){ for(int i=2; i<maxnum; i++){ if(prime[i]==0){ prime[++prime[0]]=i; } for(int j = 1;j<=prime[0]&&i*prime[j]<=maxnum;j++){ prime[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main() { getPrime(); cin>>t; while(t--) { cin>>n; long long ans=(long long)(3+n)*(n-2)/2; for(int i=2;i<=prime[0];i++) { if(prime[i]<=n) { ans+=prime[i]; } } cout<<ans<<endl; } }
H题 Maximal submatrix 题目地址
题目大意:给出一个矩阵,要你找一个最大的子矩阵,要求这个子矩阵每一列从上往下都是单调不下降序列。输出最大子矩阵的面积。
先标记好单调序列,然后直接找最大矩阵(单调栈)。
代码
#include<bits/stdc++.h> using namespace std; int n,m; int a[2010][2010]; int sum[2010][2010]; int stk[2010],top=0; int w[2010]; int now[2010]; int main() { int t; cin>>t; while(t--) { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]>=a[i-1][j]) sum[i][j]=sum[i-1][j]+1; else sum[i][j]=1; } } int res=0; for(int i=1;i<=n;i++) { top=0; for(int j=1;j<=m;j++) now[j]=sum[i][j]; int ans=0; for(int j=1;j<=m;j++) { int x=now[j]; if(top==0||stk[top]<=x) stk[++top]=x,w[top]=1; else { int wid=0; while(top&&stk[top]>x) { wid+=w[top]; ans= max(ans,wid*stk[top]); top-= 1; } stk[++top]=x; w[top]=wid+1; } } int wid=0; while(top) { wid+=w[top]; ans=max(ans,stk[top]*wid); top--; } res=max(ans,res); } printf("%d\n",res); } return 0; }
I题 KD-Graph 题目地址
题目大意:给定一个图,求一个长度D,使得这个图可以分成K份,满足每一份之中的两两之间的距离 <= D,两份之间距离要>D。
思路:
贪心+并查集,只需要把不断把最小的边加入,求出来D。
代码:
#include<bits/stdc++.h> using namespace std; struct dian { int x,y,w; }a[500010]; int n,m,k; bool cmp(dian a,dian b) { return a.w < b.w; } int fa[100010]; void init() { for(int i=0;i<100010;i++) fa[i] = i; } int Find(int x) { if(x == fa[x]) return x; return fa[x] = Find(fa[x]); } bool merge(int x,int y) { x = Find(x); y = Find(y); if(x != y) { fa[x] = y; return 1; } return 0; } int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%d %d %d",&n,&m,&k); for(int i=0;i<m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); if(n == k) { cout<<"0"<<endl; } else { sort(a,a+m,cmp); int nn=n; int ans=-1; int i=0; while(i<m) { int cw=a[i].w; while(i<m&&cw==a[i].w) { int x=a[i].x; int y=a[i].y; if(merge(x,y)) nn--; i++; } if(nn==k) { ans=cw; break; } } printf("%d\n",ans); } } }