首页 > 代码库 > cumt周练题解

cumt周练题解

cumt2017春季——周练(一)

A.CodeForces - 785A

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     cin >> n;
 7     map<string, int>ma;
 8     ma["Tetrahedron"] = 4;
 9     ma["Cube"] = 6;
10     ma["Octahedron"] = 8;
11     ma["Dodecahedron"] = 12;
12     ma["Icosahedron"] = 20;
13     int ans = 0;
14     for(int i = 0; i < n; i++)
15     {
16         string str;
17         cin >> str;
18         ans += ma[str];
19     }
20     cout << ans<< endl;
21     return 0;
22 }

 

B.CodeForces 785B

思路:

  这题小心一个坑,就是AB两节课,没说必须先上A,再上B。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 200000 + 5;
 4 const int INF = 0x3f3f3f3f;
 5 
 6 int main()
 7 {
 8     int n;
 9     scanf("%d", &n);
10     int minn1 = INF, maxx1 = -INF;
11     for (int i = 0; i < n; i++)
12     {
13         int x, y;
14         scanf("%d%d", &x, &y);
15         if(y < minn1)
16         {
17             minn1 = y;
18         }
19         if(x > maxx1)
20         {
21             maxx1 = x;
22         }
23     }
24     int m;
25     scanf("%d", &m);
26     int minn2 = INF, maxx2 = -INF;
27     for(int i = 0; i < m; i++)
28     {
29         int x, y;
30         scanf("%d%d", &x, &y);
31         if(y < minn2)
32         {
33             minn2 = y;
34         }
35         if(x > maxx2)
36         {
37             maxx2 = x;
38         }
39 
40     }
41 
42     int ans1 = maxx2 - minn1;
43     int ans2 = maxx1 - minn2;
44     if(ans1 < 0) ans1 = 0;
45     if(ans2 < 0)  ans2 = 0;
46     int ans = max(ans1, ans2);
47     printf("%d\n", ans);
48     return 0;
49 }

 

C.POJ 1064 (二分入门)

思路:

  简单二分,这题好像比较卡精度,所以用for循环多/2几次,而不用while

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <map>
 4 #include <set>
 5 #include <queue>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <iostream>
 9 using namespace std;
10 typedef long long LL;
11 const int INF = 0x3f3f3f3f;
12 #define mem0(x) memset(x,0,sizeof(x))
13 #define mem1(x) memset(x,-1,sizeof(x))
14 const long double eps = 1e-12;
15 
16 int N,K;
17 double L[10000+50];
18 bool C(double x)
19 {
20     int num = 0;
21     for(int i = 0; i < N; i++)
22     {
23         num += (int)(L[i]/x);
24     }
25     return num >= K;
26 }
27 int main()
28 {
29     while(~scanf("%d%d",&N,&K))
30     {
31         for(int i = 0; i < N; i++)
32             scanf("%lf",&L[i]);
33         double lb = 0, rb = INF;
34 
35         for(int i = 0; i < 100; i++)
36         {
37             double mid = (lb + rb) / 2;
38             if(C(mid))  lb = mid;
39             else rb = mid;
40         }
41         printf("%.2f\n",floor(lb*100) / 100);
42     }
43     return 0;
44 }

 

D.POJ 2456 (二分之最大化最小值)

思路:

  这题窝发现有几个同学没做出来呀,也是个很经典的二分问题,二分的重要用途,记住这几个字最大化最小值”,看到这种题可以拿二分做!!!可能你们被卡了 牛棚的距离数组 没有sort吧,它没说输入的时候就是递增的。

 1 #include <cstdio>
 2 #include <map>
 3 #include <set>
 4 #include <queue>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <iostream>
 8 #include <cmath>
 9 using namespace std;
