【链接】http://acm.hdu.edu.cn/showproblem.php?pid=6109


【题意】


在这里写题意

【题解】


要处理的关系越多,肯定就越容易错.
->单调性.
根据这个二分出每组数据的最后一个是什么就好.
二分判断这样:先处理出哪些数据是一样的,并在一起;并查集
然后再处理不一样的,看看不一样的x,y是不是在同一个集合里,在的话就不合法了.
但是这题有一组数据,这一组数据的最后一组是全都合法的,然后你要省略掉这组数据.
UPD
那个最后一组数据好像又去掉了

【错的次数】


0

【反思】


在这了写反思

【代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x+1)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0) typedef pair<int,int> pii;
typedef pair<LL,LL> pll; const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e5+100; int L,x[N],y[N],z[N],f[N],st=1;
vector <int> v; int ff(int x){
    if (f[x]==x) return x;
    else
        return f[x] = ff(f[x]);
} bool ok(int n){
    rep1(i,0,100000) f[i] = i;
    rep1(i,st,n)
        if (z[i]==1){
            int r1 = ff(x[i]),r2 = ff(y[i]);
            if (r1!=r2)
                f[r1] = r2;
        }
    rep1(i,st,n)
        if (z[i]==0){
            int r1 = ff(x[i]),r2 = ff(y[i]);
            if (r1==r2)
                return false;
        }
    return true;
} int main(){
    //Open();
    //Close();
    ri(L);
    rep1(i,1,L)
        ri(x[i]),ri(y[i]),ri(z[i]);
    while (st <= L){
        int l = st,r = L,ans = 0;
        while (l <= r){
            int m = (l+r)>>1;
            if ( ok(m) ){
                ans = m,l = m + 1;
            }else
                r = m - 1;
        }
        if (ans == 0){
            v.pb(1);
            st = st + 1;
        }else{
            v.pb(ans+1 - st + 1);
            st = ans + 2;
        }
    }
    int len = v.size();
    oi((int) v.size());puts("");
    rep1(i,0,len-1)
        oi(v[i]),puts("");
    return 0;
}

最新文章

  1. 免费的Android UI库及组件推荐
  2. [转] Xcode4.4.1下安装高德地图详细教程
  3. Unity3D 几个基本动画(控制物体移动、旋转、缩放)
  4. 将HTML转成XHTML并清除一些无用的标签和属性
  5. PowerShell远程安装应用程序
  6. Codeforces Round #325 (Div. 2) B. Laurenty and Shop 前缀和
  7. JavaScript数组的学习
  8. MOUNT MACBOOK DISK (OSX / HFS+) ON UBUNTU 12.04 LTS WITH READ/WRITE
  9. 04747_Java语言程序设计(一)_第3章_面向对象编程基础
  10. HDU 3756 Dome of Circus
  11. Python实现制度转换(货币,温度,长度)
  12. JDBC连接最新版Mysql数据库url设置
  13. windows slaver 脚本执行xcopy 报错无效驱动器规格
  14. Python&#160;标准类库-日期类型之datetime模块
  15. Why do Kafka consumers connect to zookeeper, and producers get metadata from brokers?
  16. Linux拷贝U盘文件(命令行)
  17. badgeview
  18. json介绍和使用
  19. python之文件操作的函数
  20. RecyclerView下拉刷新上拉加载更多

热门文章

  1. Android入门篇(一)Androidproject的搭建,导入与导出,图标的改动
  2. vue14 自定义过滤器
  3. vim插件之delimitMate.vim
  4. .Net经典笔试题
  5. BZOJ 3224 平衡树模板题
  6. gym 100735I
  7. JWT 使用介绍
  8. Linux下搭建iSCSI共享存储详细步骤(服务器模拟IPSAN存储)
  9. tensorflow学习之路-----简单卷积神经网路
  10. 今日SGU 5.13