文章目录
  1. 1. 引言
  2. 2. 1001. Alisha’s Party (hdu5437)
    1. 2.1. 中文題意
    2. 2.2. 解題報告
    3. 2.3. 樣例代碼
  3. 3. 1002. Ponds (hdu5438)
    1. 3.1. 中文題意
    2. 3.2. 解題報告
    3. 3.3. 樣例代碼
  4. 4. 1003. Aggregated Counting (hdu5439)
    1. 4.1. 中文題意
    2. 4.2. 解題報告
    3. 4.3. 樣例代碼
  5. 5. 1005. Travel (hdu5441)
    1. 5.1. 中文題意
    2. 5.2. 解題報告
    3. 5.3. 樣例代碼
  6. 6. 1006. Favorite Donut (hdu5442)
    1. 6.1. 中文題意
    2. 6.2. 解題報告
    3. 6.3. 樣例代碼
  7. 7. 1007. The Water Problem (hdu5443)
    1. 7.1. 中文題意
    2. 7.2. 解題報告
    3. 7.3. 樣例代碼
  8. 8. 1008. Elven Postman (hdu5444)
    1. 8.1. 中文題意
    2. 8.2. 解題報告
    3. 8.3. 樣例代碼
  9. 9. 1010. Unknown Treasure (hdu5446)
    1. 9.1. 中文題意
    2. 9.2. 解題報告
    3. 9.3. 樣例代碼
  10. 10. 後記

引言

すみません、すみません、すみません、
因爲我的愚蠢,坑了1010,最後才出6道。

1001. Alisha’s Party (hdu5437)

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

中文題意

朋友來訪,室內空間有限,優先讓禮物貴重者進入。
有$k$個朋友依次前來,第$i$個叫$B_{i}$,帶了價值爲$v_{i}$的禮物。
開$m$次門,第$i$次開門在第$t_{i}$個朋友來時,放$p_{i}$個朋友入室。
有$q$次詢問,求第$n_{i}$個進入者的名字。

解題報告

  1. 切忌對整個結構體進行排序,可以對指針進行排序
  2. 用優先隊列維護$v_{i}$最高者

樣例代碼

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//@ Including Header
#include <csl_std.h>

