BZOJ NOI十连测 第二测 T1

时间：2022-09-19 14:24:52

BZOJ NOI十连测 第二测 T1

BZOJ NOI十连测 第二测 T1

BZOJ NOI十连测 第二测 T1

出题人居然是个哲学家。。

26%的程序，太SB了。。。本来我的想法也是二分+贪心，但是贪心是个怪怪的SX贪心。。

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #include<time.h>

 #define inf 0x7fffffff

 struct edge{

     int u,v,id;

 }e[];

 int tot,go[],first[],next[];

 int Tot,Go[],First[],Next[];

 int c[],b[],son[],ans,vis[],pd;

 int pass[],op[],C[],Cnt,block,sum,B[];

 int id1,id2;

 int n,k;

 int read(){

     char ch=getchar();int t=,f=;

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void Dfs(int x,int fa){

     if (vis[x]) return;

     c[x]=b[x];son[x]=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa) continue;

         if (pass[i]) continue;

         Dfs(pur,x);

         son[x]+=son[pur];

         c[x]+=c[pur];

     }

     if (c[x]&&(n-c[x]>)) ans=std::min(ans,std::max(son[x],n-son[x]));

 }

 void sbpianfen(){

     ans=inf;

     Dfs(,);

     printf("%d\n",ans);

 }

 void insert(int x,int y){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     pass[tot]=;

 }

 void add(int x,int y){

     insert(x,y);op[tot]=tot+;insert(y,x);op[tot]=tot-;

 }

 void Insert(int x,int y){

     Tot++;

     Go[Tot]=y;

     Next[Tot]=First[x];

     First[x]=Tot;

 }

 void Add(int x,int y){

     Insert(x,y);Insert(y,x);

 }

 int bfs(int x){

     int h=,t=;

     bool ck=;

     c[]=x;vis[x]=;if (b[x]) ck=;

     while (h<=t){

         int now=c[h++];

         for (int i=First[now];i;i=Next[i]){

             int pur=Go[i];

             if (vis[pur]) continue;

             c[++t]=pur;

             vis[pur]=;

             if (b[pur]) ck=;

         }

     }

     if (!ck) pd=;

     return t;

 }

 void dFs(int x){

     if (x==n){

         pd=;

         int bl=;

         for (int i=;i<=n;i++)

          First[i]=;

         Tot=;

         for (int i=;i<n;i++)

          if (!e[i].id) Add(e[i].u,e[i].v);

         for (int i=;i<=n;i++)

           vis[i]=;

         for (int i=;i<=n;i++)

          if (!vis[i])

           bl=std::max(bl,bfs(i));

         if (pd==) ans=std::min(ans,bl);

         return;

     }

     e[x].id=;

     dFs(x+);

     e[x].id=;

     dFs(x+);

 }

 void sxpianfen(){

     for (int i=;i<n;i++) e[i].id=;

     dFs();

 }

 void clear(int x){

     int h=,t=;

     C[]=x;

     bool ppp=;

     if (b[x]) Cnt++,ppp=;

     vis[x]=;b[x]=;

     while (h<=t){

         int now=C[h++];

         for (int i=first[now];i;i=next[i]){

             int pur=go[i];

             if (pass[i]) continue;

             if (vis[pur]) continue;

             C[++t]=pur;

             vis[pur]=;

             if (b[pur]) Cnt++,ppp=;

             b[pur]=;

         }

     }

     if (ppp) {

         pd=;

         return;

     }

     if (t>block) pd=;

     sum-=t;

 }

 void work(int x,int mid,int fa,int Edge){

     if (c[x]==&&b[fa]==&&son[x]<=block) {

         pass[Edge]=;

         pass[op[Edge]]=;

         clear(x);

         id1=x;id2=fa;

         if (pd) return;

         return;

     }

     else

     if (k-Cnt-c[x]==&&b[x]==&&sum-son[x]<=block){

         pass[Edge]=;

         pass[op[Edge]]=;

         clear(fa);

         id1=x;id2=fa;

         if (pd) return;

         return;

     }

     else

     if (c[x]==&&son[x]<=block&&son[fa]>=block){

         pass[Edge]=;

         pass[op[Edge]]=;

         clear(x);

         id1=x;id2=fa;

         if (pd) return;

         return;

     }else

     if (k-Cnt-c[x]==&&sum-son[x]==block){

         pass[Edge]=;

         pass[op[Edge]]=;

         clear(fa);

         id1=x;id2=fa;

         if (pd) return;

         return;

     }

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (pur==fa) continue;

         if (vis[pur]) continue;

         if (pass[i]) continue;

         work(pur,mid,x,i);

     }

 }

 bool check(int mid){

     for (int i=;i<n;i++) std::swap(e[rand()%(n-)+],e[rand()%(n-)+]);

     for (int i=;i<=n;i++) first[i]=;

     tot=;

     for (int i=;i<n;i++)

      add(e[i].u,e[i].v);

     block=mid;pd=;

     for (int i=;i<=tot;i++)

      pass[i]=;

     for (int i=;i<=n;i++)

      b[i]=B[i],vis[i]=;

     id1=;id2=;vis[]=;

     sum=n;Cnt=;

     for (int i=;i<=k;i++){

       if (vis[id1]&&vis[id2]) break;

       if (k-Cnt==) break;

       if (!vis[id1]){

        Dfs(id1,);

        work(id1,mid,,);

       }else{

        Dfs(id2,);

        work(id2,mid,,);

       }

       if (pd) return ;

     }

     for (int i=;i<=n;i++)

      if (!vis[i]) clear(i);

     if (pd) return ;

     return ;

 }

 void solve(){

     int l=n/k,r=n,Ans=n;

     while (l<=r){

         int mid=(l+r)/;

         if (check(mid)) r=mid-,Ans=mid;

         else l=mid+;

     }

     printf("%d\n",Ans);

 }

 void solve2(){

     int l=n/k,r=n,Ans=n;

     while (l<=r){

         int mid=(l+r)/;

         if (check(mid)) r=mid-,Ans=mid;

         else l=mid+;

     }

     int Tn=Ans;

     l=n/k,r=n,Ans=n;

     while (l<=r){

         int mid=(l+r)/;

         if (check(mid)) r=mid-,Ans=mid;

         else l=mid+;

     }

     Tn=std::min(Tn,Ans);

     printf("%d\n",Tn);

 }

 int main(){

     //♂

     freopen("deep.in","r",stdin);

     freopen("deep.out","w",stdout);

     srand(time(NULL));

     ans=inf;

     n=read();k=read();

     for (int i=;i<n;i++){

         int x=read(),y=read();

         add(x,y);

         e[i].u=x;e[i].v=y;

     }

     for (int i=;i<=k;i++){

         int x=read();

         b[x]=;B[x]=;

     }

     if (n<=) {sxpianfen();printf("%d\n",ans);return ;}

     if (k==) {printf("%d\n",n);return ;}

     if (k==) {sbpianfen();return ;}

     if (n<=) {solve();return ;}

     if (k==) {solve2();return ;}

     if (k==n) {printf("%d\n",);return ;}

     if (k==n-) {printf("%d\n",);return ;}

     solve();

 }

