首页 > 代码库 > 2016ACM青岛区域赛题解

2016ACM青岛区域赛题解

A、Relic Discovery_hdu5982

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 57    Accepted Submission(s): 49

Problem Description
Recently, paleoanthropologists have found historical remains on an island in the Atlantic Ocean. The most inspiring thing is that they excavated in a magnificent cave and found that it was a huge tomb. Inside the construction,researchers identified a large number of skeletons, and funeral objects including stone axe, livestock bones and murals. Now, all items have been sorted, and they can be divided into N types. After they were checked attentively, you are told that there areAi items of the i-th type. Further more, each item of the i-th type requires Bi million dollars for transportation, analysis, and preservation averagely. As your job, you need to calculate the total expenditure.
 
Input
The first line of input contains an integer T which is the number of test cases. For each test case, the first line contains an integer N which is the number of types. In the next N lines, the i-th line contains two numbers Ai and Bi as described above. All numbers are positive integers and less than 101.
 
Output
For each case, output one integer, the total expenditure in million dollars.
 
Sample Input
1 2 1 2 3 4
 
Sample Output
14
 
Source
2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)
 

 

Recommend
jiangzijing2015   |   We have carefully selected several similar problems for you:  5994 5993 5992 5991 5990 
思路:第一题很简单,求费用,把每次的乘积都加起来就行了。
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
    int t;
    int a,b;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
        scanf("%d",&n);
        int sum=0;
        for(int j=0;j<n;j++){
            scanf("%d %d",&a,&b);
            sum+=a*b;
        }
        printf("%d\n",sum);
    }

    return 0;
}

 

B、Pocket Cube_5983

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 23    Accepted Submission(s): 9


Problem Description
The Pocket Cube, also known as the Mini Cube or the Ice Cube, is the 2 × 2 × 2 equivalence of a Rubik’s Cube.
The cube consists of 8 pieces, all corners.
Each piece is labeled by a three dimensional coordinate (h, k, l) where h, k, l ∈ {0, 1}. Each of the six faces owns four small faces filled with a positive integer.
For each step, you can choose a certain face and turn the face ninety degrees clockwise or counterclockwise.
You should judge that if one can restore the pocket cube in one step. We say a pocket cube has been restored if each face owns four same integers.
 

 

Input
The first line of input contains one integer N(N ≤ 30) which is the number of test cases.
For each test case, the first line describes the top face of the pocket cube, which is the common 2 × 2 face of pieces
labelled by (0, 0, 1),(0, 1, 1),(1, 0, 1),(1, 1, 1). Four integers are given corresponding to the above pieces.
The second line describes the front face, the common face of (1, 0, 1),(1, 1, 1),(1, 0, 0),(1, 1, 0). Four integers are
given corresponding to the above pieces.
The third line describes the bottom face, the common face of (1, 0, 0),(1, 1, 0),(0, 0, 0),(0, 1, 0). Four integers are
given corresponding to the above pieces.
The fourth line describes the back face, the common face of (0, 0, 0),(0, 1, 0),(0, 0, 1),(0, 1, 1). Four integers are
given corresponding to the above pieces.
The fifth line describes the left face, the common face of (0, 0, 0),(0, 0, 1),(1, 0, 0),(1, 0, 1). Four integers are given
corresponding to the above pieces.
The six line describes the right face, the common face of (0, 1, 1),(0, 1, 0),(1, 1, 1),(1, 1, 0). Four integers are given
corresponding to the above pieces.
In other words, each test case contains 24 integers a, b, c to x. You can flat the surface to get the surface development
as follows.

+ - + - + - + - + - + - +
| q | r | a | b | u | v |
+ - + - + - + - + - + - +
| s | t | c | d | w | x |
+ - + - + - + - + - + - +
| e | f |
+ - + - +
| g | h |
+ - + - +
| i | j |
+ - + - +
| k | l |
+ - + - +
| m | n |
+ - + - +
| o | p |
+ - + - +
Output
For each test case, output YES if can be restored in one step, otherwise output NO.
 
