Chengrui's Blog

0%

发表于 分类于 ， ， Disqus：

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
46
47
48
49
50
/*
 ID: wcr19961
 PROG: nuggets
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int maxn = 12;
const int maxm = (1 << 16) + 10;
int a[maxn];
bool dp[maxm];

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  freopen("nuggets.in", "r", stdin);
  freopen("nuggets.out", "w", stdout);
  int n;
  scanf("%d", &n);
  dp[0] = true;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    if (a[i] == 1) {
      puts("0");
      return 0;
    }
    for (int j = a[i]; j < maxm; ++j) {
      dp[j] |= dp[j - a[i]];
    }
  }
  for (int i = 1; i < n; ++i) {
    a[i] = gcd(a[i], a[i - 1]);
  }
  if (a[n - 1] != 1) {
    puts("0");
    return 0;
  }
  int ans = maxm - 1;
  while (dp[ans]) {
    --ans;
  }
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

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
/*
 ID: wcr19961
 PROG: rockers
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int maxn = 25;
int dp[maxn][maxn];

int main() {
  freopen("rockers.in", "r", stdin);
  freopen("rockers.out", "w", stdout);
  int n, t, m;
  scanf("%d%d%d", &n, &t, &m);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    for (int j = m; j >= 1; --j) {
      for (int k = 0; k <= t; ++k) {
        if (k < x) {
          if (t >= x && j < m) {
            dp[j + 1][t - x] = max(dp[j + 1][t - x], dp[j][k] + 1);
          }
        } else {
          dp[j][k - x] = max(dp[j][k - x], dp[j][k] + 1);
        }
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < t; ++j) {
      ans = max(ans, dp[i][j]);
    }
  }
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

Pick's theorem.

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
/*
 ID: wcr19961
 PROG: fence9
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  freopen("fence9.in", "r", stdin);
  freopen("fence9.out", "w", stdout);
  int n, m, p;
  scanf("%d%d%d", &n, &m, &p);
  int S = m * p / 2, B = gcd(n, m) + p + gcd(abs(p - n), m);
  printf("%d\n", S - B / 2 + 1);
  return 0;
}

发表于 分类于 ， ， Disqus：

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
46
47
48
49
50
/*
 ID: wcr19961
 PROG: heritage
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int maxn = 30;
int L[maxn], R[maxn];
char s1[maxn], s2[maxn];

int Split(int l1, int r1, int l2, int r2) {
  if (l1 == r1) {
    return 0;
  }
  char c = s2[l2];
  int u = c - 'A' + 1, len = 0;
  for (int i = l1; i < r1; ++i) {
    if (s1[i] == c) {
      break;
    }
    ++len;
  }
  L[u] = Split(l1, l1 + len, l2 + 1, l2 + len + 1);
  R[u] = Split(l1 + len + 1, r1, l2 + len + 1, r2);
  return u;
}

void Print(int u) {
  if (u == 0) {
    return;
  }
  Print(L[u]);
  Print(R[u]);
  putchar(u + 'A' - 1);
}

int main() {
  freopen("heritage.in", "r", stdin);
  freopen("heritage.out", "w", stdout);
  scanf("%s%s", s1, s2);
  int len = int(strlen(s1));
  Print(Split(0, len, 0, len));
  puts("");
  return 0;
}

发表于 分类于 ， ， Disqus：

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
/*
 ID: wcr19961
 PROG: game1
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

typedef long long LL;
const int maxn = 110;
int a[maxn], sum[maxn];
int dp[maxn][maxn];

int Sum(int l, int r) {
  return sum[r] - sum[l - 1];
}

int main() {
  freopen("game1.in", "r", stdin);
  freopen("game1.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    sum[i] = sum[i - 1] + a[i];
  }
  for (int i = n; i >= 1; --i) {
    dp[i][i] = a[i];
    for (int j = i + 1; j <= n; ++j) {
      dp[i][j] = max(Sum(i + 1, j) - dp[i + 1][j] + a[i], Sum(i, j - 1) - dp[i][j - 1] + a[j]);
    }
  }
  printf("%d %d\n", dp[1][n], sum[n] - dp[1][n]);
  return 0;
}

发表于 分类于 ， ， Disqus：

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
46
47
48
49
50
51
52
53
54
/*
 ID: wcr19961
 PROG: range
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

typedef long long LL;
const int maxn = 255;
char s[maxn][maxn];
int sum[maxn][maxn], ans[maxn];

int Sum(int x, int y, int a, int b) {
  return sum[a][b] - sum[x - 1][b] - sum[a][y - 1] + sum[x - 1][y - 1];
}

int main() {
  freopen("range.in", "r", stdin);
  freopen("range.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s[i] + 1);
    for (int j = 1; j <= n; ++j) {
      sum[i][j] = s[i][j] == '1' ? 1 : 0;
      sum[i][j] += sum[i][j - 1];
    }
    for (int j = 1; j <= n; ++j) {
      sum[i][j] += sum[i - 1][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 2; k <= n; ++k) {
        if (i + k <= n + 1 && j + k <= n + 1) {
          if (Sum(i, j, i + k - 1, j + k - 1) == k * k) {
            ++ans[k];
          }
        }
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    if (ans[i] > 0) {
      printf("%d %d\n", i, ans[i]);
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

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
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
/*
 ID: wcr19961
 PROG: camelot
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

typedef long long LL;
const int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const int inf = 0x3f3f3f3f;
const int maxr = 27;
const int maxc = 31;
char s[10];
int d[maxr][maxc][maxr][maxc];
int cnt, kx[maxr * maxc], ky[maxr * maxc];
struct node {
  int x, y;
  node() {}
  node(int x, int y) : x(x), y(y) {}
};
queue<node> q;

int Dis(int x, int y) {
  return max(abs(x), abs(y));
}

int Sum(int x, int y) {
  int sum = 0;
  for (int i = 1; i < cnt; ++i) {
    sum += d[kx[i]][ky[i]][x][y];
    if (sum > inf) {
      sum = inf;
    }
  }
  return sum;
}

int main() {
  freopen("camelot.in", "r", stdin);
  freopen("camelot.out", "w", stdout);
  int r, c;
  scanf("%d%d%s%d", &c, &r, s, &ky[0]);
  kx[cnt++] = s[0] - 'A', --ky[0];
  while (~scanf("%s%d", s, &ky[cnt])) {
    kx[cnt] = s[0] - 'A', --ky[cnt];
    ++cnt;
  }
  memset(d, 0x3f, sizeof d);
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      while (!q.empty()) {
        q.pop();
      }
      d[i][j][i][j] = 0;
      q.push(node(i, j));
      while (!q.empty()) {
        node k = q.front();
        q.pop();
        for (int l = 0; l < 8; ++l) {
          int a = k.x + dx[l], b = k.y + dy[l];
          if (a >= 0 && a < r && b >= 0 && b < c && d[i][j][a][b] == inf) {
            d[i][j][a][b] = d[i][j][k.x][k.y] + 1;
            q.push(node(a, b));
          }
        }
      }
    }
  }
  int ans = inf;
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      int len = Sum(i, j);
      if (len < ans) {
        int tmp = len + Dis(kx[0] - i, ky[0] - j);
        for (int k = 1; k < cnt; ++k) {
          for (int l = -2; l <= 2; ++l) {
            for (int m = -2; m <= 2; ++m) {
              int px = kx[0] + l, py = ky[0] + m;
              if (px >= 0 && px < r && py >= 0 && py < c) {
                tmp = min(tmp, len - d[kx[k]][ky[k]][i][j] + Dis(l, m) + d[kx[k]][ky[k]][px][py] + d[px][py][i][j]);
              }
            }
          }
        }
        ans = min(ans, tmp);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
 ID: wcr19961
 PROG: shopping
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 7;
const int maxs = 110;
const int maxm = 1010;
int id[maxm], cnt, aim[maxn];
int dp[maxn][maxn][maxn][maxn][maxn];
int p[maxs], num[maxs], a[maxs][maxn];

int ID(int x) {
  return id[x] == 0 ? id[x] = ++cnt : id[x];
}

int main() {
  freopen("shopping.in", "r", stdin);
  freopen("shopping.out", "w", stdout);
  int s, x;
  scanf("%d", &s);
  for (int i = 1; i <= s; ++i) {
    scanf("%d", &num[i]);
    for (int j = 0; j < num[i]; ++j) {
      scanf("%d", &x);
      scanf("%d", &a[i][ID(x)]);
    }
    scanf("%d", &p[i]);
  }
  int b;
  scanf("%d", &b);
  for (int i = 1; i <= b; ++i) {
    scanf("%d", &x);
    a[s + i][ID(x)] = 1;
    scanf("%d%d", &aim[ID(x)], &p[s + i]);
  }
  memset(dp, 0x3f, sizeof dp);
  dp[0][0][0][0][0] = 0;
  for (int i = 1; i <= s + b; ++i) {
    for (int j = a[i][1]; j <= 5; ++j) {
      for (int k = a[i][2]; k <= 5; ++k) {
        for (int l = a[i][3]; l <= 5; ++l) {
          for (int m = a[i][4]; m <= 5; ++m) {
            for (int n = a[i][5]; n <= 5; ++n) {
              dp[j][k][l][m][n] = min(dp[j][k][l][m][n], dp[j - a[i][1]][k - a[i][2]][l - a[i][3]][m - a[i][4]][n - a[i][5]] + p[i]);
            }
          }
        }
      }
    }
  }
  printf("%d\n", dp[aim[1]][aim[2]][aim[3]][aim[4]][aim[5]]);
  return 0;
}

发表于 分类于 ， ， Disqus：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
 ID: wcr19961
 PROG: fence
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 510;
int d[maxn];
int g[maxn][maxn];
int odd[5], cnt;
stack<int> s;

void dfs(int u) {
  for (int i = 1; i < maxn; ++i) {
    if (g[u][i] > 0) {
      --g[u][i], --g[i][u];
      dfs(i);
      s.push(i);
    }
  }

}

int main() {
  freopen("fence.in", "r", stdin);
  freopen("fence.out", "w", stdout);
  int F;
  scanf("%d", &F);
  while (F--) {
    int u, v;
    scanf("%d%d", &u, &v);
    ++d[u], ++d[v];
    ++g[u][v], ++g[v][u];
  }
  int st = -1;
  bool first = true;
  for (int i = 1; i < maxn; ++i) {
    if (d[i] & 1) {
      odd[++cnt] = i;
    }
    if (d[i] > 0 && first) {
      st = i;
      first = false;
    }
  }
  if (cnt == 2) {
    st = odd[1];
  }
  dfs(st);
  s.push(st);
  while (!s.empty()) {
    printf("%d\n", s.top());
    s.pop();
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

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
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
/*
 ID: wcr19961
 PROG: butter
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 810;
int a[maxn];

struct Edge {
  int from, to, dist;
  Edge(int u, int v, int d): from(u), to(v), dist(d) {}
};

struct Dijkstra {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool done[maxn];
  int d[maxn];
  int p[maxn];

  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; ++i) {
      G[i].clear();
    }
    edges.clear();
  }

  void AddEdge(int from, int to, int dist) {
    edges.push_back(Edge(from, to, dist));
    m = int(edges.size());
    G[from].push_back(m - 1);
  }

  struct HeapNode {
    int d, u;
    HeapNode(int d, int u): d(d), u(u) {}
    bool operator < (const HeapNode& rhs) const {
      return d > rhs.d;
    }
  };

  void dijkstra(int s) {
    priority_queue<HeapNode> Q;
    for (int i = 0; i < n; ++i) {
      d[i] = inf;
    }
    d[s] = 0;
    memset(done, 0, sizeof done);
    Q.push(HeapNode(0, s));
    while (!Q.empty()) {
      HeapNode x = Q.top();
      Q.pop();
      int u = x.u;
      if (done[u]) {
        continue;
      }
      done[u] = true;
      for (int i = 0; i < G[u].size(); ++i) {
        Edge& e = edges[G[u][i]];
        if (d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          Q.push(HeapNode(d[e.to], e.to));
        }
      }
    }
  }
} dij;

int main() {
  freopen("butter.in", "r", stdin);
  freopen("butter.out", "w", stdout);
  int N, P, C;
  scanf("%d%d%d", &N, &P, &C);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &a[i]);
  }
  dij.init(P + 1);
  for (int i = 0; i < C; ++i) {
    int u, v, len;
    scanf("%d%d%d", &u, &v, &len);
    dij.AddEdge(u, v, len);
    dij.AddEdge(v, u, len);
  }
  int ans = inf;
  for (int i = 1; i <= P; ++i) {
    dij.dijkstra(i);
    int res = 0;
    for (int j = 0; j < N; ++j) {
      res += dij.d[a[j]];
      if (res > inf) {
        res = inf;
      }
    }
    if (res < ans) {
      ans = res;
    }
  }
  printf("%d\n", ans);
  return 0;
}