[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
先记录数据，保留有效部分，删掉不可能的边，然后跑二分图板子
**能预处理+套板子 就不要魔改了 ~~~(>_<)~~~ **
课比较多，平时还是多看书吧
