By

文章目录
  1. 1. 引言
  2. 2. 1001. 超级赛亚ACMer (hdu5246)
    1. 2.1. 解題報告
    2. 2.2. 樣例代碼
  3. 3. 1002. 找连续数 (hdu5247)
    1. 3.1. 解題報告
    2. 3.2. 樣例代碼
  4. 4. 1003. 序列变换 (hdu5248)
    1. 4.1. 解題報告
    2. 4.2. 樣例代碼
  5. 5. 1004. KPI (hdu5249)
    1. 5.1. 解題報告
    2. 5.2. 樣例代碼
  6. 6. 1005. 三阶魔方 (hdu5250)
    1. 6.1. 解題報告
    2. 6.2. 樣例代碼
  7. 7. 1006. 矩形面积 (hdu5251)
    1. 7.1. 解題報告
    2. 7.2. 樣例代碼

引言

在一直沒有寫出能正常運行的平衡樹模板，這個坑拖了很久（然而是取巧的）。
還有一個就是魔方，之前打了27的表發現還要考慮色向和，怎麼都wa簡直崩潰。

1001. 超级赛亚ACMer (hdu5246)

http://acm.hdu.edu.cn/showproblem.php?pid=5246

解題報告

排個序，貪心搞一搞，過了。

樣例代碼

1001view raw
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
//@ Including Header
#include <csl_std.h>

/*
 *  Name : hdu5246.cpp
 *  Date : 2015年8月4日 下午8:29:04
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

#define maxn 10010
ll a[maxn];

//@ Main Function
int main() {
  //for (; scanf("%d", &_) != EOF; ) {
  int _, __ = 0;
  for (scanf("%d", &_); _; _--) {
    printf("Case #%d:\n", ++__);
    int n; ll m, k; scanf("%d" i64 i64, &n, &m, &k);
    rep(i, 0, n) scanf(i64, a+i); sort(a, a+n);
    int idx = -1;
    rep(i, 0, n) if (a[i] > m) break; else idx = i;
    if (~idx) {
      for (int tmp = idx; k && idx != n-1; k--, idx = tmp) {
        rep(i, idx+1, n) if (a[i] > a[idx] + max(k, 0ll)) break; else tmp = i;
        if (tmp == idx) break;
      }
    }
    printf(idx != n-1 ? "madan!\n" : "why am I so diao?\n");
  }
  return 0;
}

1002. 找连续数 (hdu5247)

http://acm.hdu.edu.cn/showproblem.php?pid=5247

解題報告

維護三種值：

  1. 區間內的最小值$x$
  2. 區間內的最大值$y$
  3. 區間內所有元素上次出現的下標的最大值$z$

因此對於區間$[i,i+k-1]$：
滿足$y - x + 1 = k$，約束了數據範圍；
且$z < i$，約束了重複元素。

樣例代碼

1002view raw
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
//@ Including Header
#include <csl_std.h>
#include <csl_algo.h>
#include <sparse.h>

/*
 *  Name : hdu5247.cpp
 *  Date : 2015年8月5日 下午7:41:50
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

#define maxn 10010
int a[maxn], b[maxn];

//@ Main Function
int main() {
  int _, __ = 0;
  //for (; scanf("%d", &_) != EOF; ) {
  for (_ = 1; _; _--) {
    printf("Case #%d:\n", ++__);
    int n, m; scanf("%d%d", &n, &m);
    rep(i, 0, n) scanf("%d", a+i);

    map<int, int> p;
    map<int, int>::iterator it;
    rep(i, 0, n) {
      it = p.find(a[i]);
      b[i] = (it == p.end()) ? -1 : it->second;
      p[a[i]] = i;
    }

    csl::sparse_table< int, csl::less<int> > st1; st1.build(a, n);
    csl::sparse_table< int, csl::greater<int> > st2; st2.build(a, n);
    csl::sparse_table< int, csl::greater<int> > st3; st3.build(b, n);

    while (m--) {
      int k; scanf("%d", &k);
      int ans = 0;
      rep(i, 0, n-k+1) {
        int x = st1.query(i, i+k-1);
        int y = st2.query(i, i+k-1);
        if (y - x + 1 != k) continue;
        int z = st3.query(i, i+k-1);
        if (z >= i) continue;
        ++ans;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}

1003. 序列变换 (hdu5248)

http://acm.hdu.edu.cn/showproblem.php?pid=5248

解題報告

二分答案，然後貪心之。
第一頁嗑瓜子。

樣例代碼

1003view raw
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
//@ Including Header
#include <csl_std.h>

/*
 *  Name : hdu5248.cpp
 *  Date : 2015年8月5日 下午10:07:15
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */
#define maxn 100010
int n, a[maxn];

