首页 > 其他分享 >20230628水题选做

20230628水题选做

时间：2023-06-28 16:01:11浏览次数：56  
标签：cnt return 水题 int head 20230628 dep lca

约束条件

题意

给定一些关系\(x=y 或x\neq y\)。求是否能满足。

分析

显然并查集。我们考虑将约束条件排序，先使形如\(x_{i}=x_{j}\)的\(x_{i}\)和\(x_{j}\)合并。而后我们观察是否存在\(x_{i}\)和\(x_{j}\)已经合并但是关系是\(\neq\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int T;
int b[N];
int fa[N];
int n,cnt;
struct node{
    int e,x,y;
}a[N];
bool cmp(node a,node b){
    return a.e>b.e;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
    cin>>T;
    while(T--){
        cnt=0;
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        for(int i=1;i<=N;i++) fa[i]=i;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
            b[++cnt]=a[i].x,b[++cnt]=a[i].y;
        }
        sort(b+1,b+1+cnt);
        int m=unique(b+1,b+1+cnt)-b-1;
        for(int i=1;i<=n;i++){
            a[i].x=lower_bound(b+1,b+1+m,a[i].x)-b;
            a[i].y=lower_bound(b+1,b+1+m,a[i].y)-b;
        }
        sort(a+1,a+1+n,cmp);
        bool flag=1;
        for(int i=1;i<=n;i++){
            int fx=find(a[i].x),fy=find(a[i].y);
            if(fx==fy&&!a[i].e) {printf("NO\n");flag=0;break;}
            if(fx!=fy&&a[i].e) fa[fx]=fy;
        }
        if(flag) printf("YES\n");
    }
    return 0;
}

CF379F

题意

一个树，只含有三个并列节点和一个根。一共\(q\)次操作，每次操作可以在叶节点上加入两个子节点，而后请输出每次操作后树的直径。

分析

