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

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

int main() {
  freopen("milk2.in", "r", stdin);
  freopen("milk2.out", "w", stdout);
  int n, l, r, L = maxn, R = 0;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &l, &r);
    L = min(L, l), R = max(R, r);
    ++a[l], --a[r];
  }
  int ans1 = 0, ans2 = 0, pre1 = maxn, pre2 = maxn, tmp = 0;
  for (int i = L; i <= R; ++i) {
    if (tmp > 0 && tmp + a[i] <= 0) {
      pre2 = i;
      ans1 = max(ans1, i - pre1);
    }
    if (tmp <= 0 && tmp + a[i] > 0) {
      pre1 = i;
      ans2 = max(ans2, i - pre2);
    }
    tmp += a[i];
  }
  printf("%d %d\n", ans1, ans2);
  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
/*
ID: wcr19961
PROG: beads
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

typedef long long LL;
const int maxn = 710;
char s[maxn];
int lr[maxn], lb[maxn], rr[maxn], rb[maxn];

int main() {
  freopen("beads.in", "r", stdin);
  freopen("beads.out", "w", stdout);
  int n;
  scanf("%d%s", &n, s + 1);
  for (int i = 1; i <= n; ++i) {
    s[n + i] = s[i];
  }
  int n2 = n << 1;
  for (int i = 1; i <= n2; ++i) {
    lb[i] = s[i] == 'r' ? 0 : lb[i - 1] + 1;
    lr[i] = s[i] == 'b' ? 0 : lr[i - 1] + 1;
  }
  for (int i = n2; i > 0; --i) {
    rb[i] = s[i] == 'r' ? 0 : rb[i + 1] + 1;
    rr[i] = s[i] == 'b' ? 0 : rr[i + 1] + 1;
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, max(lb[i - 1], lr[i - 1]) + max(rb[i], rr[i]));
  }
  printf("%d\n", min(ans, 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
/*
ID: wcr19961
PROG: friday
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

typedef long long LL;
const int maxn = 10;
const int md[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int ans[10];

inline bool isLeap(int y) {
  return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}

inline void NexT(int& c) {
  ++c;
  if (c == 8) {
    c = 1;
  }
}

int main() {
  freopen("friday.in", "r", stdin);
  freopen("friday.out", "w", stdout);
  int n, cur = 1;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int y = 1900 + i;
    for (int j = 1; j <= 12; ++j) {
      for (int k = 1; k <= md[j]; ++k) {
        if (k == 13) {
          ++ans[cur];
        }
        NexT(cur);
      }
      if (j == 2 && isLeap(y)) {
        NexT(cur);
      }
    }
  }
  for (int i = 1; i <= 7; ++i) {
    printf("%d%c", ans[(i + 4) % 7 + 1], i == 7 ? '\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
/*
ID: wcr19961
PROG: gift1
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

typedef long long LL;
const int maxn = 15;
char s[maxn][maxn];
int sum[maxn];
map<string, int> dict;

int main() {
  freopen("gift1.in", "r", stdin);
  freopen("gift1.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%s", s[i]);
    dict[s[i]] = i;
  }
  for (int i = 0; i < n; ++i) {
    int x, y;
    char s1[maxn], s2[maxn];
    scanf("%s%d%d", s1, &x, &y);
    for (int j = 0; j < y; ++j) {
      scanf("%s", s2);
      sum[dict[s2]] += x / y;
      sum[dict[s1]] -= x / y;
    }
  }
  for (int i = 0; i < n; ++i) {
    printf("%s %d\n", s[i], sum[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
/*
ID: wcr19961
PROG: ride
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int maxn = 7;
const int mod = 47;
char a[maxn], b[maxn];

int main() {
  freopen("ride.in", "r", stdin);
  freopen("ride.out", "w", stdout);
  scanf("%s%s", a, b);
  int len1 = int(strlen(a)), len2 = int(strlen(b));
  int cnt1 = 1, cnt2 = 1;
  for (int i = 0; i < len1; ++i) {
    cnt1 *= a[i] - 'A' + 1;
  }
  for (int i = 0; i < len2; ++i) {
    cnt2 *= b[i] - 'A' + 1;
  }
  puts(cnt1 % mod == cnt2 % mod ? "GO" : "STAY");
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有\(n\)个城市，要从第1个出发，经过\(k\)天到第\(n\)个。给出每天城市间旅行的花费，输出最小的话费值。

思路

定义\(dp[d][i]\)为第\(d\)天到城市\(i\)的最小花费。如果第\(d + 1\)天在城市\(i\)与城市\(j\)之间有航线，则可以转移至\(dp[d + 1][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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 12;
const int maxd = 35;
const int maxk = 1010;
int c[maxn][maxn][maxd], num[maxn][maxn];
int dp[maxk][maxn];

int main() {
  freopen("/Users/wangchengrui/Desktop/in.txt", "r", stdin);
  //freopen("/Users/wangchengrui/Desktop/out.txt", "w", stdout);
  int n, k, t = 0;
  while (~scanf("%d%d", &n, &k) && (n || k)) {
		for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (i != j) {
          scanf("%d", &num[i][j]);
          for (int d = 0; d < num[i][j]; ++d) {
            scanf("%d", &c[i][j][d]);
          }
        }
      }
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][1] = 0;
    for (int d = 1; d <= k; ++d) {
      for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
          if (i != j) {
            int x = (d - 1) % num[i][j];
            if (c[i][j][x] != 0) {
              dp[d][j] = min(dp[d][j], dp[d - 1][i] + c[i][j][x]);
            }
          }
        }
      }
    }
    printf("Scenario #%d\n", ++t);
    if (dp[k][n] != inf) {
      printf("The best flight costs %d.\n\n", dp[k][n]);
    } else {
      puts("No flight possible.\n");
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(n\)个主题，给出每节课的长度\(L\)和不满意度参数\(C\)，要安排课程。要求单个主题不能拆分在两节课上，主题间的顺序不能打乱。另外每堂课根据剩余时间\(x\)有不同不满意度：

  • 当\(x = 0\)时，不满意度为0；
  • 当\(1 \leq x \leq 10\)时，不满意度为\(-C\)；
  • 当\(x \geq 11\)时，不满意度为\((x - 10) ^ 2\)。

输出最少安排课程的节数，和最小的不满意度。

思路

定义状态\(d[i][j]\)为上\(i\)节课，讲到第\(j\)个主题时最小的不满意度。对于\(d[i][j]\)如果第\(k\)个主题连续讲到第\(j\)个主题可以在一节课之内完成，则可以从\(dp[i - 1][k]\)转移。

代码

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

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int a[maxn], L, C;
int dp[maxn][maxn];

inline int cal(int x) {
  return x == 0 ? 0 : x > 10 ? (x - 10) * (x - 10) : C;
}

int main() {
  int n, t = 0;
  while (~scanf("%d", &n) && n) {
    if (t) {
      puts("");
    }
    scanf("%d%d", &L, &C);
    C = -C;
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      a[i] += a[i - 1];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        for (int k = j - 1; k >= i - 1; --k) {
          int x = L - a[j] + a[k];
          if (x >= 0) {
            if (dp[i - 1][k] != inf) {
              dp[i][j] = min(dp[i][j], dp[i - 1][k] + cal(x));
            }
          } else {
            break;
          }
        }

      }
      if (dp[i][n] != inf) {
        ans = i;
        break;
      }
    }
    printf("Case %d:\n", ++t);
    printf("Minimum number of lectures: %d\n", ans);
    printf("Total dissatisfaction index: %d\n", dp[ans][n]);
  }
  return 0;
}

发表于 分类于 ， Disqus：

链接

传送门

题意

给出一串不同颜色方块，每次可以消去一段连续的颜色相同的方块，获得的分数为消去部分长度的平方，输出最大可能得分。

思路

定义状态\(d[i][j][k]\)为消去原序列中\(i\)到\(j\)的序列右边接上长度为\(k\)的与\(j\)相同颜色的方块后的最大得分。

  • 直接消去与\(j\)相连的同色方块，转移至\(dp[i][p][0] + (j - p + k) ^ 2\)；
  • 在\(j\)前找到与\(j\)颜色相同的方块\(q\)，消去\(j\)到\(q\)中间的部分，转移至\(dp[q + 1][p][0] + dp[i][q][j - p + k]\)。

代码

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

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 250;
int a[maxn], dp[maxn][maxn][maxn];

int DP(int i, int j, int k) {
  int& x = dp[i][j][k];
  if (x != -1) {
    return x;
  }
  if (i > j) {
    return x = 0;
  }
  int p = j;
  while (p >= i && a[p] == a[j]) {
    --p;
  }
  x = DP(i, p, 0) + (j - p + k) * (j - p + k);
  for (int q = p - 1; q >= i; --q) {
    if (a[q] == a[j] && a[q] != a[q + 1]) {
      x = max(x, DP(q + 1, p, 0) + DP(i, q, j - p + k));
    }
  }
  return x;
}

int main() {
  int t, tt = 0;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
    }
    memset(dp, -1, sizeof dp);
    printf("Case %d: %d\n", ++tt, DP(1, n, 0));
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

用四个柱子进行的汉诺塔游戏。每次把前\(k\)个盘子放到第四个柱子上，然后按照三个柱子的汉诺塔玩法把剩余盘子转移到目标柱子上，最后把第四个柱子上的盘子转移到目标柱子上。输出转移\(n\)个盘子到目标柱子上的最少移动次数。

思路

思路出自：D_Double's Journey

设\(g[n]\)为三根柱子的汉诺塔移动\(n\)个圆盘所需最少步数，\(f[n]\)为四根柱子所需要的最少步数。可得\(f[n] = min(f[k] \times 2 + g[n - k])\)。打表求出前几项后可以得出规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
f[1] = 1
----------------
f[2] = 3,  f[2] = f[1] + 2^1
f[3] = 5,  f[3] = f[2] + 2^1
共 2 个 2^1
----------------
f[4] = 9,  f[4] = f[3] + 2^2
f[5] = 13,  f[5] = f[4] + 2^2
f[6] = 17,  f[6] = f[5] + 2^2
共 3 个 2^2
----------------
f[7] = 25,  f[7] = f[6] + 2^3
f[8] = 33,  f[8] = f[7] + 2^3
f[9] = 41,  f[9] = f[8] + 2^3
f[10] = 49,  f[10] = f[9] + 2^3
共 4 个 2^3

代码

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
import java.math.*;
import java.util.*;

public class Main {
  static final int maxn = 10010;

  public static void main(String[] args) {
    BigInteger[] a = new BigInteger[maxn];
    a[0] = BigInteger.ZERO;
    BigInteger k = BigInteger.ONE;
    int i = 1, cnt = 1;
    while (i < maxn) {
      for (int j = 0; j < cnt && i < maxn; ++j) {
        a[i] = a[i - 1].add(k);
        ++i;
      }
      k = k.add(k);
      ++cnt;
    }
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
      System.out.println(a[sc.nextInt()]);
    }
  } 
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个长度为\(n\)的字符串，输出要将它变成回文串所需要添加字母数目的最小值和任意一个转换之后的回文串。

思路

区间dp。定义状态\(dp[i][j]\)为把从i到j连续子串变为回文串，所需添加字母数目的最小值。有如下转移：

  • 当\(s[i] == s[j]\)时，\(dp[i][j] = dp[i + 1][j - 1]\)；
  • 当\(s[i] != s[j]\)时，\(dp[i][j] = min(dp[i + 1][j]， dp[i][j - 1]) + 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 = 1010;
char s[maxn];
int dp[maxn][maxn];

int DP(int i, int j) {
  if (i >= j) {
    return 0;
  }
  int& k = dp[i][j];
  if (k != -1) {
    return k;
  }
  if (s[i] == s[j]) {
    return k = DP(i + 1, j - 1);
  }
  return k = min(DP(i + 1, j), DP(i, j - 1)) + 1;
}

void print(int i, int j) {
  if (i > j) {
    return;
  }
  if (i == j) {
    putchar(s[i]);
  } else {
    if (s[i] == s[j]) {
      putchar(s[i]);
      print(i + 1, j - 1);
      putchar(s[j]);
    } else if (dp[i][j - 1] >= dp[i + 1][j]){
      putchar(s[i]);
      print(i + 1, j);
      putchar(s[i]);
    } else {
      putchar(s[j]);
      print(i, j - 1);
      putchar(s[j]);
    }
  }
}

int main() { 
  while (~scanf("%s", s)) {
    int len = int(strlen(s));
    memset(dp, -1, sizeof dp);
    printf("%d ", DP(0, len - 1));
    print(0, len - 1);
    puts("");
  }
  return 0;
}