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
75
76
/*
 ID: wcr19961
 PROG: sprime
 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;
const int tmp[] = {1, 3, 7, 9};
int p[1250], pnum;
bool np[maxn];
vector<int> bit[10];

void Euler_Prime() {
  np[1] = true;
  for (int i = 2; i < maxn; ++i) {
    if (!np[i]) {
      p[pnum++] = i;
    }
    for (int j = 0; j < pnum; ++j) {
      if (i * p[j] >= maxn) {
        break;
      }
      np[i * p[j]] = true;
      if (i % p[j] == 0) {
        break;
      }
    }
  }
}

bool isprime(int n) {
  if (n < maxn) {
    return !np[n];
  }
  for (int i = 0; i < pnum; ++i) {
    if (n % p[i] == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  freopen("sprime.in", "r", stdin);
  freopen("sprime.out", "w", stdout);
  Euler_Prime();
  bit[1].push_back(2);
  bit[1].push_back(3);
  bit[1].push_back(5);
  bit[1].push_back(7);
  int n;
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j < bit[i - 1].size(); ++j) {
      int x = bit[i - 1][j] * 10;
      for (int k = 0; k < 4; ++k) {
        if (isprime(x + tmp[k])) {
          bit[i].push_back(x + tmp[k]);
        }
      }
    }
  }
  sort(bit[n].begin(), bit[n].end());
  for (int i = 0; i < bit[n].size(); ++i) {
    printf("%d\n", bit[n][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
/*
 ID: wcr19961
 PROG: pprime
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <queue>
using namespace std;

typedef long long LL;
const int maxn = 10000010;
const int maxm = 664579;

int p[maxm], pnum;
unsigned int np[(maxn >> 5) + 1];

void Euler_Prime() {
  for (LL i = 2; i < maxn; ++i) {
    if (!(np[i >> 5] & (1 << (i % 32)))) {
      p[pnum++] = i;
    }
    for (int j = 0; j < pnum; ++j) {
      if (i * p[j] >= maxn) {
        break;
      }
      np[(i * p[j]) >> 5] |= 1 << (i * p[j] % 32) ;
      if (i % p[j] == 0) {
        break;
      }
    }
  }
}

int main() {
  freopen("pprime.in", "r", stdin);
  freopen("pprime.out", "w", stdout);
  Euler_Prime();
  int a, b, len, tmp[10], x;
  scanf("%d%d", &a, &b);
  int l = int(lower_bound(p, p + maxm, a) - p), r = int(upper_bound(p, p + maxm, b) - p);
  for (int i = l; i < r; ++i) {
    x = p[i], len = 0;
    while (x) {
      tmp[len] = x % 10;
      x /= 10;
      ++len;
    }
    if ((len & 1) || p[i] == 11) {
      bool ok = true;
      for (int j = len >> 1; j < len; ++j) {
        if (tmp[j] != tmp[len - j - 1]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        printf("%d\n", p[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
/*
 ID: wcr19961
 PROG: numtri
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <queue>
using namespace std;

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

int main() {
  freopen("numtri.in", "r", stdin);
  freopen("numtri.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      int x;
      scanf("%d", &x);      
      dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + x;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, dp[n][i]);
  }
  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
/*
 ID: wcr19961
 PROG: milk3
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <queue>
using namespace std;

const int maxn = 25;
const int F[] = {0, 0, 1, 1, 2, 2};
const int T[] = {1, 2, 0, 2, 0, 1};
int a[3];
bool vis[maxn][maxn][maxn];
struct Node {
  int a[3];
  Node(int x, int y, int z) {
    a[0] = x, a[1] = y, a[2] = z;
  }
};
queue<Node> q;

void pour(int f, int t, Node k) {
  if (k.a[f] > 0 && k.a[t] < a[t]) {
    int dt = min(k.a[f], a[t] - k.a[t]);
    k.a[f] -= dt, k.a[t] += dt;
    if (!vis[k.a[0]][k.a[1]][k.a[2]]) {
      q.push(k);
      vis[k.a[0]][k.a[1]][k.a[2]] = true;
    }
  }
}

int main() {
  freopen("milk3.in", "r", stdin);
  freopen("milk3.out", "w", stdout);
  scanf("%d%d%d", &a[0], &a[1], &a[2]);
  q.push(Node(0, 0, a[2]));
  vis[0][0][a[2]] = true;
  while (!q.empty()) {
    Node k = q.front();
    q.pop();
    for (int i = 0; i < 6; ++i) {
      pour(F[i], T[i], k);
    }
  }
  bool flag = true;
  for (int i = 0; i <= a[2]; ++i) {
    if (vis[0][a[2] - i][i]) {
      if (flag) {
        flag = false;
      } else {
        putchar(' ');
      }
      printf("%d", i);
    }
  }
  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
50
51
52
53
54
55
56
/*
 ID: wcr19961
 PROG: ariprog
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 126010;
bool vis[maxn];

int main() {
  freopen("ariprog.in", "r", stdin);
  freopen("ariprog.out", "w", stdout);
  int n, m, num = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i <= m; ++i) {
    int k = i * i;
    for (int j = 0; j <= i; ++j) {
      vis[k + j * j] = true;
    }
  }
  num = m * m * 2;
  bool flag = true;
  for (int i = 1; i <= num; ++i) {
    for (int j = 0; j <= num; ++j) {
      if (i * (n - 1) + j > num) {
        break;
      }
      bool ok = true;
      int st = j, tmp = n;
      while (tmp--) {
        if (!vis[st]) {
          ok = false;
          break;
        }
        st += i;
      }
      if (ok) {
        printf("%d %d\n", j, i);
        flag = false;
      }
    }
  }
  if (flag) {
    puts("NONE");
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

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

typedef long long LL;
const int maxn = 55;
int d[maxn], g[maxn][maxn];
bool vis[maxn];

int dfs1(int u) {
  vis[u] = true;
  int res = 1;
  for (int i = 0; i < maxn; ++i) {
    if (!vis[i] && g[u][i]) {
      res += dfs1(i);
    }
  }
  return res;
}

void dfs2(int u) {
  for (int i = 0; i < maxn; ++i) {
    if (g[u][i] > 0) {
      --g[u][i], --g[i][u];
      dfs2(i);
      printf("%d %d\n", i, u);
    }
  }
}

int main() {
  int t, tt = 0;
  scanf("%d", &t);
  while (t--) {
    if (tt) {
      puts("");
    }
    memset(d, 0, sizeof d);
    memset(g, 0, sizeof g);
    memset(vis, 0, sizeof vis);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      g[u][v]++, g[v][u]++;
      ++d[u], ++d[v];
    }
    bool ok = true;
    int num = 0, root = -1;
    for (int i = 1; i < maxn; ++i) {
      if (d[i]) {
        root = i;
        ++num;
        if (d[i] & 1) {
          ok = false;
          break;
        }
      }
    }
    if (ok && dfs1(root) != num) {
      ok = false;
    }
    printf("Case #%d\n", ++tt);
    if (!ok) {
      puts("some beads may be lost");
    } else {
      dfs2(root);
    }
  }
  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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 1010;
int tmp[maxn];
struct Node {
  int r, c, v;
  bool operator < (const Node& rhs) const {
    return r < rhs.r || (r == rhs.r && c < rhs.c);
  }
} a[maxn];

int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    memset(a, 0, sizeof a);
    int tot = 0;
    for (int i = 0; i < n; ++i) {
      int x;
      scanf("%d", &x);
      for (int j = 0; j < x; ++j) {
        scanf("%d", &tmp[j]);
      }
      for (int j = 0; j < x; ++j) {
        scanf("%d", &a[tot].v);
        a[tot].c = i + 1, a[tot].r = tmp[j];
        ++tot;
      }
    }
    sort(a, a + tot);
    printf("%d %d\n", m, n);
    int p1 = 0, p2 = 0;
    for (int i = 1; i <= m; ++i) {
      while (a[p2].r == i) {
        ++p2;
      }
      printf("%d", p2 - p1);
      for (int j = p1; j < p2; ++j) {
        printf(" %d", a[j].c);
      }
      puts("");
      for (int j = p1; j < p2; ++j) {
        if (j != p1) {
          putchar(' ');
        }
        printf("%d", a[j].v);
      }
      puts("");
      p1 = p2;
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有\(n\)个椰子，一群人和一只猴子，这些人要平分椰子，第一个人在第一天晚上把椰子平分后剩1个给了猴子，然后拿走了自己的一份，其他的人也都这样做了。最后椰子正好平分，没有猴子的。输出满足要求的最大人数。

思路

从枚举\(sqrt(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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 55;
int a[maxn];

bool check(int n, int p) {
  for (int i = 0; i < p; ++i) {
    if (n % p == 1) {
      n = n / p * (p - 1);
    } else {
      return false;
    }
  }
  return n % p == 0;
}

int main() {
  int n;
  while (~scanf("%d", &n) && n >= 0) {
    printf("%d coconuts, ", n);
    bool ok = false;
    for (int i = sqrt(n) + 1; i > 1; --i) {
      if ((n - 1) % i == 0 && check(n, i)) {
        printf("%d people and 1 monkey\n", i);
        ok = true;
        break;
      }
    }
    if (!ok) {
      puts("no solution");
    }
  }
  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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

typedef long long LL;
const int maxn = 55;
int a[maxn];

int main() {
  int n, t = 0;
  while (~scanf("%d", &n) && n) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
      sum += a[i];
    }
    sum /= n;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += abs(a[i] - sum);
    }
    printf("Set #%d\nThe minimum number of moves is %d.\n\n", ++t, ans >> 1);
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一条河的宽度\(d\)，水流速度\(v\)，船速\(u\)，输出最快渡河和垂直渡河的时间差。

思路

垂直渡河时间为\(d / u\)，垂直渡河时船速的水平分量等于水流速度。

代码

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

typedef long long LL;
const int maxn = 55;
int a[maxn];

int main() {
  int t, tt = 0;
  scanf("%d", &t);
  while (t--) {
    double d, v, u;
    scanf("%lf%lf%lf", &d, &v, &u);
    printf("Case %d: ", ++tt);
    if (u > v && v) {
      printf("%.3f\n", d / sqrt(u * u - v * v) -  d / u);
    } else {
      puts("can't determine");
    }
  }
  return 0;
}