https://ac.nowcoder.com/acm/contest/4120

A - Alternative Accounts

 

题意：有 k≤3k\leq 3 场比赛，知道每场哪些人参加，同一场的账号一定不会是同一个人，问至少有多少真人。

当 k=1k=1 时，最少为参加比赛的人数。

当 k=2k=2 时，最少为 max(num[1],num[2])max(num[1],num[2]) 。

当 k=3k=3 时，以二进制表示状态，则互补的账户可能是同一个人，且参加两场的只可能会和只参加一场的账号是同一个人。所以把参加两场的先加入答案，再从对应的参加的人数中减掉，表示他们被消耗掉了。最后还剩下的都是只参加一场，且没有人合并的，他们可能三场都是同一个人，所以再取 max(num[1],num[2],num[4])max(num[1],num[2],num[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
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
int n, k;
const int maxn = 1e5 + 50;
int state[maxn];
int num[8];
int t[3];
int main()
{
    cin>>n>>k;
    for(int i = 0; i < k; ++i){
        cin>>t[i];
        for(int j = 0; j < t[i]; ++j){
            int x; scanf("%d", &x); state[x] |= (1<<i);
        }
    }
    for(int i = 1; i <= n; ++i) num[state[i]]++;
    if(k == 1){
        cout<<t[0]<<endl;
    }else if(k == 2){
        cout<<max(num[1] , num[2])+num[3]<<endl;
    }else{
        int ans = num[7];
        for(int i = 0; i < 3; ++i){
            int t = 7^(1<<i);
            ans += num[t];
            if(num[t] <= num[(1<<i)]) num[(1<<i)] -= num[t];
            else num[1<<i] = 0;
        }
        int temp = max(num[1], num[2]);
        temp = max(temp, num[4]);
        ans += temp;
        cout<<ans<<endl;
    }
}

 

G - Cryptographically Secure PRNG

 

题意：给定质数 pp，问有哪些数 xx，满足 xx 的逆元是 22 ~ xx 的逆元中最小的。

枚举

先说结论：从 22 开始枚举，当遇到第一个满足 xx 的逆元 inv[x]<xinv[x]<x 时结束，由于 inv[i]inv[i] 要小于前缀的 invinv，所以枚举的同时记录逆元最小值minmin，判断当前如果 inv[i]<mininv[i]<min，则把 (i,inv[i])(i,inv[i]) 和 (inv[i],i)(inv[i],i) 都加入答案，复杂度为 O(p)O(\sqrt{p})。

证明：

假设 inv[k]<kinv[k]<k，且 j>kj>k。

若 inv[j]>jinv[j]>j，则 inv[j]>j>k>inv[k]inv[j]>j>k>inv[k]，即 inv[k]<inv[j]∧k<jinv[k]<inv[j]\wedge k<j，所以 jj 不可能成为答案。

若 inv[j]≤jinv[j]\le j，则在 jj 之前必定已经枚举过 (inv[j],j)(inv[j],j)，也就已经统计过答案了。

所以在 kk 之后的都不需要考虑了。

又易证 (i,inv[i])(i,inv[i]) 满足条件等价于 (inv[i],i)(inv[i],i) 满足条件，不满足则都不满足，所以可以放在一起考虑。

则复杂度等于满足 inv[i]≥iinv[i]\ge i 的前缀的长度，打表发现是 O(q)O(\sqrt{q})，常数在10左右，不会证，有大佬会证求告知。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
ll p;
ll inv[N];
typedef pair<int, int> pii;
vector<pii>vc;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &p);
		vc.clear();
		int mn = INF;
		inv[0] = inv[1] = 1;
		for (int i = 2; i < p; i++) {
			inv[i] = (p - p / i)*inv[p%i] % p;
			if (i > inv[i])break;
			if (inv[i] >= mn)continue;
			mn = inv[i];
			vc.push_back({ i,inv[i] });
			if (i != inv[i])vc.push_back({ inv[i],i });
		}
		sort(vc.begin(), vc.end());
		vc.erase(unique(vc.begin(), vc.end()), vc.end());
		printf("%d\n", (int)vc.size());
		for (pii p : vc) {
			printf("%d %d\n", p.first, p.second);
		}
	}
	return 0;
}

 

I - Practice for KD Tree

 

题意：一个初始全为 0 的方阵，先 m1 次矩形区间加，再 m2 次矩形区间询问最大值。

如果直接莽二维线段树，区间修改需要持久化标记。

但是这里是先全都修改完再询问，所以对于修改操作，先用二维前缀和暴力修改完。对于询问操作再用只需要询问的二维线段树。

但是本题恶心的地方在于卡常！！

二维线段树有两种写法。

第一种是分别两个函数处理行和列，在一个函数中调用另一个。

但是问题在于，这样的空间是 16N216N^2，因为两个维度都要开4倍，所以空间gg。

