SRM 598

250pt

给定，每个桶容量300，问最少多少个桶能装完给定的a[i]。

看到过的有两种做法，一种把数字从小到大排序，然后从大到小每次贪心装。我的做法是因为只有三个100能放进一个桶里，其它至多两个，那么就枚举有多少组100是三个三个叠在一起的，剩下用sort，每次小的值，找一个尽量大的值来匹配。

550pt

有两个剑士一开始距离为d，A剑士一回合可以移动mov1，攻击范围为rng1。B剑士一回合可以移动mov2，攻击范围为rng2。A、B轮流动，问最优策略下，谁赢或者平局。

先把双方第一步能秒杀的情况排除掉，然后就是看谁mov + rng大，这个值小的必定不能赢(反证一下)。然后这个值大的要看能不能追上另外一个人，如果追的mov比较小，必定平局。mov比较大的条件下，最近是追到对方的mov+rng+1，否则再近一步对方就要反扑了。于是判断mov_op+rng_op+1+mov_op(这是因为追到最近以后，对方可以后退一步才轮到进攻方攻击)这个值是否小于等于mov_me + rng_me，如果是，就是可以赢，否则不行。

写的时候想当然了，几行的代码就写挂了-。-

    string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d)  {
        if (mov1 + rng1 >= d) return WIN;
        if (mov1 + d <= mov2 + rng2) return LOSE;
        if (mov1 + rng1 > mov2 + rng2) {
            if (mov1 > mov2) {
                return mov2 + rng2 + 1 + mov2 <= mov1 + rng1 ? WIN : DRAW;
            } else {
                return DRAW;
            }
        } else if (mov2 + rng2 > mov1 + rng1) {
            if (mov2 > mov1) {
                return mov1 + rng1 + 1 + mov1 <= mov2 + rng2 ? LOSE : DRAW;
            } else {
                return DRAW;
            }
        } else {
            return DRAW;
        }
    }

1000pt

给定一棵边长为1的树，问最少在多少个点上添加信号塔，使得每个点对信号塔的距离序列互不相同。

枚举一个放信号塔的树根，然后dfs下去，统计没有填信号塔的子树数目(记为cnt)。里面最多只能有一个子树子树不填信号塔，所以ans += cnt – 1。比赛的时候也想到这个了，但是只证出他是必要条件，充分性没证出来- -b，于是就弄了个按覆盖个数的贪心果断跪了。再仔细想想怎么证吧。

[update]
-。-想了一下，充分性好像也是显然的，这样每个节点的不同分叉都可以分辨……也是充分的。

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template <class T> void checkmin(T &t, T x) { if (x < t) t = x; }
const int N = 55;
int n;
vector <int> E[N];

int dfs(int u, int fa) {
    int res = 0, cnt = 0;
    rep (i, E[u].size()) {
        int v = E[u][i];
        if (v == fa) continue;
        int tmp = dfs(v, u);    
        if (tmp == 0) {
            cnt++;
        } else {
            res += tmp;
        }
    }
    if (cnt > 1) {
        res += cnt - 1;
    }
    return res;
}

class TPS { 
    public: 
    int minimalBeacons(vector <string> linked)  { 
        n = linked.size();
        rep (i, n) E[i].clear();
        if (n == 1) return 0;
        rep (i, n) rep (j, n) if (linked[i][j] == 'Y')
            E[i].push_back(j);
        int ans = 0x7FFFFFFF;
        rep (i, n)
            checkmin(ans, dfs(i, -1));
        return ans + 1;
    }
};