0%

链接

传送门

题意

给出两个\(n \times m\)的矩阵,分别代表两种矿石在每个点的数目,第一种矿石只能从右向左运输,第二种只能从左向右运输,运输管道不能交叉,输出两种矿石运输总量的最大值。

思路

定义状态\(dp[i][j][k]\)为在从\((1, 1)\)\((i, j)\)的矩形运输量的最大值,其中\(k\)为0时代表在\((i, j)\)处向左运输,为1代表向右运输。以\(k\)为0为例,当\((i, j)\)要向左运输时,则从\((i, 1)\)\((i, j - 1)\)也要向左运输,则最大值只与\((i - 1, j)\)处的最大值有关。从而得到转移方程\(dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i][j]\),其中\(a[i][j]\)代表第一种矿石第i行的前j列的和。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

typedef long long LL;
const int maxn = 510;
int a[maxn][maxn], b[maxn][maxn];
LL dp[maxn][maxn][2];

int main() {
int n, m;
while (~scanf("%d%d", &n, &m) && (n || m)) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &b[i][j]);
b[i][j] += b[i - 1][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i][j];
dp[i][j][1] = max(dp[i][j - 1][0], dp[i][j - 1][1]) + b[i][j];
}
}
printf("%lld\n", max(dp[n][m][0], dp[n][m][1]));
}
return 0;
}

链接

传送门

题意

有1个初始武器,\(n (1 \leq n \leq 16)\)个敌人,击败每个敌人之后都会获得新的武器,每个武器所能击败的敌人也不同,给出每个武器能击败的敌人,输出最终击败所有敌人的方法总数。

思路

用二进制数表示当前状态。定义\(dp[i]、sta[i]\)分别表示击败敌人的集合为\(i\)时的方法总数和武器所能击败的敌人的集合。每个状态可以转移至击败一名新的敌人之后的状态,时间复杂度\(O(n2^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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 20;
const int maxm = (1 << 16) + 10;
char s[maxn];
int n, a[maxn];
int sta[maxm];
LL dp[maxm];

inline int read() {
scanf("%s", s);
int x = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
x |= 1 << i;
}
}
return x;
}

int main() {
int t, tt = 0;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i <= n; ++i) {
a[i] = read();
}
int S = 1 << n;
memset(dp, 0, sizeof dp);
memset(sta, 0, sizeof sta);
dp[0] = 1, sta[0] = a[0];
for (int i = 0; i < S; ++i) {
int k = sta[i] & (~i);
for (int j = 0; j < n; ++j) {
if (k & (1 << j)) {
dp[i | (1 << j)] += dp[i];
sta[i | (1 << j)] = sta[i] | a[j + 1];
}
}
}
printf("Case %d: %lld\n", ++tt, dp[S - 1]);
}
return 0;
}

链接

传送门

题意

\(w\)只白老鼠和\(b\)只黑老鼠,龙和公主轮流取,取到每只老鼠的概率相同,公主先取,龙取完之后会有一只老鼠跑掉。先取到白老鼠的胜利,如果没有人取到白老鼠,龙胜利。输出公主胜利的概率。

思路

定义状态\(d[i][j]\)为剩余\(i\)只白老鼠,\(j\)只黑老鼠是公主胜利的概率。只剩白老鼠时,概率为1;只剩黑老鼠时,概率为0。当公主和龙都取到黑老鼠时,可以根据跑掉的老鼠的颜色进行转移。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 1010;
double dp[maxn][maxn];
int main() {
int w, b;
scanf("%d%d", &w, &b);
for (int i = 0; i <= b; ++i) {
dp[0][i] = 0;
}
for (int i = 1; i <= w; ++i) {
dp[i][0] = 1;
}
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= b; ++j) {
dp[i][j] = double(i) / (i + j);
if (j >= 3) {
dp[i][j] += double(j) / (i + j) * double(j - 1) / (i + j - 1) * double(j - 2) / (i + j - 2) * dp[i][j - 3];
}
if (j >= 2) {
dp[i][j] += double(j) / (i + j) * double(j - 1) / (i + j - 1) * double(i) / (i + j - 2) * dp[i - 1][j - 2];
}
}
}
printf("%.10f\n", dp[w][b]); return 0; }

链接

传送门

题意

给出\(n\)个整数\(a[i]\),再给出\(m\)个查询,对于每个查询,给出一个整数\(x,y\),可以进行两种操作:

  • 反转\(x\)二进制表示中的一位;
  • \(x\)与给出的\(n\)个整数做异或运算;

\(x\)变为\(y\)。输出\(S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)\)\(z_i\)是第\(i\)次查询的最小操作次数。

思路

定义\(d[i]\)为使用给出的数字和二进制反转将0转化为i所需要的最少操作次数,用bfs预处理出所有范围内的结果。对于每次查询操作次数等于\(d[x \oplus y]\)

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