10 typedef long long LL;
11 const int INF = 0x3f3f3f3f;
12 const int maxn = 100000 + 5;
13 
14 int n, m;
15 int x[maxn];
16 
17 bool judge(int d)
18 {
19     int last = 0, cur;
20     //第一头牛住在x[0]中了
21     for (int i = 1; i < m; i++)
22     {
23         cur = last + 1;
24         while (cur < n && x[cur] - x[last] < d)  cur++;
25         if (cur == n) return false;
26         last = cur;
27     }
28     return true;
29 }
30 int main()
31 {
32     scanf("%d%d", &n, &m);
33     for (int i = 0; i < n; i++)
34         scanf("%d", &x[i]);
35     sort(x, x + n);
36     int lb = 0, rb = INF;
37 
38     for (int i = 0; i < 100; i++)
39     {
40         int mid = (lb + rb) / 2;
41         if (judge(mid))  lb = mid;
42         else rb = mid;
43     }
44     printf("%d\n", lb);
45 
46     return 0;
47 }

 

E.UVA 11636 (水贪心?)

题意:

  经过复制/粘贴可以变成原来的两倍,求最小复制/粘贴次数。

 1 #include <stdio.h>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int mod = 1e9 + 7;
 5 const int maxn = 1000000 + 5;
 6 const int INF = 0x3f3f3f3f;
 7 typedef long long LL;
 8 typedef unsigned long long ull;
 9 
10 int main()
11 {
12     int n ,cas = 1;
13     while(~scanf("%d", &n))
14     {
15         if(n < 0)   break;
16 
17         int ans = 0, temp = 1;
18         while(n > temp)
19         {
20             temp <<= 1;
21             ans++;
22         }
23         printf("Case %d: %d\n", cas ++, ans);
24     }
25     return 0;
26 }

 

F.UVA 11039

题意:

  n个绝对值各不相同的非0整数,选出尽量多的数,排成一个序列,使得正负号交替且绝对值递增。

思路:

  按绝对值排序,然后间次输出正负数即可。

 1 #include <stdio.h>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int mod = 1e9 + 7;
 5 const int maxn = 500000 + 5;
 6 const int INF = 0x3f3f3f3f;
 7 typedef long long LL;
 8 typedef unsigned long long ull;
 9 
10 int a[maxn];
11 bool cmp(int &x, int &y)
12 {
13     return abs(x) < abs(y);
14 }
15 int main()
16 {
17     int t;
18     scanf("%d", &t);
19     while(t--)
20     {
21         int n;
22         scanf("%d", &n);
23         for(int i = 0; i < n; i++)
24         {
25             scanf("%d", &a[i]);
26         }
27         sort(a, a + n, cmp);
28         int last = a[0] > 0, len = 1;
29         for(int i = 1; i < n; i++)
30         {
31             int temp = a[i] > 0;
32             if(last != temp)
33             {
34                 last = temp;
35                 len++;
36             }
37         }
38         cout << len << "\n";
39     }
40     return 0;
41 }

 

G.UVA 11292 (简单贪心)

题意:

  n条恶龙,m个勇士,用勇士来杀恶龙。一个勇士只能杀一个恶龙。而且勇士只能杀直径不超过自己能力值的恶龙。每个勇士需要支付能力值一样的金币。问杀掉所有恶龙需要的最少金币。

思路:

  贪心,为每一条龙找一个恰好能杀他的骑士。简单贪心。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 20000 + 5;
 4 int n, m;
 5 int night[maxn], dragon[maxn];
 6 void solve()
 7 {
 8     int cost = 0;
 9     int cur = 0;
10     for(int i = 0; i < m; i++)
11     {
12         if(night[i] >= dragon[cur])
13         {
14             cost += night[i];
15             if(++cur == n)
16             {
17                 printf("%d\n", cost);
18                 return ;
19             }
20         }
21     }
22     printf("Loowater is doomed!\n");
23     return ;
24 }
25 int main()
26 {
27     while(~scanf("%d%d", &n, &m))
28     {
29         if(n + m == 0) break;
30         for(int i = 0; i < n; i++)
31             scanf("%d", &dragon[i]);
32         for(int j = 0; j < m; j++)
33             scanf("%d", &night[j]);
34         sort(dragon, dragon + n);
35         sort(night, night + m);
36         solve();
37     }
38     return 0;
39 }

 

