[题解] ZOJ Monthly, September 2012

=_____=拖了好久啊,我是渣渣。

ZOJ 3644 Kitty’s Game

有一只喵身上有个记分牌,她每沿着边走一步,记分牌上的数字就会变为$$lcm(x, x_i)$$,其中$$x_i$$表示这一步的终点的一个给定值。问从起点S走到终点T,最后记分牌上写着k的方案有多少种。

因为最后记分牌到达到k,而记分牌上数字唯一的变化操作是lcm,所以中间过程必须是k的约数,注意到这点就可以只对有效状态dp了。复杂度$$O(\sqrt{k} * (V + E))$$

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

const int N = 2005;
const int Mod = 1000000007;
int n, m, o;
int p[N];
vector  edge;

int f[N][N];
int ref[1000005];
vector  num;

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

long long lcm(int x, int y) {
	return 1LL * x * y / gcd(x, y);
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d %d %d", &n, &m, &o) != EOF) {
		assert(2 <= n); assert(n <= 2000); assert(2 <= m); assert(m <= 20000);
		edge.clear();
		for (int i = 0; i < m; i++) {
			int x, y;
			assert(scanf("%d %d", &x, &y) == 2);
			assert(1 <= x); assert(x <= n); assert(1 <= y); assert(y <= n);
			x--;
			y--;
			edge.push_back(PII(x, y));
		}
		for (int i = 0; i < n; i++) {
			assert(scanf("%d", &p[i]) == 1);
			assert(p[i] >= 1); assert(p[i] <= 1000000);
		}
		memset(ref, 0xFF, sizeof(ref));
		num.clear();
		for (int i = 1; i <= o; i++) {
			if (o % i == 0) {
				ref[i] = num.size();
				num.push_back(i);
			}
		}
		if (ref[p[0]] == -1) {
			puts("0");
		} else {
			memset(f, 0, sizeof(f));
			f[ref[p[0]]][0] = 1;
			for (int i = 0; i < num.size(); i++) {
				foreach (j, edge) {
					long long l = lcm(num[i], p[j->second]);
					if (l <= 1000000 && ref[l] != -1 && l != num[i]) {
						f[ref[l]][j->second] += f[i][j->first];
						f[ref[l]][j->second] %= Mod;
					}
				}
			}
			printf("%d\n", f[num.size() - 1][n - 1]);
		}
	}
}

ZOJ 3645 BiliBili

定义11维空间中点与点的距离为$$\sqrt{\sum (a_i – b_i)^2}$$。先给出一个未知点与另外12个点的距离,问这个未知点的坐标。

把$$(a_i – b_i)^2$$展开,得$$a_i^2 + b_i^2 + 2a_ib_i$$,然后对12个方程两两作差,得出11个11元线性方程。用gauss解之即可。
需要注意的是,答案不要输出-0.00,否则会WA的。

#include 
#include 
#include 
#include 
#include 
using namespace std;

int n=11;

double a[15][15];
double x[15];

void guass(){
    int i,j,k; double sum,rate;
    for (k=1;kfabs(a[j][k])?i:j;
        for (i=k;i<=n+1;i++) swap(a[j][i],a[k][i]);
        for (i=k+1;i<=n;i++)
          for (rate=a[i][k]/a[k][k],j=k;j<=n+1;j++)
            a[i][j]-=a[k][j]*rate;    
    }
    for (i=n;i>=1;i--){
        for (sum=0,j=i+1;j<=n;sum+=a[i][j]*x[j],j++);
        x[i]=(a[i][n+1]-sum)/a[i][i];
    }
}

double mat[15][15];
double result[15];

double Fix(double y){
	if (fabs(y)<5e-3) return 0;
	return y;
}

int main(){
	int Tc;
	scanf("%d",&Tc);
	while (Tc--){
		for (int i=1;i<=12;i++){
			for (int j=1;j<=11;j++)
				scanf("%lf",&mat[i][j]);
			scanf("%lf",&result[i]);
			result[i]=result[i]*result[i];
			for (int j=1;j<=11;j++){
				result[i]-=mat[i][j]*mat[i][j];
				mat[i][j]*=-2;
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++)
				a[i][j]=mat[i][j]-mat[i+1][j];
			a[i][n+1]=result[i]-result[i+1];
		}
		guass();
		for (int i=1;i<=n;i++){
			if (i!=1) printf(" ");
			printf("%.2lf",Fix(x[i]));
		}
		printf("\n");
	}
}

