# ECJTUACM16 Winter vacation training #1 题解&源码

//寒假训练赛，第一次拿第一，感觉很爽哦，AC3题！

A--------------------------------------------------------------------------------------------

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5     int a,b,c,d,s;
6     while(scanf("%d%d%d",&a,&b,&c)!=EOF)
7     {
8         if(a>=b&&b>=c)d=b;
9         else if(b>=a&&a>=c)d=a;
10         else if(a>=c&&c>=b)d=c;
11         else if(b>=c&&c>=a)d=c;
12         else if(c>=a&&a>=b)d=a;
13         else if(c>=b&&b>=a)d=b;
14         s=fabs(d-a)+fabs(d-b)+fabs(d-c);
15         printf("%d\n",s);
16     }
17     return 0;
18 }```

B---------------------------------------------------------------

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5     char s[10000];
6     int n,len=0,s1 = 0,s2 = 0;
7     bool flag = 0;
8     while(scanf("%d%s",&n,&s)!=EOF)
9     {
10         //for(int i=0;i<n;i++)
11             //scanf("%c",&s[i]);
12             for(int j = 0; j < n; j++)
13              {
14         if(s[j] == '(') flag=1;
15         if(s[j] == ')') flag=0;
16         if((s[j] >= 'a' && s[j] <= 'z') || (s[j] >= 'A' && s[j] <= 'Z')) {
17             len++;
18         }
19         else len = 0;
20         if(!flag) s1=max(s1, len);
21         else if(len==1)s2++;
22     }
23     printf("%d %d\n", s1,s2);
24 }
25 return 0;
26 }```

C---------------------------------------------------------------

``` 1 #include<bits/stdc++.h>
2 using namespace std;
3 __int64 judge(char c)
4 {
5     if(c=='f')
6     return 1;
7     if(c=='e')
8     return 2;
9     if(c=='d')
10     return 3;
11     if(c=='a')
12     return 4;
13     if(c=='b')
14     return 5;
15     if(c=='c')
16     return 6;
17 }
18 int main()
19 {
20     __int64 n,m,k,l,sum;
21     char str[3];
22     while(scanf("%I64d%s",&n,str)!=EOF)
23     {
24         k=n/4;
25         l=n%4;
26         if(l==1||l==2)
27         {
28             sum=(k*2+l)*6+(n-1);
29         }
30         else if(l==3)
31         {
32             sum=(k*2+1)*6+(n-1)-2;
33         }
34         else if(l==0)
35         {
36             k=k-1;
37             sum=(k*2+2)*6+(n-1)-2;
38         }
39         sum+=judge(str[0])-6;
40         printf("%I64d\n",sum);
41     }
42     return 0;
43 }```

D---------------------------------------------------------------

①、这道题目的题意理解比较明显，意思就是提供一些底面积为6*6的箱子，各种规格的物品，底面积不一致。要想使得使用的箱子数目最少，那么就是使得每个箱子底面积都装满，显然要从大的物品开始装。问题的关键在于如何计算一个完整的箱子装完一中规格的物品之后，如何去装剩下的其他的物品，空间如何分配。

②、对于6*6的物品的而言，装一个就满了；对于5*5的物品而言，装一个以后还剩下11个1*1的空间，这些空间只能放1*1规格的物品；对于4*4的物品而言，装一个以后还剩下5个2*2的空间，或者是完全换算成20个1*1的空间，当然这里面的空间也可以拆分成部分2*2的空间以及部分1*1的空间；

③、比较难处理的是装3*3规格的物品，一个6*6的箱子最终可以完全装4个3*3的物品，并且需要的箱子数目是3*3的物品的数目除以4向上取整，因为3*3的物品不能和4*4以及5*5的物品放在一起。（向上取整编码时有一个技巧在于不要直接使用向上取整的函数，比如对于除以4向上取整可以编码为 (a+3)/4 。

④、问题的关键在于如何处理最后一个装3*3的箱子其剩下的空间怎么才处理：第一种情况，当装3个3*3物品时，那么还剩下1个2*2和5个1*1的空间；第二种情况，当装2个3*3的物品时，那么还剩下3个2*2和6个1*1的物品空间；第三种情况，当装1个3*3的物品时，那么还剩下5个2*2和7个1*1的物品空间（这个剩余空间的计算方法是按照优先2*2的物品，是的2*2的物品能放的数目最大，然后再考虑1*1的物品）