bool judge(int k) {
  int now = a[0] - k;
  rep(i, 1, n) {
    now = max(now + 1, a[i] - k);
    if (now > a[i] + k) return false;
  }
  return true;
}

//@ Main Function
int main() {
  int _, __ = 0;
  //for (; scanf("%d", &_) != EOF; ) {
  for (scanf("%d", &_); _; _--) {
    printf("Case #%d:\n", ++__);
	scanf("%d", &n);
	rep(i, 0, n) scanf("%d", a+i);

	int l = 0, r = 2000000;
	while (l < r) {
	  int m = (l + r) >> 1;
	  if (judge(m)) r = m; else l = m + 1;
	}
	printf("%d\n", l);
  }
  return 0;
}

1004. KPI (hdu5249)

http://acm.hdu.edu.cn/showproblem.php?pid=5249

解題報告

  1. 兩個set瞎搞
  2. 離線離散化，二分樹狀數組
  3. 數據結構題，用平衡樹維護

第一頁第三個。

樣例代碼

1004view raw
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
//@ Including Header
#include <csl_std.h>

/*
 *  Name : hdu5249-1.cpp
 *  Date : 2015年8月5日 下午10:18:37
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

struct channel {
private :
  set<int> head, tail;
  set<int>::iterator it;
  deque<int> order;
public :
  void clear() {
    head.clear();
    tail.clear();
    order.clear();
  }
  void insert(int x) {
    if (head.empty() || x > *head.rbegin()) tail.insert(x);
    else head.insert(x);
    order.push_back(x);
  }
  void erase() {
    if (order.empty()) return;
    int x = order.front(); order.pop_front();
    it = head.find(x); if (it != head.end()) head.erase(it);
    it = tail.find(x); if (it != tail.end()) tail.erase(it);
  }
  void query() {
    while (tail.size() < head.size()) {
      it = --head.end();
      tail.insert(*it);
      head.erase(it);
    }
    while (tail.size() > head.size() + 1) {
      it = tail.begin();
      head.insert(*it);
      tail.erase(it);
    }
    if (!tail.empty()) printf("%d\n", *tail.begin());
  }
} q;

//@ Main Function
int main() {
  int _, __ = 0;
  for (int n; scanf("%d", &n) != EOF; ) {
//  for (scanf("%d", &_); _; _--) {
    printf("Case #%d:\n", ++__);
    q.clear();
	while (n--) {
	  char s[10]; scanf("%s", s); int x;
	  switch (s[0]) {
	    case 'i' : scanf("%d", &x); q.insert(x); break;
	    case 'o' : q.erase(); break;
	    case 'q' : q.query(); break;
	  }
	}
  }
  return 0;
}
1004view raw
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
//@ Including Header
#include <csl_std.h>
#include <fenwick.h>
#include <discrete.h>

/*
 *  Name : hdu5249-2.cpp
 *  Date : 2015年8月5日 下午11:37:55
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

#define maxn 10010
char op[maxn];

csl::fenwick_tree<int> ft;
size_t search(int k) {
  size_t res = 0; int cnt = 0;
  rrep(i, 0, 20) {
    size_t tmp = res + (1 << i);
    if (tmp >= ft.m_data.size()) continue;
    if (cnt + ft.m_data[tmp] >= k) continue;
    res = tmp; cnt += ft.m_data[tmp];
  }
  return res + 1;
}

//@ Main Function
int main() {
  int __ = 0;
  for (int n; scanf("%d", &n) != EOF; ) {
//  for (scanf("%d", &_); _; _--) {
    printf("Case #%d:\n", ++__);
    vector<int> u;
    csl::discrete<int> v;
    rep(i, 0, n) {
      char s[10]; scanf("%s", s); op[i] = s[0];
      if (s[0] == 'i') {
        int x; scanf("%d", &x);
        u.push_back(x); v.insert(x);
      }
    }
    v.build();

    ft.build(v.size());
    int l = -1, r = -1, pos;
    rep(i, 0, n)
      switch (op[i]) {
        case 'i' :
          pos = v.query(u[++r]); ft.update(pos + 1, +1); break;
        case 'o' :
          pos = v.query(u[++l]); ft.update(pos + 1, -1); break;
        case 'q' :
          pos = search((r - l) / 2 + 1); printf("%d\n", v[pos - 1]); break;
      }
  }
  return 0;
}
1004view raw
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
//@ Including Header
#include <csl_std.h>
#include <rb_tree.h>

/*
 *  Name : hdu5249-3.cpp
 *  Date : 2015年8月8日 上午9:53:05
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

typedef csl::rb_tree<int, __gnu_pbds::null_type, less<int>,
    __gnu_pbds::tree_order_statistics_node_update> rb_tree;

//@ Main Function
int main() {
  int __ = 0;
  for (int n; scanf("%d", &n) != EOF; ) {
    printf("Case #%d:\n", ++__);
    rb_tree p;
    std::queue<int> q;
    while (n--) {
      char s[10]; scanf("%s", s); int x;
      switch (s[0]) {
        case 'i' :
          scanf("%d", &x), q.push(x), p.insert(x); break;
        case 'o' :
          if (!q.empty()) x = q.front(), q.pop(), p.erase(x); break;
        case 'q' :
          if (!p.empty()) x = *p.find_by_order(p.size() / 2); printf("%d\n", x); break;
      }
    }
  }
  return 0;
}

1005. 三阶魔方 (hdu5250)

http://acm.hdu.edu.cn/showproblem.php?pid=5250

解題報告

對發生變化的48個面打個表，然後暴力跑一跑能過。
我這裏爲了衝榜首，用了找循環節然後求gcd的方法。

樣例代碼

1005view raw
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
//@ Including Header
#include <csl_std.h>

/*
 *  Name : hdu5250.cpp
 *  Date : 2015年9月25日 上午12:32:37
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

#define maxn 48
const int g[6][maxn] = {
    5,3,0,6,1,7,4,2,8,9,42,11,44,13,14,47,16,17,18,19,20,21,22,23,39,25,26,36,28,34,30,31,32,33,10,35,12,37,38,15,40,41,29,43,27,45,46,24,
    37,1,2,38,4,39,6,7,13,11,8,14,9,15,12,10,16,17,40,19,41,21,22,42,24,25,26,27,28,29,30,31,32,33,34,35,36,23,20,18,5,3,0,43,44,45,46,47,
    24,25,26,3,4,5,6,7,0,1,2,11,12,13,14,15,8,9,10,19,20,21,22,23,16,17,18,27,28,29,30,31,37,35,32,38,33,39,36,34,40,41,42,43,44,45,46,47,
    0,1,2,3,4,5,6,7,32,9,10,35,12,37,14,15,21,19,16,22,17,23,20,18,24,25,45,27,43,29,30,40,31,33,34,28,36,26,38,39,8,41,42,11,44,13,46,47,
    0,1,47,3,46,5,6,45,8,9,10,11,12,13,14,15,34,17,18,33,20,32,22,23,29,27,24,30,25,31,28,26,2,4,7,35,36,37,38,39,40,41,42,43,44,16,19,21,
    0,1,2,3,4,13,14,15,8,9,10,11,12,21,22,23,16,17,18,19,20,29,30,31,24,25,26,27,28,5,6,7,32,33,34,35,36,37,38,39,45,43,40,46,41,47,44,42,
};
char c[110];
int s[maxn], t[maxn], v[maxn];
int *p = s, *q = t;

void trans(const int func[]) {
  rep(i, 0, maxn) q[i] = p[func[i]];
  swap(p, q);
}

int dfs(int i, int x) {
  v[i] = 1;
  if (p[i] == x) return 1;
  return dfs(p[i], x) + 1;
}

//@ Main Function
int main() {
  int _, __ = 0; scanf("%d", &_);
  while (_--) {
    rep(i, 0, maxn) p[i] = i;
    scanf("%s", c);
    for (char* ch = c; *ch; ++ch) {
      int type, time = 1;
      switch (*ch) {
        case 'U' : type = 0; break;
        case 'R' : type = 1; break;
        case 'F' : type = 2; break;
        case 'D' : type = 3; break;
        case 'L' : type = 4; break;
        case 'B' : type = 5; break;
      }
      switch (*(ch + 1)) {
        case '\'' : time += 2; ++ch; break;
        case '2' :  time += 1; ++ch; break;
      }
      while (time--) trans(g[type]);
    }

    int ans = 1;
    rep(i, 0, maxn) v[i] = 0;
    rep(i, 0, maxn) if (!v[i]) {
      int x = dfs(i, i);
      if (x == 1) continue;
      ans = ans / __gcd(ans, x) * x;
    }
    printf("Case #%d:\n%d\n", ++__, ans);
  }
  return 0;
}

1006. 矩形面积 (hdu5251)

http://acm.hdu.edu.cn/showproblem.php?pid=5251

解題報告

最小包圍矩形。

樣例代碼

1006view raw
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
//@ Including Header
#include <csl_std.h>
#include <csl_algo.h>
#include <geometry.h>

/*
 *  Name : hdu5251.cpp
 *  Date : 2015年9月24日 下午3:19:01
 *  Copyright : fateud.com
 *  Anti-Mage : The magic ends here.
 */