设原来树的直径路径为\(l\to{r}\)，那么本次在\(x\)后加两个子节点\(n+1,n+2\)，我们显然有树的直径可以为\(l\to{r}\)或\(l\to{n+1}\)或\(r\to{n+1}\)。而后我们只需要倍增维护\(n+1,n+2\)的倍增\(Fa\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int dep[N],fat[N];
int cnt,head[N],nxt[N],to[N],val[N];
int f[N][25];
int dis[N];
// void add(int u,int v,int w){
	// cnt++;to[cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;
// }
// void dfs(int x,int fa){
	// for(int i=head[x];i;i=nxt[i]){
		// int y=to[i];
		// if(y==fa) continue;
		// dep[y]=dep[x]+1;dis[y]=dis[x]+val[i];fat[y]=x;dfs(y,x);
	// }
// }
int n,m;
// void init(){
	// for(int i=1;i<=n;i++) f[i][0]=fat[i];
	// for(int j=1;j<=20;j++){
		// for(int i=1;i<=n;i++){
			// f[i][j]=f[f[i][j-1]][j-1];
		// }
	// }
// }
int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    if (dep[x] != dep[y]) {
        for (int i = 20; i >= 0; i--)
            if (dep[f[x][i]] > dep[y])
                x = f[x][i];
        x = f[x][0];
    }
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int len=2;
int q;
int x;
int main(){
//	freopen("in.txt","r",stdin);
    n=4;
    f[2][0]=f[3][0]=f[4][0]=1;
    int a=2,b=3;
    dep[1]=0,dep[2]=dep[3]=dep[4]=1;
    cin>>q;
    for(int i=1;i<=q;i++){
        int u=n+1,v=n+2;
        n+=2;
        scanf("%d",&x);
        f[u][0]=f[v][0]=x;
        dep[u]=dep[v]=dep[x]+1;
        for(int j=1;(1<<j)<=n;j++){
            f[u][j]=f[f[u][j-1]][j-1];
            f[v][j]=f[f[v][j-1]][j-1];
        }
        int _lca=lca(a,u);
        if(dep[u]+dep[a]-dep[_lca]*2>len) b=u,len++;
        _lca=lca(b,u);
        if(dep[u]+dep[b]-dep[_lca]*2>len) a=u,len++;
        printf("%d\n",len);
    }
	return 0;
}

CF1296F

题意

给你一颗大小为 \(n\) 的无根树，树边的边权尚未确定。现在你从 \(m\) 个人中得知在 \((u,v)\) 这条路径(最短路径)上的最小边权为 \(w\) 。请你构造一种方案满足这 \(m\) 个人的条件，如果不存在，请输出 \(-1\)。

分析

我们显然可以先把边权按照从小到大排序，而后构造一种最优方案即把这条路径上的所有边都赋值为 \(w\)。这样我们可以使得每条路径上的最小值都尽可能满足题面的要求。而后我们检验是否合法。使用 \(LCA\) 维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
struct node{int u,v,w;}a[N];
int f[N][50];
int head[N],to[N],nxt[N];
int fat[N];
int dis[N],dep[N];
int cnt;
int n,m;
int num[N];
int w[N];
void add(int u,int v){
	cnt++;to[cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
int xx;
void dfs(int x,int fa){
	++xx;
	if (xx > 1e6) exit(0);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
        num[y]=(i+1)/2;
		dep[y]=dep[x]+1;fat[y]=x;dfs(y,x);
	}
}
void init(){
	for(int i=1;i<=n;i++) f[i][0]=fat[i];
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    if (dep[x] != dep[y]) {
        for (int i = 20; i >= 0; i--)
            if (dep[f[x][i]] > dep[y])
                x = f[x][i];
        x = f[x][0];
    }
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
void modify(int u,int v,int val){
    int _lca=lca(u,v);
    while(u!=_lca) w[num[u]]=val,u=f[u][0];
    while(v!=_lca) w[num[v]]=val,v=f[v][0];
}
int query(int u,int v){
    int _lca=lca(u,v);
    int res=0x3f3f3f3f;
    while(u!=_lca) res=min(res,w[num[u]]),u=f[u][0];
    while(v!=_lca) res=min(res,w[num[v]]),v=f[v][0];
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    sort(a+1,a+1+m,[](const node a,const node b){return a.w<b.w;});
    // for(int i=1;i<=m;i++) printf("%d\n",a[i].w);
     // for(int i=1;i<=n;i++) printf("%d\n",num[i]);
    for(int i=1;i<=m;i++) modify(a[i].u,a[i].v,a[i].w);
    bool flag=0;
    for(int i=1;i<=m;i++){
    	// printf("%d ",query(a[i].u,a[i].v));
        if(query(a[i].u,a[i].v)!=a[i].w){flag=1;break;}
    }
    if(flag) printf("-1\n");
    else{
        for(int i=1;i<=n-1;i++){
            printf("%d ",w[i]?w[i]:1);
        }
        // printf("%d\n",w[n-1]?w[n-1]:1);
    }
    return 0;
}

标签：cnt,return,水题,int,head,20230628,dep,lca
From： https://www.cnblogs.com/Zimo233/p/17511635.html

相关文章

  • 20230626水题选做
    「数学基础」第6章期望问题单选错位题意单选把答案填在后面那道题了。假设所有题都正确，求答对题目的期望值。分析期望入门题。\(E(Ans)=\sumP[i]\)。那么显然有答对本题的期望为\(\dfrac{1}{\max\left(a\left[i+1\right],a\left[i\right]\right)}\)。代码#inc......
  • 2023.4-2023.5 水题记录 (持续更新)
    摆烂了属于是.1.P4071[SDOI2016]排列计数错排板子,显然答案为\(\dbinom{n}{m}D_{n-m}\),\(D_k\)m为错排数.2.P5104红包发红包连续型随机变量入门题.本人不太熟练,写一下过程.根据题中条件,抽到钱数在\([0,x](x\in[0,w])\)间的概率为\(\dfrac{x}{w}\).求导得概......
  • 线段树水题
    [THUSCH2017]大魔法师​ 给定\(n\)个三元组\((A,B,C)\)。共有\(m\)种区间操作，分为三大类，七小类。1.\(A_i=A_i+B_i\)2.\(B_i=B_i+C_i\)3.\(C_i=C_i+A_i\)给定值\(v\)4.\(A_i=A_i+v\)5.\(B_i=B_i\timesv\)6.\(C_i=v\)7.区间查询所有三元组......
  • hdu:这是真正的水题（RMQ）
    ProblemDescription在缺水的地方，水是非常有限的资源，所以人们常常为争夺最大的水源而战。给定一系列水源，用a1,a2,a3,…,an代表水源的大小。给定一组查询，每个查询包含2整数L和R，请找出L和R之间最大的水源。Input输入数据首先给定一个整数T（T≤10）表示测试用例的数量。......
  • Codeforces Round #358 (Div. 2) -- B. Alyona and Mex （思路水题）
    B.AlyonaandMextimelimitpertestmemorylimitpertestinputoutputSomeonegaveAlyonaanarraycontainingnpositiveintegersa1, a2, ..., an.Inoneoperation,Alyonacanchooseanyelementofthearray......
  • POJ - 2029 Get Many Persimmon Trees(暴力水题)
    题目大意：给你一个矩阵，矩阵上面有N个柿子树，现在要求你画一个s*t的矩阵，使得这个矩阵内的柿子树达到最多解题思路：100*100，直接暴力#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintN=110;intn,w,h,s,t;intmap[N][N];voidin......
  • ZOJ - 2421 Recaman's Sequence(打表水题)
    题目大意：A0=0Am=A(m-1)-m，如果Am小于0或者Am前面已经出现过了，那么Am＝A(m-1)+m解题思路：打表水题我用的是map，纪录数是否出现过了#include<cstdio>#include<cstring>#include<map>usingnamespacestd;constintN=500010;typedeflonglongLL;map<LL,int>Ma......
  • P5219 无聊的水题 I
    P5219无聊的水题I计有标号树，容易想到\(\text{Prufer}\)序列，那么对于度数的限制即使，每一个数的出现次数要小于等于\(m-1\)，且一定要有等于的，容斥一下，用小于等于\(m-1......
  • CF-25C - Roads in Berland（水题）
    C-RoadsinBerlandCrawlinginprocess...CrawlingfailedTimeLimit:2000MSMemoryLimit:262144KB64bitIOFormat:%I64d&%I64u​​Submit​​​......
  • 二分查找水题--疯牛(POJ 2456)
    DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2<=N<=100,000)stalls.Thestallsarelocatedalongastraightlineatpositionsx1,...,xN(0<=x......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99