H.UVA 11729 (经典贪心问题)

题意:

  n个任务,需要交代B分钟,执行J分钟,让你合理选择交代任务的次序,求得n个任务完成的最小总时长。

思路:

  经典贪心,通过比较俩俩的关系,得到整个序列的贪心排序方法。这个不明白可以问啊,虽然寒假讲过0 0.贪心套路。需要稍微理解一下sort函数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 10000 + 5;
 4 const int INF = 0x3f3f3f3f;
 5 int n, Cas;
 6 int sum[maxn];
 7 struct node
 8 {
 9     int j, b;
10     bool operator < (const node &other)const
11     {
12         return j > other.j;
13     }
14 }a[maxn];
15 void solve()
16 {
17     Cas ++;
18     sort(a, a + n);
19 
20     sum[0] = a[0].b;
21     for(int i = 1; i < n; i++)
22     {
23         sum[i] = sum[i - 1] + a[i].b;
24     }
25 
26     int maxx = 0;
27     for(int i = 0; i < n; i++)
28     {
29         sum[i] += a[i].j;
30         maxx = max(maxx, sum[i]);
31     }
32 
33     printf("Case %d: %d\n", Cas, maxx);
34 }
35 int main()
36 {
37     Cas = 0;
38     while(~scanf("%d", &n) && n)
39     {
40         for(int i = 0; i < n; i++)
41         {
42             scanf("%d%d", &a[i].b, &a[i].j);
43         }
44         solve();
45     }
46     return 0;
47 }

 

I.UVA 11300 (数学题)

题意:

  n个人围成一圈,每个人都有一些硬币,,每个人只能给左右相邻的人硬币,问最少交换几个硬币,使每个人硬币一样多;

思路:

  大白书上的例题我就不写题解了吧,不懂群里问,我给你po照片。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 1000000 + 5;
 5 const int INF = 0x3f3f3f3f;
 6 int n, Cas;
 7 LL a[maxn], c[maxn];
 8 
 9 int main()
10 {
11     while(~scanf("%d", &n))
12     {
13         LL sum = 0;
14         for(int i = 0; i < n; i++)
15         {
16             scanf("%lld", &a[i]);
17             sum += a[i];
18         }
19         LL ave = sum / n;
20         c[0] = a[0] - ave;
21         for(int i = 1; i < n; i++)
22         {
23             c[i] = c[i - 1] + a[i] - ave;
24         }
25         sort(c, c + n);
26         LL ans = 0, d = c[n / 2];
27         for(int i = 0; i < n; i++)
28         {
29             ans += abs(c[i] - d);
30         }
31         printf("%lld\n", ans);
32     }
33     return 0;
34 }

 

J.UVA 10881 (思维题)

题意:

  有很多只蚂蚁在一条直线上,每个蚂蚁移动速度都是1,并且有一个初始方向。并且当相邻两个蚂蚁相撞时转向。现在问t时间后各个蚂蚁的位置,及状态。

思路:

  需要理解:因为两只蚂蚁碰撞以后一起回头,所以结束以后和发生以前的蚂蚁之间的相对顺序是不变的。

 1 #include <stdio.h>
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int mod = 1e9 + 7;
 5 const int maxn = 10000 + 5;
 6 const int INF = 0x3f3f3f3f;
 7 typedef long long LL;
 8 typedef pair<int, int>pii;
 9 typedef pair<LL, LL>pLL;
