Chengrui's Blog

0%

发表于 分类于 ， Disqus：

链接

传送门

题意

给出\(n \times m\)的矩阵，'#'代表沼泽，'.'代表空地，对于每个点向右上方能扩展到周长最大的矩形，记录不同周长的矩形的个数。

思路

对于每一行维护举行高度和左边界的单调栈。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1005;
const int maxm = 2005;
int h[maxn], ans[maxm];
char s[maxn];
int r[maxn], c[maxn];

int main(){
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(h, 0, sizeof h);
    memset(ans, 0, sizeof ans);
    for (int i = 0; i < n; ++i) {
      scanf("%s", s);
      int p = -1;
      for (int j = 0; j < m; ++j) {
        if (s[j] == '.') {
          ++h[j];
          int cc = j;
          while (p >= 0 && r[p] >= h[j]) {
            cc = c[p--];
          }
          if (p == -1 || r[p] - c[p] < h[j] - cc) {
            ++p;
            r[p] = h[j];
            c[p] = cc;
          }
          ++ans[r[p] + j + 1 - c[p]];
        } else {
          p = -1;
          h[j] = 0;
        }
      }
    }
    for (int i = 0; i < maxm; ++i) {
      if (ans[i] > 0) {
        printf("%d x %d\n", ans[i], i << 1);
      }
    }
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出一个黑白色魔方，最多有五个黑块，求最多有几种不同形态。

思路

场上感觉这道能搞，搞了搞就出来了。枚举移动，用最小表示判重就好了。

代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;
typedef long long LL;
const int rf[][16] = {
  { 0,  1,  2,  5,  8,  7,  6,  3,  0,  1,  2,  5,  8,  7,  6,  3},
  { 9, 10, 11, 14, 17, 16, 15, 12,  9, 10, 11, 14, 17, 16, 15, 12},
  {18, 19, 20, 23, 26, 25, 24, 21, 18, 19, 20, 23, 26, 25, 24, 21},
  {27, 28, 29, 32, 35, 34, 33, 30, 27, 28, 29, 32, 35, 34, 33, 30},
  {36, 37, 38, 41, 44, 43, 42, 39, 36, 37, 38, 41, 44, 43, 42, 39},
  {45, 46, 47, 50, 53, 52, 51, 48, 45, 46, 47, 50, 53, 52, 51, 48},
};
const int re[][24] = {
  {38, 37, 36, 29, 28, 27, 20, 19, 18, 11, 10,  9, 38, 37, 36, 29, 28, 27, 20, 19, 18, 11, 10,  9},
  { 0,  3,  6, 18, 21, 24, 45, 48, 51, 44, 41, 38,  0,  3,  6, 18, 21, 24, 45, 48, 51, 44, 41, 38},
  { 6,  7,  8, 27, 30, 33, 47, 46, 45, 17, 14, 11,  6,  7,  8, 27, 30, 33, 47, 46, 45, 17, 14, 11},
  {36, 39, 42, 53, 50, 47, 26, 23, 20,  8,  5,  2, 36, 39, 42, 53, 50, 47, 26, 23, 20,  8,  5,  2},
  { 2,  1,  0,  9, 12, 15, 51, 52, 53, 35, 32, 29,  2,  1,  0,  9, 12, 15, 51, 52, 53, 35, 32, 29},
  {15, 16, 17, 24, 25, 26, 33, 34, 35, 42, 43, 44, 15, 16, 17, 24, 25, 26, 33, 34, 35, 42, 43, 44},
  { 1,  4,  7, 19, 22, 25, 46, 49, 52, 43, 40, 37,  1,  4,  7, 19, 22, 25, 46, 49, 52, 43, 40, 37},
  {12, 13, 14, 21, 22, 23, 30, 31, 32, 39, 40, 41, 12, 13, 14, 21, 22, 23, 30, 31, 32, 39, 40, 41},
  { 3,  4,  5, 28, 31, 34, 50, 49, 48, 16, 13, 10,  3,  4,  5, 28, 31, 34, 50, 49, 48, 16, 13, 10},
};
const LL Mask[] = {-481977700336, -2588525269081674, -246300532427201, -10278919686062373, -15796654028395016, -17447110756761601, -5146951406846099, -3855821598721, -1970344432837689};
set<LL> s;
queue<LL> q;

LL Rotate(LL k, int x, int d1, int d2) {
  LL res = k & Mask[x];
  for (int i = 0; i < 8; ++i) {
    if (k & (1LL << rf[x][i])) {
      res |= 1LL << rf[x][i + d1];
    }
  }
  for (int i = 0; i < 12; ++i) {
    if (k & (1LL << re[x][i])) {
      res |= 1LL << re[x][i + d2];
    }
  }
  return res;
}

LL Rotate2(LL k, int x, int d) {
  LL res = k & Mask[x];
  for (int i = 0; i < 12; ++i) {
    if (k & (1LL << re[x][i])) {
      res |= 1LL << re[x][i + d];
    }
  }
  return res;
}

LL trans(LL k) {
  LL res = k, x = k;
  for (int i = 1; i < 4; ++i) {
    x = Rotate(x, 2, 2, 3);
    x = Rotate(x, 4, 6, 9);
    x = Rotate2(x, 8, 3);
    if (x < res) {
      res = x;
    }
  }
  x = Rotate(k, 0, 2, 3);
  x = Rotate(x, 5, 6, 9);
  x = Rotate2(x, 7, 9);
  if (x < res) {
    res = x;
  }
  for (int i = 1; i < 4; ++i) {
    x = Rotate(x, 2, 2, 3);
    x = Rotate(x, 4, 6, 9);
    x = Rotate2(x, 8, 3);
    if (x < res) {
      res = x;
    }
  }
  x = Rotate(k, 0, 4, 6);
  x = Rotate(x, 5, 4, 6);
  x = Rotate2(x, 7, 6);
  if (x < res) {
    res = x;
  }
  for (int i = 1; i < 4; ++i) {
    x = Rotate(x, 2, 2, 3);
    x = Rotate(x, 4, 6, 9);
    x = Rotate2(x, 8, 3);
    if (x < res) {
      res = x;
    }
  }
  x = Rotate(k, 0, 6, 9);
  x = Rotate(x, 5, 2, 3);
  x = Rotate2(x, 7, 3);
  if (x < res) {
    res = x;
  }
  for (int i = 1; i < 4; ++i) {
    x = Rotate(x, 2, 2, 3);
    x = Rotate(x, 4, 6, 9);
    x = Rotate2(x, 8, 3);
    if (x < res) {
      res = x;
    }
  }
  x = Rotate(k, 1, 2, 3);
  x = Rotate(x, 3, 6, 9);
  x = Rotate2(x, 6, 3);
  if (x < res) {
    res = x;
  }
  for (int i = 1; i < 4; ++i) {
    x = Rotate(x, 2, 2, 3);
    x = Rotate(x, 4, 6, 9);
    x = Rotate2(x, 8, 3);
    if (x < res) {
      res = x;
    }
  }
  x = Rotate(k, 1, 6, 9);
  x = Rotate(x, 3, 2, 3);
  x = Rotate2(x, 6, 9);
  if (x < res) {
    res = x;
  }
  for (int i = 1; i < 4; ++i) {
    x = Rotate(x, 2, 2, 3);
    x = Rotate(x, 4, 6, 9);
    x = Rotate2(x, 8, 3);
    if (x < res) {
      res = x;
    }
  }
  return res;
}

int main() {
  int t, tt = 0;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    LL st = 0;
    for (int i = 0; i < n; ++i) {
      int x;
      scanf("%d", &x);
      st |= 1LL << x;
    }
    st = trans(st);
    q = queue<LL>();
    s.clear();
    q.push(st);
    s.insert(st);
    while (!q.empty()) {
      LL k = q.front();
      q.pop();
      for (int i = 0; i < 6; ++i) {
        LL a = trans(Rotate(k, i, 2, 3));
        if (!s.count(a)) {
          s.insert(a);
          q.push(a);
        }
        LL b = trans(Rotate(k, i, 6, 9));
        if (!s.count(b)) {
          s.insert(b);
          q.push(b);
        }
      }
    }
    printf("Case #%d: %d\n", ++tt, int(s.size()));
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(m\)和\(n\)个数字\(a_i\)，求\(a_1\)\(a_2\)\(\cdot \cdot \cdot\)^\(a_n % m\)的值。

思路

利用欧拉定理进行解决。

代码

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

typedef long long LL;
const int maxn = 12;
const int maxm = 10010;
char s[maxn];
int a[maxn];
int phi[maxm];

void phi_table() {
  phi[1] = 1;
  for (int i = 2; i < maxm; ++i) {
    if (!phi[i]) {
      for (int j = i; j < maxm; j += i) {
        if (!phi[j]) {
          phi[j] = j;
        }
        phi[j] = phi[j] / i * (i - 1);
      }
    }
  }
}

int pow_mod(int x, int k, int mod) {
  if (x == 1 || k == 0) {
    return 1;
  }
  int res = 1;
  for (int i = 0; i < k; ++i) {
    res *= x;
    if (res >= mod) {
      break;
    }
  }
  if (res < mod) {
    return res;
  }
  res = 1;
  int cur = x;
  while (k) {
    if (k & 1) {
      res = res * cur % mod;
    }
    cur = cur * cur % mod;
    k >>= 1;
  }
  return res + mod;
}

int dfs(int d, int mod, int n) {
  if (d == n) {
    return a[d] >= mod ? a[d] % mod + mod : a[d];
  }
  return pow_mod(a[d], dfs(d + 1, phi[mod], n), mod);
}

int main() {
  phi_table();
  int t = 0;
  while (~scanf("%s", s) && s[0] != '#') {
    int n, m;
    sscanf(s, "%d", &m);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
    }
    printf("Case #%d: %d\n", ++t, dfs(1, m, n) % m);
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

有\(n\)个点，每个点有\(x_i\)、\(a_i\)、\(b_i\)、\(c_i\)、\(d_i\)，五个值，从\(i\)点到\(j\)点移动的代价为：

  • 当\(i < j\)时，\(|x_i - x_j| + c_i + b_j\)。
  • 当\(i > j\)时，\(|x_i - x_j| + d_i + a_j\)。

给出起点\(s\)终点\(e\)，从\(s\)到\(e\)的哈密顿道路的最小代价。

思路

状态\(dp[i][j][k][l]\)表示前\(i\)个点的导出子图中有\(j\)个连通分量可以接任意起点和终点，有\(k\)条的起点为\(s\)可以接任意终点，有\(l\)条终点是\(e\)可以接任意起点时的最小代价。其中\(k\)和\(l\)最大为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
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
89
90
#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL inf = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 5010;
int x[maxn], a[maxn], b[maxn], c[maxn], d[maxn];
LL dp[2][maxn][2][2];

inline void Set(LL& a, LL b) {
  if (a > b) {
    a = b;
  }
}

int main() {
  int n, s, e;
  scanf("%d%d%d", &n, &s, &e);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &b[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &c[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &d[i]);
  }
  memset(dp[0], 0x3f, sizeof dp[0]);
  dp[0][0][0][0] = 0;
  for (int p = 1; p <= n; ++p) {
    int i = p & 1;
    LL A = a[p] + x[p], B = b[p] - x[p];
    LL C = c[p] + x[p], D = d[p] - x[p];
    memset(dp[i], 0x3f, sizeof dp[i]);
    for (int j = min(p, n - p); j >= 0; --j) {
      for (int k = 0; k < 2; ++k) {
        for (int l = 0; l < 2; ++l) {
          LL& v = dp[1 - i][j][k][l];
          if (v == inf) {
            continue;
          }
          if (p == n) {
            if (p == s) {
              Set(dp[i][0][0][0], v + C);
            } else if (p == e) {
              Set(dp[i][0][0][0], v + A);
            } else {
              Set(dp[i][0][0][0], v + A + C);
            }
          } else {
            if (p == s) {
              if (j > 0) {
                Set(dp[i][j - 1][1][l], v + C);
              }
              Set(dp[i][j][1][l], v + D);
            } else if (p == e) {
              if (j > 0) {
                Set(dp[i][j - 1][k][1], v + A);
              }
              Set(dp[i][j][k][1], v + B);
            } else {
              Set(dp[i][j + 1][k][l], v + B + D);
              if (j > 0) {
                Set(dp[i][j][k][l], v + min(A + D, B + C));
                if (j > 1 || k > 0 || l > 0) {
                  Set(dp[i][j - 1][k][l], v + A + C);
                }
              } else {
                if (k > 0) {
                  Set(dp[i][j][k][l], v + A + D);
                }
                if (l > 0) {
                  Set(dp[i][j][k][l], v + B + C);
                }
              }
            }
          }
        }
      }
    }
  }
  printf("%I64d\n", dp[n & 1][0][0][0]);
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出圆周上的\(n(1 \leq n \leq 40)\)个点，取\(m(1 \leq m \leq n)\)个点围成多边形，输出最大的面积。

思路

\(dp[i][j][k]\)代表取的第一个点为\(i\)，最后一个点为\(j\)，总共取了\(k\)个点的最大面积。则有\(dp[i][j][k] = max(dp[i][x][k - 1] + S_{ijx});\)

代码

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

typedef long long LL;
const int maxn = 42;
const double PI = acos(-1);
double a[maxn];
double l[maxn][maxn];
double s[maxn][maxn][maxn];
double dp[maxn][maxn][maxn];

inline double dis(int i, int j) {
  double x = fabs(a[i] - a[j]);
  if (x > 0.5) {
    x = 1 - x;
  }
  return 2 * sin(x * PI);
}

inline double S(int i, int j, int k) {
  double a = l[i][j], b = l[j][k], c = l[i][k];
  double p = (a + b + c) / 2;
  return sqrt(p * (p - a) * (p - b) * (p - c));
}

int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m) && (n || m)) {
    for (int i = 1; i <= n; ++i) {
      scanf("%lf", &a[i]);
      for (int j = 1; j < i; ++j) {
        l[j][i] = dis(i, j);
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j) {
        for (int k = j + 1; k <= n; ++k) {
          s[i][j][k] = S(i, j, k);
        }
      }
    }
    memset(dp, 0, sizeof dp);
    for (int k = 3; k <= m; ++k) {
      for (int i = 1; i <= n; ++i) {
        for (int x = i + k - 2; x <= n; ++x) {
          for (int j = x + 1; j <= n; ++j) {
            dp[i][j][k] = max(dp[i][j][k], dp[i][x][k - 1] + s[i][x][j]);
          }
        }
      }
    }
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j) {
        ans = max(ans, dp[i][j][m]);
      }
    }
    printf("%.6f\n", ans);
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个沙漏，求从顶至底经过数字的和为定值的路径数目。如果数目不为零，输出字典序最小的一条。

思路

类似于背包的dp，对于每个点保存从当前点到沙漏底部不同值的路径数目。

代码

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

typedef long long LL;
const int maxn = 21;
const int maxs = 505;
int a[maxn << 1][maxn];
LL dp[maxn << 1][maxn][maxs];

int main() {
  int n, s;
  while (~scanf("%d%d", &n, &s) && (n || s)) {
    for (int i = 1; i < n; ++i) {
      for (int j = 1; j <= n - i + 1; ++j) {
        scanf("%d", &a[i][j]);
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        scanf("%d", &a[n + i - 1][j]);
      }
    }
    memset(dp, 0, sizeof dp);
    int n2 = (n << 1) - 1;
    for (int i = 1; i <= n; ++i) {
      dp[n2][i][a[n2][i]] = 1;
    }
    for (int i = n2 - 1; i >= n; --i) {
      for (int j = 1; j <= i - n + 1; ++j) {
        for (int k = a[i][j]; k <= s; ++k) {
          dp[i][j][k] = dp[i + 1][j][k - a[i][j]] + dp[i + 1][j + 1][k - a[i][j]];
        }
      }
    }
    LL ans = 0;
    for (int i = n - 1; i >= 1; --i) {
      for (int j = 1; j <= n - i + 1; ++j) {
        for (int k = a[i][j]; k <= s; ++k) {
          dp[i][j][k] = 0;
          if (j > 1) {
            dp[i][j][k] += dp[i + 1][j - 1][k - a[i][j]];
          }
          if (j < n - i + 1) {
            dp[i][j][k] += dp[i + 1][j][k - a[i][j]];
          }
        }
        if (i == 1) {
          ans += dp[i][j][s];
        }
      }
    }
    printf("%lld\n", ans);
    if (ans > 0) {
      for (int i = 1; i <= n; ++i) {
        if (dp[1][i][s] > 0) {
          printf("%d ", i - 1);
          int p = i, ss = s;
          for (int j = 1; j < n; ++j) {
            ss -= a[j][p];
            if (p > 1 && dp[j + 1][p - 1][ss] > 0) {
              putchar('L');
              --p;
            } else {
              putchar('R');
            }
          }
          for (int j = n; j < n2; ++j) {
            ss -= a[j][p];
            if (dp[j + 1][p][ss] > 0) {
              putchar('L');
            } else {
              ++p;
              putchar('R');
            }
          }
          break;
        }
      }
    }
    puts("");
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

两家公司有多个申请，每个申请包含一些资源的使用权并且会给政府一些资金，同一个公司的申请中不含相同的资源。资源的使用权不能同时批给两个公司，求政府的最大收益。

思路

从原点向T公司的申请连容量为申请金额的边，从M公司的申请向汇点连容量为申请金额的边，两公司冲突的申请之间连容量为无穷大的边。政府解决冲突的最小代价就是源点到汇点的最小割。

代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 6010;
const int maxm = 300010;
int p[maxn], vis[maxm];
int g[maxn >> 1][maxn >> 1];

struct Edge {
  int from, to, cap, flow;
  Edge() {}
  Edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f) {}
};

struct ISAP {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool vis[maxn];
  int p[maxn];
  int d[maxn];
  int num[maxn];
  int cur[maxn];
  
  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = int(edges.size());
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }
  
  void ClearAll(int n) {
    this -> n = n;
    for (int i = 0; i < n; ++i) {
      G[i].clear();
    }
    edges.clear();
  }
  
  bool BFS() {
    memset(vis, 0, sizeof vis);
    vis[t] = true;
    d[t] = 0;
    queue<int> Q;
    Q.push(t);
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); ++i) {
        Edge& e = edges[G[x][i] ^ 1];
        if (!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = true;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
  }
  
  int Augment() {
    int x = t, a = inf;
    while (x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap - e.flow);
      x = e.from;
    }
    x = t;
    while (x != s) {
      edges[p[x]].flow += a;
      edges[p[x] ^ 1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
  }
  
  int Maxflow(int s, int t) {
    this -> s = s, this -> t = t;
    int flow = 0;
    BFS();
    memset(num, 0, sizeof num);
    for (int i = 0; i < n; ++i) {
      ++num[d[i]];
    }
    memset(cur, 0, sizeof cur);
    int x = s;
    while (d[s] < n) {
      if (x == t) {
        flow += Augment();
        x = s;
      }
      bool ok = false;
      for (int i = cur[x]; i < G[x].size(); ++i) {
        Edge& e = edges[G[x][i]];
        if (e.cap > e.flow && d[x] == d[e.to] + 1) {
          ok = true;
          p[e.to] = G[x][i];
          cur[x] = i;
          x = e.to;
          break;
        }
      }
      if (!ok) {
        int m = n - 1;
        for (int i = 0; i < G[x].size(); ++i) {
          Edge& e = edges[G[x][i]];
          if (e.cap > e.flow) {
            m = min(m, d[e.to]);
          }
        }
        if (--num[d[x]] == 0) {
          break;
        }
        ++num[d[x] = m + 1];
        cur[x] = 0;
        if (x != s) {
          x = edges[p[x]].from;
        }
      }
    }
    return flow;
  }
  
  void ClearFlow() {
    for (int i = 0; i < m; ++i) {
      edges[i].flow = 0;
    }
  }
} isap;

int main() {
  int t, tt = 1;
  scanf("%d", &t);
  while (t--) {
    int n, m, ans = 0;
    scanf("%d", &n);
    memset(vis, -1, sizeof vis);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &p[i]);
      ans += p[i];
      while (getchar() != '\n') {
        int x;
        scanf("%d", &x);
        vis[x] = i;
      }
    }
    scanf("%d", &m);
    int k = n + m;
    for (int i = n; i < k; ++i) {
      scanf("%d", &p[i]);
      ans += p[i];
      while (getchar() != '\n') {
        int x;
        scanf("%d", &x);
        if (vis[x] != -1) {
          if (g[vis[x]][i - n] != tt) {
            isap.AddEdge(vis[x], i, inf);
            g[vis[x]][i - n] = tt;
          }
        }
      }
    }
    isap.n = k + 5;
    for (int i = 0; i < n; ++i) {
      isap.AddEdge(k, i, p[i]);
    }
    for (int i = n; i < k; ++i) {
      isap.AddEdge(i, k + 1, p[i]);
    }
    ans -= isap.Maxflow(k, k + 1);
    printf("Case %d:\n%d\n", tt++, ans);
    if (t) {
      puts("");
    }
    isap.ClearAll(k + 5);
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有\(n, (1 \leq n \leq 1000)\)个人，\(m, (1 \leq m \leq 500)\)个组，一个人可能属于多个组。现在从一些组中删除一部分人，使得每个人仅在一个组中，且包含人数最多的组的人数最少。

思路

源点向每个人连一条容量为1的边，人和组之间连容量为1的边，组与汇点之间的边的容量为最大人数。二分最大人数，判断最大流是否等于\(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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1510;

struct Edge {
  int from, to, cap, flow;
  Edge() {}
  Edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f) {}
};

struct ISAP {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool vis[maxn];
  int p[maxn];
  int d[maxn];
  int num[maxn];
  int cur[maxn];
  
  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = int(edges.size());
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }
  
  void ClearAll(int n) {
    this -> n = n;
    for (int i = 0; i < n; ++i) {
      G[i].clear();
    }
    edges.clear();
  }
  
  bool BFS() {
    memset(vis, 0, sizeof vis);
    vis[t] = true;
    d[t] = 0;
    queue<int> Q;
    Q.push(t);
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); ++i) {
        Edge& e = edges[G[x][i] ^ 1];
        if (!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = true;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
  }
  
  int Augment() {
    int x = t, a = inf;
    while (x != s) {
      Edge& e = edges[p[x]];
      a = min(a, e.cap - e.flow);
      x = e.from;
    }
    x = t;
    while (x != s) {
      edges[p[x]].flow += a;
      edges[p[x] ^ 1].flow -= a;
      x = edges[p[x]].from;
    }
    return a;
  }
  
  int Maxflow(int s, int t) {
    this -> s = s, this -> t = t;
    int flow = 0;
    BFS();
    memset(num, 0, sizeof num);
    for (int i = 0; i < n; ++i) {
      ++num[d[i]];
    }
    memset(cur, 0, sizeof cur);
    int x = s;
    while (d[s] < n) {
      if (x == t) {
        flow += Augment();
        x = s;
      }
      bool ok = false;
      for (int i = cur[x]; i < G[x].size(); ++i) {
        Edge& e = edges[G[x][i]];
        if (e.cap > e.flow && d[x] == d[e.to] + 1) {
          ok = true;
          p[e.to] = G[x][i];
          cur[x] = i;
          x = e.to;
          break;
        }
      }
      if (!ok) {
        int m = n - 1;
        for (int i = 0; i < G[x].size(); ++i) {
          Edge& e = edges[G[x][i]];
          if (e.cap > e.flow) {
            m = min(m, d[e.to]);
          }
        }
        if (--num[d[x]] == 0) {
          break;
        }
        ++num[d[x] = m + 1];
        cur[x] = 0;
        if (x != s) {
          x = edges[p[x]].from;
        }
      }
    }
    return flow;
  }
  
  void ClearFlow() {
    for (int i = 0; i < m; ++i) {
      edges[i].flow = 0;
    }
  }
} isap;

int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m) && (n || m)) {
    isap.ClearAll(n + m + 5);
    for (int i = 0; i < n; ++i) {
      scanf("%*s");
      isap.AddEdge(n + m, i, 1);
      while (getchar() != '\n') {
        int x;
        scanf("%d", &x);
        isap.AddEdge(i, n + x, 1);
      }
    }
    int L = 1, R = n, x = isap.m;
    for (int i = 0; i < m; ++i) {
      isap.AddEdge(n + i, n + m + 1, inf);
    }
    int ans = n;
    while (L <= R) {
      int M = L + (R - L) / 2;
      isap.ClearFlow();
      for (int i = x; i < isap.m; i += 2) {
        isap.edges[i].cap = M;
      }
      if (isap.Maxflow(n + m, n + m + 1) == n) {
        R = M - 1;
        ans = min(ans, M);
      } else {
        L = M + 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

发表于 分类于 ， Disqus：

链接

传送门

题意

给出\(n \times m, (1 \leq n, m \leq 1000)\)的矩阵，给出\(T,(1 \leq T \leq 100000)\)个询问，对于每个询问\(t_i\)，输出比\(t_i\)大的数字组成的四连块的个数。

思路

离线操作，用dsu维护连通块。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1010;
const int maxq = 100010;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int a[maxn][maxn];
int fa[maxn * maxn], ans[maxq];

struct node {
  int x, y, v;
  bool operator < (const node& rhs) const {
    return v > rhs.v;
  }
} nd[maxn * maxn];

struct query {
  int x, id;
  bool operator < (const query& rhs) const {
    return x > rhs.x;
  }
} q[maxq];

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m, num = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        a[i][j] = false;
        scanf("%d", &nd[num].v);
        nd[num].x = i, nd[num].y = j;
        fa[num] = num;
        ++num;
      }
    }
    sort(nd, nd + num);
    int qn;
    scanf("%d", &qn);
    for (int i = 0; i < qn; ++i) {
      q[i].id = i;
      scanf("%d", &q[i].x);
    }
    sort(q, q + qn);
    int p = 0, cnt = 0;
    for (int i = 0; i < qn; ++i) {
      while (p < num && nd[p].v > q[i].x) {
        a[nd[p].x][nd[p].y] = true;
        int u = nd[p].x * m + nd[p].y;
        for (int j = 0; j < 4; ++j) {
          int x = nd[p].x + dx[j], y = nd[p].y + dy[j];
          if (x < 0 || x >= n || y < 0 || y >= m || !a[x][y]) {
            continue;
          }
          int fu = Find(u), fv = Find(x * m + y);
          if (fu != fv) {
            fa[fu] = fv;
            ++cnt;
          }
        }
        ++p;
      }
      ans[q[i].id] = p - cnt;
    }
    for (int i = 0; i < qn; ++i) {
      printf("%d ", ans[i]);
    }
    puts("");
  }
  return 0;
}

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n , (1 \leq n \leq 1000000)\)个数字，\(m, (1 \leq m \leq 1000000)\)个查询，每次查询输出\(l_i\)到\(r_i\)中出现偶数次的数字的异或和。