但是本题虽然写了空间限制，但却并没有卡死？？所以还是能过？？

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
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m1, m2;
ll a[2010][2010];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll tr[2005 << 2][2005 << 2];
void up(int id, int rt) {
	while (id) {
		if (id >> 1)tr[id >> 1][rt] = max(tr[id >> 1][rt], tr[id][rt]);
		id >>= 1;
	}
}
void buildr(int q, int id, int l, int r, int rt) {
	if (l == r) {
		tr[id][rt] = a[q][l];
		up(id, rt);
		return;
	}
	buildr(q, id, lson);
	buildr(q, id, rson);
	tr[id][rt] = max(tr[id][rt << 1], tr[id][rt << 1 | 1]);
	up(id, rt);
}
inline void build(int l, int r, int rt) {
	if (l == r) {
		buildr(l, rt, 1, n, 1);
		return;
	}
	build(lson);
	build(rson);
}
ll qryr(int id, int ql, int qr, int l, int r, int rt) {
	if (ql <= l && qr >= r)return tr[id][rt];
	ll ans = 0;
	if (ql <= mid)ans = max(ans, qryr(id, ql, qr, lson));
	if (qr > mid && ans < tr[id][rt << 1 | 1])ans = max(ans, qryr(id, ql, qr, rson));
	return ans;
}
inline ll qry(int ql, int qr, int pl, int pr, int l, int r, int rt) {
	if (ql <= l && qr >= r)return qryr(rt, pl, pr, 1, n, 1);
	ll ans = 0;
	if (ql <= mid)ans = max(ans, qry(ql, qr, pl, pr, lson));
	if (qr > mid && ans < tr[rt << 1 | 1][1])ans = max(ans, qry(ql, qr, pl, pr, rson));
	return ans;
}
int main() {
	scanf("%d%d%d", &n, &m1, &m2);
	while (m1--) {
		int x1, y1, x2, y2, w;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w);
		a[x1][y1] += w; a[x2 + 1][y2 + 1] += w;
		a[x1][y2 + 1] -= w; a[x2 + 1][y1] -= w;
	}
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {
		a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	}
	build(1, n, 1);
	while (m2--) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		printf("%lld\n", qry(x1, x2, y1, y2, 1, n, 1));
	}
	return 0;
}

第二种是把行和列一起处理，这次二分行，下次二分列，再下次二分行，再再下次又二分列。。。

但是这样时间上又会比第一种慢，虽然不知道为什么，但是慢了3到4倍。

在写的时候还发现，**把 ans 作为全局变量修改，比作为返回值要快。**这才终于卡过去。

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
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2010;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m1, m2;
ll a[N][N];
ll tr[N*N * 4];
void up(int rt) {
	tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
void build(int xl, int xr, int yl, int yr, int rt, int flg) {
	if (xl > xr || yl > yr)return;
	if (xl == xr && yl == yr) {
		tr[rt] = a[xl][yl];
		return;
	}
	if (flg) {
		int mid = ((xl + xr) >> 1);
		build(xl, mid, yl, yr, rt << 1, flg ^ 1);
		build(mid + 1, xr, yl, yr, rt << 1 | 1, flg ^ 1);
		up(rt);
	}
	else {
		int mid = ((yl + yr) >> 1);
		build(xl, xr, yl, mid, rt << 1, flg ^ 1);
		build(xl, xr, mid + 1, yr, rt << 1 | 1, flg ^ 1);
		up(rt);
	}
}
ll ans;
void qry(int qxl, int qxr, int qyl, int qyr, int xl, int xr, int yl, int yr, int rt, int flg) {
	if (qxl <= xl && qxr >= xr && qyl <= yl && qyr >= yr) {
		ans = max(ans, tr[rt]);
		return;
	}
	if (flg) {
		int mid = ((xl + xr) >> 1);
		if (qxl <= mid)qry(qxl, qxr, qyl, qyr, xl, mid, yl, yr, rt << 1, flg ^ 1);
		if (qxr > mid && ans < tr[rt << 1 | 1])qry(qxl, qxr, qyl, qyr, mid + 1, xr, yl, yr, rt << 1 | 1, flg ^ 1);
	}
	else {
		int mid = ((yl + yr) >> 1);
		if (qyl <= mid)qry(qxl, qxr, qyl, qyr, xl, xr, yl, mid, rt << 1, flg ^ 1);
		if (qyr > mid && ans < tr[rt << 1 | 1])qry(qxl, qxr, qyl, qyr, xl, xr, mid + 1, yr, rt << 1 | 1, flg ^ 1);
	}
}
int main() {
	scanf("%d%d%d", &n, &m1, &m2);
	while (m1--) {
		int x1, y1, x2, y2, w;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w);
		a[x1][y1] += w; a[x2 + 1][y2 + 1] += w;
		a[x1][y2 + 1] -= w; a[x2 + 1][y1] -= w;
	}
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {
		a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	}
	build(1, n, 1, n, 1, 1);
	while (m2--) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		ans = 0;
		qry(x1, x2, y1, y2, 1, n, 1, n, 1, 1);
		printf("%lld\n", ans);
	}
	return 0;
}