10 typedef unsigned long long ull;
11 
12 struct node
13 {
14     int id, pos, d;//这个id是输入数据的顺序
15     bool operator < (const node &other)const
16     {
17         return pos < other.pos;
18     }
19 }before[maxn], after[maxn];
20 int order[maxn];//这个是蚂蚁在绳索上的相对顺序
21 const char dirName[][10] = {"L", "Turning", "R"};
22 
23 int main()
24 {
25     int Test;
26     scanf("%d", &Test);
27     for(int cas = 1; cas <= Test; cas++)
28     {
29         int L, T, n;
30         scanf("%d%d%d", &L, &T, &n);
31         for(int i = 0; i < n; i++)
32         {
33             int pos;
34             char dir;
35             scanf("%d %c", &pos, &dir);
36             int d = (dir == L) ? -1 : 1;//L -1  R 1
37             before[i] = {i, pos, d};
38             after[i] = {0, pos + T * d, d};
39         }
40 
41         sort(before, before + n);
42         for(int i = 0; i < n; i++)
43         {
44             order[before[i].id] = i;
45         }//order 记录 蚂蚁在绳索上的顺序
46 
47         sort(after, after + n);
48         for(int i = 0; i < n - 1; i++)
49         {
50             if(after[i].pos == after[i + 1].pos)    after[i].d = after[i + 1].d = 0;
51         }
52         printf("Case #%d:\n", cas);
53         for(int i = 0; i < n; i++)
54         {
55             int num = order[i];
56             if(after[num].pos < 0 || after[num].pos > L)    puts("Fell off");
57             else printf("%d %s\n", after[num].pos, dirName[after[num].d + 1]);
58         }
59         puts("");
60     }
61     return 0;
62 }

 

K.CodeForces 786A (博弈dp)

题意:

  有n个点围成一个圈,两个人。两个人分别有k1,k2个数,他们玩一个游戏。轮流进行,每个人可以选择一个数(每个数都可以被多次选择)并且把棋子前移这么多格,到达1号点胜利,问两个人分别从2-n开始是否必胜,必败或者会循环。n<=7000

思路:

  严格按照必胜必败态来考虑!!!

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 7000 + 5;
 4 
 5 int n, k1, k2;
 6 int cntPre[2][maxn], s[2][maxn];
 7 bool vis[2][maxn], lose[2][maxn], win[2][maxn];
 8 
 9 void  dfs(int turn , int cur)
10 {
11     for (int i = 0 ; i < (turn ^ 1 == 0 ? k1 : k2) ; i ++)//你上一个人是谁,所以是turn ^ 1
12     {
13         int nxt = (cur + n - s[turn ^ 1][i]) % n;//那么找到上一节点。
14         if (vis[turn^1][nxt]) continue;//如果上一个人在nxt处先手的状态已经被访问过了。continue
15 
16         if (lose[turn][cur])//如果当前态为从必败态,转移到必胜态
17             win[turn^1][nxt] = true;
18 
19         else if (--cntPre[turn^1][nxt] == 0 )//当前态为非必败态,如果上一个节点的的k个前继状态都是非必败的,那么转移到必败态。
20             lose[turn^1][nxt] = true;//转移到必败态
21         else continue;
22         vis[turn^1][nxt] = true;
23         dfs(turn^1, nxt);//迭下去
24     }
25 
26 }
27 
28 
29 int main()
30 {
31     scanf("%d", &n);
32     scanf("%d", &k1);
33     for (int i = 0; i < k1; i++)    scanf("%d", &s[0][i]);
34     scanf("%d", &k2);
35     for (int i = 0; i < k2; i++)    scanf("%d", &s[1][i]);
36 
37     for (int i = 0 ; i < n ; i ++)
38         cntPre[0][i] = k1 , cntPre[1][i] = k2;
39 
40     lose[0][0] = lose[1][0] = true;
41     vis[0][0] = vis[1][0] = true;
42     dfs(0,0),dfs(1,0);
43 
44 
45     int turn = 0;
46     for (int i = 1 ; i < n ; i++)
47     {
48         if(win[turn][i])   printf("Win");
49         else if(lose[turn][i]) printf("Lose");
50         else printf("Loop");
51         printf("%c", i == n - 1 ? \n :  );
52     }
53     turn ^= 1;
54     for (int i = 1 ; i < n ; i++)
55     {
56         if(win[turn][i])   printf("Win");
57         else if(lose[turn][i]) printf("Lose");
58         else printf("Loop");
59         printf("%c", i == n - 1 ? \n :  );
60     }
61     return 0;
62 }

 

