2019牛客多校第八场

发表于 分类于 阅读次数： 本文字数： 6.1k 阅读时长 ≈ 6 分钟

A. All-one Matices

solved at 01:58(+2)

求一个\(n \ast m\)的\(01\)矩阵的极大全\(1\)子矩阵数目 悬线法处理出\(d\)数组（从这个位置最多向上延伸多少个\(1\)），然后单调栈处理出每个位置的\(d\)能延伸的左右最远位置，\(vis\)打标记的时候如果发现标记不是\(i-1\)也不是\(0\)说明这里之前有一个极大矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

char a[N][N];
int d[N][N], s[N][N], s2[N][N], n, m, vis[N][N], ans;
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", a[i] + 1);
	}
	for(int j = 1; j <= m; ++j) {
		for(int i = 1; i <= n; ++i) {
			if(a[i][j] == '0')
				d[i][j] = 0;
			else
				d[i][j] = d[i - 1][j] + 1;
		}
	}
	for(int i = 1; i <= n; ++i) {
		stack<int> st;
		while(!st.empty()) st.pop();
		d[i][m + 1] = -1;
		st.push(m + 1);
		for(int j = m; j; --j) {
			while(d[i][st.top()] >= d[i][j]) st.pop();
			s[i][j] = st.top() - 1;
			st.push(j);
		}
	}
	for(int i = 1; i <= n; ++i) {
		stack<int> st;
		while(!st.empty()) st.pop();
		d[i][0] = -1;
		st.push(0);
		for(int j = 1; j <= m; ++j) {
			while(d[i][st.top()] >= d[i][j]) st.pop();
			s2[i][j] = st.top() + 1;
			st.push(j);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(a[i][j] == '0') continue;
			int r = s[i][j], l = s2[i][j];
			if(vis[l][r] == i) continue;
			if(vis[l][r] != i - 1 && vis[l][r]) ans++;
			vis[l][r] = i;
		}
	}
	for(int i = 1; i <= m; ++i) 
		for(int j = i; j <= m; ++j) 
			ans += vis[i][j] != 0;
	printf("%d\n", ans);
	return 0;
}

B. Beauty Values

solved at 00:13

定义beauty values为数组中不同的数的数量，求所有区间的beauty values 之和

期望的线性性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, a[N];
long long ans;
vector<int> pos[N];