/*
* Name : hdu5437.cpp
* Date : 2015年9月13日 下午3:47:00
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxk 150010
struct node {
char s[201];
int v;
int w;
};
node a[maxk];
pii c[maxk];

struct cmp {
bool operator () (node* a, node* b) const {
return a->v != b->v ? a->v < b->v : a->w > b->w;
}
};

//@ Main Function
int main() {
int _;
for (scanf("%d", &_); _; _--) {
int k, m, q; scanf("%d%d%d", &k, &m, &q);
rep(i, 0, k) scanf("%s%d", a[i].s, &a[i].v), a[i].w = i;
rep(i, 0, m) scanf("%d%d", &c[i].first, &c[i].second);
sort(c, c + m);

int cur = 0;
priority_queue< node*, vector<node*>, cmp > p;
vector<node*> ans; ans.reserve(k);
rep(i, 0, m) {
for (int x = c[i].first; cur < x; ++cur) p.push(a + cur);
for (int x = c[i].second; x && !p.empty(); --x, p.pop())
ans.push_back(p.top());
}
for (; cur < k; ++cur) p.push(a + cur);
for (; !p.empty(); p.pop())
ans.push_back(p.top());

rep(i, 0, q) {
int x; scanf("%d", &x);
printf("%s%c", ans[x-1]->s, i == q-1 ? '\n' : ' ');
}
}
return 0;
}

1002. Ponds (hdu5438)

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

中文題意

一個無向圖有$p$個點,第$i$個點點權$v_{i}$;$m$條邊,第$i$條邊連接$a_{i}$和$b_{i}$。
刪除所有度小於$2$的點,求點個數爲奇數的聯通塊的所有點權之和。

解題報告

  1. 先進行拓撲刪點
  2. 然後遍歷所有聯通塊

樣例代碼

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//@ Including Header
#include <csl_std.h>
#include <graph.h>

/*
* Name : hdu5438.cpp
* Date : 2015年9月13日 下午7:32:30
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxn 10010
#define maxm 100010

typedef csl::graph<bool> graph;
typedef csl::graph<bool>::_Link edge;
typedef std::pair<int,ll> node;

graph g;
int n, m, a[maxn], b[maxm], c[maxm];
int d[maxn]; bool e[maxn];

void bfs() {
queue<int> q;
rep(i, 1, n+1) if (d[i] <= 1) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
if (e[u]) continue; e[u] = true;
if (d[u] != 1) continue;
for (edge i = g.getHead(u); i; i = i->next) {
int v = i->to;
if (e[v]) continue;
if ((--d[v]) == 1) q.push(v);
}
}
}

node dfs(int u) {
node res(1,a[u]);
e[u] = true;
for (edge i = g.getHead(u); i; i = i->next) {
int v = i->to;
if (e[v]) continue;
node tmp = dfs(v);
res.first += tmp.first;
res.second += tmp.second;
}
return res;
}

//@ Main Function
int main() {
int _; scanf("%d", &_);
while (_--) {
scanf("%d%d", &n, &m);
rep(i, 1, n+1) scanf("%d", a+i);
rep(i, 0, m) scanf("%d%d", b+i, c+i);

g.build(n+1, m<<1);
rep(i, 1, n+1) d[i] = 0, e[i] = 0;
rep(i, 0, m) g.add_double_edge(b[i], c[i], true), ++d[b[i]], ++d[c[i]];

bfs();
ll ans = 0;
rep(i, 1, n+1) if (!e[i]) {
node res = dfs(i);
if (res.first & 1) ans += res.second;
}
cout << ans << endl;
}
return 0;
}

1003. Aggregated Counting (hdu5439)

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

中文題意

  1. 先寫下數列1,2,2
  2. 第三個數是2,在末尾添加2個3
  3. 第四個數是3,在末尾添加3個4
  4. 第五個數是3,在末尾添加3個5
  5. 以此類推

令$f_{n}$爲$n$出現最後的位置,$f_{2}=3$,$f_{3}=5$,$f_{4}=8$
給你一個$n$,求$f_{f_{n}} \bmod 1000000007$的值

解題報告

  1. $a_{n}$爲1,2,2,3,3,4,4,4,5,5,5,6,6,6,6…
  2. $f_{n}$爲1,3,5,8,11,15…顯然$f_{n} = \sum\limits_{i=1}^{n} a_{i}$
  3. $f_{f_{n}}$爲1,5,11,23,38,62…$f_{f_{n}} = \sum\limits_{i=1}^{n} i * a_{i}$。具體證明略,自行參考Solution
  4. 對於$f_{f_{n}}$的公式,我們可以合併同類項,得$1*1+2*(2+3)+3*(4+5)+4*(6+7+8)+\dotsb$
  5. 得到這個規律,我們只要維護出$a_{n}$中連續$x$的區間,區間的長度可以通過查詢之前維護出的值得知。用二分查是$O(logn)$的效率,事實上這是單調的,$O(1)$就能維護出來。

樣例代碼

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
40
41
42
43
//@ Including Header
#include <csl_std.h>
#include <csl_math.h>

/*
* Name : hdu5439.cpp
* Date : 2015年9月13日 下午8:34:38
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxm 1000000000
#define maxn 500010
#define mod 1000000007
ll f[maxn];

//@ Main Function
int main() {
vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(3);
for (int i = 3, s = 3, cur = 2; s < maxm; ++i) {
if (i > v[cur]) ++cur;
v.push_back(s+=cur);
}
ll half = csl::pow(1ll, 2ll, mod-2, (ll)mod);
rep(i, 1, (int)v.size()) {
ll tmp = ll(v[i] - v[i-1]) * (v[i] + v[i-1] + 1) % mod * half % mod;
f[i] = (f[i-1] + tmp * i) % mod;
}

int _; scanf("%d", &_);
while (_--) {
int n; scanf("%d", &n);
int p = lower_bound(v.begin(), v.end(), n) - v.begin();
ll tmp = ll(n - v[p-1]) * (n + v[p-1] + 1) % mod * half % mod;
ll ans = (f[p-1] + tmp * p) % mod;
printf(i64 "\n", ans);
}

return 0;
}

1005. Travel (hdu5441)

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

中文題意

一個無向圖有$n$個點,$m$條邊,第$i$條邊連接$a_{i}$和$b_{i}$,邊權爲$d_{i}$。
有$q$次詢問,給你一個整數$x$,求不存在邊權大於等於x的邊時,聯通的點對共有多少。

解題報告

  1. 先將邊按邊權排序,然後用並查集維護聯通塊內的點數。
  2. 每加一條邊,對兩端聯通塊進行一次“並”操作,且記錄當前答案。
  3. 對於每個查詢,用二分尋找邊權小於$x$且最大的邊,輸出對應的記錄。

樣例代碼

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

/*
* Name : hdu5441.cpp
* Date : 2015年9月13日 上午9:23:47
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxn 20010
#define maxm 100010
#define maxq 5010
int s[maxn];
int a[maxm],b[maxm],c[maxm],d[maxm],f[maxm];
int g[maxn],h[maxn];

bool cmp(const int& a, const int& b) {
return c[a] < c[b];
}

int root(int u) {
return g[u] == u ? u : g[u] = root(g[u]);
}

int merge(int u, int v) {
int ru = root(u);
int rv = root(v);
if (ru == rv) return 0;
int ret = s[h[ru]] + s[h[rv]];
g[rv] = ru;
h[ru] += h[rv];
return s[h[ru]] - ret;
}

//@ Main Function
int main() {
rep(i, 1, maxn) s[i] = i * (i-1) / 2;
int _;
for (scanf("%d", &_); _; _--) {
int n, m, q; scanf("%d%d%d", &n, &m, &q);
rep(i, 0, m) scanf("%d%d%d", a+i, b+i, c+i), d[i]=i;
sort(d, d+m, cmp);

rep(i, 1, n+1) g[i]=i, h[i]=1;
int cnt = 0;
rep(i, 0, m) {
int j = d[i];
f[j] = (cnt += merge(a[j],b[j]));
}

rep(i, 0, q) {
int x; scanf("%d", &x);
int l = 0, r = m-1;
while (l < r) {
int m = (l + r) >> 1;
if (c[d[m]] <= x) l = m+1;
else r = m;
}
if (l && c[d[l]] > x) --l;
printf("%d\n", c[d[l]] <= x ? f[d[l]] << 1 : 0);
}
}
return 0;
}

1006. Favorite Donut (hdu5442)

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

中文題意

給你一個長度爲$n$的字符串,求串的正反循環的所有同構中,字典序最大的下標和方向。
如果字典序相同,輸出下標最小的;如果下標相同,輸出方向爲正的。

解題報告

算法一:

  1. 求正串的最小表示法中下標最小的解
  2. 求反串的最小表示法中下標最大的解
  3. 運算出兩解在原串中的下標,進行比較
  4. 因爲沒有極端數據,所以第二步不會達到$O(n^2)$

算法二:
後綴數組搞一搞

樣例代碼

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
32
33
34
35
36
//@ Including Header
#include <csl_std.h>
#include <csl_algo.h>

/*
* Name : hdu5442.cpp
* Date : 2015年9月17日 上午11:47:07
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxn 20010
char s[maxn], t1[maxn*2], t2[maxn*2];
//@ Main Function
int main() {
int _; scanf("%d", &_);
while (_--) {
int n; scanf("%d", &n);
scanf("%s", s);

rep(i, 0, n) t1[i] = t1[n+i] = s[i];
rep(i, 0, n) t2[i] = t2[n+i] = s[n-1-i];
t1[2*n] = 0, t2[2*n] = 0;
int x = csl::isomorph_min(t1, n, std::greater<char>());
int y = csl::isomorph_max(t2, n, std::greater<char>());
t1[x+n] = 0, t2[y+n] = 0;

int ans1 = x + 1, ans2 = n - y;
int z = strcmp(t1+x, t2+y);
if (z)
printf("%d %d\n", z > 0 ? ans1 : ans2, z <= 0);
else
printf("%d %d\n", min(ans1,ans2), ans1 > ans2);
}
return 0;
}

1007. The Water Problem (hdu5443)

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

中文題意

給你一個長度爲$n$的序列,進行$q$次詢問,求區間$[l,r]$內最大值。

解題報告

直接把$Sparse Table$往上一套,聽說暴力也能過。

樣例代碼

1007view 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 <sparse.h>

/*
* Name : hdu5443.cpp
* Date : 2015年9月13日 上午9:01:38
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxn 1010
int a[maxn];

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

csl::sparse_table<int, csl::greater<int> > s;
s.build(a, n);

int m; scanf("%d", &m);
rep(i, 0, m) {
int x, y; scanf("%d%d", &x, &y);
int z = s.query(x - 1, y - 1);
printf("%d\n", z);
}
}
return 0;
}

1008. Elven Postman (hdu5444)

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

中文題意

一棵$n$個節點的二叉樹,從右往左編號爲$1 \dotsb n$,按高度從小到大告訴你節點的編號。
有$q$次詢問,求點$x_{i}$應該如何到達。

解題報告

區間內,根爲高度最低的節點,然後同理劃分左右子樹。
然後類似於二分搜索樹的思路,找到詢問的節點即可。

樣例代碼

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

/*
* Name : hdu5444.cpp
* Date : 2015年9月18日 下午4:20:29
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxn 1010
int a[maxn], b[maxn], c[maxn];

int dfs(int l, int r) {
if (l > r) return -1;
int x = l;
for (int i = l + 1; i <= r; ++i)
if (a[i] < a[x]) x = i;
b[x] = dfs(l, x - 1);
c[x] = dfs(x + 1, r);
return x;
}

//@ Main Function
int main() {
int _; scanf("%d", &_);
while (_--) {
int n; scanf("%d", &n);
rep(i, 0, n) {
int x; scanf("%d", &x);
a[x] = i + 1;
}
int r = dfs(1, n);

int q; scanf("%d", &q);
while (q--) {
int x; scanf("%d", &x);
int t = r;
while (t != x) {
printf("%c", t > x ? 'E' : 'W');
t = (t > x) ? b[t] : c[t];
}
printf("\n");
}
}
return 0;
}

1010. Unknown Treasure (hdu5446)

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

中文題意

給你$n,m,k$,以及$k$個質數$p_{i}$,模數$M = \prod_{i=1}^{k} p_{i}$,求$C_{n}^{m} \bmod M$

解題報告

  1. 對於每個$i$,用$Lucas$定理求$C_{n}^{m} \bmod p_{i}$
  2. 然後用$\text{Chinese Remainder Theorem}$合併這些結果

樣例代碼

1010view 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_math.h>

/*
* Name : hdu5446.cpp
* Date : 2015年9月18日 下午4:37:28
* Copyright : fateud.com
* Anti-Mage : The magic ends here.
*/