ZOJ 3646 Matrix Transformer

给定一个矩阵,里面包含了U和D,你可以随意交换任意列以及任何行,问最后能否使得矩阵主对角线上的元素都是U。

把这个矩阵看成邻接矩阵,U为1,然后做最大匹配即可。最后第i对匹配占领第i行第i列,就成了一个对角线全是U的矩阵。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 205;
int n;
int cover[N];
int Link[N];
char mat[N][N];

bool find(int i) {
	for (int j = 0; j < n; j++) {
		if (mat[i][j] == 'U' && !cover[j]) {
			cover[j] = 1;
			int q = Link[j];
			Link[j] = i;
			if (q == -1 || find(q)) return 1;
			Link[j] = q;
		}
	}
	return 0;
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d", &n) != EOF) {
		fill(Link, Link + n, -1);
		for (int i = 0; i < n; i++) {
			scanf("%s", mat[i]);
		}
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			memset(cover, 0, sizeof(cover));
			if (find(i)) {
				cnt++;
			}
		}
		puts(cnt == n ? "YES" : "NO");
	}
	return 0;
}

ZOJ 3647 Gao the Grid

问一个网络内点在整点上的非退化三角形的数目。

就是求C((n + 1)*(m + 1), 3) - 共线三角形的数目。共线的话,不妨先假设斜率 > 0。然后线段的右上角的端点减左下角的端点就会得到一个向量,这个向量一样的线段,都是本质相同的。枚举这个向量,再用gcd求中间整点的个数,就可以得解。根据对称性不难得出斜率 < 0的情况。 = 0的再特判一下就好了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

int m, n;

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

long long C(int m, int n) {
	if (n < 0 || n > m) return 0;
	if (n >= 10) n = m - n;
	long long ret = 1;
	for (int i = 0; i < n; i++) {
		ret = ret * (m - i);
	}
	for (int i = 0; i < n; i++) {
		ret = ret / (i + 1);
	}
	return ret;
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (cin >> m >> n) {
		assert(1 <= m); assert(m <= 1000); assert(1 <= n); assert(n <= 1000);
		long long ret = C((m + 1) * (n + 1), 3);
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (gcd(i, j)) {
					long long delta = 1LL * (m - i + 1) * (n - j + 1) * (gcd(i, j) - 1);
					if (i && j) delta += delta;
					ret -= 1LL * delta;
				}
			}
		}
		cout << ret << endl;
	}
}

ZOJ 3648 Gao the Grid II

问一个网络内点在整点上的非退化锐角三角形的数目。

对三角形占领的最小矩形范围分类,然后分别算出来输出即可。(相当于打表,累加一下即可) 分别算的时候注意非锐角三角形满足$$a^2 + b^2 \leq c^2$$ 就很简单了。

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 101;
const double EPS = 1e-10;

long long f[maxn][maxn];
int n, m;
int x, y;

long long gao(int m, int n, int & a, int & b) {
	// x*x - m*x + n > 0
	// 0 < x < m, x, m, n: integer
	// return: number of solution(x)
	long long d = (long long) m * m - 4LL * n;
	if (d < 0) return (m-1 > 0) ? m-1 : 0;
	if (d == 0) {
        if (m & 0x1) return (m-1 > 0) ? m-1 : 0;
        a = b = m / 2;
        return (m-2 > 0) ? m-2 : 0;
    }
	a = (int)floor((m + sqrt(d)) / 2.0);
	b = (int)ceil((m - sqrt(d)) / 2.0);
	return b-1 + m-1-a;
}