⑤、剩下的2*2的物品就比较好办了，把前面各物品堆放时的剩下的空间堆放，不够就继续使用新的箱子；

``` 1 #include <stdlib.h>
2 #include <stdio.h>
3 int main()
4 {
5     int N, a, b, c, d, e, f, y, x;
6     //N表示使用的箱子的数目，a-f一次表示1*1--6*6规格物品的个数
7     //x y是编码时使用的一个技巧，x表示1*1的剩余空间数，y表示2*2
8     //int u[4] = {0,5,3,1};
9
10     while(1)
11     {
12         scanf("%d %d %d %d %d %d",&a, &b, &c, &d, &e, &f);
13         if(a==0 && b==0 && c==0 && d==0 && e==0 && f==0)
14             break;
15         N = f+e+d+(c+3)/4; //先计算大块头的物品6*6和5*5和4*4以及3*3的物品所需要的箱子
16
17         //关键是计算剩余的 2*2的空间，以最大化2*2的空间为计算标准
18
19         y = d*5; //6*6和5*5的物品均不剩下2*2的空间，一个箱子装一个4*4的物品剩下5个2*2的空间
20
21         if( c%4 == 3)
22             y += 1;
23         else if( c%4 == 2)
24             y += 3;
25         else if( c%4 == 1)
26             y += 5; //这里是关键，把这一个3*3的物品摆放在中间的位置才有可能放入5个2*2的物品
27
28         if( y < b)
29             N += ((b-y)+8)/9; //如果2*2的剩余空间不够，那么就需要新开箱子
30
31         x = 36*N - 36*f - 25*e - 16*d - 9*c - 4*b;  //计算剩余的1*1的空间用了一个比较好的方法
32
33         if( x <a)
34             N += ((a-x)+35)/36; //如果1*1的空间不够，那么就需要开新的箱子
35
36         printf("%d\n", N);
37     }
38     return 0;
39 } ```

E---------------------------------------------------------------

dp代码：

``` 1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 #include <iomanip>
5 using namespace std;
6
7 const int maxn=1100;
8 const int inf=0x3f3f3f3f;
9 int dp[maxn];
10
11 struct node{
12     int flow,sum;
13     node(int flow0=0,int sum0=0){
14         flow=flow0,sum=sum0;
15     }
16 };
17
18 void solve(){
19     queue <node> q;
20     q.push(node(inf,0));
21     int n,m,flow,price;
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++){
24         scanf("%d",&m);
25         for(int i=0;i<maxn;i++) dp[i]=inf;
26         while(m-- >0){
27             scanf("%d%d",&flow,&price);
28             int qsize=q.size();
29             while(qsize-- >0){
30                 node s=q.front();
31                 q.pop();
32                 if(s.flow<flow){
33                     if(s.sum+price<dp[s.flow]) dp[s.flow]=s.sum+price;
34                 }else{
35                     if(s.sum+price<dp[flow]) dp[flow]=s.sum+price;
36                 }
37                 q.push(s);
38             }
39         }
40         while(!q.empty()) q.pop();
41         for(int i=0;i<maxn;i++){
42             if(dp[i]<inf) q.push(node(i,dp[i]));
43         }
44     }
45     double ans=0;
46     while(!q.empty()){
47         node s=q.front();
48         q.pop();
49         if(double(s.flow)/double(s.sum) > ans) ans= double(s.flow)/double(s.sum) ;
50     }
51     cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;
52 }
53
54 int main(){
55     int t;
56     scanf("%d",&t);
57     while(t-- >0){
58         solve();
59     }
60     return 0;
61 }```

780 篇文章62 人订阅

0 条评论

## 相关文章

1053

1905

### 博弈论进阶之SG函数

SG函数 个人理解：SG函数是人们在研究博弈论的道路上迈出的重要一步，它把许多杂乱无章的博弈游戏通过某种规则结合在了一起，使得一类普遍的博弈问题得到了解决。 从...

3955

### Hanlp自然语言处理工具的使用演练

Hanlp是由一系列模型与算法组成的工具包，目标是普及自然语言处理在生产环境中的应用。Hanlp具备功能完善、性能高效、架构清洗、语料时新、可自定义的特点；提供...

1942

8570

1881

1683

2908