srm 542

发表于   |   分类于   |  

250

Description

从矩形地图中选三个点，使得A-B,B-C,C-A的曼哈顿距离和在给定的一个范围内，求多少种选法。$X,Y\le 3000$

Solution

水题，很容易发现曼哈顿距离和是一个矩形的周长，枚举长和宽统计即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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 M = 1e9 + 7;
const int N = 5000;
struct PatrolRoute {
    int countRoutes(int X, int Y, int minT, int maxT) {
		LL ans = 0;
  		for (int i = 2; i < X; ++i)
			for (int j = 2; j < Y; ++j) {
				if ((i + j) * 2 >= minT && (i + j) * 2 <= maxT) {
					ans += 1ll * (X - i) * (Y - j) % M * (i - 1) % M * (j - 1) % M;
				}
			}
		return ans * 6 % M;
    }
};

500

Description

给出$n$个长度都为$m$的字符串。$n\le 16, m\le 50$，任两个字符串之间的大小关系由一个随即产生的排列来决定。即，如果比较至第$i$位，则去比较$pa_i$和$pb_i$的大小关系，从而确定字符串的大小关系。问$words_i$排完序后是最小串的概率。

Solution

感觉这题很难QAQ，首先n=16可以想到状压Dp，但是状态很难想，看了别人的题解才会做。。
$dp[i][mask]$表示当前状态是$mask$，第$i$个人是最小串的概率，$mask$为i的位置表示该串已被选择。在统计第$i$个串的概率时同时记录每位字母对应比该串小的和相等的状态。分别用$small[j]$和$same[j]$存二进制状态。
当$small[j] \& mask > 0$时，显然不可以转移，当$same[j] \& mask=mask$时，转移没什么意义，否则$dp[i][mask] += dp[i][same[j] \& mask]$

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
//状压Dp
#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 = 16;
int small[51], same[51];
vector<double> ans; 
double dp[N][1 << N];
double gao(int x, int mask, int l) {
	if (dp[x][mask] != -1.0)	return dp[x][mask];
	double &t = dp[x][mask];
	if (mask == (1 << x))	return t = 1.0;
	t = 0.0;
	int cnt = 0;
	for (int i = 0; i < l; ++i) {
		if ((small[i] & mask) > 0)	++cnt;
		else if ((same[i] & mask) != mask)	++cnt, t += gao(x, mask & same[i], l);
	}
	t /= cnt;
	return t;
}
struct StrangeDictionary2 {
    vector <double> getProbabilities(vector <string> words) {
  		int n = words.size(), l = words[0].size();
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < 1 << n; ++j)
				dp[i][j] = -1.0;
		for (int i = 0; i < n; ++i) {
			memset(small, 0, sizeof(small));
			memset(same, 0, sizeof(same));
			for (int k = 0; k < l; ++k)
				for (int j = 0; j < n; ++j) {
					if (words[j][k] < words[i][k])	small[k] |= 1 << j;
					else if (words[j][k] == words[i][k])	same[k] |= 1 << j;
				}
			ans.pb(gao(i, (1 << n) - 1, l));
		}
		return ans;
    }
};