杭电第一场题解1001题 Mod, Or and Everything1005题 Minimum spanning tree 最小生成树1008题 Maximal submatrix 最大子矩阵1006题 Xor sum 异或和1009题 KD-Graph KD图

66 阅读 0 评论 44 点赞

我是靠谱客的博主阳光嚓茶，最近开发中收集的这篇文章主要介绍杭电第一场题解1001题 Mod, Or and Everything1005题 Minimum spanning tree 最小生成树1008题 Maximal submatrix 最大子矩阵1006题 Xor sum 异或和1009题 KD-Graph KD图，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

杭电第一场题解

by fn

1001题 Mod, Or and Everything

考察内容
找规律

分析：
当n为偶数时，设m=n/2-1
当n为奇数时，设m=(n-1)/2
可以发现，n mod i<=m，且当i<=m时，有 n mod (n-i)=i。于是可以得出n mod i取到0~m的所有整数，因此答案会是2^k-1，k的具体值判断一下即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,m,a[N];
int main(){
for(int i=1;i<=50;i++){
a[i]=pow(2,i-1);
}
int t;
cin>>t;
while(t--){
cin>>n;
if(n==1)puts("0");
else{
int i=50;
while(n<=a[i]){
i--;
}
cout<<a[i]-1<<endl;
}
}
return 0;
}

1005题 Minimum spanning tree 最小生成树

题目大意
给定n-1个点，从2到n，点a和点b之间的边权为lcm(a, b)，
找出它们所形成的最小生成树。
考察内容
找规律

分析
对于编号为3~n的点，将所有编号为合数的点向其约数连边，编号为质数的点向2连边，不难证明这样形成的生成树是最小的。
总的边权和为（质数的和*2+合数的和），用欧拉筛预处理前缀和即可。
效率:O(n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
ll n,m,a[N];
int v[N],prime[N];
bool b[N];
void primes(int n){
memset(v,0,sizeof(v));
m=0;
for(int i=2;i<=n;i++){
if(v[i]==0){ v[i]=i; prime[++m]=i; }
for(int j=1;j<=m;j++){
if(prime[j]>v[i]||prime[j]>n/i) break;
v[i*prime[j]]=prime[j];
}
}
for(int i=1;i<=m;i++) b[prime[i]]=1;
}
int main(){ // 
primes(N-1);
a[2]=0;
for(int i=3;i<=1e7;i++){
if(b[i]){ // 是质数 
a[i]+=a[i-1]+i*2;
}
else{
a[i]=a[i-1]+i;
}
}
ll t; cin>>t;
while(t--){
cin>>n;
cout<<a[n]<<endl;
}
return 0;
}

1008题 Maximal submatrix 最大子矩阵

题目大意
求一个最大面积的满足每列非递减的矩阵。

分析：
转化为01矩阵每个位置1代表该位是否比上面一位小，然后用悬线法求最大01矩阵即可复杂度O(n^2)

传送门：
悬线法：最大矩阵

#include<bits/stdc++.h>
using namespace std;
const int N=5e3;
int a[N][N],b[N][N];
int h[N];
int que[N];
void solve() // 先转换为01矩阵，再求解最大1矩阵的面积 
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
b[i][j]=0;
if(i>1){
b[i][j]=(a[i][j]>=a[i-1][j]);
}
}
}
for(int i=1;i<=m;i++){
h[i]=0;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i][j]==0){
h[j]=1;
}else{
h[j]++;
}
}
int tot=0;
h[m+1]=0;
for(int j=1;j<=m+1;j++){
while(tot&&h[que[tot]]>h[j]){
ans=max(ans,(j-que[tot-1]-1)*h[que[tot]]); // 更新ans 
tot--;
}
que[++tot]=j;
}
}
printf("%dn",ans);
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
solve();
}
}

1006题 Xor sum 异或和

考察内容
字典树

分析：
对数列做前缀异或，将题面转化为找两个距离最近的数，使得他们的异或值不小于k。
枚举靠右的那个数，同时维护字典树，字典树每个节点保存范围内最靠右的点的位置。根据k来询问对应的log个节点，从而更新答案。
效率:O(nlogn)

代码：

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int inf=1e9;
const int N=1e5+10;
const int M=3e6+10;
const int mo=998244353;
int p[M][2],mx[M],a[N];
void sol(){
int n,k;
scanf("%d%d",&n,&k);
rep(i,1,n){
scanf("%d",&a[i]);
a[i]^=a[i-1]; // 保存前缀和 
}
int anl=-1,anr=n,tot=1;
mx[1]=-1;
p[1][0]=p[1][1]=0;
rep(i,0,n){
int x=1,res=-1;
dep(j,29,0){
int w=(a[i]>>j)&1;
if(!((k>>j)&1)){
if(p[x][w^1])res=max(res,mx[p[x][w^1]]);
x=p[x][w];
}else x=p[x][w^1];
if(!x)break;
}
if(x)res=max(res,mx[x]);
if(res>=0&&i-res<anr-anl)anl=res,anr=i;
x=1;
dep(j,29,0){
int w=(a[i]>>j)&1;
if(!p[x][w]){
p[x][w]=++tot;mx[tot]=-1;
p[tot][0]=p[tot][1]=0;
}
x=p[x][w];
mx[x]=max(mx[x],i);
}
}
if(anl>=0)printf("%d %dn",anl+1,anr);
else printf("-1n");
}
int main(){
int t;
scanf("%d",&t);
rep(i,1,t)sol();
}

1009题 KD-Graph KD图

题目大意

满足以下条件的加权连通无向图为KD图。

n个顶点严格分为K组，每组至少包含一个顶点
如果顶点p和q (p≠q)在同一组中，则p和q之间必须至少有一条路径满足这条路径的最大值小于或等于D。
如果顶点p和q (p≠q)在不同的组中，p和q之间不可能有任何路径满足这条路径的最大值小于或等于D。

给定一个有n个顶点和m条边的加权连通无向图G和一个整数K。

你的任务是找到最小的非负D可以使有一种方法将n个顶点分成K组使G满足KD图的定义。如果不存在D，则输出−1。

考察内容
并查集

分析
将边按权值从小到大排序，每一阶段取出同权值的所有边，将这些边的端点用并查集两两合并，若某一阶段的全部边合并完，并查集数量为k，则当前阶段合并边的权值就是答案，否则输出-1。
可以用反证法证明正确性。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int T,n,m,k,fa[maxn],now,ans;
struct da{int u,v,w;}q[maxn];
bool cmp(da aa,da bb){return aa.w<bb.w;}
int getf(int x){
if (fa[x]==x) return x;
fa[x]=getf(fa[x]);
return fa[x];
}
void solve(){
scanf("%d%d%d",&n,&m,&k);
now=n; ans=0;
for (int i=1;i<=n;i++) fa[i]=i; // 初始化并查集 
for (int i=1;i<=m;i++) scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
sort(q+1,q+m+1,cmp);
for (int i=1;i<=m;i++){
if (q[i].w!=q[i-1].w){if (now==k) {printf("%dn",ans); return;}}
if (getf(q[i].u)==getf(q[i].v)) continue;
now--;
fa[getf(q[i].u)]=getf(q[i].v);
ans=q[i].w;
}
printf("%dn",now==k?ans:-1);
}
int main(){
scanf("%d",&T);
while (T--) solve();
}