CodeForces Round#158 Div2

上场比赛的rating掉的很科学啊，正好回到div2可以做一下今年的最后一场codeforces。最后的结果还是3题，rank28。什么时候能在div1 rank28啊？
现在完成了前四道题，写一下简单的题解。

260A Adding Digits
先从0到9枚举加的第一位，如果有能整除的，那么就不断在这个数字后面补0，显然得到的数字也能整除b；反之则输出-1。
260B Ancient Prophesy
暴力枚举所有长度等于10的子串，然后判断合法性即可。这种题我写的还是有点慢。
260C Balls and Boxes
我们很容易发现，被选中的box最后剩下的球数量肯定是最少的之一。但是现在的问题是，如果有多个box最终剩余球的数量同时是最少的，应该选哪一个呢？画个图就可以看出，选位置x之前的第一个即可。这是这道题的一个trick。
代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef __int64 lld;
const lld INF = 2e9;

lld a[N];
lld mod(lld a, lld b)
{
    return (a % b + b) % b;
}

int main()
{
    lld n, x;
    int ind;

    do
    {
        scanf("%I64d%I64d", &n, &x);
        --x;
        lld mi = INF;
        for (int i = 0;i < n;++i)
        {
            scanf("%I64d", a + i);
            if (a[i] < mi)
                mi = a[i];
        }
        for (int i = 0;i < n;++i)
            if (a[mod(x - i, n)] == mi)
            {
                ind = mod(x - i, n);
                break;
            }
        // ind is the answer
        lld tot = mi * n + mod(x - ind, n);
        for (int i = 0;i < n;++i)
        {
            if (i == ind)
                printf("%I64d", tot);
            else
            {
                if (mod(i - ind, n) <= mod(x - ind, n) )
                    printf("%I64d", a[i] - a[ind] - 1);
                else
                    printf("%I64d", a[i] - a[ind]);
            }
            if (i == n - 1)
                printf("\n");
            else
                printf(" ");
        }
    }
    while (0);
    return 0;
}

260D Black and White Tree
比赛的时候想多了，其实就是一个很简单的构造。YY能力有待提高啊。
由于只能在黑白节点之间连边，这样就构成了一个二分图。首先我们考虑这个问题：什么样的情况下存在解？经过一些YY我们可以发现，只要黑色节点和白色节点的权值总和相等，就一定有解。
接下来我们YY一下如何构造一个解。其实还是按照最直观的方法进行：我们每次都选择一个黑色节点和一个白色节点，设它们的权值分别是b_weight和w_weight。那么我们只要在它们之间连一条权值等于min(b_weight,w_weight)的边，然后删除总权值较小的那个节点。将这个过程重复(n-1)次，就得到了一棵树。
我的逻辑比较混乱的代码如下（这个代码里的sort()是多余的，事实上根本不需要对节点排序）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100005;

pair<int, int> w[N], b[N]; //0->w, 1->b
int main()
{
    int n, c, s;
    int wc, bc;

    do
    {
        scanf("%d", &n);
        wc = bc = 0;

        for (int i = 1;i <= n;++i)
        {
            scanf("%d%d", &c, &s);
            if (!c)
                w[wc++] = make_pair(s, i);
            else
                b[bc++] = make_pair(s, i);
        }

        sort(w, w + wc);
        sort(b, b + bc);
        int e = 0;
        for (int i = 0, j = 0;e < n - 1;++e)
        {
            int wei = min(w[i].first, b[j].first);
            w[i].first -= wei;
            b[j].first -= wei;
            printf("%d %d %d\n", w[i].second, b[j].second, wei);
            if (!w[i].first && i != wc - 1) //next vertex
                ++i;
            else if (!b[j].first)
                ++j;
        }
    }
    while (0);
    return 0;
}

260E Dividing Kingdom
好像是枚举9个城市的排列，然后扫描线？总感觉很麻烦的样子= =