typedef long long LL;
const LL mod = 1000000007;
const int maxn = 50;
const int maxm = 200010;
int a[maxn], len[maxm];
bool vis[maxm];
queue<int> q;

int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 0; i < 17; ++i) {
a[n + i] = 1 << i;
}
n += 17;
memset(vis, 0, sizeof vis);
q = queue<int>();
q.push(0);
vis[0] = true;
len[0] = 0;
while (!q.empty()) {
int k = q.front();
q.pop();
for (int i = 0; i < n; ++i) {
int x = k ^ a[i];
if (vis[x]) {
continue;
}
len[x] = len[k] + 1;
vis[x] = true;
q.push(x);
}
}
LL ans = 0;
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
ans = (ans + LL(i) * len[u ^ v]) % mod;
}
cout << ans << endl;
}
return 0;
}

链接

传送门

题意

有一条长度为\(n\)的链,相邻的点之间的距离为1,再给出三条额外的边长度也为1。给出\(m\)组查询,查询\(u\)\(v\)之间的距离,输出\(S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)\)\(z_i\)是第\(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
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

typedef long long LL;
const LL mod = 1000000007;
const int maxn = 6;
int a[maxn];
int d[maxn][maxn];

int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
memset(d, 0x3f, sizeof d);
for (int i = 0; i < maxn; i += 2) {
scanf("%d%d", &a[i], &a[i + 1]);
d[i][i + 1] = d[i + 1][i] = min(d[i][i + 1], 1);
}
for (int i = 0; i < maxn; ++i) {
for (int j = i + 1; j < maxn; ++j) {
d[i][j] = d[j][i] = min(d[i][j], abs(a[i] - a[j]));
}
}
for (int k = 0; k < maxn; ++k) {
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
LL ans = 0LL;
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
LL len = abs(u - v);
for (int j = 0; j < maxn; ++j) {
for (int k = 0; k < maxn; ++k) {
len = min(len, LL(abs(u - a[j]) + abs(v - a[k]) + d[j][k]));
}
}
ans = (ans + len * i) % mod;
}
printf("%d\n", int(ans));
}
return 0;
}

链接

传送门

题意

给出\(n\)个城市的坐标和人口,现在要修建道路是所有城市连通,可以使用魔法造出一条路,设使用魔法造出的路的人口和为\(A\),剩余道路的修建长度为\(B\),输出\(A/B\)的最大值。

思路

首先构建mst求出修建mst的长度\(L\),然后预处理出mst中任意两点间的路径中最长边的长度。枚举使用魔法修建的道路连接的城市求得\(A\),在mst中减去链接的道路的最长边长\(B=L-maxcost[i][j]\)

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int maxn = 1010;
int x[maxn], y[maxn], p[maxn];
int fa[maxn], vis[maxn], visn;
double maxcost[maxn][maxn];
vector<int> G[maxn];
vector<double> W[maxn];
struct Edge {
int u, v;
double len;
bool operator < (const Edge& rhs) const {
return len < rhs.len;
}
} e[maxn * maxn];

int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void dfs(int u, int fa, double facost) {
for (int i = 0; i < visn; ++i) {
int x = vis[i];
maxcost[u][x] = maxcost[x][u] = max(maxcost[x][fa], facost);
}
vis[visn++] = u;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(v != fa) {
dfs(v, u, W[u][i]);
}
}
}

int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
scanf("%d%d%d", &x[i], &y[i], &p[i]);
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
e[m].u = i, e[m].v = j;
e[m].len = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
++m;
}
}
sort(e, e + m);
fill(G, G + n + 1, vector<int>());
fill(W, W + n + 1, vector<double>());
int cnt = n;
double mstl = 0;
for (int i = 0; i < m; ++i) {
int fu = find(e[i].u), fv = find(e[i].v);
if (fu != fv) {
fa[fu] = fv;
G[e[i].u].push_back(e[i].v);
W[e[i].u].push_back(e[i].len);
G[e[i].v].push_back(e[i].u);
W[e[i].v].push_back(e[i].len);
mstl += e[i].len;
if (--cnt == 1) {
break;
}
}
}
visn = 0;
memset(maxcost, 0, sizeof maxcost);
dfs(1, -1, 0);
double ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
ans = max(ans, (p[i] + p[j]) / (mstl - maxcost[i][j]));
}
}
printf("%.2lf\n", ans);
}
return 0;
}

链接

传送门

题意

给出一个长度为\(n\)的01串,找出其中长度大于等于\(L\)的每一位的平均值最大的连续子串。输出子串的左右端点。

思路

