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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
 ID: wcr19961
 PROG: fracdec
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

set<int> s;
int main() {
  freopen("fracdec.in", "r", stdin);
  freopen("fracdec.out", "w", stdout);
  int n, d;
  scanf("%d%d", &n, &d);
  int x = n / d;
  printf("%d.", x);
  n %= d;
  if (n == 0) {
    puts("0");
    return 0;
  }
  int tmp = n, len = (x == 0 ? 0 : floor(log10(x))) + 2;
  bool ok = false;
  while (n) {
    if (s.count(n)) {
      ok = true;
      break;
    }
    s.insert(n);
    n *= 10;
    n -= n / d * d;
  }
  swap(tmp, n);
  if (tmp == 0) {
    while (n) {
      n *= 10;
      printf("%d", n / d);
      if (++len % 76 == 0) {
        puts("");
      }
      n -= n / d * d;
    }
  } else {
    int cnt = 0;
    for (;;) {
      if (n == tmp) {
        if (cnt == 0) {
          putchar('(');
        } else {
          putchar(')');
          break;
        }
        if (++len % 76 == 0) {
          puts("");
        }
        ++cnt;
      }
      n *= 10;
      printf("%d", n / d);
      if (++len % 76 == 0) {
        puts("");
      }
      n -= n / d * d;
    }
  }
  if (len % 76) {
    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
40
41
42
43
44
45
46
47
48
49
/*
 ID: wcr19961
 PROG: comehome
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 160;
char s1[maxn], s2[maxn];
int d[maxn][maxn];

inline int C(char c) {
  return c < 'a' ? c - 'A' + 26 : c - 'a';
}

int main() {
  freopen("comehome.in", "r", stdin);
  freopen("comehome.out", "w", stdout);
  memset(d, 0x3f, sizeof d);
  int p;
  scanf("%d", &p);
  for (int i = 0; i < p; ++i) {
    int len;
    scanf("%s%s%d", s1, s2, &len);
    int u = C(s1[0]), v = C(s2[0]);
    d[u][v] = d[v][u] = min(d[u][v], len);
  }
  for (int k = 0; k < 52; ++k) {
    for (int i = 0; i < 52; ++i) {
      for (int j = 0; j < 52; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  int Min = 0x3f3f3f3f, ans = 0;
  for (int i = 26; i < 51; ++i) {
    if (d[i][51] < Min) {
      Min = d[i][51], ans = i;
    }
  }
  printf("%c %d\n", ans + 'A' - 26, Min);
  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
/*
 ID: wcr19961
 PROG: cowtour
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 160;
int x[maxn], y[maxn], p[maxn];
char s[maxn];
double len[maxn], len2[maxn];
double d[maxn][maxn];

double dis(int i, int j) {
  return sqrt(double(x[i] - x[j]) * (x[i] - x[j]) + double(y[i] - y[j]) * (y[i] - y[j]));
}

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

int main() {
  freopen("cowtour.in", "r", stdin);
  freopen("cowtour.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
    scanf("%d%d", &x[i], &y[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + 1);
    for (int j = 1; j < i; ++j) {
      if (s[j] == '1') {
        p[find(i)] = p[find(j)];
        d[i][j] = d[j][i] = dis(i, j);
      } else {
        d[i][j] = d[j][i] = 1e9;
      }
    }
  }
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    find(i);
    for (int j = 1; j < i; ++j) {
      if (p[i] == p[j]) {
        len[i] = max(len[i], d[i][j]);
        len[j] = max(len[j], d[i][j]);
      }
    }
    len2[p[i]] = max(len2[p[i]], len[i]);
  }
  double ans = 1e9;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
      if (p[i] != p[j]) {
        ans = min(ans, len[i] + len[j] + dis(i, j));
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, len2[i]);
  }
  printf("%.6f\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
63
64
65
66
67
68
69
70
71
72
73
/*
 ID: wcr19961
 PROG: maze1
 LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

typedef long long LL;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxh = 210;
const int maxw = 110;
char g[maxh][maxw];
int len[maxh][maxw];

struct node {
  int x, y;
  node(int x = 0, int y = 0) : x(x), y(y) {}
};

int main() {
  freopen("maze1.in", "r", stdin);
  freopen("maze1.out", "w", stdout);
  int w, h;
  scanf("%d%d%*c", &w, &h);
  for (int i = 0; i <= (h << 1); ++i) {
    fgets(g[i], maxw, stdin);
  }
  queue<node> q;
  for (int i = (w << 1) - 1; i > 0; i -= 2) {
    if (g[0][i] == ' ') {
      q.push(node(1, i));
      len[1][i] = 1;
    }
    if (g[h << 1][i] == ' ') {
      q.push(node((h << 1) - 1, i));
      len[(h << 1) - 1][i] = 1;
    }
  }
  for (int i = (h << 1) - 1; i > 0; i -= 2) {
    if (g[i][0] == ' ') {
      q.push(node(i, 1));
      len[i][1] = 1;
    }
    if (g[i][w << 1] == ' ') {
      q.push(node(i, (w << 1) - 1));
      len[i][(w << 1) - 1] = 1;
    }
  }
  int ans = 1;
  while (!q.empty()) {
    node k = q.front();
    q.pop();
    for (int i = 0; i < 4; ++i) {
      int x = k.x + dx[i], y = k.y + dy[i];
      if (g[x][y] == ' ') {
        x += dx[i], y += dy[i];
        if (x > 0 && x < (h << 1) && y > 0 && y < (w << 1) && len[x][y] == 0) {
          len[x][y] = len[k.x][k.y] + 1;
          ans = max(ans, len[x][y]);
          q.push(node(x, y));
        }
      }
    }
  }
  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
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
/*
 ID: wcr19961
 PROG: ttwo
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

typedef long long LL;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxn = 12;
char g[maxn][maxn];
int len[maxn][maxn][4][maxn][maxn][4];
bool vis[maxn][maxn][4][maxn][maxn][4];

struct node {
  int ax, ay, ad;
  int bx, by, bd;
  
  void Go(int a, int b, int& a0, int& b0, int& c) {
    if (a >= 0 && a < 10 && b >= 0 && b < 10 && g[a][b] != '*') {
      a0 = a, b0 = b;
    } else {
      c = (c + 1) % 4;
    }
  }

  void Go() {
    Go(ax + dx[ad], ay + dy[ad], ax, ay, ad);
    Go(bx + dx[bd], by + dy[bd], bx, by, bd);
  }

  bool& Vis() {
    return vis[ax][ay][ad][bx][by][bd];
  }
  
  int& Len() {
    return len[ax][ay][ad][bx][by][bd];
  }

  bool Ok() {
    return ax == bx && ay == by;
  }
};

int main() {
  freopen("ttwo.in", "r", stdin);
  freopen("ttwo.out", "w", stdout);
  node s;
  for (int i = 0; i < 10; ++i) {
    scanf("%s", g[i]);
    for (int j = 0; j < 10; ++j) {
      if (g[i][j] == 'C') {
        s.ax = i, s.ay = j, s.ad = 0;
      }
      if (g[i][j] == 'F') {
        s.bx = i, s.by = j, s.bd = 0;
      }
    }
  }
  s.Vis() = true;
  queue<node> q;
  q.push(s);
  bool flag = false;
  while (!q.empty()) {
    node k = q.front();
    q.pop();
    int Len = k.Len();
    if (k.Ok()) {
      printf("%d\n", k.Len());
      flag = true;
      break;
    }
    k.Go();
    if (!k.Vis()) {
      k.Vis() = true;
      k.Len() = Len + 1;
      q.push(k);
    }
  }
  if (!flag) {
    puts("0");
  }
  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
/*
 ID: wcr19961
 PROG: concom
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
using namespace std;

typedef long long LL;
const int maxn = 110;
int d[maxn][maxn], c[maxn];
bool vis[maxn];

void dfs(int u) {
  vis[u] = true;
  for (int i = 1; i < maxn; ++i) {
    c[i] += d[u][i];
    if (c[i] > 50 && !vis[i]) {
      dfs(i);
    }
  }
}

int main() {
  freopen("concom.in", "r", stdin);
  freopen("concom.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int u, v, x;
    scanf("%d%d%d", &u, &v, &x);
    d[u][v] = x;
  }
  for (int i = 1; i < maxn; ++i) {
    memset(c, 0, sizeof c);
    memset(vis, 0, sizeof vis);
    dfs(i);
    for (int j = 1; j < maxn; ++j) {
      if (i != j && c[j] > 50) {
        printf("%d %d\n", i, j);
      }
    }
  }
  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
/*
 ID: wcr19961
 PROG: money
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 10010;
LL dp[maxn];

int main() {
  freopen("money.in", "r", stdin);
  freopen("money.out", "w", stdout);
  int v, n;
  scanf("%d%d", &v, &n);
  dp[0] = 1;
  while (v--) {
    int x;
    scanf("%d", &x);
    for (int i = x; i <= n; ++i) {
      dp[i] += dp[i - x];
    }
  }
  printf("%lld\n", dp[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
55
56
57
58
59
60
61
/*
 ID: wcr19961
 PROG: zerosum
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 10;
const char s[] = " +-";
int a[maxn];

void dfs(int d, int n) {
  if (d == n) {
    int sum = 0, pre = 1;
    for (int i = 1; i < n; ++i) {
      if (a[i] == 1) {
        sum += pre;
        pre = i + 1;
      } else if (a[i] == 2) {
        sum += pre;
        pre = -i - 1;
      } else {
        pre *= 10;
        if (pre > 0) {
          pre += i + 1;
        } else {
          pre -= i + 1;
        }
      }
    }
    sum += pre;
    if (sum == 0) {
      putchar('1');
      for (int i = 1; i < n; ++i) {
        printf("%c%d", s[a[i]], i + 1);
      }
      puts("");
    }
    return;
  }
  for (int i = 0; i < 3; ++i) {
    a[d] = i;
    dfs(d + 1, n);
  }
}

int main() {
  freopen("zerosum.in", "r", stdin);
  freopen("zerosum.out", "w", stdout);
  int n;
  scanf("%d", &n);
  dfs(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
/*
 ID: wcr19961
 PROG: nocows
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 210;
const int maxk = 110;
const int mod = 9901;
int dp[maxn][maxk];

int main() {
  freopen("nocows.in", "r", stdin);
  freopen("nocows.out", "w", stdout);
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k; ++i) {
    dp[1][i] = 1;
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      for (int l = 1; l <= i - 2; ++l) {
        dp[i][j] = (dp[i][j] + dp[l][j - 1] * dp[i - l - 1][j - 1]) % mod;
      }
    }
  }
  printf("%d\n", ((dp[n][k] - dp[n][k - 1]) % mod + mod) % mod);
  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
/*
 ID: wcr19961
 PROG: prefix
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 200010;
const int maxm = 210;
string s;
string e[maxm];
char tmp[maxn];
bool dp[maxn];

int main() {
  freopen("prefix.in", "r", stdin);
  freopen("prefix.out", "w", stdout);
  int n = 0, ans = 0;
  while (~scanf("%s", tmp) && tmp[0] != '.') {
    e[n++] = tmp;
  }
  sort(e, e + n);
  while (~scanf("%s", tmp)) {
    s += tmp;
  }
  dp[0] = true;
  for (int i = 0; i < s.length(); ++i) {
    if (dp[i]) {
      for (int j = 1; j <= 10 && i + j <= s.length(); ++j) {
        if (!dp[i + j] && binary_search(e, e + n, s.substr(i, j))) {
          dp[i + j] = true;
          ans = max(ans, i + j);
        }
      } 
    }
  }
  printf("%d\n", ans);
  return 0;
}