L.CodeForces 786B (最短路+线段树)

题意:

  有n个点,m条路径。每条路径可以从一个点到一个点,也可以从一个区间到一个点,也可以从一个点到一个区间,都有一定的费用。求从s号点到达其他点的最小距离。 

数据:

  n,m<=100000.

思路:

  搞两棵线段树,然后可以把区间[l,r]和v之间连边e条的数量,利用二叉树,降到log(e)条,就能做了。就这样~,在纸上画画就明白了。

  set写的最短路很骚!!!。学习一发。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const LL INF = 1LL << 60;
  5 typedef pair<int,int> pii;
  6 
  7 const int maxn = 1e5 + 5;
  8 const int N = 9 * maxn;
  9 
 10 vector<int>ve;
 11 vector<pii>e[N];
 12 set<pair<LL, int>>hs;
 13 
 14 LL dis[N];
 15 int tot;
 16 int vis[N];
 17 int nd[2][N];
 18 
 19 
 20 void add(int u,int v,int w)
 21 {
 22     e[u].push_back({v, w});
 23 }
 24 
 25 void dijkstra(int s,int n)
 26 {
 27     for (int i = 1; i <= n; i++)
 28     {
 29         dis[i] = INF;
 30         vis[i] = 0;
 31     }
 32     dis[s]=0;
 33 
 34     for (int i = 1; i <= n; i++)
 35     {
 36         hs.insert({dis[i], i});
 37     }
 38 
 39     for (int i = 1; i <= n; i++)
 40     {
 41         int u = hs.begin()->second;
 42         hs.erase(hs.begin());
 43         vis[u] = 1;
 44         for (auto edges : e[u])
 45         {
 46             int v = edges.first, co = edges.second;
 47             if (dis[v] > dis[u] + co)
 48             {
 49                 hs.erase({dis[v], v});
 50                 dis[v]= dis[u] + co;
 51                 hs.insert({dis[v], v});
 52             }
 53         }
 54     }
 55 }
 56 
 57 
 58 void build(int p, int l, int r, int ty)
 59 {
 60     nd[ty][p] = ++tot;
 61     if (l == r)
 62     {
 63         if (ty == 0) add(nd[0][p], l, 0);
 64         else add(l, nd[1][p], 0);
 65         return;
 66     }
 67     int m = (l + r) >> 1;
 68     int lson = p << 1, rson = p << 1 | 1;
 69     build(lson, l, m, ty);
 70     build(rson, m + 1, r, ty);
 71 
 72     if (ty == 0)
 73     {
 74         add(nd[0][p], nd[0][lson],0);
 75         add(nd[0][p], nd[0][rson],0);
 76     }
 77     else
 78     {
 79         add(nd[1][lson], nd[1][p],0);
 80         add(nd[1][rson], nd[1][p],0);
 81     }
 82 }
 83 
 84 void modify(int p, int l, int r, int tl, int tr, int ty)
 85 {
 86     if (tl == l && tr == r) ve.push_back(nd[ty][p]);
 87     else
 88     {
 89         int m = (l + r) >> 1;
 90        int lson = p << 1, rson = p << 1 | 1;
 91 
 92         if (tr <= m) modify(lson , l, m, tl, tr, ty);
 93         else if (tl > m) modify(rson, m + 1, r, tl, tr, ty);
 94         else modify(lson, l, m, tl, m, ty), modify(rson, m + 1, r, m + 1, tr, ty);
 95     }
 96 }
 97 
 98 int main()
 99 {
100     int n, q, s;
101     scanf("%d%d%d", &n, &q, &s);
102 
103     tot = n+1;//??
104     //建出两颗线段树
105     build(1, 1, n, 0);
106     build(1, 1, n, 1);
107 
108     for(int i = 0;i < q; i++)
109     {
110         int ty, u, v, w, l, r;
111         scanf("%d", &ty);
112 
113         if (ty == 1)
114         {
115             scanf("%d%d%d", &v, &u, &w);
116             add(v, u, w);
117         }
118         else
119         {
120             scanf("%d%d%d%d", &v, &l, &r, &w);
121             ve.clear();
122             modify(1, 1, n, l, r, ty - 2);
123 
124             if (ty == 2)
125             {
126                 for (auto u : ve) add(v, u, w);
127             }
128             else
129             {
130                 for (auto u : ve) add(u, v, w);
131             }
132         }
133     }
134     dijkstra(s, tot-1);
135     for (int i = 1; i <= n; i++)
136     {
137         if (dis[i] >= INF) dis[i] = -1;
138         printf("%lld%c", dis[i], i == n ? \n :  );
139     }
140 }

 

 