首先预处理出前缀和\(sum[i]\),设点\(P[i]=(i,S[i])\),则序列\(i~j\)上的平均值为\((S[j]-S[i])/(j-i+1)\)也就是直线\(P[j]P[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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100010;
char s[maxn];
int sum[maxn], p[maxn];

inline double cmp(int x1, int x2, int x3, int x4) {
--x1, --x3;
return (sum[x2] - sum[x1]) * (x4 - x3) - (sum[x4] - sum[x3]) * (x2 - x1);
}

int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, L;
scanf("%d%d%s", &n, &L, s + 1);
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + s[i] - '0';
}
int ansL = 1, ansR = L;
int i = 0, j = 0;
for (int t = L; t <= n; ++t) {
while (j - i > 1 && cmp(p[j - 2], t - L, p[j - 1], t - L) >= 0) {
--j;
}
p[j++] = t - L + 1;
while (j - i > 1 && cmp(p[i], t, p[i + 1], t) <= 0) {
++i;
}
int c = cmp(p[i], t, ansL, ansR);
if (c > 0 || (c == 0 && t - p[i] < ansR - ansL)) {
ansL = p[i]; ansR = t;
}
}
printf("%d %d\n", ansL, ansR);
}
return 0;
}

链接

传送门

题意

给出一个\(n \times n (1 \leq n \leq 75)\)的矩阵,矩阵可以滚动,求最大的连续子矩阵的和。

思路

将矩阵扩展为\(2n \times 2n\)的矩阵,枚举行的起点和终点,求出每一列的和的前缀和,然后用前缀和求最大连续和,但是由于有最长不能超过\(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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 160;
int a[maxn][maxn];
int s[maxn], ss[maxn], n, n2;
deque<int> q;

int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, ans = -100;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%d", &a[i][j]);
a[i + n][j] = a[i][j + n] = a[i + n][j + n] = a[i][j];
if (a[i][j] > ans) {
ans = a[i][j];
}
}
}
int n2 = n << 1;
if (ans > 0) {
for (int i = 1; i <= n; ++i) {
memset(s, 0, sizeof s);
for (int j = i; j < i + n; ++j) {
for (int k = 1; k <= n2; ++k) {
s[k] += a[j][k];
ss[k] = s[k] + ss[k - 1];
}
q.clear();
for(int k = 1; k <= n2; ++k) {
while(!q.empty() && ss[q.back()] > ss[k]) {
q.pop_back();
}
q.push_back(k);
while(k - q.front() > n) {
q.pop_front();
}
int val = ss[k] - ss[q.front()];
if(val > ans) {
ans = val;
}
}
}
}
}
printf("%d\n", ans);
}
return 0;
}

链接

传送门

大意

给出一个正整数\(n(5 \leq n \leq 1000)\), 输出将它分解为尽可能多的大于2的不同的正整数之和,输出分解方案,输出时最小值要尽量大。

思路

预处理出从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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 10010;
int sum[maxn];

int main() {
sum[2] = 2;
for (int i = 3; i < maxn; ++i) {
sum[i] = sum[i - 1] + i;
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int p = int(upper_bound(sum, sum + maxn, n) - sum) - 1;
n -= sum[p];
int num = p - 2 + 1, pl = n / num;
n = p - (n % num);
for (int i = 2; i <= p; ++i) {
printf("%d%c", i <= n ? i + pl : i + pl + 1, i == p ? '\n' : ' ');
}
if (t) {
puts("");
}
}
return 0;
}

链接

传送门

大意

给出一个字符串,每次可以交换两个相邻的字母,输出把它变为回文串的最少交换次数,无解输出"-1"。

思路

当且仅当存在两个及以上的字母的出现次数为奇数时,无解。在其他时候,每次都完成字符串靠两端的字母的匹配,对比固定左端和右端时的移动次数,选择较小的执行。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 110;
bool flag[maxn];
char s[maxn][maxn];
int lcp[maxn][maxn], len[maxn], idx[maxn];

int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%s", s[i]);
len[i] = int(strlen(s[i]));
}
for (int i = 0; i < n; ++i) {
lcp[i][i] = len[i];
for (int j = i + 1; j < n; ++j) {
int k = 0;
while (s[i][k] == s[j][k] && k < len[i] && k < len[j]) {
++k;
}
lcp[i][j] = lcp[j][i] = k;
}
}
memset(flag, 0, sizeof flag);
flag[0] = true, idx[0] = 0;
int ans = len[0], pre = 0, cur = 0, curlcp = -1, cnt = 1;
while (cnt <= n) {
for (int i = 0; i < n; ++i) {
if (flag[i]) {
continue;
}
if (lcp[i][pre] > curlcp) {
cur = i;
curlcp = lcp[i][pre];
}
}
ans += len[cur] - lcp[pre][cur];
pre = cur;
flag[cur] = true;
idx[cnt++] = cur;
curlcp = -1;
}
printf("%d\n", ans);
for (int i = 0; i < n; ++i) {
puts(s[idx[i]]);
}
}
return 0;
}