//寒假训练赛,第一次拿第一,感觉很爽哦,AC3题!
A--------------------------------------------------------------------------------------------
题目链接:http://codeforces.com/problemset/problem/723/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---------------------------------------------------------------
题目链接:http://codeforces.com/problemset/problem/723/B
正解:模拟
解题报告:
直接模拟,注意处理字符串的计数器的诸多情况,有一点细节。
下面给出AC代码:
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---------------------------------------------------------------
题目链接:http://codeforces.com/problemset/problem/725/B
思路:注意第一个乘务员是从1开始,第二个从三开始,然后模拟下即可
下面给出AC代码:
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---------------------------------------------------------------
题目链接:http://poj.org/problem?id=1017
问题的理解:
①、这道题目的题意理解比较明显,意思就是提供一些底面积为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的物品就比较好办了,把前面各物品堆放时的剩下的空间堆放,不够就继续使用新的箱子;
下面给出AC代码:
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---------------------------------------------------------------
题目链接:http://poj.org/problem?id=1018
题意:
某公司要建立一套通信系统,该通信系统需要n种设备,而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产,而每个厂家生产的同种设备都会存在两个方面的差别:带宽bandwidths 和 价格prices。
现在每种设备都各需要1个,考虑到性价比问题,要求所挑选出来的n件设备,要使得B/P最大。
其中B为这n件设备的带宽的最小值,P为这n件设备的总价。
分析:此题目可用多种方法求解,DP 、 搜索 、贪心 、三分法
这里讲dp的思路。
我们定义状态dp 【i】【j】 表示选择了前 i 个宽带其容量为 j 的最小费用。
很容易得到转移方程 :dp【i】【j】=min(dp【i】【j】,dp【i-1】【k】+p);
注意选择 j 的时候的大小情况。
顺便提供一下贪心的思路。(正确性未知)
从初始的第一个要选的宽带的每一个开始,每次向下贪心选择一个总的 B/P 的最大值,找出其中最大的既为答案。有兴趣的可以验证一下正确性!
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 }