2016CCPC东北地区大学生程序设计竞赛（2018年8月22日组队训练赛）

题目链接：http://acm.hdu.edu.cn/search.php?field=problem&key=2016CCPC%B6%AB%B1%B1%B5%D8%C7%F8%B4%F3%D1%A7%C9%FA%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC+-+%D6%D8%CF%D6%C8%FC&source=1&searchmode=source

A题题目：

题意：

　　生成一棵最小生成树，边权值为两个节点的最小公倍数。

思路：

　　由最小公倍数的和最大公约数的关系：lcm(a, b) = a * b / gcd(a, b)知，我们要使这棵树边权之和尽可能小，那么就要使的等号右边尽可能小，由于b是固定的（从1遍历到n），那么就只能使a / gcd(a,b)尽可能小。又因为我们知道任何数与1的最大公约数为1，且1/1=1，此时是lcm(a, b)是最小值（毕竟lcm(a, b)不可能为0嘛。

　　综上所述，将2~n都与1相连时所得到的结果最小。此时结果为

代码实现如下：

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long LL;
17 typedef pair<LL, LL> pLL;
18 typedef pair<LL, int> pli;
19 typedef pair<int, LL> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long uLL;
22 
23 #define lson i<<1
24 #define rson i<<1|1
25 #define lowbit(x) x&(-x)
26 #define bug printf("*********
");
27 #define debug(x) cout<<"["<<x<<"]" <<endl;
28 #define FIN freopen("D://code//in.txt", "r", stdin);
29 #define IO ios::sync_with_stdio(false),cin.tie(0);
30 
31 const double eps = 1e-8;
32 const int mod = 1e9 + 7;
33 const int maxn = 100000 + 7;
34 const double pi = acos(-1);
35 const int inf = 0x3f3f3f3f;
36 const LL INF = 0x3f3f3f3f3f3f3f3f;
37 
38 int t, n;
39 
40 int main() {
41     int icase = 0;
42     scanf("%d", &t);
43     while(t--) {
44         scanf("%d", &n);
45         printf("Case #%d: %lld
", ++icase, (LL) (n + 2) * (n - 1) / 2);
46     }
47     return 0;
48 }

B题题目：

题意：

　　给你A,B，让你找到所有满足A <= C <= B,A <= D <= B使得A / B + B / A <= C / D + D / C.

思路：

　　对于本题我们通过证明得到当C=A，D=B或D=A,C=B时才满足题目要求，证明如下：

代码实现如下：

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long LL;
17 typedef pair<LL, LL> pLL;
18 typedef pair<LL, int> pli;
19 typedef pair<int, LL> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long uLL;
22 
23 #define lson i<<1
24 #define rson i<<1|1
25 #define lowbit(x) x&(-x)
26 #define bug printf("*********
");
27 #define debug(x) cout<<"["<<x<<"]" <<endl;
28 #define FIN freopen("D://code//in.txt", "r", stdin);
29 #define IO ios::sync_with_stdio(false),cin.tie(0);
30 
31 const double eps = 1e-8;
32 const int mod = 1e9 + 7;
33 const int maxn = 100000 + 7;
34 const double pi = acos(-1);
35 const int inf = 0x3f3f3f3f;
36 const LL INF = 0x3f3f3f3f3f3f3f3f;
37 
38 int t;
39 LL a, b;
40 
41 int main() {
42     int icase = 0;
43     scanf("%d", &t);
44     while(t--) {
45         scanf("%lld %lld", &a, &b);
46         printf("Case #%d:
", ++icase);
47         if(a == b) printf("1
%lld %lld
", a, b);
48         else printf("2
%lld %lld
%lld %lld
", a, b, b, a);
49     }
50     return 0;
51 }

E题题目：

题意：

　　童年时的连连看~本题需要判断的是你第一步是否能够消掉一对相同的数，本题的消除条件为两个相同的数相连，或者两个相同的数在同一个边界（不可以第一行与第一列进行消除）。

思路：

　　直接进行模拟即可。

代码实现如下：

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long LL;
17 typedef pair<LL, LL> pLL;
18 typedef pair<LL, int> pli;
19 typedef pair<int, LL> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long uLL;
22 
23 #define lson i<<1
24 #define rson i<<1|1
25 #define lowbit(x) x&(-x)
26 #define bug printf("*********
");
27 #define debug(x) cout<<"["<<x<<"]" <<endl;
28 #define FIN freopen("D://code//in.txt", "r", stdin);
29 #define IO ios::sync_with_stdio(false),cin.tie(0);
30 
31 const double eps = 1e-8;
32 const int mod = 1e9 + 7;
33 const int maxn = 100000 + 7;
34 const double pi = acos(-1);
35 const int inf = 0x3f3f3f3f;
36 const LL INF = 0x3f3f3f3f3f3f3f3f;
37 
38 int t, n, m;
39 int mp[35][35], vis[4][1007];
40 
41 bool check() {
42     for(int i = 0; i < n; i++) {
43         for(int j = 1; j < m; j++) {
44             if(mp[i][j] == mp[i][j-1]) return true;
45         }
46     }
47     for(int j = 0; j < m; j++) {
48         for(int i = 1; i < n; i++) {
49             if(mp[i][j] == mp[i-1][j]) return true;
50         }
51     }
52     return false;
53 }
54 
55 int main() {
56     scanf("%d", &t);
57     int icase = 0;
58     while(t--) {
59         memset(vis, 0, sizeof(vis));
60         scanf("%d%d", &n, &m);
61         for(int i = 0; i < n; i++) {
62             for(int j = 0; j < m; j++) {
63                 scanf("%d", &mp[i][j]);
64             }
65         }
66         int flag = 0;
67         for(int i = 0; i < m; i++) {
68             vis[0][mp[0][i]]++;
69             vis[1][mp[n-1][i]]++;
70             if(vis[0][mp[0][i]] >= 2 || vis[1][mp[n-1][i]] >= 2) {
71                 flag = 1;
72             }
73         }
74         for(int i = 0; i < n; i++) {
75             vis[2][mp[i][0]]++;
76             vis[3][mp[i][m-1]]++;
77             if(vis[2][mp[i][0]] >= 2 || vis[3][mp[i][m-1]] >= 2) {
78                 flag = 1;
79             }
80         }
81         if(check()) {
82             flag = 1;
83         }
84         if(flag) printf("Case #%d: Yes
", ++icase);
85         else printf("Case #%d: No
", ++icase);
86     }
87     return 0;
88 }

F题题面：

题意：

　　给你一棵有n个节点的树，有q次查询，每次查询告诉你k个不重要的点的编号，要求你统计：

　　　　1.重要节点的个数；

　　　　2.是两个重要节点的LCA的节点个数。

　　上述两种统计的节点不会重复。

思路：

　　本题初看会以为需要求LCA，但是很显然这么大的数据，如果求LCA的话妥妥的T，因此我们得换个思路。

　　我们知道对于节点u，如果它的至少有两个子节点（互不相同）的子孙节点有重要节点，那么这个节点就一定满足第二个条件。

　　因此我们对于每次查询，我们先将这k个数按照他们的深度进行排序，如果某一个不重要它的子节点中没有重要节点，那么这个节点就不用考虑，且相当于父亲节点少了一个子节点；当它的子节点中的重要节点数大于等于2，那么这个节点需要进行统计，且它的父亲节点不需要减少子节点。

代码实现如下：

  1 #include <set>
  2 #include <map>
  3 #include <queue>
  4 #include <stack>
  5 #include <cmath>
  6 #include <bitset>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 typedef long long LL;
 17 typedef pair<LL, LL> pLL;
 18 typedef pair<LL, int> pli;
 19 typedef pair<int, LL> pil;;
 20 typedef pair<int, int> pii;
 21 typedef unsigned long long uLL;
 22 
 23 #define lson i<<1
 24 #define rson i<<1|1
 25 #define lowbit(x) x&(-x)
 26 #define bug printf("*********
");
 27 #define debug(x) cout<<"["<<x<<"]" <<endl;
 28 #define FIN freopen("D://code//in.txt", "r", stdin);
 29 #define IO ios::sync_with_stdio(false),cin.tie(0);
 30 
 31 const double eps = 1e-8;
 32 const int mod = 1e9 + 7;
 33 const int maxn = 100000 + 7;
 34 const double pi = acos(-1);
 35 const int inf = 0x3f3f3f3f;
 36 const LL INF = 0x3f3f3f3f3f3f3f3f;
 37 
 38 int t, n, q, u, v, tot, k, ans;
 39 int num[maxn], sz[maxn], vis[maxn], head[maxn];
 40 int fa[maxn],dep[maxn],cnt[maxn];
 41 
 42 struct Edge {
 43     int v, next;
 44 }ed[maxn<<1];
 45 
 46 void init() {
 47     tot = 0;
 48     for(int i = 0; i < maxn; i++) fa[i] = i;
 49     memset(sz, 0, sizeof(sz));
 50     memset(vis, 0, sizeof(vis));
 51     memset(head, -1, sizeof(head));
 52 }
 53 
 54 void addedge(int u, int v) {
 55     ed[tot].v = v;
 56     ed[tot].next = head[u];
 57     head[u] = tot++;
 58     ed[tot].v = u;
 59     ed[tot].next = head[v];
 60     head[v] = tot++;
 61 }
 62 
 63 void dfs(int u, int p,int d) {
 64     sz[u] = 0;
 65     fa[u] = p;
 66     dep[u] = d;
 67     for(int i = head[u]; ~i; i = ed[i].next) {
 68         int v = ed[i].v;
 69         if(v != p) {
 70             sz[u]++;
 71             dfs(v, u, d+1);
 72         }
 73     }
 74 }
 75 
 76 struct node {
 77     int v,dep;
 78 }qu[maxn];
 79 
 80 int cmp(node a,node b){
 81     return a.dep>b.dep;
 82 }
 83 
 84 int main() {
 85     scanf("%d", &t);
 86     int icase = 0;
 87     while(t--) {
 88         scanf("%d%d", &n, &q);
 89         init();
 90         for(int i = 1; i < n; i++) {
 91             scanf("%d%d", &u, & v);
 92             addedge(u, v);
 93         }
 94         dfs(1, 0,1);
 95         printf("Case #%d:
", ++icase);
 96         while(q--) {
 97             scanf("%d", &k);
 98             ans = n - k;
 99             for(int i = 1; i <= k; i++) {
100                 scanf("%d", &qu[i].v);
101                 qu[i].dep = dep[qu[i].v];
102             }
103             sort(qu+1,qu+1+k,cmp);
104             for (int i = 1; i <= k; i++) {
105                 if (sz[qu[i].v] - vis[qu[i].v] >= 2) ans++;
106                 else if (sz[qu[i].v] - vis[qu[i].v] == 0)  vis[fa[qu[i].v]]++;
107             }
108             for(int i = 1; i <= k; i++) {
109                 vis[qu[i].v] = 0;
110                 vis[fa[qu[i].v]] = 0;
111             }
112             printf("%d
", ans);
113         }
114     }
115     return 0;
116 }

H题题目：

题意：

　　模拟栈。

思路：

　　直接模拟即可，对于每次query，我们可以通过找规律发现，只需统计当前栈栈底第一个0下方有多少个1，因为当1上方有0，且0上面有数，那么0及其上方的数进行操作后一定为1，然后对于下方的1奇偶进行讨论即可，具体情况请看代码。

代码实现如下：

  1 #include <set>
  2 #include <map>
  3 #include <queue>
  4 #include <stack>
  5 #include <cmath>
  6 #include <bitset>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 typedef long long LL;
 17 typedef pair<LL, LL> pLL;
 18 typedef pair<LL, int> pli;
 19 typedef pair<int, LL> pil;;
 20 typedef pair<int, int> pii;
 21 typedef unsigned long long uLL;
 22 
 23 #define lson i<<1
 24 #define rson i<<1|1
 25 #define lowbit(x) x&(-x)
 26 #define bug printf("*********
");
 27 #define debug(x) cout<<"["<<x<<"]" <<endl;
 28 #define FIN freopen("D://code//in.txt", "r", stdin);
 29 #define IO ios::sync_with_stdio(false),cin.tie(0);
 30 
 31 const double eps = 1e-8;
 32 const int mod = 1e9 + 7;
 33 const int maxn = 100000 + 7;
 34 const double pi = acos(-1);
 35 const int inf = 0x3f3f3f3f;
 36 const LL INF = 0x3f3f3f3f3f3f3f3f;
 37 
 38 int t, n;
 39 char s[10];
 40 int a[400007];
 41 multiset<int> st;
 42 multiset<int>::iterator it;
 43 
 44 void solve() {
 45     int nw = 0, l = 200000, r = 200000, sz = 0;
 46     while(n--) {
 47         scanf("%s", s);
 48         if(s[2] == 'S') {
 49             int x;
 50             sz++;
 51             scanf("%d", &x);
 52             if(nw & 1) {
 53                 a[--l] = x;
 54                 if(x == 0) st.insert(l);
 55             } else {
 56                 if(x == 0) st.insert(r);
 57                 a[r++] = x;
 58             }
 59         } else if(s[2] == 'P') {
 60             if(l == r) continue;
 61             sz--;
 62             if(nw & 1) {
 63                 st.erase(l);
 64                 l++;
 65             } else {
 66                 r--;
 67                 st.erase(r);
 68             }
 69         } else if(s[2] == 'V') {
 70             nw++;
 71         } else {
 72             if(l == r) {
 73                 printf("Invalid.
");
 74                 continue;
 75             }
 76             if(r-l == 1) {
 77                 printf("%d
", a[l]);
 78                 continue;
 79             }
 80             int sum;
 81             if(st.empty()) {
 82                 sum = r - l;
 83                 if(sum & 1) printf("1
");
 84                 else printf("0
");
 85             } else {
 86                 if(nw & 1) {
 87                     int k = *--st.end();
 88                     sum = r - k - 1;
 89                 } else {
 90                     int k = *st.begin();
 91                     sum = k - l;
 92                 }
 93                 if(sum == sz - 1) {
 94                     if(sum & 1) printf("1
");
 95                     else printf("0
");
 96                 } else {
 97                     if(sum & 1) printf("0
");
 98                     else printf("1
");
 99                 }
100             }
101         }
102     }
103 }
104 
105 int main() {
106     //FIN;
107     int icase = 0;
108     scanf("%d", &t);
109     while(t--) {
110         st.clear();
111         printf("Case #%d:
", ++icase);
112         scanf("%d", &n);
113         solve();
114     }
115     return 0;
116 }

J题题目：

题意：

　　你要穿过长度为d的区域，你每秒会被攻击掉A的血量，当你某一秒的血量小于0时你将死亡（刚好等于0时不会死亡）。你初始时的血量、速度、血量恢复值都为0，但是你可以随时花费G1的钱来增加1单位的血，G2的钱来增加1单位的速度（不能大于d），G3的钱来增加G3的恢复速度，问你能通过这片区域的最小花费。

思路：

　　这就是一个贪心模拟，不是很懂这题为什么给18s的时限……你肯定是在出发时将三个的属性提高到一定的值再出发时最优，然后你通过这片区域可以有两种方法，一种是你的速度足够快，在到达终点时血量仍然大于等于0，另一种方法是你每秒减少的血量恰好等于你每秒恢复的血量值。我们可以进行枚举速度从1到d，然后将这两种方法进行比较取最小值。（ps.这题貌似卡中间过程的精度，很烦。）

代码实现如下：

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long LL;
17 typedef pair<LL, LL> pLL;
18 typedef pair<LL, int> pli;
19 typedef pair<int, LL> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long uLL;
22 
23 #define lson i<<1
24 #define rson i<<1|1
25 #define lowbit(x) x&(-x)
26 #define bug printf("*********
");
27 #define debug(x) cout<<"["<<x<<"]" <<endl;
28 #define FIN freopen("D://code//in.txt", "r", stdin);
29 #define IO ios::sync_with_stdio(false),cin.tie(0);
30 
31 const double eps = 1e-8;
32 const int mod = 1e9 + 7;
33 const int maxn = 100000 + 7;
34 const double pi = acos(-1);
35 const int inf = 0x3f3f3f3f;
36 const LL INF = 0x3f3f3f3f3f3f3f3f;
37 
38 int t, d, a, g1, g2, g3;
39 
40 int main() {
41     //FIN;
42     int icase = 0;
43     scanf("%d", &t);
44     while(t--) {
45         scanf("%d%d%d%d%d", &d, &a, &g1, &g2, &g3);
46         LL ans = INF;
47         for(int i = 1; i <= d; i++) {
48             double pp = 1.0 * d / i;
49             LL cnt1 = 1LL*ceil(pp * a)*g1;
50             LL cnt2 = 1LL * a * (g1 + g3);
51             LL tmp = cnt1 + 1LL * i * g2;
52             ans = min(tmp, ans);
53             ans = min(ans, cnt2 + 1LL * i * g2);
54         }
55         printf("Case #%d: %lld
", ++icase, ans);
56     }
57     return 0;
58 }

2016CCPC东北地区大学生程序设计竞赛 （2018年8月22日组队训练赛）

2016CCPC东北地区大学生程序设计竞赛（2018年8月22日组队训练赛）