Log_1

[2017/3/5/-2017/3/11]

Codeforces #403 Div 2

Prob B

n 个人在意直线上，位置为x_i ,最大速度为 v_i ，求所有人到达同一点的最少时间（可能是浮点数）

二分时间

• 限制二分次数以免误差导致 TLE（降低精度到 1e6 也行！>@#@<！）

• check 所有人在时间 t 内能到达的区间L_i ，R_i 的交集是否为空

bool chk(double x){

  double l = a[0].x-a[0].v*x,r = a[0].x+a[0].v*x;

  double ll,rr,dx;

  for(int i = 1;i < N;i++){

    dx = a[i].v*x;

    ll = a[i].x-dx,rr = a[i].x+dx;

    if(ll > r || rr < l)  return false;

      l = max(l,ll),r = min(r,rr);

    if(l>r)  return false;

  return true;

Prob C

给一幅树，要求形如 a-b-c 的任意三个点不同色

记录遍历时每一个点的father 和 grandfather，DFS 或是 BFS 染色保证不同色即可

void DFS(int u,int fa){

  int len = G[u].size();

  int c = 1,v;

  for(int i = 0;i < len;i++){

    v = G[u][i];

    if(v == fa)  continue;

    while(c == col[u] || c == col[fa])  c++;

    col[v] = c++;

    //cout << v << " = " << col[v] << endl;

    DFS(v,u);

  }

}

/// BFS

  Q.push(1);col[1] = 1;fa[1]=1;

  while(!Q.empty()){

    int u,v,len,c;

    u =  Q.front();

    Q.pop();

    len = e[u].size(),c = 1;

    for(int i = 0;i < len;i++){

      v = e[u][i];

      if(col[v])  continue;

      if(c == col[u] || c == col[fa[u]])  c++;

      if(c == col[u] || c == col[fa[u]])  c++;

      col[v] = c++;

      Q.push(v);

      fa[v] = u;

      //cout << v << " col = " << c << endl;

    }

  }

Prob D

• club name = team name + hometown name

DINAMO BYTECITY

• abbr = team name.substr(0,3)

"DIN"

• abbr = team name.substr(0,2)+home town name.substr(0,1)

"DIB"

• 一个 club 用了 II 类缩写则它的 I 类缩写不能被其他 club 作为 I 类缩写使用，但可被其它作为 II 类使用

• 所有 club 的缩写名不同

详细可看sample

先记录数据，保留有效部分，删掉不可能的边，然后跑二分图板子

---

• **能预处理+套板子 就不要魔改了 ~~~_{(>_<)}~~~ **

• 课比较多，平时还是多看书吧