#define maxk 20
#define maxn 100010
ll a[maxk], fac[maxn];

ll com(ll n, ll m, ll mod) {
if (m > n) return 0;
return fac[n] * csl::inv(fac[m] * fac[n-m], mod) % mod;
}

ll lucas(ll n, ll m, ll mod) {
fac[0] = 1, fac[mod] = 0;
rep(i, 1, mod) fac[i] = fac[i-1] * i % mod;

ll res = 1;
while (m) {
res = res * com(n % mod, m % mod, mod) % mod;
n /= mod, m /= mod;
}
return res;
}

//@ Main Function
int main() {
int _; scanf("%d", &_);
while (_--) {
ll n, m; scanf(i64 i64, &n, &m);
int k; scanf("%d", &k);
rep(i, 0, k) scanf(i64, a+i);

ll M = 1; rep(i, 0, k) M *= a[i];
ll ans = 0;
rep(i, 0, k) {
ll p = lucas(n, m, a[i]);
ll q = M / a[i];
ans += csl::mul(p, csl::mul(q, csl::inv(q, a[i]), M), M);
ans %= M;
}
printf(i64 "\n", ans);
}
return 0;
}

後記

今朝是先父小生日,願逝者安息,生者堅強。

文章目录
  1. 1. 引言
  2. 2. 1001. Alisha’s Party (hdu5437)
    1. 2.1. 中文題意
    2. 2.2. 解題報告
    3. 2.3. 樣例代碼
  3. 3. 1002. Ponds (hdu5438)
    1. 3.1. 中文題意
    2. 3.2. 解題報告
    3. 3.3. 樣例代碼
  4. 4. 1003. Aggregated Counting (hdu5439)
    1. 4.1. 中文題意
    2. 4.2. 解題報告
    3. 4.3. 樣例代碼
  5. 5. 1005. Travel (hdu5441)
    1. 5.1. 中文題意
    2. 5.2. 解題報告
    3. 5.3. 樣例代碼
  6. 6. 1006. Favorite Donut (hdu5442)
    1. 6.1. 中文題意
    2. 6.2. 解題報告
    3. 6.3. 樣例代碼
  7. 7. 1007. The Water Problem (hdu5443)
    1. 7.1. 中文題意
    2. 7.2. 解題報告
    3. 7.3. 樣例代碼
  8. 8. 1008. Elven Postman (hdu5444)
    1. 8.1. 中文題意
    2. 8.2. 解題報告
    3. 8.3. 樣例代碼
  9. 9. 1010. Unknown Treasure (hdu5446)
    1. 9.1. 中文題意
    2. 9.2. 解題報告
    3. 9.3. 樣例代碼
  10. 10. 後記