思路

出现偶数次的数字的异或和等于整个区间的异或和与区间不相同的数字的异或和。整个区间的异或和可以用前缀和在\(O(1)\)的时间查询，区间不相同数字的异或和可以数状数组在\(O(logn)\)的时间查询。

代码

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

typedef long long LL;
const int maxn = 1000010;
int n, m, num;
int a[maxn], ans[maxn];
int sum[maxn], bit[maxn];
int Hash[maxn], last[maxn];

struct query {
  int l, r, id;
  bool operator < (const query& rhs) const {
    return r < rhs.r;
  }
} q[maxn];

inline int lowbit(int i) {
  return i & -i;
}

int Sum(int i) {
  int res = 0;
  while (i > 0) {
    res ^= bit[i];
    i -= lowbit(i);
  }
  return res;
}

void Update(int i, int x) {
  while (i <= n) {
    bit[i] ^= x;
    i += lowbit(i);
  }
}

int& Last(int x) {
  return last[lower_bound(Hash, Hash + num, x) - Hash];
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    Hash[i - 1] = a[i];
    sum[i] = sum[i - 1] ^ a[i];
  }
  sort(Hash, Hash + n);
  num = int(unique(Hash, Hash + n) - Hash);
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    q[i].id = i;
    scanf("%d%d", &q[i].l, &q[i].r);
  }
  sort(q, q + m);
  int p = 0;
  for (int i = 1; i <= n; ++i) {
    int& k = Last(a[i]);
    if (k != 0) {
      Update(k, a[i]);
    }
    Update(k = i, a[i]);
    while (p < m && q[p].r == i) {
      ans[q[p].id] = sum[i] ^ sum[q[p].l - 1] ^ Sum(i) ^ Sum(q[p].l - 1);
      ++p;
    }
  }
  for (int i = 0; i < m; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}