M.CodeForces 786C (树状数组 or 主席树)

题意:

  给定n个数si,你要对这个序列分段,并且对于每个k(1<=k<=n)求出每段最多有k种不同的数的时候的最小分段数。  1<=si<=n<=100000

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 5;
 4 
 5 int n;
 6 int a[maxn];
 7 int c[maxn];
 8 int ans[maxn];
 9 int nxt[maxn];
10 vector<int>r[maxn];
11 int pos[maxn];//pos[i]:数字i出现的最早位置
12 
13 int lowbit(int x){return x & (-x);}
14 
15 void add(int x, int k)
16 {
17     while(x <= n + 1)
18     {
19         c[x] += k;
20         x += lowbit(x);
21     }
22 }
23 
24 int query(int x)
25 {
26     int ret = 0;
27     for(int i = 18; i >= 0; i--)
28     {
29         if(ret + (1 << i) <= n + 1 && c[ret + (1 << i)] < x)
30         {
31             x -= c[ret + (1 << i)];
32             ret += (1 << i);
33         }
34     }
35     return ret + 1;
36 }
37 int main()
38 {
39     scanf("%d", &n);
40     for(int i =1; i <= n; i++)
41     {
42         scanf("%d", &a[i]);
43     }
44     for(int i = 1; i <= n; i++)
45     {
46         pos[i] = n + 1;//置为n+1,表示数字i都没出现过
47     }
48     for(int i = n; i >= 1; i--)
49     {
50         nxt[i] = pos[a[i]];//数字a[i]下一次出现的位置
51         pos[a[i]] = i;//pos[j]: 找到每个数字j,即a[i],最早的出现位置
52     }
53     //用树状数组维护
54     for(int i = 1; i <= n; i++)
55     {
56         add(pos[i], 1);//给他们的位置加上1,树状数组维护以后,一段前缀和,就是这段区间中有几种数字了
57         r[1].push_back(i);//第1个位置往后跳i个不同的数字
58     }
59 
60     for(int i = 1; i <= n; i++)// 枚举r[i]。即 从第i个位置往后跳
61     {
62         for(auto d : r[i])//取出此时要从位置i跳出d个不同的数字。
63         {
64             int k = query(d + 1);//查询的时候要查d+1一个不同数字的位置,才是新一段的起始点k。如果查d的话,可能这段会少算一点长度。比如1 2 3 3 3 3 4,取三个不同的数字。实际上第一个区间可以去到1 2 3 3 3 3
65             ans[d]++;//每段最多有d种数字的划分方案的段数+1。
66             r[k].push_back(d);//第k个位置往后跳d步
67         }
68         add(i, -1);//第i个位置不会再有人跳过来了,因为至少跳一步,所以删除它的影响。
69         add(nxt[i], 1);//增加新的位置的影响。//因为树状数组维护的,所以同类数字只要且只能维护第一个。
70     }
71 
72     for(int i =1; i <= n; i++)
73     {
74         printf("%d%c", ans[i], i == n ? \n :  );
75     }
76 
77 
78     return 0;
79 }

 

cumt周练题解