Chengrui's Blog

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

const int maxn = 110;
int y[maxn];
struct point {
  int x, y;
  bool operator < (const point& rhs) const {
    return x < rhs.x;
  }
} p[maxn];

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, w, h;
    scanf("%d%d%d", &n, &w, &h);
    int cnt = 2;
    y[0] = 0, y[1] = h;
    for (int i = 0; i < n; ++i) {
      scanf("%d%d", &p[i].x, &p[i].y);
      y[cnt++] = p[i].y;
    }
    sort(p, p + n);
    sort(y, y + cnt);
    p[n++].x = w;
    cnt = int(unique(y, y + cnt) - y);
    int len = 0, ansx = 0, ansy = 0;
    for (int i = 0; i < cnt; ++i) {
      for (int j = i + 1; j < cnt; ++j) {
        int x = 0, pre = 0, l = 0;
        for (int k = 0; k < n; ++k) {
          if (k == n - 1 || (p[k].y > y[i] && p[k].y < y[j])) {
            if (p[k].x - pre > l) {
              l = p[k].x - pre;
              x = pre;
            }
            pre = p[k].x;
          }
        }
        l = min(l, y[j] - y[i]);
        if (l > len) {
          ansx = x;
          ansy = y[i];
          len = l;
        }
      }
    }
    printf("%d %d %d\n", ansx, ansy, len);
    if (t) {
      puts("");
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个由'a'和'b'组成的字符串及八种变化方式，输出变化\(s\)次之后的字符串的最小字典序形式。

思路

长度最大为15，可以模拟出所有字符串，找出周期。

代码

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

char str[20], c[10][5];
int n, s;
map<string, int> m;

string Next(string x) {
  string res = x;
  for (int i = 0; i < 8; ++i) {
    for (int j = 0; j < n; ++j) {
      bool ok = true;
      for (int k = 0; k < 3; ++k) {
        int p = k == 0 ? -2 : -1;
        p = (n + j + k + p) % n;
        if (x[p] != c[i][k]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        res[j] = c[i][3];
      }
    }
  }
  return res;
}

int main() {
  while (~scanf("%d", &n)) {
    m.clear();
    scanf("%s", str);
    for (int i = 0; i < 8; ++i) {
      scanf("%s", c[i]);
    }
    scanf("%d", &s);
    string tmp = str;
    m[tmp] = 0;
    int cnt = 0, cnt2 = 0;
    for (;;) {
      ++cnt;
      tmp = Next(tmp);
      if (m.count(tmp)) {
        cnt2 = m[tmp];
        break;
      }
      m[tmp] = cnt;
    }
    if (s >= cnt) {
      s -= cnt;
      s %= (cnt - cnt2);
    } else {
      tmp = str;
    }
    while (s--) {
      tmp = Next(tmp);
    }
    string ans = tmp;
    tmp += tmp;
    for (int i = 0; i < n; ++i) {
      if (tmp.substr(i, n) < ans) {
        ans = tmp.substr(i, n);
      }
    }
    puts(ans.c_str());
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个\(0\)到\(n-1\)的排列，若其中没有子数列为等差数列，输出"yes"，否则，输出"no"。

思路

记录每个数字出现的位置，枚举公差验证。

代码

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>
using namespace std;

const int maxn = 10010;
int pos[maxn];

int main() {
  int n;
  while (~scanf("%d:", &n) && n) {
    for (int i = 0; i < n; ++i) {
      int x;
      scanf("%d", &x);
      pos[x] = i;
    }
    bool flag = true;
    for (int i = 0; flag && i < n; ++i) {
      for (int j = 1; flag && i + j * 2 < n; ++j) {
        flag = !((pos[i] < pos[i + j]) ^ (pos[i + j] > pos[i + 2 * j]));
      }
    }
    puts(flag ? "yes" : "no");
  }
  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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int maxn = 510;
const double PI = acos(-1);
const double eps = 1e-8;
double ax[maxn], ay[maxn], bx[maxn], by[maxn];

struct range {
  double ang;
  int v;
  bool operator < (const range& rhs) const {
    if (fabs(ang - rhs.ang) > eps) {
      return ang < rhs.ang;
    } else {
      return v > rhs.v;
    }
  }
} a[maxn << 1];

int main() {
  int n;
  while (~scanf("%d", &n) && n) {
    for (int i = 0; i < n; ++i) {
      scanf("%lf%lf%lf%lf", &ax[i], &ay[i], &bx[i], &by[i]);
    }
    double x, y;
    int cnt = 0;
    scanf("%lf%lf", &x, &y);
    for (int i = 0; i < n; ++i) {
      double l = atan2(ax[i] - x, ay[i] - y);
      double r = atan2(bx[i] - x, by[i] - y);
      if (l > r) {
        swap(l, r);
      }
      if (r - l >= PI) {
        a[cnt].ang = -PI, a[cnt].v = 1;
        ++cnt;
        a[cnt].ang = l, a[cnt].v = -1;
        ++cnt;
        l = r, r = PI;
      }
      a[cnt].ang = l, a[cnt].v = 1;
      ++cnt;
      a[cnt].ang = r, a[cnt].v = -1;
      ++cnt;
    }
    sort(a, a + cnt);
    int ans = 0, cur = 0;
    for (int i = 0; i < cnt; ++i) {
      cur += a[i].v;
      ans = max(ans, cur);
    }
    printf("%d\n", ans);
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有\(n\)个人要过桥，只有一盏灯，每个人过桥的速度不同，每次最多过两个。输出最短过桥时间和方案。

思路

来回送等的人一定选用时最少的，有两种方案：1、让最快的两个人先到对岸，然后一个送灯回来，再让两个慢的过去，另一个快的再送灯回来；2、让最快的送一个人过去再回来。每次选择两种方案中耗时较少的一个执行。

代码

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

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
    }
    sort(a, a + n);
    if (n <= 2) {
      printf("%d\n", a[n - 1]);
      for (int i = 0; i < n; ++i) {
        printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
      }
    } else {
      int ans = n & 1 ? a[0] + a[1] + a[2] : a[1];
      for (int i = n - 1; i > 2; i -= 2) {
        ans += min(a[1] << 1, a[i - 1] + a[0]) + a[0] + a[i];
      }
      printf("%d\n", ans);
      for (int i = n - 1; i > 2; i -= 2) {
        if (a[1] << 1 < a[i - 1] + a[0]) {
          printf("%d %d\n", a[0], a[1]);
          printf("%d\n", a[0]);
          printf("%d %d\n", a[i - 1], a[i]);
          printf("%d\n", a[1]);
        } else {
          printf("%d %d\n", a[0], a[i - 1]);
          printf("%d\n", a[0]);
          printf("%d %d\n", a[0], a[i]);
          printf("%d\n", a[0]);
        }
      }
      if (n & 1) {
        printf("%d %d\n", a[0], a[2]);
        printf("%d\n", a[0]);
      }
      printf("%d %d\n", a[0], a[1]);
    }
    if (t) {
      puts("");
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

处理器要处理\(n\)个任务，每个任务有开始时间\(r_i\)，截止时间\(d_i\)，工作量\(w_i\)三个参数，任务必须在截止时间之前完成，输出处理器完成所有任务的最大单位时间工作量的最小值。

思路

最大值的最小值问题，二分出答案，然后验证是否可行。验证时优先处理结束时间早的任务。

代码

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

const int maxn = 10010;
int n, t;
struct prog {
  int l, r, w;
  bool operator < (const prog& rhs) const {
    return r > rhs.r;
  }
} pr[maxn];

bool cmp(const prog& a, const prog& b) {
  return a.l < b.l;
}

bool check(int x) {
  int p = 0;
  priority_queue<prog> q;
  for (int i = 1; i < 20010; ++i) {
    while (p < n && pr[p].l < i) {
      q.push(pr[p]);
      ++p;
    }
    int sum = x;
    while (sum > 0 && !q.empty()) {
      if (q.top().r < i) {
        return false;
      }
      prog k = q.top();
      q.pop();
      k.w -= sum;
      if (k.w > 0) {
        q.push(k);
      }
      sum = -k.w;
    }
    if (p == n && q.empty()) {
      break;
    }
  }
  return true;
}

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d%d%d", &pr[i].l, &pr[i].r, &pr[i].w);
    }
    sort(pr, pr + n, cmp);
    int L = 1, R = n * 1010, ans = R;
    while (L <= R) {
      int m = (L + R) >> 1;
      if (check(m)) {
        ans = min(ans, m);
        R = m - 1;
      } else {
        L = m + 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(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
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 10010;
int n, k, cnt;
int p[maxn], id[maxn];

void dfs(int x) {
  printf("%d %d\n", p[x], x);
  id[x] = x;
  int tmp = p[x];
  p[x] = x;
  id[tmp] = 0;
  if (tmp <= cnt) {
    dfs(tmp);
  }
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    cnt = 0;
    memset(p, 0, sizeof p);
    memset(id, 0, sizeof id);
    while (k--) {
      int x;
      scanf("%d", &x);
      for (int i = 0; i < x; ++i) {
        scanf("%d", &p[++cnt]);
        id[p[cnt]] = cnt;
      }
    }
    bool flag = true;
    for (int i = 1; i <= cnt; ++i) {
      if (p[i] != i) {
        flag = false;
        break;
      }
    }
    if (flag) {
      puts("No optimization needed");
    }
    for (int i = 1; i <= cnt; ++i) {
      if (id[i] == 0) {
        dfs(i);
      }
    }
    for (int i = 1; i <= cnt; ++i) {
      if (id[i] != i) {
        printf("%d %d\n", i, n);
        p[id[i]] = n;
        id[n] = id[i];
        id[i] = 0;
        dfs(i);
      }
    }
    if (t) {
      puts("");
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个由'0', '1', '?'组成的字符串，其中'?'既可以当做'0'，也可以当做'1'。输出最短的最长连续相同的字符长度。

思路

预处理出每一段的字符和长度，然后对于'?'，与前一段和后一段字符是否相同进行分类讨论。有个trick是当'?'的长度为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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1010;
char s[maxn], tp[maxn];
int l[maxn];

int main() {
  int t, tt = 0;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s);
    int len = int(strlen(s)), n = 0;
    tp[n] = s[0], l[n] = 0;
    for (int i = 0; i < len; ++i) {
      if (s[i] != tp[n]) {
        ++n;
        tp[n] = s[i], l[n] = 0;
      }
      ++l[n];
    }
    ++n;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      if (tp[i] != '?') {
        ans = max(ans, l[i]);
        continue;
      }
      if (i == 0 || i == n - 1) {
        continue;
      }
      if (tp[i - 1] == tp[i + 1]) {
        if ((l[i] & 1) == 0) {
          ans = max(ans, 2);
        }
      } else {
        if (l[i] & 1) {
          if (l[i] != 1) {
            ans = max(ans, 2);
          } else {
            if (l[i - 1] > l[i + 1]) {
              ++l[i + 1];
            } else {
              ans = max(ans, l[i - 1] + 1);
            }
          }
        }
      }
    }
    printf("Case %d: %d\n", ++tt, ans);
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出5种操作，给出\(n\)个初始数字，及\(n\)个结果。输出能使所有给定初始数字转化为给定结果的操作，多解输出字典序最小的解，忽略10次以上的操作序列。

思路

bfs搜出第一个数字的操作序列，然后验证其他数字是否满足。

代码

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

const int maxn = 15;
const char *op[] = {"ADD", "DIV", "DUP", "MUL", "SUB"};
int n, t;
int x[maxn], y[maxn];

struct node{
  stack<int> s;
  int p[maxn], len;
  node() {}
  node(int x) {
    s = stack<int>();
    s.push(x);
    len = 0;
  }
} ans;
queue<node> q;

bool judge(node& k) {
  for (int i = 1; i < n; ++i) {
    stack<int> s;
    s.push(x[i]);
    for (int j = 0; j < k.len; ++j) {
      if (k.p[j] == 2) {
        s.push(s.top());
      } else {
        if (s.size() <= 1) {
          return false;
        }
        int a = s.top();
        s.pop();
        int b = s.top();
        s.pop();
        if (k.p[j] == 0) {
          s.push(a + b);
        } else if (k.p[j] == 1) {
          if (a == 0) {
            return false;
          }
          s.push(b / a);
        } else if (k.p[j] == 3) {
          s.push(a * b);
        } else {
          s.push(b - a);
        }
      }
      if (s.top() > 30000 || s.top() < -30000) {
        return false;
      }
    }
    if (s.size() != 1 || s.top() != y[i]) {
      return false;
    }
  }
  return true;
}

bool bfs() {
  q = queue<node>();
  q.push(node(x[0]));
  while (!q.empty()) {
    node k = q.front();
    q.pop();
    if (k.s.top() == y[0] && judge(k)) {
      ans = k;
      return true;
    }
    if (k.len >= 10) {
      continue;
    }
    for (int i = 0; i < 5; ++i) {
      node tmp = k;
      tmp.p[tmp.len++] = i;
      if (i == 2) {
        if (int(k.s.size() + k.len - 10) > 1) {
          continue;
        }
        tmp.s.push(tmp.s.top());
      } else {
        if (int(k.s.size()) <= 1) {
          continue;
        }
        int a = tmp.s.top();
        tmp.s.pop();
        int b = tmp.s.top();
        tmp.s.pop();
        if (i == 0) {
          tmp.s.push(a + b);
        } else if (i == 1) {
          if (a == 0) {
            continue;
          }
          tmp.s.push(b / a);
        } else if (i == 3) {
          tmp.s.push(a * b);
        } else {
          tmp.s.push(b - a);
        }
      }
      if (tmp.s.top() > 30000 || tmp.s.top() < -30000) {
        continue;
      }
      q.push(tmp);
    }
  }
  return false;
}

int main() {
  while (~scanf("%d", &n) && n) {
    for (int i = 0; i < n; ++i) {
      scanf("%d", &x[i]);
    }
    for (int i = 0; i < n; ++i) {
      scanf("%d", &y[i]);
    }
    printf("Program %d\n", ++t);
    if (bfs()) {
      if (ans.len == 0) {
        puts("Empty sequence");
      } else {
        for (int i = 0; i < ans.len; ++i) {
          printf("%s%c", op[ans.p[i]], i == ans.len - 1 ? '\n' : ' ');
        }
      }
    } else {
      puts("Impossible");
    }
    puts("");
  }
  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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 210;
char s[maxn][maxn];
int n, t;
int d[maxn][maxn], u[maxn][maxn];

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

int main() {
  while (~scanf("%d", &n) && n) {
    memset(s, 0, sizeof s);
    memset(d, -1, sizeof d);
    memset(u, -1, sizeof u);
    for (int i = 1; i <= n; ++i) {
      scanf("%s", s[i] + i);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      int len = (n - i) * 2 + 1;
      for (int j = 0; j < len; ++j) {
        if (s[i][i + j] == '-') {
          if (j & 1) {
            ans = max(ans, DP(i, i + j, 1, d));
          } else {
            ans = max(ans, DP(i, i + j, -1, u));
          }
        }
      }
    }
    printf("Triangle #%d\n", ++t);
    printf("The largest triangle area is %d.\n\n", ans * ans);
  }
  return 0;
}