标签存档：SRM

给定n, w, x(n ≤ 3000)表示把n个物品放进宽为w的矩形内。其中第i号物品放在第(i – 1) / w行，第(i – 1) % w列上。每次能圈取一个平行坐标轴的矩形把里面的物品全部删除掉。删除以后，对应的物品会往前往上凑上空掉的位置。问至少要多少次操作可以使得最后只剩第x号物品。

这题其实有三个point，都发现了就好做了。

1. 答案最多是4。做法是先删掉所有行号小于x的物品，然后x被放到第一行了。接着删掉所有行号大于第一行的。最后删除一左一右即可。
2. 离达到目标只剩一步的时候，是可以O(1)判断出来的。
3. 对于同样的x和w，随着n的递减，答案不增。

比赛的时候想到第一条和第二条，但是第三条没有注意到。
有了第一条，那么只需要能判断3次以内能不能做到即可。再根据第二条，只要能枚举两步的行为，问题就能够得到顺利解决。
本来一个r*c＝n的矩形里，子矩形的数目是$$r^2 * c^2 \leq n^2$$级别的。但是由于第三点，分x的上下左右分别考虑的时候，会发现都可以少掉一维r和一维c。于是枚举一次操作的复杂度就是O(r*c=n)的了。这样就足够pass这道题目。

#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>

using namespace std;

int w, ans;

bool isOne(int n, int x) {
	if (x % w == 0 && x + 1 == n)
		return 1;
	else if (w == 1 && !x)
		return 1;
	else if (n <= w && x + 1 == n)
		return 1;
	else if (n <= w && !x)
		return 1;
	else if (n < 2 * w && x + 1 == w && !(x / w))
		return 1;
	else
		return 0;
}

void solve(int n, int x, int cur) {
	if (n == 1) {
		ans = cur;
		return;
	}
	if (isOne(n, x)) {
		ans = cur + 1;
		return;
	}
	if (cur + 2 >= ans) return;
	int r = (n - 1) / w + 1;
	int c = w;
	int xr = x / w;
	int xc = x % w;
	for (int i = 1; i <= xr; i++)
		for (int j = 1; j <= w; j++)
			solve(n - i * j, x - i * j, cur + 1);
	if (xr + 1 != r) solve(c * (xr + 1), x, cur + 1);
	for (int i = 0; i <= xr; i++) {
		for (int j = 1; j <= xc; j++) {
			int d = (r - xr) * j + i * j - max(0, j - 1 - (n - 1) % w);
			solve(n - d, x - (i + 1) * j, cur + 1);
		}
	}
	for (int i = 0; i <= xr; i++) {
		for (int j = 1; j <= w - xc - 1; j++) {
			int d = (r - xr) * j - max(0, min(xc + j - (n - 1) % w, j));
			d += i * j;
			solve(n - d, x - i * j, cur + 1);
		}
	}
}

int gao(int n, int w, int x) {
	::w = w;
	x--;
	ans = 4;
	solve(n, x, 0);
	return ans;
}

class FoxAndAvatar {
public:
	int minimalSteps(int, int, int);
};

int FoxAndAvatar::minimalSteps(int n, int width, int x) {
	return gao(n, width, x);
}

250pt
找规律……
比较瞎的是官方题解也是这么干的。
找规律，然后用数学归纳法证明这个规律的……

500pt
算期望的好题，用矩阵混过去的，2*10^7次double运算居然TLE了。
注意利用期望的累加性质和线性性质就好。

1000pt
经典的拆点网络流，题目给定了黑白格染色，然后再把白格按所在行的奇偶性再染色一次色，就可以流了。
-.-总之网络流或者最小割的关键还是于2这个数字。要么A要么B。

256pt
bfs

576pt

有m块长度为L的木板，这些木板放置的位置只能是(i, i+L)这个区间，其中i必须是自然数。
在x = 0.5, 1.5, … (n-1).5都有对应的水滴下落频率。
每块木板放置的高度必须互不相同，如果两块模板同时占据了某个区间，那么只有高度比较高的那块木板能接到对应点的水。
每块木板接到的水的频率之和要在[A,B]这个区间内，问有多少不同的木板放置方案。
两个方案视作不相同当且仅当，有两个木板接到的水的区间范围不一样。

f[i][j][0] 表示第i个位置前没有木板，并已经放置了j块木板的方案数
f[i][j][1] 表示第i个位置前有一块木板的末尾，并已经放置了j块木板的方案数
f[i][j][2] 表示第i个位置前有一块木板，但那不是木板的结尾，需要放置一块木板在第(i, i+L)这个位置上以盖住这块木板的伸出部分。
转移一下即可。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
#define foreach(it, v) for (typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define iter(v) typeof((v).end())
#define all(v) (v).begin(), (v).end()
#define DEBUG(a) cout << #a" = " << a << endl
#define DEBUGARR(a, n) rep(i, n) cout << #a"[" << i << "] = " << a[i] << endl
typedef long long ll;

const int N = 305;
const int Mod = 1000000009;
int n;
int a[N];
int sum[N];
int f[N][N][3];

void add(int &t, int x) {
	t += x;
	if (t >= Mod) t -= Mod;
}

