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

B. 筱玛爱阅读

 

题意：n本书，m个促销活动，买一个活动中的所有书可以免去活动中最便宜的那本，有n个价格标签，要求与书一一对应，使得买完所有书花钱最少。1≤n≤15,1≤m≤2n−11≤n≤15,1≤m≤2^n−1

子集dp

要让总花费最少，就是要让免费的书总价格最大。

dp[S]dp[S] 表示买了 S 状态的书，免费的书的总价格。

对于子集 t，如果存在 s^t 的促销活动，那么免费的书就增加了，但是并不知道最便宜的那本书的价格，所以考虑规定一个顺序，把所有标签从大到小排序，每次新买进一些书，就把这些书的价格规定为比之前买的书都便宜，假设原先有 jj 本书，又买进了 ii 本书，新增加的免费书的价格就是 i+ji+j 本书中最便宜的那本书的价格，一直这样操作，之前买的 jj 本书一定是最贵的 jj 本，才能使得最便宜的书最贵（贪心），而之前把标签从大到小排序了，所以新增加的书的价格就是 price[i+j]price[i+j]。

由于这样是规定新买的书参加促销，所以还要有新买的书不促销，那么还要在求完 dp[S]dp[S] 后把 dp[S∣(1<<i)]dp[S|(1<<i)] 都更新一边，表示再买一本不免费的书。

否则像

3 1

1 2 3

2 2 3

这样的数据，先买2本书参加促销（价格更贵），然后再买一本不促销的情况就没法枚举到，而只会有先买一本不促销，再买2本促销（更便宜）的情况。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, k;
int a[N], vis[N], cnt[N], dp[N], sum;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
	}
	for (int i = 1; i < (1 << n); i++)cnt[i] = cnt[i&(i - 1)] + 1;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &k);
		int tmp = 0, x;
		for (int j = 0; j < k; j++) {
			scanf("%d", &x);
			tmp |= (1 << (x - 1));
		}
		vis[tmp] = 1;
	}
	sort(a + 1, a + n + 1, greater<int>());
	for (int s = 0; s < (1 << n); s++) {
		if (vis[s])dp[s] = max(dp[s], a[cnt[s]]);
		for (int t = s; t; t = (t - 1)&s)
			if (vis[s^t])dp[s] = max(dp[s], dp[t] + a[cnt[s]]);
		for (int i = 0; i < n; i++)
			dp[s | (1 << i)] = max(dp[s | (1 << i)], dp[s]);
	}
	printf("%d\n", sum - dp[(1 << n) - 1]);
	return 0;
}

 

D. 筱玛爱线段树

 

题意：长为n的数组，m次操作：

1 l r：将 Al∼ArA_l\sim A_r 的每一项的值加上 11。

2 l r：执行操作编号在 [l,r][l,r] 内的所有操作各一次，保证 rr 小于当前操作的编号。

问最终每个数的值。

 

差分

每次2操作都会使得前面某段的操作重复一次，那么考虑从后往前建立差分数组，同时进行前缀和，从后往前遍历操作，保证遍历到时它的值就是它被重复操作的次数。

同时再维护一个A数组上的差分数组，维护数组的区间加法。

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
#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;
int n, m;
ll L[N], R[N], P[N], A[N], Q[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)scanf("%lld%lld%lld", &P[i], &L[i], &R[i]);
	for (int i = m; i >= 1; i--) {
		Q[i] = (Q[i] + Q[i + 1]) % mod;
		if (P[i] == 1) {
			A[L[i]] = (A[L[i]] + Q[i] + 1) % mod;
			A[R[i] + 1] = (A[R[i] + 1] - Q[i] - 1 + mod) % mod;
		}
		else {
			Q[R[i]] = (Q[R[i]] + Q[i] + 1) % mod;
			Q[L[i] - 1] = (Q[L[i] - 1] - Q[i] - 1 + mod) % mod;
		}
	}
	for (int i = 1; i <= n; i++)A[i] = (A[i - 1] + A[i]) % mod;
	for (int i = 1; i <= n; i++)printf("%lld%s", A[i], i == n ? "\n" : " ");
	return 0;
}

 

E. 筱玛爱游戏

 

题意：n个数，两个人轮流取走一个数放入公共的那个集合里，如果集合里存在子集的异或和为0，则最后放的人输，如果全拿完，则最后拿的人赢。

博弈+线性基

把每个数拆成二进制，就变成了n个01向量，那么存在子集的异或和为0，就表示这n个向量线性相关。

而至于为什么就是线性相关，则是因为每个向量都可以由其它向量的线性组合表示，而手算几个发现线性表示中每个向量的系数只会是-1，0，1，而每次-1时都一定是可以不出现结果向量中有-1的情况，那么就可以视为向量的异或消去了向量中的1，或者增加了向量中的1。

最多可以存在的线性无关的向量组个数就是这n个向量的矩阵的秩，求秩可以用线性基。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
int n, ans;
ll b[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		ll x;
		scanf("%lld", &x);
		for (int j = 62; j >= 0; j--) {
			if (x&(1ll << j)) {
				if (!b[j]) { b[j] = x; ans ^= 1; break; }
				x ^= b[j];
			}
		}
	}
	puts(ans ? "First" : "Second");
	return 0;
}