void init() {
	memset(f, 0, sizeof(f));
	//   a*a - m*a + n*b > 0
	//   b*b - n*b + m*a > 0
	for (int i = 2; i < maxn; i++) { // n
		for (int j = i; j < maxn; j++) { // m
			for (int k = 1; k < j; k++) { // a
				// k*k - m*k + n*b > 0 --> n*b > k*(m-k)
				// b*b - n*b + m*k > 0
				x = y = 0;
				long long ret = gao(i, j*k, y, x); // b in (0, x) + (y, i)
				int c = k*(j-k) / i; // b > c
				if (x == 0 && y == 0) {
                    f[i][j] += max(i-1-c, 0);
                    continue;
                }
				if (c < x) f[i][j] += max(x-1-c, 0) + max(i-1-y, 0); // b in (c, x) + (y, i)
				else {
					if (c < i && c > y) f[i][j] += max(i-1-c, 0);
					if (c < i && c <= y) f[i][j] += max(i-1-y, 0);
				}
			}
			f[j][i] = f[i][j];
        }
	}
}

long long count(int n, int m) {
	long long ret = 0;
	ret = 2 * (gao(n, m*m, x, y) + gao(m, n*n, x, y)) + 4 * f[n][m];
	return ret;
}

int main() {
	init();
	
	while (scanf("%d%d", &n, &m) == 2) {
		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				long long ret = count(i, j);
				ans += ret * (n-i+1) * (m-j+1);
			}
		}
		printf("%lld\n", ans);
	}
		
	return 0;
}

ZOJ 3649 Social Net

每次问一棵最大生成树上,把x->y的边拿出来按顺序放在一个list里面,求$$\max(a_j - a_i) j \geq i, 0 \leq i, j \leq n$$

先最大生成树然后使用倍增算法。算出向根走$$2^k$$步这一段区间的max, min, 正向ans, 反向ans。询问的时候把路径上的若干段取出来然后先取里面的ans,再考虑段与段间的max, min即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

const int N = 30005;

struct Edge{int x, y, w;}edge[N + N];

int n, m;
int a[N];
vector  E[N];
int root[N];
int depth[N];
int fa[N][15];
int _max[N][15];
int _min[N][15];
int _ans[N][15];
int _rans[N][15];


bool cmp(Edge a, Edge b) {
	return a.w > b.w;
}

int getRoot(int x) {
	return root[x] = root[x] == x ? x : getRoot(root[x]);
}

void dfs(int x, int f) {
	fa[x][0] = f;
	foreach (it, E[x]) {
		if (*it != f) {
			depth[*it] = depth[x] + 1;
			dfs(*it, x);
		}
	}
}

void init() {
	for (int i = 0; i < n; i++) {
		_max[i][0] = max(a[i], a[fa[i][0]]);
		_min[i][0] = min(a[i], a[fa[i][0]]);
		_ans[i][0] = a[fa[i][0]] - a[i];
		_rans[i][0] = a[i] - a[fa[i][0]];
	}
	for (int k = 1; (1 << k) < n; k++) {
		for (int i = 0; i < n; i++) {
			fa[i][k] = fa[fa[i][k - 1]][k - 1];
			_max[i][k] = max(_max[i][k - 1], _max[fa[i][k - 1]][k - 1]);
			_min[i][k] = min(_min[i][k - 1], _min[fa[i][k - 1]][k - 1]);
			_ans[i][k] = max(_ans[i][k - 1], _ans[fa[i][k - 1]][k - 1]);
			checkmax(_ans[i][k], _max[fa[i][k - 1]][k - 1] - _min[i][k - 1]);
			_rans[i][k] = max(_rans[i][k - 1], _rans[fa[i][k - 1]][k - 1]);
			checkmax(_rans[i][k], _max[i][k - 1] - _min[fa[i][k - 1]][k - 1]);
		}
		m = k;
	}
}

int getVec(vector  &vec, int x, int goal) {
	for (int k = m; k >= 0 && depth[x] > goal; k--) {
		if (depth[fa[x][k]] >= goal) {
			vec.push_back(PII(x, k));
			x = fa[x][k];
		}
	}
	return x;
}

int gao(vector  vec) {
	vector  tmp_min;
	tmp_min.resize(vec.size());
	int n = vec.size();
	if (n) {
		tmp_min[0] = _min[vec[0].first][vec[0].second];
		for (int i = 1; i < n; i++) {
			tmp_min[i] = min(tmp_min[i - 1], _min[vec[i].first][vec[i].second]);
		}
		int ret = 0, tmp_max = 0;
		for (int i = n - 1; i > 0; i--) {
			checkmax(tmp_max, _max[vec[i].first][vec[i].second]);
			checkmax(ret, tmp_max - tmp_min[i - 1]);
		}
		return ret;
	} else {
		return 0;
	}
}

