srm 540

发表于   |   分类于   |  

topcoder, srm 540题解

250

Description:

给定 一个数组B，和一个”+-“组成的字符数组，求有多少种A数组。
B数组是由A数组相邻的两个数和符号运算后的结果。

Solution

显然如果第一个数固定，整个A数组就固定下来了，所以就是求第一个数有多少种可能。我们发现给定的是$A_1+x_2，A_2-A_3…$这种形式。于是我们可以通过连续的运算得到$A_1$和其他$A_i$的关系，取上下界即可。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
vector<LL> B(51);
struct ImportantSequence {
	int getCount(vector <int> b, string operators) {
		int n = b.size();
		for (int i = 0; i < n; ++i)	B[i] = b[i];
		LL L = 1, R = 1e18, now = -1, last = 0;
		for (int i = 0; i < n; ++i) {
			if (now == 1)	B[i] = last - B[i];
			else B[i] += last;
			now = (now == 1) ? (operators[i] == '+' ? -1 : 1) : (operators[i] == '+' ? 1 : -1);
			if (now == 1)	R = min(R, (LL)B[i] - 1);
			else L = max(L, (LL)B[i] + 1);
			last = B[i];
		}
		return L > R ? 0 : R - L > 2e9 ? -1 : R - L + 1;
	}
};

550

Description

$N$ 个栅栏按照标号$0,1,…,N-1$围成一个圈，从$0$号栅栏开始染色。每一种颜色用$（R,G,B）$三原色表示，并且$0\le R<maxR, 0\le G<maxG, 0\le B<maxB$。规定相邻的两个栅栏颜色必须符合以下的颜色过渡条件：

  • 两种颜色的对应R,G,B差值全部都小于等于d2
  • 两种颜色的对应R,G,B差值至少有一个大于等于d1

将$0$号栅栏染色为$(startR, startG, startB)$, 然后按编号逐一染色，每次选择颜色时都是考虑前一个栅栏的颜色，随机等概率从所有符合过渡条件的颜色中挑选。问当完成$N-1$号栅栏的染色时，$N-1$与$0$之间不符合颜色过渡条件的概率是多少。
数据范围为50

Solution

容易想到dp[i][r][g][b],但是暴力转移的复杂度显然是不能接受的，接下来很容易想到三维前缀和维护转移，不妨反向考虑第$N-1$不合理的情况，看有多少概率最后可以变成初始状态即可。
复杂度$O(n \times maxR \times maxG \times maxB)$。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 51;
double dp[41][N][N][N], _[N], sum[N][N][N];
struct RandomColoring {
	double getProbability(int n, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) {
		for (int r = 0; r < maxR; ++r)
			for (int g = 0; g < maxG; ++g)
				for (int b = 0; b < maxB; ++b) {
					int t1 = abs(r - startR), t2 = abs(g - startG), t3 = abs(b - startB);
					if (!(t1 <= d2 && t2 <= d2 && t3 <= d2 && (t1 >= d1 || t2 >= d1 || t3 >= d1)))	dp[n - 1][r][g][b] = 1.0;
				}
		for (int i = n - 2; i >= 0; --i) {
			for (int r = 1; r <= maxR; ++r)
				for (int g = 1; g <= maxG; ++g)
					for (int b = 1; b <= maxB; ++b)
						sum[r][g][b] = dp[i + 1][r - 1][g - 1][b - 1] + sum[r - 1][g][b] + sum[r][g - 1][b] + sum[r][g][b - 1] - sum[r - 1][g - 1][b] - sum[r][g - 1][b - 1] - sum[r - 1][g][b - 1] + sum[r - 1][g - 1][b - 1];
			for (int r = 0; r < maxR; ++r)
				for (int g = 0; g < maxG; ++g)
					for (int b = 0; b < maxB; ++b) {
						double &t = dp[i][r][g][b];
						int r1 = max(r - d2, 0), r2 = min(r + d2 + 1, maxR);
						int g1 = max(g - d2, 0), g2 = min(g + d2 + 1, maxG);
						int b1 = max(b - d2, 0), b2 = min(b + d2 + 1, maxB);
						int tot = (r2 - r1) * (g2 - g1) * (b2 - b1);
						t = sum[r2][g2][b2] - sum[r1][g2][b2] - sum[r2][g1][b2] - sum[r2][g2][b1] + sum[r1][g1][b2] + sum[r2][g1][b1] + sum[r1][g2][b1] - sum[r1][g1][b1];
						if (d1) {
							r1 = max(r - d1 + 1, 0), r2 = min(r + d1, maxR);
							g1 = max(g - d1 + 1, 0), g2 = min(g + d1, maxG);
							b1 = max(b - d1 + 1, 0), b2 = min(b + d1, maxB);
							tot -= (r2 - r1) * (g2 - g1) * (b2 - b1);
							t -= sum[r2][g2][b2] - sum[r1][g2][b2] - sum[r2][g1][b2] - sum[r2][g2][b1] + sum[r1][g1][b2] + sum[r2][g1][b1] + sum[r1][g2][b1] - sum[r1][g1][b1];
						}
						if (tot)	t /= tot;
					}
		}
		return dp[0][startR][startG][startB];
	}
};