Chengrui's Blog

0%

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出两个\(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;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有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;
}

发表于 分类于 Disqus：

链接

传送门

题意

有\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}

发表于 分类于 Disqus：

链接

传送门

题意

有一条长度为\(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;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(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;
}

发表于 分类于 ， Disqus：

链接

传送门

题意

给出一个长度为\(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;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个\(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;
}

发表于 分类于 ， ， Disqus：

链接

传送门

大意

给出一个正整数\(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;
}

发表于 分类于 ， ， Disqus：

链接

传送门

大意

给出一个字符串，每次可以交换两个相邻的字母，输出把它变为回文串的最少交换次数，无解输出"-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;
}