Sample Input
4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 6 6 6 6 1 1 1 1 2 2 2 2 3 3 3 3 5 5 5 5 4 4 4 4 1 4 1 4 2 1 2 1 3 2 3 2 4 3 4 3 5 5 5 5 6 6 6 6 1 3 1 3 2 4 2 4 3 1 3 1 4 2 4 2 5 5 5 5 6 6 6 6
 
Sample Output
YES YES YES NO
 
Source
2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)
 
Recommend
jiangzijing2015   |   We have carefully selected several similar problems for you:  5994 5993 5992 5991 5990 
思路:在比赛的时候理解错意思了,以为是判断能不能复原模仿,而没看到只需要一步。
魔方是2*2的,有三种转的方法,上面顺时针转90度,逆时针转,前面顺时针,前面逆时针,左边顺时针(相当于右边顺时针),左边逆时针(相当于左边逆时针)
还有再加上不操作算是一种,总共七种类,模拟出来就行了。
  1 #include <iostream>
  2 #include <cstdio>
  3 
  4 using namespace std;
  5 
  6 int a[7][5];
  7 int b[7][5];
  8 
  9 bool judge(){
 10     int i=0;
 11     for(int j=1;j<=6;j++){
 12         if(a[j][1]==a[j][2]&&a[j][2]==a[j][3]&&a[j][3]==a[j][4]){
 13             i++;
 14         }
 15     }
 16     if(i==6){
 17         return true;
 18     }else{
 19         return false;
 20     }
 21 }
 22 
 23 void opera1(){//前面顺时针
 24     int t1,t2;
 25     t1=a[6][3];
 26     t2=a[6][4];
 27 
 28     a[6][3]=a[1][3];
 29     a[6][4]=a[1][4];
 30 
 31     a[1][3]=a[5][3];
 32     a[1][4]=a[5][4];
 33 
 34     a[5][3]=a[3][2];
 35     a[5][4]=a[3][1];
 36 
 37     a[3][1]=t2;
 38     a[3][2]=t1;
 39 }
 40 void opera2(){//前面逆时针
 41     int t1,t2;
 42     t1=a[5][3];
 43     t2=a[5][4];
 44 
 45     a[5][3]=a[1][3];
 46     a[5][4]=a[1][4];
 47 
 48     a[1][3]=a[6][3];
 49     a[1][4]=a[6][4];
 50 
 51     a[6][3]=a[3][2];
 52     a[6][4]=a[3][1];
 53 
 54     a[3][1]=t2;
 55     a[3][2]=t1;
 56 }
 57 void opera3(){//上面顺时针
 58     int t1,t2;
 59     t1=a[2][1];
 60     t2=a[2][2];
 61 
 62     a[2][1]=a[6][3];
 63     a[2][2]=a[6][1];
 64 
 65     a[6][3]=a[4][4];
 66     a[6][1]=a[4][3];
 67 
 68     a[4][4]=a[5][2];
 69     a[4][3]=a[5][4];
 70 
 71     a[5][2]=t1;
 72     a[5][4]=t2;
 73 }
 74 void opera4(){//上面逆时针
 75     int t1,t2;
 76     t1=a[2][1];
 77     t2=a[2][2];
 78 
 79     a[2][1]=a[5][2];
 80     a[2][2]=a[5][4];
 81 
 82     a[5][2]=a[4][4];
 83     a[5][4]=a[4][3];
 84 
 85     a[4][4]=a[6][3];
 86     a[4][3]=a[6][1];
 87 
 88     a[6][1]=t2;
 89     a[6][3]=t1;
 90 }
 91 void opera5(){//左边顺指针
 92     int t1,t2;
 93     t1=a[1][1];
 94     t2=a[1][3];
 95 
 96     a[1][1]=a[4][1];
 97     a[1][3]=a[4][3];
 98 
 99     a[4][1]=a[3][1];
100     a[4][3]=a[3][3];
101 
102     a[3][1]=a[2][1];
103     a[3][3]=a[2][3];
104 
105     a[2][1]=t1;
106     a[2][3]=t2;
107 }
108 void opera6(){//左边逆时针
109     int t1,t2;
110     t1=a[1][1];
111     t2=a[1][3];
112 
113     a[1][1]=a[2][1];
114     a[1][3]=a[2][3];
115 
116     a[2][1]=a[3][1];
117     a[2][3]=a[3][3];
118 
119     a[3][1]=a[4][1];
120     a[3][3]=a[4][3];
121 
122     a[4][1]=t1;
123     a[4][3]=t2;
124 }
125 int main()
126 {
127     int n;
128     scanf("%d",&n);
129     while(n--){
130         for(int i=1;i<=6;i++){
131             for(int j=1;j<=4;j++){
132                 scanf("%d",&a[i][j]);
133                 b[i][j]=a[i][j];
134             }
135         }
136         if(judge()){
137             printf("YES\n");
138             continue;
139         }
140         opera1();
141         if(judge()){
142             printf("YES\n");
143             continue;
144         }
145         for(int i=1;i<=6;i++){
146             for(int j=1;j<=4;j++){
147                 a[i][j]=b[i][j];
148             }
149         }
150         opera2();
151         if(judge()){
152             printf("YES\n");
153             continue;
154         }
155         for(int i=1;i<=6;i++){
156             for(int j=1;j<=4;j++){
157                 a[i][j]=b[i][j];
158             }
159         }
160         opera3();
161         if(judge()){
162             printf("YES\n");
163             continue;
164         }
165         for(int i=1;i<=6;i++){
166             for(int j=1;j<=4;j++){
167                 a[i][j]=b[i][j];
168             }
169         }
170         opera4();
171         if(judge()){
172             printf("YES\n");
173             continue;
174         }
175         for(int i=1;i<=6;i++){
176             for(int j=1;j<=4;j++){
177                 a[i][j]=b[i][j];
178             }
179         }
180         opera5();
181         if(judge()){
182             printf("YES\n");
183             continue;
184         }
185         for(int i=1;i<=6;i++){
186             for(int j=1;j<=4;j++){
187                 a[i][j]=b[i][j];
188             }
189         }
190         opera6();
191         if(judge()){
192             printf("YES\n");
193             continue;
194         }
195         for(int i=1;i<=6;i++){
196             for(int j=1;j<=4;j++){
197                 a[i][j]=b[i][j];
198             }
199         }
200         printf("NO\n");
201     }
202     return 0;
203 }

 

