SRM 620

难得踩楼爷啊……
屏幕快照 2014-05-11 下午1.31.24

 

250

直接辗转相减法,把所有中途的pair放进set,查一查就出来了。

500

给n个元素,每个元素都包含m个关键字的value,再给一个排序后的结果,问是否存在一种对关键字重要程度的排序,使得按多关键字排序这n个元素以后,得到某个给定的顺序。

按重要到不重要的顺序贪心取这个关键字。正确性的关键在于,如果有两个关键字当前都可以取,那么取了其中一个以后,另一个在之后任意时刻都是可以取的。

800

01域下的高斯消元求方案数。直接算秩,2^(元素个数-秩)就是答案。当然还要小心无解的情况。

SRM 614

250

三次方枚举卡住左方,下方,以及右方/上方,再一个for计算矩形内的点,n^4暴力。

其实枚举前两个之后,每个点要求的len是固定的,按这个sort能达到n^3 lg n的复杂度。

525

这题比赛的时候没有过是很不应该的……就是一个很典型的dp。回忆一下这场SRM的过程,总结了一下为什么写这种计数自己经常会写但写得很慢。得出以下几点:

  1. 我想的过程中,经常会陷入局部情况或者说特例的求解,这样弄得最后整个代码就非常混乱,往往写出很多种情况,而这会极大的降低编码的效率。
  2. 组合计数问题,对独立的步骤进行划分是尤为重要的。而不同情况下每个步骤的操作都是类似的。把类似的过程统一处理往往能得到事半功倍的效果。
  3. 总得来看,其实这是architecture上的失败和大局观上的失败。

既然意识到了这个问题,那就在以后练习/比赛的时候注意提高吧。

算法大致是分小环和大环dp。

小环通过一个函数统一处理:count(int x, int y, int n, bool o)。这个函数返回的是,在小环上,一个接口在x号点,另一个接口在y号点,整个环的人数是n,x接口和y接口的颜色是否相等时的方案数。这个conut可以通过递推进行预处理(只和两条独立的链有关)。

然后在大环上,用g[i][j]表示处理完前i个小环,给下面的接口的颜色和“第0个环给第n-1个环的颜色”是否相等。再次递推。

最后输出g[n-1][0]即可。

1000

这题就是给定N, M, goalX, goalY求下面这个函数……

  1. 当i = goalX, j = goalY, f(i, j) = 0
  2. 其他情况 f(i, j) = (f((i + 1) % N, j) + f(i, (j + 1) % M)) / 2 + 1

输出f(0, 0)即可。

规模有100,迭代是可行的一个做法。

但是这样的迭代是过不了的……

        clr(f, 0);
        rep (it, 10000) {
            rep (i, N) rep (j, M) {
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

这是因为顺序不科学导致的……因为(goalX, goalY)才是不动点,这样盲目地走看上去就很悲剧。
假设现在我在goalX, goalY,那么我影响到的路线应当是沿着-1方向过来的。
所以改成下面这样迭代顺序就过了。

        clr(f, 0);
        rep (it, 10000) {
            rep (_i, N) rep (_j, M) {
                int i = goalX - _i, j = goalY - _j;
                if (i < 0) i += N;
                if (j < 0) j += M;
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

除了迭代以外,对于这种互相依赖的关系,迭代矩阵的又是满秩的,高斯消元解方程也是一个选择。那么假设M+N-1个未知量,其中M个在同一行,N个在同一列(为了方便,最好把不动点放在交错的位置)。这样其它的所有函数值都可以表示为这N+M-1个未知量的线性组合。绕了一圈一个,就可以得到M+N级别个方程,而M+N只有200,高斯消元是没有压力的。

但是zYc大师说好像有问题,等下写个代码看看能不能过。

更新
这个高斯消元算法是可以AC的。
代码在此

SRM 613

250

枚举分隔的位置,左边的一起向左,右边的一起向右。统计答案即可。

500

看了WJMZBMR的代码才明白过来T_T,容斥太弱了。算出区间内每个数包含的素因子。然后因为要gcd变为1,所以可以看成不能包含素因子Pi这若干个条件的与。接着就可以用容斥原理了。

900

看了芒果的代码才明白过来。首先是不能一行一行来填,这样dp的状态太难表示。

然后考虑一列一列来填。

  1. 假如只有left的话,就可以f[i][j]来表示填好前i列,其中有j列还没分配的时候的方案数。然后这个j其实蕴含了前面有j列是要填东西的,但是还没决定填在哪些行这么个意思。然后遇到left的结束端点,就可以拿这些数目去分配。大致就是乘个A几几的组合数。
  2. 现在如果有right的话,可以按left反过来那样处理,但是现在要统一起来,只能考虑从左往右填。由于一个行进入可填范围就不会变没了,所以f[i][j]表示填好前i列,还有j行没搞定。于是每次可以选择(或者不选)一个行,用当前列来填上。
  3. 最后把前两种dp合起来,f[i][j][k]转移一下就好了。

SRM 598

250pt

给定100 \leq a[i] \leq 300,每个桶容量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;
    }
};

SRM 593 1000pt

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

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

递推方程是裸的。


即可。

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

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

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

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