ACM-ICPC 2015 Changchun Preliminary Contest ABEGHJ

A Alisha's Party

Princess Alisha invites her friends to come to her birthday party. Each of her friends will bring a gift of some value

Each time when Alisha opens the door, she can decide to let

If there are two friends who bring gifts of the same value, then the one who comes first should enter first. Given a query

Input Format

The first line of the input gives the number of test cases,

In each test case, the first line contains three numbers

The $B_iBi, which consists of no more than 200200 English characters, and an integer v_i, 1 le v_i le 10^8vi, 1≤vi≤108, separated by a blank. B_iBi is the name of the ii−th person coming to Alisha's party and B_iBi brings a gift of value v_ivi.$

Each of the following

The last line of each test case will contain $n_1, ..., n_qn1, ..., nq separated by a space, which means Alisha wants to know who are the n_1-th, ..., n_q-thn1−th, ..., nq−th friends to enter her castle.$

Note: there will be at most two test cases containing

Output Format

For each test case, output the corresponding name of Alisha's query, separated by a space.

样例输入

1
5 2 3
Sorey 3
Rose 3
Maltran  3
Lailah 5
Mikleo  6
1 1
4 2
1 2 3

样例输出

Sorey Lailah Rose


模拟题

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 150010;
 5 int n, m, t, x, k, q;
 6 struct Nod{
 7     char s[201];
 8     int id, v;
 9     bool friend operator < (const Nod &a , const Nod &b) {
10         return ((a.v == b.v && a.id > b.id) || (a.v < b.v));
11     }
12 }e[N];
13 struct Node{
14     int t, p;
15     bool friend operator < (const Node &a, const Node &b) {
16         return a.t < b.t;
17     }
18 }b[N];
19 Nod str[50000];
20 int main() {
21     cin >> t;
22     priority_queue<Nod> que;
23     while(t--) {
24         while(que.size()) que.pop();
25         cin >> k >> m >> q;
26         for(int i = 1; i <= k; i ++) {
27             cin >> e[i].s >> e[i].v;
28             e[i].id = i;
29         }
30         for(int i = 0; i < m; i ++) {
31             scanf("%d%d",&b[i].t,&b[i].p);
32         }
33         sort(b,b+m);
34         int cnt = 1, cnt1 = 1;
35         for(int i = 0; i < m; i ++) {
36             while(cnt <= b[i].t) que.push(e[cnt++]);
37             for(int j = 0; j < b[i].p; j ++) {
38                 if(que.empty()) break;
39                 str[cnt1++] = que.top(), que.pop();
40             }
41         }
42         while(cnt <= k) que.push(e[cnt++]);
43         while(que.size()) str[cnt1++] = que.top(), que.pop();
44         for(int i = 1; i <= q; i ++) {
45             scanf("%d", &x);
46             printf("%s%c",str[x].s," 
"[i==q]);
47         }
48     }
49     return 0;
50 }

B Ponds

Betty owns a lot of ponds, some of them are connected with other ponds by pipes, and there will not be more than one pipe between two ponds. Each pond has a value

Now Betty wants to remove some ponds because she does not have enough money. But each time when she removes a pond, she can only remove the ponds which are connected with less than two ponds, or the pond will explode.

Note that Betty should keep removing ponds until no more ponds can be removed. After that, please help her calculate the sum of the value for each connected component consisting of a odd number of ponds

Input Format

The first line of input will contain a number

For each test case, the first line contains two number separated by a blank. One is the number $10^4)p(1≤p≤104)which represents the number of ponds she owns, and the other is the number m(1 le m le 10^5)m(1≤m≤105) which represents the number of pipes.$

The next line contains $v_1, ..., v_pv1, ..., vp, where v_i(1 le v_i le 10^8)vi(1≤vi≤108) indicating the value of pond ii.$

Each of the last

Output Format

For each test case, output the sum of the value of all connected components consisting of odd number of ponds after removing all the ponds connected with less than two pipes.

样例输入

1
7 7
1 2 3 4 5 6 7
1 4
1 5
4 5
2 3
2 6
3 6
2 7

样例输出

dfs搜索下就行。

 1 #include <bits/stdc++.h>
 2 #define ll unsigned     long long
 3 using namespace std;
 4 const int N = 10010;
 5 int n, m, t, u, v, p, cnt;
 6 ll a[N];
 7 std::vector<int> vs[N], vv;
 8 int vis[N], vis1[N];
 9 
