一. Mod, Or and Everything
思路:
当i=n/2+1~n时,n%i依次为(n-1)/2~0(连续,这就保证了从最低位到最高位经过或运算都可以变成1)。
当i< n/2+1时,n%i的最大值<=n/2-1<(n-1)/2,所以不需要考虑。我们只需求余数的最大值((n-1)/2)的位数x。
答案就是二进制下的 x个1变成十进制。收获:或运算只要某一位上有1,结果就有1。
本题代码:
#include<iostream> using namespace std; int t; long long n; int main() { cin>>t; while(t--) { cin>>n; n=(n-1)/2; int ans=0; if(n) { while(n) { n>>=1; ans++; } long long x=1; for(int i=1;i<ans;i++) { x<<=1; x+=1; } cout<<x<<endl; } else cout<<0<<endl; } return 0; }View Code
二. Minimum spanning tree
思路:
最小生成树:包含原图的所有点且边的权重和最小。
每两点之间的权重为两点的最小公倍数。可以让合数x与它的因子连起来,这样权重就是合数x,将大于2的素数x与2连起来,权重就是2*x。
故答案为Σ合数+Σ2*(大于2的)素数
本题代码:
#include<iostream> using namespace std; const int N=1e7+10; int prime[N]; int st[N]; int visit[N]; void Prime(){ for (int i = 2;i <= N; i++) { if (!visit[i]) { prime[++prime[0]] = i; st[i]=1; } for (int j = 1; j <=prime[0] && i*prime[j] <= N; j++) { visit[i*prime[j]] = 1; if (i % prime[j] == 0) { break; } } } } int main() { Prime(); int t; cin>>t; while(t--) { int n; long long ans=0; cin>>n; for(int i=3;i<=n;i++) { if(st[i])ans+=2*i; else ans+=i; } cout<<ans<<endl; } return 0; }View Code
三. Maximal submatrix
思路:
变成01矩阵用悬线法求最大子矩阵。
时间复杂度O(m*n)
细节:
子矩阵最上端可以为0
收获:
悬线法模板:
if((i-1,j)满足条件) { left[i][j]=max(left[i][j],left[i-1][j]); right[i][j]=min(right[i][j],right[i-1][j]); up[i][j]=up[i-1][j]+1; }View Code
本题代码:
#include<iostream> #include<algorithm> using namespace std; const int N=2e3+10; int le[N][N],ri[N][N],up[N][N],st[N][N]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int ans=m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&st[i][j]); le[i][j]=ri[i][j]=j; up[i][j]=1; } } for(int i=n;i;i--) { for(int j=1;j<=m;j++) { if(st[i][j]>=st[i-1][j])st[i][j]=1; else st[i][j]=0; } } for(int i=2;i<=n;i++) { for(int j=1;j<=m;j++) { if(st[i][j]&&!st[i-1][j])up[i][j]++; } } for(int i=1;i<=n;i++) { for(int j=2;j<=m;j++) { if(st[i][j-1])le[i][j]=le[i][j-1]; } } for(int i=1;i<=n;i++) { for(int j=m-1;j;j--) { if(st[i][j+1])ri[i][j]=ri[i][j+1]; } } for(int i=2;i<=n;i++) { for(int j=1;j<=m;j++) { if(st[i][j]&&st[i-1][j]) { le[i][j]=max(le[i][j],le[i-1][j]); ri[i][j]=min(ri[i][j],ri[i-1][j]); up[i][j]=up[i-1][j]+1; } ans=max(ans,up[i][j]*(ri[i][j]-le[i][j]+1)); } } printf("%d\n",ans); } return 0; }View Code
四. KD-Graph
思路:
排序+并查集
将n个点分成k个满足要求的集合,如果把边从小到大排序,
每次将权重相同的边放在一个集合里,当我们合并完一个集合时如果此时的集合数正好等于k,那此时的权重就是答案。
本题代码:
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int N=1e5+10; struct edge { int u,v,w; }h[5*N]; bool cmp(edge aa,edge bb){return aa.w<bb.w;} int p[N]; int tot,tt; int n,m,k; int find(int x) { if(p[x]!=x)p[x]=find(p[x]); return p[x]; } void solution() { scanf("%d%d%d",&n,&m,&k); int ans=0; for(int i=1;i<=n;i++)p[i]=i; tt=n; for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); h[i]={a,b,c}; } sort(h+1,h+m+1,cmp); for(int i=1;i<=m;i++) { if(h[i-1].w!=h[i].w) { if(tt==k) { printf("%d\n",ans); return; } if(tt<k) { printf("-1\n"); return; } } if(find(h[i].u)==find(h[i].v))continue; p[find(h[i].u)]=find(h[i].v); tt--; ans=h[i].w; } if(tt==k)printf("%d\n",ans); else printf("-1\n"); return; } int main() { int t; cin>>t; while(t--)solution(); return 0; }View Code
五. Xor sum
思路:
将输入进行前缀和,转化为找两个距离最近且异或值大于k的点。
但是不知道为什么枚举右端点之后再找异或和最大的点就可以过去(求高人指点)
tips(A^B=B^A A^B=C C^A=B Trie树)
#include<iostream> #include<cstdio> using namespace std; const int N=1e5+10; int son[31*N][3],idx; int a[N]; int n,k; void insert(int x,int y) { int p=0; for(int i=30;i>=0;i--) { int q=x>>i&1; if(!son[p][q]) { son[p][q]=++idx; } p=son[p][q]; } son[p][2]=y; } int query(int x) { int p=0; for(int i=30;i>=0;i--) { int c=x>>i&1; if(son[p][!c])p=son[p][!c]; else p=son[p][c]; if(!p)return -1; } return son[p][2]; } void solve() { for(int i=0;i<=idx;i++) { son[i][0]=son[i][1]=son[i][2]=0; } idx=0; int ans=N; int l=-1,r=N; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]^=a[i-1]; } for(int i=1;i<=n;i++) { int c=query(a[i]); if((a[i]^a[c])>=k) { if(i-c<ans) { ans=i-c; r=i; l=c+1; } } insert(a[i],i); } if(ans==N)printf("-1\n"); else printf("%d %d\n",l,r); } int main() { int t; scanf("%d",&t); while(t--)solve(); return 0; }View Code