int gao(int x, int y) {
	vector  pos, neg;
	if (depth[x] > depth[y]) {
		x = getVec(pos, x, depth[y]);
	} else if (depth[x] < depth[y]) {
		y = getVec(neg, y, depth[x]);
	}
	for (int k = m; k >= 0 && x != y; k--) {
		if (fa[x][k] != fa[y][k]) {
			pos.push_back(PII(x, k));
			neg.push_back(PII(y, k));
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	if (x != y) {
		pos.push_back(PII(x, 0));
		neg.push_back(PII(y, 0));
	}
	reverse(neg.begin(), neg.end());
	int ret = 0;
	vector  vec;
	foreach (it, pos) {
		vec.push_back(*it);
		checkmax(ret, _ans[it->first][it->second]);
	}
	foreach (it, neg) {
		vec.push_back(*it);
		checkmax(ret, _rans[it->first][it->second]);
	}
	checkmax(ret, gao(vec));
	return ret;
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
			root[i] = i;
			E[i].clear();
		}
		int m;
		scanf("%d", &m);
		for (int i = 0; i < m; i++) {
			scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
			edge[i].x--;
			edge[i].y--;
		}
		long long sum = 0;
		sort(edge, edge + m, cmp);
		for (int i = 0; i < m; i++) {
			int x = edge[i].x;
			int y = edge[i].y;
			if (getRoot(x) != getRoot(y)) {
				root[root[x]] = root[y];
				E[x].push_back(y);
				E[y].push_back(x);
				sum += edge[i].w;
//				printf("connect %d %d\n", x, y);
			}
		}
		cout << sum << "\n";
		depth[0] = 0;
		dfs(0, 0);
		init();
		int q, x, y;
		scanf("%d", &q);
		for (int i = 0; i < q; i++) {
			scanf("%d%d", &x, &y);
			x--; y--;
//			printf("Q %d %d\n", x, y);
			printf("%d\n", gao(x, y));
		}
	}
}

ZOJ 3650 Toy Blocks

在数轴上给定若干多米诺骨牌,然后每次你可以选择一个未推倒的骨牌把他向左或者向右推倒,推倒条件为$$| X_i - X_j | \leq H_i $$,问你最少要推几次。

先用线段树预处理出这个牌向左倒能推到哪里,向右能推到哪里。最后再用线段树优化dp的转移即可。dp的状态是f[i]表示前i个牌全倒了的方案数,转移就是像左推以及向右推。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

const int N = 105555;
const int INF = 0x7FFFFFFF;
int n;
map  mp;
int x[N];
int h[N];
int gl[N];
int gr[N];

struct Seg_t {
#define M Tr[p]
#define L Tr[p * 2]
#define R Tr[p * 2 + 1]
	struct Node {
		int l, r, max, min, tag;
	}Tr[N << 2];

	void push_down(int p) {
		if (M.tag != INF) {
			checkmin(M.min, M.tag);
			if (M.l != M.r) {
				checkmin(L.tag, M.tag);
				checkmin(R.tag, M.tag);
			}
			M.tag = INF;
		}
	}

	void update(int p) {
		push_down(p * 2);
		push_down(p * 2 + 1);
		M.max = max(L.max, R.max);
		M.min = min(L.min, R.min);
	}

	void init(int p, int l, int r, int w = 0) {
		M.l = l;
		M.r = r;
		M.max = M.min = w;
		M.tag = INF;
		if (l != r) {
			int mid = (l + r) / 2;
			init(p * 2, l, mid, w);
			init(p * 2 + 1, mid + 1, r, w);
		}
	}

	void set(int p, int x, int w) {
		push_down(p);
		if (M.l == M.r) {
			M.min = M.max = w;
		} else {
			int mid = (M.l + M.r) / 2;
			if (x <= mid) {
				set(p * 2, x, w);
			} else {
				set(p * 2 + 1, x, w);
			}
			update(p);
		}
	}