10 bool ok(int x) {
11     int ans = 0;
12     for(auto u : vs[x]) {
13         if(!vis[u]) ans++;
14     }
15     return ans < 2;
16 }
17 
18 void dfs(int v) {
19     vis[v] = 1;
20     for(auto u : vs[v]) {
21         if(!vis[u]&&ok(u)) dfs(u);
22     }
23 }
24 void dfs1(int v) {
25     vis1[v] = 1;
26     for(auto u : vs[v]) {
27         if(!vis[u]&&!vis1[u]) {
28             vv.push_back(u);
29             dfs1(u);
30         }
31     }
32 }
33 
34 int main() {
35     cin >> t;
36     while(t--) {
37         memset(vis, 0, sizeof(vis));
38         memset(vis1, 0, sizeof(vis1));
39         cin >> p >> m;
40         for(int i = 1; i <= p; i ++) scanf("%lld", &a[i]);
41         for(int i = 0; i < m; i ++) {
42             scanf("%d%d", &v, &u);
43             vs[v].push_back(u);
44             vs[u].push_back(v);
45         }
46         for(int i = 1; i <= p; i ++) {
47             if(!vis[i]&&ok(i)) dfs(i);
48         }
49         // for(int i = 1; i <= p; i ++) printf("%d ",vis[i]);printf("
");
50         for(int i = 1; i <= p; i ++) {
51             if(!vis[i]&&!vis1[i]) {
52                 vv.clear();
53                 vv.push_back(i);
54                 dfs1(i);
55                 // printf("-=%d-=
", vv.size());
56                 if(vv.size()%2 == 0) {
57                     for(int j = 0; j < vv.size(); j ++) vis1[vv[j]] = 2;
58                 }
59             }
60         }
61         // for(int i = 1; i <= p; i ++) printf("%d ",vis1[i]);printf("
");
62         ll ans = 0;
63         for(int i = 1; i <= p; i ++) if(vis1[i]==1) ans += a[i];
64         printf("%lld
",ans);
65         for(int i = 1; i <= p; i ++) vs[i].clear();
66     }
67     return 0;
68 }

E Travel

Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are

Input Format

The first line contains one integer

For each test case, the first line consists of three integers

Each of the following

Then

Output Format

You should print

Each of them contains one integer as the number of pair of cities

Note that

样例输入

样例输出

2
6
12

先预处理下，排下序，假设选取前面 i 个的答案是多少，计算出来。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 int n, m, t, q, x, y, sum[N], fa[N], cnt[N];
 6 set<int> st;
 7 struct Nod{
 8     int from, to, w;
 9 }e[N];
10 bool cmp(Nod a, Nod b) {
11     return a.w < b.w;
12 }
13 int find(int x) {
14     return fa[x] = (fa[x] == x ?x: find(fa[x]));
15 }
16 void unite(int x, int y) {
17     x = find(x), y = find(y);
18     if(x > y) fa[x] = y;
19     else fa[y] = x;
20 }
21 int bin(int x) {
22     int l = 1, r = m;
23     while(l < r) {
24         int mid = (l+r)>>1;
25         if(e[mid].w <= x) l = mid+1;
26         else r = mid;
27     }
28     return r-1;
29 }
30 
31 int main() {
32     cin >> t;
33     while(t--) {
34         scanf("%d%d%d", &n, &m, &q);
35         st.clear();
36         for(int i = 1; i <= n; i ++) fa[i] = i, cnt[i] = 1;
37         for(int i = 1; i <= m; i ++) scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);
38         sort(e+1,e+1+m,cmp);
39         for(int i = 1; i <= m; i ++) {
40             x = find(e[i].from), y = find(e[i].to);
41             if(x != y) {
42                 sum[i] = sum[i-1];
43                 if(st.count(x)) sum[i] -= cnt[x]*(cnt[x]-1);
44                 if(st.count(y)) sum[i] -= cnt[y]*(cnt[y]-1);
45                 sum[i] += (cnt[x]+cnt[y])*(cnt[x]+cnt[y]-1);
46                 st.insert(min(x,y));
47                 st.erase(max(x,y));
48                 cnt[min(x,y)] += cnt[max(x,y)];
49                 cnt[max(x,y)] = 0;
50                 unite(x,y);
51             } else sum[i] = sum[i-1];
52         }
53         // for(int i = 1; i <= m; i ++) printf("%d ",sum[i]);printf("
");
54         while(q--) {
55             scanf("%d", &x);
56             if(x >= e[m].w) printf("%d
",sum[m]);
57             else printf("%d
",sum[bin(x)]);
58         }
59     }
60     return 0;
61 }

G The Water Problem

In Land waterless, water is a very limited resource. People always fight for the biggest source of water.

Given a sequence of water sources with $a_1, a_2, a_3, ..., a_na1, a2, a3, ..., an representing the size of the water source.$

Given a set of queries each containing $a_laland a_rar.$

Input Format

First you are given an integer

For each test case, there is a number

$a_1, a_2, a_3, ..., a_na1, a2, a3, ..., an, and each integer is in {1, ..., 10^6}{1, ..., 106}.$

On the next line, there is a number

After that, there will be

Output Format

For each query, output an integer representing the size of the biggest water source.

样例输入

样例输出

100
2
3
4
4
5
1
999999
999999
1

板子题，求区间最大。

 1 #include <iostream>
 2 #include <cstdio>
 3 #define lson l, m, rt<<1
 4 #define rson m+1,r, rt<<1|1
 5 
 6 using namespace std;
 7 const int maxn = 1e5+2;
 8 int MAX[maxn<<2];
 9 int max(int a, int b){
10     return a>b?a:b;
11 }
12 void PushDP(int rt){
13     MAX[rt] = max(MAX[rt<<1], MAX[rt<<1|1]);
14 }
15 void build(int l, int r, int rt){
16     if(l == r){
17         scanf("%d",&MAX[rt]);
18         return;
19     }
20     int m = (l + r) >> 1;
21     build(lson);
22     build(rson);
23     PushDP(rt);
24 }
25 void update(int x, int y, int l, int r, int rt){
26     if ( l == r){
27         MAX[rt] = y;
28         return ;
29     }
30     int m = (l + r) >> 1;
31     if(x <= m) update(x, y, lson);
32     else update(x, y, rson);
33     PushDP(rt);
34 }
35 int Query(int L, int R, int l, int r, int rt){
36     if(L <= l && R >= r){
37         return MAX[rt];
38     }
39     int m = (l + r) >> 1;
40     int ret = 0;
41     if( m >= L) ret = max(ret, Query(L, R ,lson));
42     if( m < R) ret = max(ret, Query(L, R, rson));
43     return ret;
44 }
45 int main()
46 {
47     int t, n, m, q, l, r;
48     cin >> t;
49     while(t--){
50         cin >> n;
51         build(1, n, 1);
52         cin >> q;
53         while(q--) {
54             cin >> l >> r;
55             printf("%d
",Query(l, r, 1, n, 1));
56         }
57     }
58     return 0;
59 }

H Elven Postman

131072K

Elves are very peculiar creatures. As we all know, they can live for a very long time and their magical prowess are not something to be taken lightly. Also, they live on trees. However, there is something about them you may not know. Although delivering stuffs through magical teleportation is extremely convenient (much like emails). They still sometimes prefer other more “traditional” methods.

So, as a elven postman, it is crucial to understand how to deliver the mail to the correct room of the tree. The elven tree always branches into no more than two paths upon intersection, either in the east direction or the west. It coincidentally looks awfully like a binary tree we human computer scientist know. Not only that, when numbering the rooms, they always number the room number from the east-most position to the west. For rooms in the east are usually more preferable and more expensive due to they having the privilege to see the sunrise, which matters a lot in elven culture.

Anyways, the elves usually wrote down all the rooms in a sequence at the root of the tree so that the postman may know how to deliver the mail. The sequence is written as follows, it will go straight to visit the east-most room and write down every room it encountered along the way. After the first room is reached, it will then go to the next unvisited east-most room, writing down every unvisited room on the way as well until all rooms are visited.

Your task is to determine how to reach a certain room given the sequence written on the root.

For instance, the sequence

Input Format

First you are given an integer

For each test case, there is a number $a_1, ..., a_na1, ..., an where a_1, ..., a_nin {1, ..., n}a1, ..., an∈{1, ..., n}.$

On the next line, there is a number

After that, there will be $x_1, ..., x_qx1, ..., xq indicating the destination room number of each mail.$

Output Format

For each query, output a sequence of move (

Note that for simplicity, we assume the postman always starts from the root regardless of the room he had just visited.

样例输入

2
4
2 1 4 3
3
1 2 3
6
6 5 4 3 2 1
1
1

样例输出

E

WE
EEEEE

二叉排序树的建立与查找，找过的点就不需要找了。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1010;
 5 int t, n, q, x;
 6 struct Nod{
 7     int num;
 8     bool is;
 9     Nod *lchild, *rchild;
10     Nod() {
11         num = -1;
12         is = false;
13         lchild = rchild = NULL;
14     }
15 };
16 void mkTree(Nod *p, int val) {
17     if(p->num == -1) {
18         p->num = val;
19         return;
20     }
21     if(p->num > val) {
22         if(p->rchild==NULL)p->rchild = new Nod;
23         mkTree(p->rchild,val);
24     } else {
25         if(p->lchild==NULL)p->lchild = new Nod;
26         mkTree(p->lchild,val);
27     }
28 }
29 void find(Nod *p, int x) {
30     if(p->num == x) {
31         if(!p->is) {
32             p->is = true;
33             return;
34         }
35     }
36     if(p->num > x) {
37         printf("E");
38         find(p->rchild,x);
39     } else {
40         printf("W");
41         find(p->lchild, x);
42     }
43 }
44 int main() {
45     cin >> t;
46     while(t--) {
47         scanf("%d", &n);
48         Nod *root = new Nod;
49         for(int i = 1; i <= n; i ++) {
50             scanf("%d", &x);
51             mkTree(root,x);
52         }
53         scanf("%d", &q);
54         while(q--) {
55             scanf("%d", &x);
56             find(root,x);printf("
");
57         }
58     }
59     return 0;
60 }

J Unknown Treasure

131072K

On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some numbers on it. After quite a research, the mathematician found out that the correct combination to the lock would be obtained by calculating how many ways are there to pick

Input Format

On the first line there is an integer

Each test case starts with three integers $10^{18}, 1le kle 10)n, m, k(1≤m≤n≤1018, 1≤k≤10) on a line where kk is the number of primes.$

Following on the next line are $p_1, ..., p_kp1, ..., pk. It is guaranteed that M=p_1 imes p_2 imes cdots imes p_kle 10^{18}M=p1×p2×⋯×pk≤1018 and p_ile 10^5pi≤105 for every iin{1, ..., k}i∈{1, ..., k}.$

Output Format

For each test case output the correct combination on a line.

样例输入

1
9 5 2
3 5

样例输出

6

求C(n,m)%M  M = p1*p2..*pk   Lucas定理。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 15;
 5 ll qmul(ll a,ll p,ll m){
 6     ll tmp = 0;
 7     while(p){
 8         if(1&p) tmp = (tmp+a)%m;
 9         a = (a+a)%m;
10         p>>=1;
11     }
12     return tmp;
13 }
14 void exgcd(ll a,ll b,ll &x,ll &y,ll &d){
15     if(!b) d=a,x = 1,y=0;
16     else exgcd(b,a%b,y,x,d),y-=(a/b)*x;
17 }
18 ll inv(ll a,ll p){
19     ll x,y,d;
20     exgcd(a,p,x,y,d);
21     return d==1?(x+p)%p:-1;
22 }
23 ll fat(ll x,ll p){
24     ll ans = 1;
25     for( int i = 2 ; i <= x ; i ++ ) ans = ( ans * i ) % p;
26     return ans;
27 }
28 ll c(ll n,ll m,ll p){
29     if (m < 0 || m > n) return 0; 
30     return fat(n,p)*inv(fat(m,p),p)%p*inv(fat(n-m,p),p)%p;
31 }
32 ll crt(ll *a,ll *m,int n){
33     ll M = 1,res = 0;
34     for( int i = 0 ; i < n ; i++ ) M*=m[i];
35     for( int i = 0 ; i < n ; i++ ){
36         ll w = M/m[i];
37         res = (res+qmul(w*inv(w,m[i]),a[i],M))%M;
38     }
39     return (res+M)%M;
40 }
41 ll Lucas(ll n,ll m,ll p){
42     return m?Lucas(n/p,m/p,p)*c(n%p,m%p,p)%p:1;
43 }
44 int main() {
45     ll a[N], p[N];
46     ll t, n, m, k;
47     cin >> t;
48     while(t--) {
49         cin >> n >> m >> k;
50         for(int i = 0; i < k; i ++) {
51             cin >> p[i];
52             a[i] = Lucas(n, m, p[i]);
53         }
54         printf("%lld
",crt(a, p, k));
55     }
56     return 0;
57 }