您的位置: 首页  >  IT文章  >  8.7模拟赛

8.7模拟赛

分类: IT文章 • 2025-01-18 15:54:19

T1 树上路径最小值

题目大意：

带点权的树 q次询问求每两个点之间路径上最小的点权

思路：

倍增lca裸题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 100100
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,q,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],cnt;
21 int mn[MAXN][20],f[MAXN][20],val[MAXN],dep[MAXN];
22 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
23 void dfs(int x)
24 {
25     for(int j=1;j<20&&(1<<j)<=dep[x];j++)
26         f[x][j]=f[f[x][j-1]][j-1],mn[x][j]=min(mn[x][j-1],mn[f[x][j-1]][j-1]);
27     for(int i=fst[x];i;i=nxt[i])
28         if(!dep[to[i]]){dep[to[i]]=dep[x]+1,f[to[i]][0]=x,mn[to[i]][0]=min(mn[to[i]][0],val[x]);dfs(to[i]);}
29 }
30 int lca(int u,int v)
31 {
32     if(dep[u]<dep[v]) swap(u,v);
33     int t=dep[u]-dep[v],res=min(val[u],val[v]);
34     for(int i=0;i<20;i++)
35         if((1<<i)&t) res=min(res,mn[u][i]),u=f[u][i];
36     if(u==v) return res;
37     for(int i=19;i>=0;i--)
38         if(f[u][i]!=f[v][i]) res=min(res,min(mn[u][i],mn[v][i])),u=f[u][i],v=f[v][i];
39     return min(res,min(mn[u][0],mn[v][0]));
40 }
41 int main()
42 {
43     freopen("min.in","r",stdin);
44     freopen("min.out","w",stdout);
45     n=read(),q=read();int a,b;
46     for(int i=1;i<=n;i++) val[i]=mn[i][0]=read();
47     for(int i=1;i<n;i++) {a=read(),b=read();add(a,b);add(b,a);}dfs(1);
48     while(q--)
49     {
50         a=read(),b=read();
51         printf("%d
",lca(a,b));
52     }
53 }
View Code

T2 第K大异或和

题目大意：

给出一个长度为n的序列 , 和q次询问，每次询问包含一个正整数 ，要求求出其第k小非空子区间异或和

思路：

n只有1e4 可以xor前缀和n方求出所有区间

因为所有数都不大 可以使用桶排序 或者在桶里二分

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 11000
12 #define maxn 1050000
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,q,s[MAXN],g[MAXN],a[MAXN],cnt,num[maxn+5];
22 int main()
23 {
24     freopen("xor.in","r",stdin);
25     freopen("xor.out","w",stdout);
26     n=read(),q=read();int x;
27     for(int i=1;i<=n;i++) g[i]=read(),s[i]=s[i-1]^g[i];
28     for(int i=0;i<n;i++)
29         for(int j=i+1;j<=n;j++) num[s[i]^s[j]]++;
30     for(int i=1;i<=maxn;i++) num[i]+=num[i-1];
31     while(q--)
32         printf("%d
",upper_bound(num,num+maxn,x=read()-1)-num);
33 }
View Code

T3 最小生成树

题目大意：

你有n个节点，m组连边方案 每个方案表示方式形如了l r v

表示编号在区间l r中的节点可以通过该方案两两任意连边，每连一条边需要付出v的代价

求使得所有n个节点联通的最小代价

思路：

法①：按边权从小到大排序，用并查集维护每个连接过的块

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 100100
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 struct node {int l,r,val;}g[MAXN];
21 bool cmp(node a,node b) {return a.val<b.val;}
22 int fa[MAXN],r[MAXN],cnt=0,ans=0;
23 int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
24 int merge(int a,int b)
25 {
26     int f1=find(a),f2=find(b);
27     r[f1]=max(r[f1],r[f2]),fa[f2]=f1;
28     return r[f1];
29 }
30 int main()
31 {
32     freopen("kruskal.in","r",stdin);
33     freopen("kruskal.out","w",stdout);
34     int n=read(),m=read();
35     for(int i=1;i<=n;i++) fa[i]=r[i]=i;
36     for(int i=1;i<=m;i++) g[i].l=read(),g[i].r=read(),g[i].val=read();
37     sort(g+1,g+m+1,cmp);
38     for(int i=1,pos;i<=m;i++)
39     {
40         pos=find(g[i].l),pos=r[pos]+1;
41         while(pos<=g[i].r)
42             cnt++,ans+=g[i].val,pos=merge(g[i].l,pos)+1;
43     }
44     if(cnt!=n-1) puts("-1");
45     else printf("%d",ans);
46 }
View Code

法②：按边权从大到小排序，用每个边左边的点表示这个边，用线段树区间修改以及整体查询

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 100100
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,m;
21 struct node {int l,r,val;}g[MAXN];
22 bool cmp(node a,node b){return a.val>b.val;}
23 int sum[MAXN<<2],vis[MAXN<<2],tag[MAXN<<2];
24 void pshd(int k,int l,int r,int mid)
25 {
26     tag[k<<1]=tag[k<<1|1]=tag[k];
27     sum[k<<1]=(mid-l+1)*tag[k],sum[k<<1|1]=(r-mid)*tag[k],tag[k]=0;
28     vis[k<<1]=vis[k<<1|1]=vis[k];
29 }
30 void mdf(int k,int l,int r,int a,int b,int x)
31 {
32     if(l==a&&r==b) {sum[k]=x*(r-l+1),tag[k]=x,vis[k]=1;return ;}
33     int mid=(l+r)>>1;
34     if(tag[k]) pshd(k,l,r,mid);
35     if(mid>=b) mdf(k<<1,l,mid,a,b,x);
36     else if(mid<a) mdf(k<<1|1,mid+1,r,a,b,x);
37     else {mdf(k<<1,l,mid,a,mid,x);mdf(k<<1|1,mid+1,r,mid+1,b,x);}
38     sum[k]=sum[k<<1]+sum[k<<1|1],vis[k]=vis[k<<1]&vis[k<<1|1];
39 }
40 int main()
41 {
42     freopen("kruskal.in","r",stdin);
43     freopen("kruskal.out","w",stdout);
44     n=read()-1,m=read();
45     for(int i=1;i<=m;i++) g[i].l=read(),g[i].r=read()-1,g[i].val=read();
46     sort(g+1,g+m+1,cmp);
47     for(int i=1;i<=m;i++) if(g[i].l<=g[i].r) mdf(1,1,n,g[i].l,g[i].r,g[i].val);
48     if(!vis[1]) puts("-1");
49     else printf("%d",sum[1]);
50 }
View Code

相关推荐