using csl::point;
using csl::line;
using csl::sgn;
#define maxn 1010
point p[maxn*4], q[maxn*4];

//@ Main Function
int main() {
  int _, __ = 0; scanf("%d", &_);
  while (_--) {
    int n; scanf("%d", &n);
    rep(i, 0, n << 2) scanf("%lf%lf", &p[i].x, &p[i].y);
    vector<point> g = csl::graham(p, n << 2);
    int m = g.size(); g.push_back(g[0]);
    double ans = csl::bound_rect(g.data(), m);
    printf("Case #%d:\n%.0f\n", ++__, ans);
  }
  return 0;
}
文章目录
  1. 1. 引言
  2. 2. 1001. 超级赛亚ACMer (hdu5246)
    1. 2.1. 解題報告
    2. 2.2. 樣例代碼
  3. 3. 1002. 找连续数 (hdu5247)
    1. 3.1. 解題報告
    2. 3.2. 樣例代碼
  4. 4. 1003. 序列变换 (hdu5248)
    1. 4.1. 解題報告
    2. 4.2. 樣例代碼
  5. 5. 1004. KPI (hdu5249)
    1. 5.1. 解題報告
    2. 5.2. 樣例代碼
  6. 6. 1005. 三阶魔方 (hdu5250)
    1. 6.1. 解題報告
    2. 6.2. 樣例代碼
  7. 7. 1006. 矩形面积 (hdu5251)
    1. 7.1. 解題報告
    2. 7.2. 樣例代碼