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

B. Galahad

 

题意：给定数列，问区间和，特殊之处在于若区间有重复数字，该数只能算一次。

树状数组+离线处理

先处理出每个位置左边最近的和它相同的数的位置。

将询问按照右端点从小到大排序，逐渐增大当前点，每次增大时从树状数组中删去与这个位置上的数相等的左边最近的位置，这样就能保证每个数都在它所能在的最右边的位置，那么每个数也就一定会被包含到，且由于在不断删除，所以一定只会同时存在一个。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
int n, m;
int a[N], lst[N], vis[N];
ll ans[N];
struct X{
	int l, r, id;
	bool operator<(const X& b) { return r < b.r; }
}q[N];
ll sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
	for (int i = p; i < N; i+=lowbit(i))
		sum[i] += x;
}
ll query(int r) {
	ll res = 0;
	for (int i = r; i > 0; i -= lowbit(i))
		res += sum[i];
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		lst[i] = vis[a[i]];
		vis[a[i]] = i;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + 1 + m);
	int R = 1;
	for (int i = 1; i <= m; i++) {
		while (R <= q[i].r) {
			if (lst[R])add(lst[R], -a[R]);
			add(R, a[R]);
			R++;
		}
		ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
	}
	for (int i = 1; i <= m; i++)printf("%lld\n", ans[i]);
	return 0;
}

 

C. 烹饪

 

题意：给定几种食材，要求挑出几个，a，b，c，d，使得ax+by+cz+dm可以形成任意正整数，其中 x,y,z,m 可以为任意不为0的整数。（并不一定是挑4个）。问有多少种挑的方式。

斐蜀定理+dp

我们知道ax+by=c有解等价于gcd(x,y)整除c，对于多元的方程同样如此。

要求多元方程右侧可以为任意数，那么gcd(x,y,z,m) 一定为1。所以就是要求挑出几个数，gcd为1的方案数。

dp[i][j]dp[i][j] 表示前 ii 个，gcd为 jj 的方案数。

dp[i][j]=dp[i−1][j],(不取a[i])dp[i][gcd(j,a[i])]+=dp[i−1][j],(取a[i])dp[i][j]=dp[i-1][j],(不取a[i])\\ dp[i][gcd(j,a[i])]+=dp[i-1][j],(取a[i]) 

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
int n;
int a[3010];
int dp[3010][2005];
int gcd(int a, int b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a%b);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		dp[i][a[i]] = 1;
		for (int j = 1; j <= 2000; j++) {
			int t = __gcd(j, a[i]);
			dp[i][j] += dp[i - 1][j];
			dp[i][t] = (dp[i][t] + dp[i - 1][j]) % mod;
		}
	}
	printf("%d\n", dp[n][1]);
	return 0;
}