	void push_min(int p, int l, int r, int w) {
		push_down(p);
		if (l <= M.l && M.r <= r) {
			checkmin(M.tag, w);
		} else {
			int mid = (M.l + M.r) / 2;
			if (l <= mid) {
				push_min(p * 2, l, r, w);
			}
			if (r > mid) {
				push_min(p * 2 + 1, l, r, w);
			}
			update(p);
		}
	}

	int get_max(int p, int l, int r) {
		push_down(p);
		if (l <= M.l && M.r <= r) {
			return M.max;
		} else {
			int mid = (M.l + M.r) / 2;
			int ret = -INF;
			if (l <= mid) {
				checkmax(ret, get_max(p * 2, l, r));
			}
			if (r > mid) {
				checkmax(ret, get_max(p * 2 + 1, l, r));
			}
			update(p);
			return ret;
		}
	}

	int get_min(int p, int l, int r) {
		push_down(p);
		if (l <= M.l && M.r <= r) {
			return M.min;
		} else {
			int mid = (M.l + M.r) / 2;
			int ret = INF;
			if (l <= mid) {
				checkmin(ret, get_min(p * 2, l, r));
			}
			if (r > mid) {
				checkmin(ret, get_min(p * 2 + 1, l, r));
			}
			update(p);
			return ret;
		}
	}
}seg;

int f[N];

void gao() {
	seg.init(1, 0, n - 1, INF);
	for (int i = 0; i < n; i++) {
		if (gl[i] == 0) {
			seg.push_min(1, i, i, 1);
		} else {
			seg.push_min(1, i, i, seg.get_min(1, gl[i] - 1, i - 1) + 1);
		}
		int pre = i ? f[i - 1] : 0;
		seg.push_min(1, i, gr[i], pre + 1);
		f[i] = seg.get_min(1, i, i);
	}
	printf("%d\n", f[n - 1]);
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d", &n) != EOF) {
		mp.clear();
		for (int i = 0, _x, _h; i < n; i++) {
			scanf("%d%d", &_x, &_h);
			checkmax(mp[_x], _h);
		}
		n = 0;
		foreach (it, mp) {
			x[n] = it->first;
			h[n++] = it->second;
		}
		gl[0] = 0;
		for (int i = 1; i < n; i++) {
			int l = 0, r = i, mid;
			while (l < r) {
				int mid = (l + r) / 2;
				if (x[i] - x[mid] <= h[i]) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			gl[i] = l;
		}
		seg.init(1, 0, n - 1);
		for (int i = 0; i < n; i++) {
			seg.set(1, i, gl[i]);
			gl[i] = seg.get_min(1, gl[i], i);
			seg.set(1, i, gl[i]);
		}
		gr[n - 1] = n - 1;
		for (int i = n - 2; i >= 0; i--) {
			int l = i, r = n - 1, mid;
			while (l < r) {
				int mid = (l + r + 1) / 2;
				if (x[mid] - x[i] <= h[i]) {
					l = mid;
				} else {
					r = mid - 1;
				}
			}
			gr[i] = l;
		}
		seg.init(1, 0, n - 1);
		for (int i = n - 1; i >= 0; i--) {
			seg.set(1, i, gr[i]);
			gr[i] = seg.get_max(1, i, gr[i]);
			seg.set(1, i, gr[i]);
		}
		gao();
	}
}

ZOJ 3651 Cipher Lock

n个拥有a, b属性的物品放成一圈,相邻物品要求$$a_i = a_{i + 1}$$或者$$b_i = b_{i + 1}$$。再限定8个位置的物品属性,问可能的不同属性分布的方案数。

mask dp + 矩阵乘法。mask的意思是前一个值等不等于接下来的u,以及后一个值等不等于接下来的v。这两个2进制位压成一个<4的数字dp即可。 注意那8个是可能重复的= =b,注意判断。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

const long long Mod = 1234567890;

long long n, p, q;
struct Restrict {
	long long x, u, v;
}re[8];
map  mp;

struct Matrix {
	long long d[4][4];

	Matrix() {
		memset(d, 0, sizeof(d));
	}

