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

C. 小魂和他的数列

 

题意：给定数组，问有多少个长度为k的严格递增序列。

和求最长递增序列一样，每次更新当前长度的值，并用树状数组维护前缀和。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n, k, tot;
int a[N], b[N];
ll sum[20][N], dp[20][N];
int lowbit(int x) { return x & -x; }
void add(int id, int b, ll x) {
	for (int i = b; i <= tot; i += lowbit(i))sum[id][i] = (sum[id][i] + x) % mod;
}
ll query(int id, int r) {
	ll res = 0;
	for (int i = r; i > 0; i -= lowbit(i))
		res = (res + sum[id][i]) % mod;
	return res;
}
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	} while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} return x * f;
}
int main() {
	n = read(); k = read();
	for (int i = 1; i <= n; i++)a[i] = read(), b[i] = a[i];
	sort(b + 1, b + n + 1);
	tot = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; i++)a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
	for (int i = 1; i <= n; i++) {
		dp[1][a[i]] = 1;
		add(1, a[i], 1);
		for (int j = 2; j <= k; j++) {
			dp[j][a[i]] = query(j - 1, a[i] - 1);
			add(j, a[i], dp[j][a[i]]);
		}
	}
	printf("%lld\n", query(k, tot));
	return 0;
}

 

D. 小翔和泰拉瑞亚

 

题意：有n个操作，每个可以使某个区间所有值减少一定值，每个操作只能用一次，要求使得数组的最大值最小值的差最大。

滑动窗口+线段树

观察发现，如果选定某个数作为最大值，包含它的所有操作一定都不会选，不包含它的操作一定会选。

那么就可以枚举最大的数，把其他操作都选上，但是每次都重新搞也不行，那么就滑动窗口每次更换最大值就把包含最大值的操作删了，再加上需要的操作。最后线段树维护区间更改。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
const ll inf = 1e18;
int n, m;
ll a[N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll tr[N << 2], laz[N << 2];
void up(int rt) {
	tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
	if (l == r) {
		tr[rt] = a[l];
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
void down(int rt) {
	ll& x = laz[rt];
	if (x) {
		tr[rt << 1] += x;
		tr[rt << 1 | 1] += x;
		laz[rt << 1] += x;
		laz[rt << 1 | 1] += x;
		x = 0;
	}
}
void add(int ql, int qr, ll x, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		laz[rt] += x;
		tr[rt] += x;
		return;
	}
	down(rt);
	if (ql <= mid)add(ql, qr, x, lson);
	if (qr > mid)add(ql, qr, x, rson);
	up(rt);
}
struct X
{
	int l, r; ll w;
	bool operator<(const X& b)const {
		return r > b.r;
	}
}p[N];
bool cmp(const X& a, const X& b) {
	return a.l < b.l;
}
priority_queue<X>q;
ll ans;
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	} while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} return x * f;
}
int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		p[i].l = read(); p[i].r = read();
		scanf("%lld", &p[i].w);
	}
	sort(p + 1, p + m + 1, cmp);
	for (int i = 1; i <= m; i++)add(p[i].l, p[i].r, -p[i].w, 1, n, 1);
	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && q.top().r < i) {
			X t = q.top();
			add(t.l, t.r, -t.w, 1, n, 1);
			q.pop();
		}
		for (; cnt <= m && p[cnt].l <= i; cnt++) {
			X t = p[cnt];
			add(t.l, t.r, t.w, 1, n, 1);
			q.push(t);
		}
		ans = max(ans, a[i] - tr[1]);
	}
	cout << ans << endl;
	return 0;
}

 

E. 小雀和他的王国

 

题意：加一条边，使得删去一条边后不连通的几率最小。

容易想到，就是要求连上一条边后边双最少。

那么边双缩点后变成树，再取树上最长链连接首尾。

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
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	} while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} return x * f;
}
int n, m;
vector<int>G[N], gg[N];
int dfn[N], low[N], clk;
int S[N], top, cc[N], cnt;
void tarjan(int u, int fa) {
	low[u] = dfn[u] = ++clk;
	int _fst = 0;
	S[top++] = u;
	for (int v : G[u]) {
		if (v == fa && ++_fst == 1) continue;
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		cnt++;
		int tmp;
		do {
			tmp = S[--top];
			cc[tmp] = cnt;
		} while (tmp != u);
	}
}
int f[N], ans;
void dfs(int u, int _fa) {
	for (int v : gg[u]) {
		if (v == _fa)continue;
		dfs(v, u);
		ans = max(ans, f[u] + f[v] + 1);
		f[u] = max(f[u], f[v] + 1);
	}
}
typedef pair<int, int> pii;
map<pii, int>mp;
ll Pow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int main() {
	n = read(); m = read();
	for (int i = 0; i < m; i++) {
		int u, v;
		u = read(); v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	tarjan(1, 0);
	for (int i = 1; i <= n; i++) {
		for (int v : G[i]) {
			if (cc[i] != cc[v] && !mp[pii(cc[i], cc[v])]) {
				gg[cc[i]].push_back(cc[v]);
				gg[cc[v]].push_back(cc[i]);
				mp[pii(cc[i], cc[v])] = 1;
				mp[pii(cc[v], cc[i])] = 1;
			}
		}
	}
	dfs(1, 0);
	printf("%lld\n", 1ll * (cnt - ans - 1)*Pow(1ll * (m + 1), mod - 2) % mod);
	return 0;
}