AC程序不知道短到哪里去了

 #include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #define N 200005

 int tot,go[N*],next[N*],first[N];

 int n,k,b[N],fa[N],mx[N],sum[N],vis[N],c[N];

 int read(){

     char ch=getchar();int t=,f=;

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void insert(int x,int y){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

 }

 void add(int x,int y){

     insert(x,y);insert(y,x);

 }

 void bfs(){

     int h=,t=;for (int i=;i<=n;i++) vis[i]=;

     c[]=;

     vis[]=;

     while (h<=t){

         int now=c[h++];

         for (int i=first[now];i;i=next[i]){

             int pur=go[i];

             if (vis[pur]) continue;

             vis[pur]=;

             c[++t]=pur;

             fa[pur]=now;

         }

     }

 }

 bool check(int mid){

     int f;

     memset(sum,,sizeof sum);

     memset(mx,,sizeof mx);

     for (int i=n;i>=;i--){

         int u=c[i];

         if (b[u]) mx[u]=mid-;

         else sum[u]++;

         f=(mx[u]>=sum[u])?mx[u]-sum[u]:-sum[u];

         if (u==&&f<) return ;

         if (f<) sum[fa[u]]-=f;

         else mx[fa[u]]=std::max(mx[fa[u]],f);

     }

     return ;

 }

 int main(){

     n=read();k=read();

     for (int i=;i<n;i++){

         int x=read(),y=read();

         add(x,y);

     }

     for (int i=;i<=k;i++){

         int x=read();

         b[x]=;

     }

     bfs();

     int l=n/k,r=n,ans;

     while (l<=r){

         int mid=(l+r)>>;

         if (check(mid)) r=mid-,ans=mid;

         else l=mid+;

     }

     printf("%d\n",ans);

 }

BZOJ NOI十连测 第二测 T1的更多相关文章

  1. BZOJ NOI十连测 第二测 T2

    思路:20%可以搜索.. #include<algorithm> #include<cstdio> #include<cmath> #include<cstr ...

  2. BZOJ NOI十连测 第一测 T1

    思路:首先考虑t=1的情况,t等于1,那么所有位置的颜色相同,我们不用考虑概率的问题,那么,k+d*x在模d下都相等,我们考虑预处理一个数组s[i][j],代表d为i,起始位置为j的等差数列的和,这个 ...

  3. BZOJ NOI十连测 第一测 T2

    思路:看到这题,就感觉是一道很熟悉的题目: http://www.cnblogs.com/qzqzgfy/p/5535821.html 只不过这题的K最多可以到N,而且边权不再只是1,考试的时候yy了 ...

  4. 痞子衡嵌入式：测一测i&period;MXRT1170 Raw NAND启动时间&lpar;从POR到进App的Reset&lowbar;Handler&rpar;

    大家好,我是痞子衡,是正经搞技术的痞子.今天痞子衡给大家介绍的是恩智浦i.MX RT1170 Raw NAND启动时间. 关于i.MXRT1170这颗划时代的MCU,痞子衡去年10月在其刚发布的时候, ...

  5. 「NOI十联测」深邃

    「NOI十联测」深邃 要使得最大的连通块最小,显然先二分答案. 先固定1结点为根. 对于一个果实,显然是先处理子树中未分配的点,再向外延伸. 每个结点记录一个\(si[]\),表示子树中未分配的点数, ...

  6. 「NOI十联测」奥义商店

    「NOI十联测」奥义商店 若lzz想花费最少的钱,那么显然要选择数目较少的颜色. 先考虑暴力的写法. 每次向两边统计,每个物品要求被买的概率可以由上一个物品推出. now=1;//now 被买概率 M ...

  7. 「NOI十联测」黑暗

    「NOI十联测」黑暗 \(n\) 个点的无向图,每条边都可能存在,一个图的权值是连通块个数的 \(m\) 次方,求所有可能的图的权值和.(n≤30000,m≤15) 令\(ans[n][m]\)为n个 ...

  8. NOI十连测 第六测 T1

    思路: 用treap动态维护,记一个sum1,sum2,注意!,写treap如果有删除操作,千万不能把权值相同的分开来..,这在删除的时候会进入死循环,这是一个惨痛的教训... #include&lt ...

  9. NOI十连测 第五测 T1

    #include<cstdio> #include<cstring> #include<cmath> #include<iostream> #inclu ...

随机推荐

  1. Android Hotpatch系列之-项目介绍

    给现实Android apk打补丁,不用强迫客户升级客户端,悄悄的就把bug修复了,程序猿再也不用被老大骂娘了. 客户端例子实现:https://github.com/fengcunhan/Hotpa ...

  2. Java 读写图像

    Java中进行图像I/O(即读图片和写图片,不涉及到复杂图像处理)有三个方法:1. Java Image I/O API,支持常见图片,从Java 2 version 1.4.0开始就内置了.主页:h ...

  3. JavaScript- 获得TreeView CheckBox里选中项的值

    获得TreeView CheckBox里选中项的值,对JSDOM控制还不是很熟,感觉不太容易.试了很多次终于成功了. 代码如下 <body> <form id="form1 ...

  4. jquery的ajax方法：ajaxStart&lpar;&rpar;和ajaxStop&lpar;&rpar;

    ajaxStart()方法: 当AJAX请求开始时,显示加载中的提示. $("#divMessage").ajaxStart(function(){ $(this).show(); ...

  5. SwiftDate 浅析

    SwiftDate是Github上开源的,使用Swift语言编写的NSDate封装库,可以很方便的在Swift中处理日期,比如日期创建,比较,输出等. 特性 支持数学运算符进行日期计算(比如myDat ...

  6. 学而精计算机公共基础学习之路TEST2（程序设计基础）

    程序设计基础 程序设计方法与风格 1.程序设计方法 程序设计: 指设计.编制.调试程序的方法和过程. 程序设计方法是研究问题求解如何进行系统构造的软件方法学.常用的程序设计方法有:结构化程序设计方法. ...

  7. MMORPG战斗系统随笔（一）、战斗系统流程简介

    前言 转载请标明出处http://www.cnblogs.com/zblade/ 很久没有更新博客,中间迁移过一次博客,后来一直忙于项目的开发,忙的晚上回去没时间写博客,周日又要自我调整一下,所以空闲 ...

  8. &lbrack;转&rsqb; Java 基础

    1. 面向对象和面向过程的区别 面向过程 面向对象 2. Java 语言有哪些特点 3. 关于 JVM JDK 和 JRE 最详细通俗的解答 JVM JDK 和 JRE 4. Oracle JDK 和 ...

  9. JS数组---转及补充--

    javascript之数组操作 1.数组的创建 var arr=Array();//写的角标数及直接写角标对应的内容简写 var arr=Array("我","爱&quo ...

  10. 卡夫卡（kafka）

    1.Kafka独特设计在什么地方?2.Kafka如何搭建及创建topic.发送消息.消费消息?3.如何书写Kafka程序?4.数据传输的事务定义有哪三种?5.Kafka判断一个节点是否活着有哪两个条件 ...

相关文章