	Matrix operator * (const Matrix &oth) {
		Matrix ret;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					ret.d[i][j] = (1LL * d[i][k] * oth.d[k][j] % Mod + 1LL * ret.d[i][j]) % Mod;
				}
			}
		}
		return ret;
	}

	void fix() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				d[i][j] %= Mod;
			}
		}
	}
}base, mul, init;

Matrix Pow(long long n) {
	if (n == 0) {
		Matrix tmp;
		for (int i = 0; i < 4; i++) {
			tmp.d[i][i] = 1;
		}
		return tmp;
	} else if (n == 1) {
		return init;
	} else {
		Matrix ret = Pow(n / 2);
		ret = ret * ret;
		if (n & 1) {
			ret = ret * init;
		}
		return ret;
	}
}

void gao(int m) {
	long long ans = 1;
	for (int i = 0; i < m; i++) {
		int j = (i + 1) % m;
		if (re[i].x % n + 1 == re[j].x) {
			if (re[i].u == re[j].u || re[i].v == re[j].v) {
				continue;
			} else {
				puts("0");
				return;
			}
		} else {
			base = Matrix();
			mul = Matrix();
			init = Matrix();
			if (re[i].u == re[j].u && re[i].v == re[j].v) {
				base.d[0][0] = 0;
				base.d[0][1] = p - 1;
				base.d[0][2] = q - 1;
				base.d[0][3] = 1;
			} else if (re[i].u == re[j].u) {
				base.d[0][0] = p - 1;
				base.d[0][1] = 0;
				base.d[0][2] = q - 1;
				base.d[0][3] = 1;
			} else if (re[i].v == re[j].v) {
				base.d[0][0] = q - 1;
				base.d[0][1] = p - 1;
				base.d[0][2] = 0;
				base.d[0][3] = 1;
			} else {
				base.d[0][0] = max(0LL, p + q - 3);
				base.d[0][1] = 1;
				base.d[0][2] = 1;
				base.d[0][3] = 0;
			}
			init.d[0][0] = max(0LL, p + q - 3);
			init.d[1][0] = q - 1;
			init.d[2][0] = p - 1;
			init.d[0][1] = 1;
			init.d[1][1] = p - 1;
			init.d[3][1] = p - 1;
			init.d[0][2] = 1;
			init.d[2][2] = q - 1;
			init.d[3][2] = q - 1;
			init.d[1][3] = 1;
			init.d[2][3] = 1;
			init.d[3][3] = 1;
			base.fix();
			mul.fix();
			init.fix();
			mul = Pow(((re[j].x - re[i].x - 2) + n) % n);
			base = base * mul;
			long long cnt = 0;
			for (int i = 1; i < 4; i++) cnt += base.d[0][i];
			cnt %= Mod;
//			cout << cnt << endl;
			ans = ans * cnt % Mod;
		}
	}
	cout << ans << endl;
}

bool cmp(Restrict a, Restrict b) {
	return a.x < b.x;
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (cin >> n >> p >> q) {
		int m = 8;
		mp.clear();
		bool flag = 1;
		for (int i = 0; i < m; i++) {
			cin >> re[i].x >> re[i].u >> re[i].v;
			if (mp.count(re[i].x)) {
				if (mp[re[i].x].first == re[i].u && mp[re[i].x].second == re[i].v) {
					i--;
					m--;
				} else {
					flag = 0;
				}
			} else {
				mp[re[i].x] = make_pair(re[i].u, re[i].v);
			}
		}
		if (flag) {
			sort(re, re + m, cmp);
			gao(m);
		} else {
			puts("0");
		}
	}
}

ZOJ 3652 Maze
蘑菇题。。。略过吧-.-,就记录那几维,mask+bfs就好了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 5;
const int px[4] = {-1,1,0,0};
const int py[4] = {0,0,-1,1};
int n, m, l, mon;
int mx[5],my[5];
int mat[55][55];
int gui[55][55];
int d[55][55][15][1 << 5];

struct Node {
	int x,y;
	int rest;
	int mask;
	Node(){}
	Node(int x,int y,int rest, int mask):x(x),y(y),rest(rest),mask(mask){}
};

vector  vec[2555];