int main() {
	scanf("%d", &n);
	for(int i = 1; i < N; ++i) pos[i].push_back(0);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pos[a[i]].push_back(i);
	}
	for(int i = 1; i < N; ++i) {
		for(int j = 1; j < pos[i].size(); ++j) {
			ans += 1LL * (pos[i][j] - pos[i][j - 1]) * (n - pos[i][j] + 1);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

C. CDMA

solved at 01:30

构造一个\(m \ast m\)的矩阵，元素均为正负一，要求满足任意两行的相应位置乘积之和为\(0\)，\(m\)为2的幂次

首先手推出\(m=2\)的解（其实样例已经给了），然后把它复制三边得到一个\(4 \ast 4\)的矩阵，把右下角的\(2 \ast 2\)个元素取反，就得到了\(m=4\)的解，以此类推即可(我是用的\(m=4\)作为初始矩阵往下推得)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int d[4][4] = {
	{1, 1, 1, 1},
	{1, 1, -1, -1},
	{1, -1, 1, -1},
	{1, -1, -1, 1}
};

int m;
int f(int i, int j, int mod) {
	if(mod == 4) return 1;
	mod /= 2;
	return (i >= mod && j >= mod ? -1 : 1) * f(i % mod, j % mod, mod);
}

int main() {
	scanf("%d", &m);
	if(m == 2) {
		puts("1 1\n1 -1");
		return 0;
	}
	for(int i = 0; i < m; ++i) {
		for(int j = 0; j < m; ++j) {
			printf("%d\t", f(i, j, m) * d[i % 4][j % 4]);
		}
		puts("");
	}
	return 0;
}

D. Distance

upsolved

有一个三维空间，有两种操作，给一个点打上标记，或者查询给定点到所有已标记点中的最小曼哈顿距离，保证三维空间长宽高乘积不超过\(1e5\)

可以定期重构\(bfs\)，但是显然三维树状数组更短

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, h, q, op, x, y, z;

struct BIT {
	static int lowbit(int x) {return x & -x;}
	static void mmax(int &x, int y) {x = (x > y ? x : y);}
	static int index(int i, int j, int k) {return (i - 1) * m * h + (j - 1) * h + k;}
	int c[N];
	void init() {memset(c, 0xc0, sizeof(c));}
	void update(int x, int y, int z, int val) {
		for(int i = x; i <= n; i += lowbit(i)) 
			for(int j = y; j <= m; j += lowbit(j))
				for(int k = z; k <= h; k += lowbit(k))
					mmax(c[index(i, j, k)], val);
	} 
	int query(int x, int y, int z) {
		int res = -1e9;
		for(int i = x; i; i -= lowbit(i))
			for(int j = y; j; j -= lowbit(j))
				for(int k = z; k; k -= lowbit(k))
					res = max(res, c[index(i, j, k)]);
		return res;
	}
}T[8];


int main() {
	scanf("%d%d%d%d", &n, &m, &h, &q);
	for(int i = 0; i < 8; ++i) T[i].init();
	while(q--) {
		scanf("%d%d%d%d", &op, &x, &y, &z);
		if(op == 1) {
			for(int mask = 0; mask < 8; ++mask) {
				int tx = x, ty = y, tz = z, vx = x, vy = y, vz = z;
				if(mask & 1) tx = n - tx + 1, vx = -vx;
				if(mask & 2) ty = m - ty + 1, vy = -vy;
				if(mask & 4) tz = h - tz + 1, vz = -vz;
				T[mask].update(tx, ty, tz, vx + vy + vz);
			}
		}
		else {
			int res = 1e9;
			for(int mask = 0; mask < 8; ++mask) {
				int tx = x, ty = y, tz = z, vx = x, vy = y, vz = z;
				if(mask & 1) tx = n - tx + 1, vx = -vx;
				if(mask & 2) ty = m - ty + 1, vy = -vy;
				if(mask & 4) tz = h - tz + 1, vz = -vz;
				res = min(res, vx + vy + vz - T[mask].query(tx, ty, tz));
			}
			printf("%d\n", res);
		}
	}
	return 0;
}

E. Explorer

upsolved

无向图，每条边有上下界限制，只有在上下界之中的数字可以通过这条边，询问有多少种数字可以从\(1\)走到\(n\)

时间分治线段树+可撤销并查集

把size限制看成时间限制就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10;
 
int u[N], v[N], l[N], r[N], b[N << 1], n, m, tot, fa[N], sz[N];
vector<int> g[N << 3];
stack<pair<int*, int>> stk[22];
long long ans;
 
int find(int x) {
    return x== fa[x] ? x : find(fa[x]);
}
 
void update(int rt, int l, int r, int L, int R, int id) {
    if(L <= l && r <= R) {g[rt].push_back(id); return;}
    int mid = l + r >> 1;
    if(L <= mid) update(rt << 1, l, mid, L, R, id);
    if(R > mid) update(rt << 1 | 1, mid + 1, r, L, R, id);
}
 
void dfs(int rt, int l, int r, int dep) {
    while(!stk[dep].empty()) stk[dep].pop();
    for(auto i: g[rt]) {
        int x = find(u[i]), y = find(v[i]);
        if(x == y) continue;
        if(sz[x] < sz[y]) swap(x, y);
        stk[dep].push(make_pair(&sz[x], sz[x]));
        stk[dep].push(make_pair(&fa[y], fa[y]));
        sz[x] += sz[y];
        fa[y] = x;
    }
    if(l == r) {
        if(find(1) == find(n))
            ans += b[r + 1] - b[l];
    }
    else {
        int mid = l + r >> 1;
        dfs(rt << 1, l, mid, dep + 1);
        dfs(rt << 1 | 1, mid + 1, r, dep + 1);
    }
    while(!stk[dep].empty()) {
        *(stk[dep].top().first) = stk[dep].top().second;
        stk[dep].pop();
    }
}
 
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d", &u[i], &v[i], &l[i], &r[i]);
        b[2 * i - 1] = l[i];
        b[2 * i] = ++r[i];
    }
    sort(b + 1, b + 2 * m + 1);
    tot = unique(b + 1, b + 2 * m + 1) - b - 1;
    for(int i = 1; i <= m; ++i) {
        l[i] = lower_bound(b + 1, b + tot + 1, l[i]) - b;
        r[i] = lower_bound(b + 1, b + tot + 1, r[i]) - b - 1;
        update(1, 1, tot, l[i], r[i], i);
    }
    for(int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    dfs(1, 1, tot, 0);
    printf("%lld\n", ans);
    return 0;
}

G. Gemstones

solved at 00:17

签到题，用栈贪心即可