L2-017. 人以群分

題意：

給定n個正整數， 然后分成規模相差盡可能接近的兩類， 這兩類之和相差要盡可能大

分析：

直接排序， 然后分成兩部分即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[123456];
 4 int sum(int l , int r){
 5     int ans = 0;
 6     for(int i = l; i <= r; i++) ans += a[i];
 7     return ans;
 8 }
 9 int main()
10 {
11     int n;
12     scanf("%d", &n);
13     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
14     sort(a + 1, a + n + 1);
15     int mid = n / 2;
16     printf("Outgoing #: %d
Introverted #: %d
Diff = %d
",n-mid, mid, sum(mid+1, n) - sum(1,mid));
17     return 0;
18 }

人以群分

L2-019. 悄悄關注

題意：

給定一個關注列表， 然后再給出一個對每個用戶的點贊數， 如果有一個對某一個用戶的點贊數大于平均值而且該用戶不在關注列表中， 輸出。

分析：

用一個set保存關注列表， 用一個map去儲存用戶點贊數， 最后遍歷一次map即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 set<string> focus; //關注列表
 4 map<string, int > like; //點贊數
 5 int main()
 6 {
 7     int n, m;
 8     cin >> n;
 9     string temp;
10     for(int i = 0; i < n; i++){
11         cin >> temp;
12         focus.insert(temp);
13     }
14     double sum = 0;
15     int a;
16     cin >> m;
17     for(int i = 0; i < m; i++){
18         cin >> temp >> a;
19         like[temp] += a;
20         sum += a;
21     }
22     sum /= (double)m;
23     int flag = 0;
24     for(auto it = like.begin(); it != like.end(); it++){
25         if(it->second > sum && !focus.count(it->first)) {
26                 flag = 1;
27                 cout << it->first << "
";
28         }
29     }
30     if(!flag) cout << "Bing Mei You
";
31 }

悄悄關注

L2-020. 功夫傳人

題意：

給定一個師傅徒弟家譜，每個師傅可以收很多個徒弟， 每個徒弟只能有一個師傅， 然后一開始有一個祖師爺有功力值Z。每代傳遞會有一個損耗r，徒弟有可能出現“得道者”會將功力放大k倍，但是“得道者”不會收徒弟， 求出“得道者”功力之和。

分析：

家譜成一個樹形結構， 用BFS遍歷一遍， 每次遇到“得道者”將功力加上即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 7;
 4 int n;
 5 double z, r;
 6 double quickpow(double a,int b)//快速冪
 7 {
 8     double ans = 1;
 9     while(b)//用一個循環從右到左便利b的所有二進制位
10     {
11         if(b&1)//判斷此時b[i]的二進制位是否為1
12         {
13             ans = (ans*a);//乘到結果上，這里a是a^(2^i)%m
14             b--;//把該為變0
15         }
16         b/=2;
17         a = a*a;
18     }
19     return ans;
20 }
21 struct node{
22     int n, dynasty; //編號、 傳遞了幾代
23     node(int _n, int _dynasty):n(_n), dynasty(_dynasty){}
24 };
25 int F[maxn], master[maxn];
26 vector<int> apprentice[maxn];
27 int main()
28 {
29     scanf("%d %lf %lf", &n, &z, &r);
30     r = (100 - r)/100;
31     for(int i = 0; i < n; i++){
32         int num;
33         scanf("%d", &num);
34         if(num == 0){
35             int t;
36             scanf("%d", &t);
37             master[i] = t;
38         }
39         else{
40             for(int j = 0; j < num; j++){
41                 int t;
42                 scanf("%d", &t);
43                 apprentice[i].push_back(t);
44             }
45         }
46     }
47     double ans = 0;
48     queue<node> q;
49     q.push(node(0,0));
50     while(!q.empty()){
51         node u = q.front(); q.pop();
52         int name = u.n , d = u.dynasty
53         if(master[name])
54         {
55             ans += quickpow(r,d) * z * (double)master[name];
56         }
57         else
58         for(int i = 0; i < apprentice[name].size(); i++){
59             q.push(node(apprentice[name][i], d + 1));
60         }
61     }
62     printf("%d
", (int)ans);
63     return 0;
64 }

功夫傳人

L3-013. 非常彈的球

題意：

給出一個球的質量， 求在一個平面拋出能得到的最遠距離。

分析：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const double eps = 1e-6;
 4 int main()
 5 {
 6     double w, p, E, v, ans;
 7     scanf("%lf%lf", &w, &p);
 8     E = 1000, ans = 0;
 9     w /= 100;
10     do{
11         v = sqrt(2*E/w);
12         ans += v*v/9.8;
13         E *= ((100-p)/100);
14     }while(v > eps);
15     printf("%.3f", ans);
16 }

非常彈的球

L3-015. 球隊“食物鏈”

題意：

給定N支隊伍的2*N場雙循環賽結果， 求出一條包含所有球隊的“食物鏈”，“食物鏈”為一個1至N的排列{ T₁ T₂ ... T_N }，滿足：球隊T₁戰勝過球隊T₂，球隊T₂戰勝過球隊T₃，……，球隊T_(N-1)戰勝過球隊T_N，球隊T_N戰勝過球隊T₁。若存在多條“食物鏈”，請找出字典序最小的。

分析：

因為這條食物鏈如果存在， 那么一定是包含所有球隊的， 所以可以從第一個點開始DFS，有一個剪枝是“如果還沒選擇的點沒有與1相連接的， 剪枝”。

另外要注意的是圖并不是對稱的， a輸b==b贏a。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 bool g[25][25];
 4 bool vis[25];
 5 int pick[25];
 6 int n, ok;
 7 bool dfs(int index , int tot)
 8 {
 9     if(tot == n){
10         if(g[index][0] == 1){
11             printf("%d", pick[0] + 1);
12             for(int i = 1; i < n; i++) printf(" %d", pick[i] + 1); puts("");
13             return true;
14         }
15         return false;
16     }
17     int cut = 1;//剪枝， 如果剩下沒挑選的點都沒有與1相連的，剪枝。
18     for(int i = 0; i < n; i++){
19         if(!vis[i] && g[i][0] == 1) {
20             cut = 0;
21             break;
22         }
23     }
24     if(cut) return false;
25     for(int i = 0; i < n; i++){
26         if(g[index][i] == 1 && !vis[i]){
27             vis[i] = 1;
28             pick[tot] = i;
29             if(dfs(i, tot + 1)) return true;
30             vis[i] = 0;
31         }
32     }
33     return false;
34 }
35 int main()
36 {
37     scanf("%d ", &n);
38     char input[123];
39     for(int i = 0; i < n; i++){
40         gets(input);
41         for(int j = 0; j < n; j++)
42             if( input[j] == 'W') g[i][j] = 1;
43             else if( input[j] == 'L') g[j][i] = 1;//注意a輸b其實等于b贏a
44     }
45     vis[0] = 1;
46     pick[0] = 0;
47     ok = dfs(0, 1);
48     if(!ok) printf("No Solution
");
49 }

球隊“食物鏈”

總結

以上是生活随笔為你收集整理的天梯赛练习（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。