C、Pocky_hdu5984

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 54    Accepted Submission(s): 20

Problem Description
Let’s talking about something of eating a pocky. Here is a Decorer Pocky, with colorful decorative stripes in the coating, of length L.
While the length of remaining pocky is longer than d, we perform the following procedure. We break the pocky at any point on it in an equal possibility and this will divide the remaining pocky into two parts. Take the left part and eat it. When it is not longer than d, we do not repeat this procedure.
Now we want to know the expected number of times we should repeat the procedure above. Round it to 6 decimal places behind the decimal point.
 
Input
The first line of input contains an integer N which is the number of test cases. Each of the N lines contains two float-numbers L and d respectively with at most 5 decimal places behind the decimal point where 1 ≤ d, L ≤ 150.
 
Output
For each test case, output the expected number of times rounded to 6 decimal places behind the decimal point in a line.
 
Sample Input
6 1.0 1.0 2.0 1.0 4.0 1.0 8.0 1.0 16.0 1.0 7.00 3.00
 
Sample Output
0.000000 1.693147 2.386294 3.079442 3.772589 1.847298
 
Source
2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)
 
Recommend
jiangzijing2015   |   We have carefully selected several similar problems for you:  5994 5993 5992 5991 5990 
思路:说实话比赛的时候根本不知道怎么做出来的。
好久之后才队友想起来,输出了一下log2,突然发现了规律。
赛后看别的队,一看0.693147就知道log2了,这就是做题多了有经验了啊。
但当时说的题解好像是求微积分,还是求导呢,把公式推导出来的。。。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int n;
10     double a,b;
11     scanf("%d",&n);
12     while(n--){
13         scanf("%lf%lf",&a,&b);
14         if(a<=b){
15             printf("0.000000\n");
16             continue;
17         }
18         printf("%.6lf\n",log(a)-log(b)+1);
19     }
20     return 0;
21 }

 

 

 

 

2016ACM青岛区域赛题解