Educational Codeforces Round 146 (Rated for Div. 2)（VP)

写个题解

A. Coins

void solve(){
    ll n, k; cin >> n >> k;
    bl ok = true;
    if (n &1 && k %2 == 0) ok = false;
    print(ok ? yes : no);
}

B. Long Legs

void solve(){
    db x, y; cin >> x >> y;
    if (x < y) swap(x, y);
    int t1 = ceil(sqrt(x)), t2 = ceil(sqrt(y));    //两个方向各自的最佳步长
    int ans = (t1 - 1) + ceil(x / t1) + ceil(y / t1);
    lfor (i, t1, sqrt(x) * 2){
        ans = min(ans, int((i - 1) + ceil(x / i) + ceil(y / i)));
    }
    print(ans);
}

讲一下b。

秉着根据题目特性面向过程编程的思想，可以发现题目中有x和y两个方向，如果只有一个方向的话，那么最佳步长设为t则y = (t - 1) + ceil(x / t)，x是距离，ceil是向上取余，求导后可以得出当

步长t=ceil(sqrt(x))时，y为极小值点，所以当只拿一个方向讨论的时候，可以得出当前方向上的最小步长。

然而题目需要讨论两个方向，我们只要把这个思想拓展并应用到两个方向上即可。两个方向与一个方向的不同点，在于当两个方向都要运动时，步长+1带来的效益（操作次数变少）是双向的（对于x轴和y轴都有益），但是有一个阈值，当步长超过这个阈值时，再增加步长将没有意义。

但是有一点可以确定，步长一定不会小于两个方向中距离较远的坐标的最佳步长，即最终的步长一定大于等于两个方向上的最佳步长的较大值。基于以上理论，可以确定步长的下限。再大致确定一下步长的上限，题目数据范围是1e9，一个比较合适的阈值上限是sqrt(1e9) + c,c是一个常数。或者直接k * (sqrt(1e9))也可。

C. Search in Parallel

贪心构造即可。

void solve(){
    int n, s1, s2; cin >> n >> s1 >> s2;
    vpi query(n + 1);
    lfor (i, 1, n){
        cin >> query[i].first;
        query[i].second = i;
    }
    sort(RALL(query));
    vi a, b;
    LITER(x, query){
        auto[r, i] = x;
        if (1ll * (len(a) * s1 + s1) > 1ll * (len(b) * s2 + s2)){
            b.pb(i);
        }
        else{
            a.pb(i);
        }
    }
    cout << len(a) << " \n"[len(a) == 0];print(a);
    cout << len(b) << " \n"[len(b) == 0];print(b);
}

这里要提一点，题目指出了每种box的request次数，但是没有指出request是连续的，所以在写题目时很容易主观的将次数*查询时间作为代价，然后不断的将代价进行累积，这种做法会在case3 WA。正确的想法应该是将查询次数多的尽可能的往前靠，最后查询的总时间减少，即每次request都是一次单独的查询，最后的总时间也是单次查询的时间*对应的查询次数。 也就是说，当前的查询次数没有后继性。查询次数的重要性只体现在总时间的计算上。

总结，B题告诉人们一定要用脑子思考

C题告诉人们读题真的很难