标签存档：SRM

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;
    }
};

给定一个size不超过2*10⁶的string，里面仅包含w, o, ?三种字符。问有多少种填写?的方式使得最终的串是一个合法的样式。合法的样式定义为：

1. n个w和n个o连接成的串是一个合法的串
2. 两个合法的串连接也是一个合法的串

递推方程是裸的。
\[ f_i = \begin{cases} 1 &\mbox{i = 0} \\ \sum{f_j} &\mbox{s[j, i) is a string like w^no^n} \end{cases} \]
求$$f_n$$即可。

关键在于如何转移。其实能加速转移的方法我遇见过的总结起来就那么几种。离不开两个关键词，连续和凸性。

稍微看了一下感觉不满足凸性，于是就找连续性。然而直接看转移区间是不满足连续性的。找了好久发现对于一个给定的对称轴，往两边增长的时候，合法的pattern是满足连续性的(即小于某一长度都是合法pattern，超出的都不合法)。想了很久，发现还是没法转移。大概这种二维关系能做优化的也只有固定一个值再去考虑别的值的影响了。于是去看了题解，发现他将可以形成$$w^no^n$$的字符串分成了两种情况考虑，而这两种情况分别满足连续性。

为了方便讨论，我们设legal(i, j)表示s[i, j)可以形成形如$$w^no^n$$的字符串。

1. 前一半全是?的。这种情况对于一个固定的i，legal(i, j)随着j的增长，值是单调的。(由true变false)，所以f[i]往后的影响是某一个区间，这用树状数组或者直接加delta值在起点和终点的办法就可以实现快速转移。
2. 前一半包含有w的。这种情况对于一个固定的j，legal(i, j)虽然i的递减，值是单峰的。(由false变true再变false)这个的证明并不是那么显然，但是只要考虑到j前面第一个出现的w就会发现是有上下界限制的。具体限制包含4个，上界两个，下界两个，取交即可。然后就可以用f的部分和来快速求出答案。

实现起来还是有一点细节的。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int MAXN = 2000005;
int f[MAXN / 2 + 10];
int fsum[MAXN / 2 + 10];
int Tr[MAXN / 2 + 10];
int prevw[MAXN], prevo[MAXN], nextw[MAXN], nexto[MAXN];
const int Mod = 1e9 + 7;
string s;

void add(int i, int x) {
	x %= Mod;
	x += Mod;
	x %= Mod;
	for (++i; i < MAXN / 2 + 10; i += i & -i) {
		Tr[i] += x;
		Tr[i] %= Mod;
	}
}

int get(int i) {
	int res = 0;
	for (++i; i; i -= i & -i) {
		res += Tr[i];
		res %= Mod;
	}
	return res;
}

int Next(int x, int i) {
	if (x == 1)
		return s[i] == 'w' ? i : nextw[i];
	else
		return s[i] == 'o' ? i : nexto[i];
}

int gao() {
	int n = s.size();
	if (n & 1) return 0;
	memset(f, 0, sizeof(f));
	memset(fsum, 0, sizeof(fsum));
	f[0] = fsum[1] = 1;
	fsum[0] = 0;
	int wp = -1, op = -1;
	rep (i, n + 1) {
		prevw[i] = wp;
		prevo[i] = op;
		if (i < n && s[i] == 'w') wp = i;
		if (i < n && s[i] == 'o') op = i;
	}
	wp = n; op = n;
	for (int i = n; i >= 0; i--) {
		nextw[i] = wp;
		nexto[i] = op;
		if (i < n && s[i] == 'w') wp = i;
		if (i < n && s[i] == 'o') op = i;
	}
	rep (i, n / 2 + 1) {
		int &res = f[i] += get(i), lhs, rhs;
		int p;
		lhs = (p = prevw[i * 2]) == -1 ? n : max((i * 2 - p + 1) / 2, i * 2 - nexto[p]);
		rhs = (p = prevw[i * 2]) == -1 ? -9 : min(i * 2 - p, (i * 2 - prevo[p] + 1) / 2);
		if (lhs < rhs)
			res += (fsum[i - lhs + 1] - fsum[i - rhs + 1] + Mod) % Mod;
		res %= Mod;
		if (i * 2 == n) break;
		int len = min((Next(1, i * 2) - i * 2) / 2, Next(0, i * 2) - i * 2);
		add(i + 1, res);
		add(i + 1 + len, -res);
		fsum[i + 1] = (fsum[i] + res) % Mod;
	}
	return f[n / 2];
}

class WolfDelaymasterHard {
public:
	int countWords(int, int, int, int, int, int, int, int, int);
};

int WolfDelaymasterHard::countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd) {
	s.resize(N);
	rep (i, N) s[i] = '?';
	ll x = w0;
	for(int i=0;i<wlen;i++){
		s[x] = 'w';				// Rewrite the x-th (0-based) character of s
		x = (x * wmul + wadd) % N;
	}
	x = o0;
	for(int i=0;i<olen;i++){
		s[x] = 'o';				// Rewrite the x-th (0-based) character of s
		x = (x * omul + oadd) % N;
	}
	memset(Tr, 0, sizeof(Tr));
	return gao();
}