bool inRange(int x, int y) {
	return 1 <= x && x <= m && 1 <= y && y <= n;
}

void update(int x,int y,int rest,int mask, int w) {
	if (d[x][y][rest][mask] == -1 || d[x][y][rest][mask] > w) {
		d[x][y][rest][mask] = w;
		vec[w].push_back(Node(x,y,rest,mask));
	}
}

	int sx,sy,ex,ey;

void bfs() {
	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	for (int i=0;i<2505;i++) vec[i].clear();
	vec[1].push_back(Node(sx,sy,l,0));
	d[sx][sy][l][0] = 1;
	for (int _i=0;_i<2505;_i++) {
		for (int _j = 0; _j < vec[_i].size(); _j++){
			Node now = vec[_i][_j];
			if (now.x == ex && now.y == ey) {
				printf("%d\n", _i);
				return;
			}
			int tmp = d[now.x][now.y][now.rest][now.mask];
			for (int k=0;k<4;k++) {
				int tx = now.x + px[k];
				int ty = now.y + py[k];
				if (inRange(tx, ty) && mat[tx][ty] != -1) {
					int _mask = now.mask;
					for (int i=0;i

ZOJ 3653 Sleeper's Schedule

...= =,似乎没看过这个题目,等下补上好了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

int n, t, k, l;
int f[15000][150];
vector e[15000];

int main() {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		scanf("%d%d%d%d", &n, &t, &k, &l);
		for (int i = 0; i < 10001; ++i) e[i].clear();
		for (int i = 0; i < n; ++i) {
			int s, ee, v;
			scanf("%d%d%d", &s, &ee, &v);
			e[s].push_back(PII(ee, v));
		}
		memset(f, 0x80, sizeof(f));
		int ans = 0;
		f[0][0] = 0;
		for (int i = 0; i < 10200; ++i) {
			for (int j = 0; j <= t + l; ++j) {
				if (f[i][j] > -0x00808080) {
					// time j+1 : wake up
					if (j < t + l) f[i+1][j+1] = max(f[i+1][j+1], f[i][j]);
					for (int z = 0; z < e[i].size(); ++z) {
						// event k
						PII k = e[i][z];
						int jj = j + k.first - i;
						if (jj > t + l) continue;
						f[k.first][jj] = max(f[k.first][jj], f[i][j]+k.second);
					}
					// time j+1 : sleep k time unit, minus dt^2
					if (j >= t) f[i+k+j-t][0] = max(f[i+k+j-t][0], f[i][j] - (j-t)*(j-t));
				}
			}
			ans = max(ans, f[i][0]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

ZOJ 3654 Letty's Math Class
这个超级大水题...就是表达式处理

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

string s;
char buf[100000];

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%s", buf) != EOF) {
		s = "";
		int n = strlen(buf);
		for (int i=0;i> ans;
		char sgn;
		long long x;
		while (iss >> sgn >> x) {
			if (sgn == '-') {
				ans -= x;
			} else {
				ans += x;
			}
		}
		long long y;
		cin >> x >> y;
//		cout << x << " " << y << endl;
		if (x == 9) {
			puts("A");
		} else if (y == 9) {
			puts("B");
		} else if (ans == x) {
			puts("B");
		} else {
			puts("A");
		}
	}
}

加入对话

15条评论

  1. mask的意思是前一个值等不等于接下来的u,以及后一个值等不等于接下来的v。这两个2进制位压成一个<4的数字dp,弱菜没看懂,能否详细点

      1. #include
        #include
        using namespace std;
        typedef unsigned u32;
        #define X first
        #define H second
        pair b[102400];
        u32 r[102400],l[102400],f[102400],m[102400];
        int main(){
        	for(u32 n;~scanf("%u",&n);){
        		for(size_t i=0;i=b[k+1].X;k=r[k+1]);	
        		for(u32 i=0,k;i=j;--k);
        			if(k

        这个是我队友写的O(n)的...

        1. 这个做法平均复杂度很低,但在极限情况下是O(n^2)的吧~例如这组数据:
          100000
          0 0
          1 1
          3 2
          6 3
          10 4
          15 5
          21 6
          28 7
          ……

留下评论

回复 edward_mj 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注