Codeforces Round #384 (Div. 2) 作者: rin 时间: December 15, 2016 分类: 未分类 评论 ~~这个灰名选手一直坚持他蓝名梦想~~ ------------ [A. Vladik and flights](http://codeforces.com/problemset/problem/743/A) 有$$n$$个机场，要从$$a$$飞到$$b$$ 每个机场有航空公司$$0$$或$$1$$，同航空公司机场间移动无费用，不同的之间为$$|ni-nj|$$，问从$$a$$到$$b$$最少花费是多少。 因为同公司无费用，所以如果$$a$$和$$b$$地相同的话就输出$$0$$； 如果不相同，那么从$$a$$一定能移动到一个地方，是$$0$$和$$1$$的交界，然后在交界换一家公司飞到b，花费是$$1$$ ```c++ int main(){ int n, a, b; char aType, bType; scanf("%d %d %d", &n, &a, &b); getchar(); for (int i = 1; i <= n; i++) { if (i == a) scanf("%c", &aType); else if (i == b) scanf("%c", &bType); else scanf("%*c"); } puts((aType == bType || a == b) ? "0" : "1"); return 0; } ``` ------------ [B. Chloe and the sequence](http://codeforces.com/problemset/problem/743/B) 初始有一个序列$$[1]$$ 然后将它本身加到后面变成$$[1,1]$$ 再将还未使用的最小的正整数加到正中的位置$$[1,2,1]$$ 重复$$n-1$$次 问这之后第$$k$$个数字是啥 由~~观察瞎猜脑洞~~，~~可以看出~~，这个序列代表从$$1$$到某个数，(二进制)从右数起第一个$$1$$的位置，比如 | 数（二进制） | 1的位置 | | ------------ | ------------ | | 1(1) | 1 | | 2(10) | 2 | |3(11)|1| |4(100)|3| |5(101)|1| |6(110)|2| |...|...| 那么第$$k$$位是啥，就是$$k$$的右起第一个$$1$$位置。 可以直接用glibc里的`__builtin_ffs()`函数 考虑到$$k$$超`int`用其`long long`版本 ` __builtin_ffsll()` ```c++ int main(){ long long k; scanf("%*lld %lld", &k); printf("%d\n", __builtin_ffsll(k)); return 0; } ```