class TheExperiment {
    public:
    int countPlacements(vector <string> intensity, int m, int L, int A, int B)  {
    	n = sum[0] = 0;
    	rep (i, intensity.size()) {
			rep (j, intensity[i].size()) {
				a[n++] = intensity[i][j] - '0';
				sum[n] = sum[n - 1] + a[n - 1];
			}
    	}
		clr(f, 0);
		f[0][0][0] = 1;
		rep (j, m + 1) {
			rep (i, n + 1) {
				int x = f[i][j][0];
				int y = f[i][j][1];
				int z = f[i][j][2];
				add(f[i + 1][j][0], (x + y) % Mod);
				int w = (x + z) % Mod;
				if (i + L <= n) {
					rep (k, L) {
						int tmp = sum[i + k + 1] - sum[i];
						if (A <= tmp && tmp <= B) {
							add(f[i + k + 1][j + 1][k + 1 == L ? 1 : 2], w);
						}
					}
				}
				for (int k = 1; k <= L; k++){
					if (i + k > n) continue;
					if (i + k - L < 0) continue;
					int tmp = sum[i + k] - sum[i];
					if (A <= tmp && tmp <= B) {
						add(f[i + k][j + 1][1], y);
					}
				}
			}
		}
		return f[n + 1][m][0];
    }


};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

900pt

一个大小为$$10^9 * W$$ 元素为$$a-z$$的字符矩阵，知道其中大小不超过$$10 * 10$$的子矩阵的元素，问生成这个矩阵的串s可能有多少种。
已知该矩阵的生成方式为：

for (int cur = 0, i = 0; i < 10000000; i++)
    for (int j = 0; j < W; j++) {
        mat[i][j] = s[cur++];
        cur %= s.size();
    }

关键是弄清什么数目比较少，像这里是子矩阵比较小。
因为这个矩阵的生成方式是线性循环的，所以先把mat[i][j]化为mat[i * W + j]。
假设我们枚举了s的size，那么首先可以做的是判断这是不是一个可行的方案。
也就是判断是否存在mat[i % s.size()] != mat[j % s.size()] && i % s.size() == j % s.size()，这个直接两两枚举子矩阵元素判断即可。
在可行的前提下，只要再算算有多少个自由元，$$ans += 26^k$$即可，计算自由元的方法同样是两两枚举子矩阵。
但是这样肯定会TLE，所以看看哪些是可以直接一并处理的。
可以发现对于一个s的size，会造成i % s.size() == j % s.size()的情况是很少的。因为子矩阵元素总共才100个，也就是一共$$C(100, 2)$$对。而上面的等式成立的条件又是i - j == k * s.size()，所以可以找出每对i - j的约数，对它们进行上面提到的暴力处理。
而剩下的部分都是不存在i % s.size() == j % s.size()的，自由元的数目都是length - 子矩阵元素个数，所以方案都是$$26^{length - n}$$，这个随着length的增长形成等比数列，求和就很简单了。

总的来说，这个问题解决的方法来源于这样一种思路：解的大部分地方都是规则的，规则的地方直接用数学方法算出来。而对于少量不规则的部分再枚举出来单独处理。
在算法的设计中，正确衡量哪些东西比较少，哪些东西比较多是非常重要的。

#include <vector>
#include <map>
#include <set>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define iter(v) __typeof((v).end())
typedef long long ll;
typedef pair <int,int> PII;
const int N = 100;
const int Mod = 1000000009;
int n, W;
ll c[N], w[N];

int power_mod(ll a, int b) {
    if (b < 0) return 0;
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % Mod;
		a = a * a % Mod;
		b >>= 1;
	}
	return res;
}

bool check(int len) {
	rep (i, n)
		for (int j = i + 1; j < n; j++)
			if ((c[j] - c[i]) % len == 0 && w[i] != w[j])
				return 0;
	return 1;
}

int calc(int len) {
	int cnt = 0;
	rep (i, n) {
		bool flag = 1;
		rep (j, i) {
			if ((c[i] - c[j]) % len == 0) {
				flag = 0;
				break;
			}
		}
		cnt += flag;
	}
	return len - cnt;
}

void add(ll &res, ll x) {
    res += x;
    res %= Mod;
    res += Mod;
    res %= Mod;
}

int solve() {
	set <ll> s;
	rep (i, n) {
		rep (j, n) {
			if (i < j && !s.count(c[j] - c[i])) {
				for (ll k = 1; k * k <= c[j] - c[i]; k++) {
					if ((c[j] - c[i]) % k == 0) {
						s.insert(k);
						s.insert((c[j] - c[i]) / k);
					}
				}
			}
		}
	}
	ll ans = 0;
	if (W >= n) {
        ans = power_mod(26, W - n + 1);
        add(ans, -1);
        ans = ans * power_mod(25, Mod - 2) % Mod;
	}
	for (int i = 1; i < n && i <= W; i++) {
        if (check(i)) {
            add(ans, power_mod(26, calc(i)));
        }
	}
	foreach (it, s) {
		if (*it <= W && *it >= n) {
            add(ans, -power_mod(26, *it - n));
            if (check(*it)) {
                add(ans, power_mod(26, calc(*it)));
            }
		}
	}
	return ans;
}

class CharacterBoard {

public:
int countGenerators(vector <string> fragment, int W, int i0, int j0) {
	::W = W;
	n = 0;
	rep (i, fragment.size()) {
		rep (j, fragment[i].size()) {
			c[n] = (ll)(i0 + i) * W + (j0 + j);
			w[n++] = fragment[i][j] - 'a';
		}
	}
	return solve();
}




};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor