2015 Multi-University Training Contest 2

多校第二场，赛后总共做出四题，总结的有点晚了，太懒，下面给出解题报告！！

Hdu 5301 Buildings

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5301

题意：有块地为n*m列的矩阵，要建造矩形公寓来完全覆盖这块地((x,y)方格除外)
　　且每个公寓必须有一边在这块地的矩阵的边缘上。
　　求满足条件的方案中公寓最大面积的最小值。

思路：相当于用矩形填充n*m的矩阵，且矩形至少有一条边在该矩阵的边界上
　　若不考虑(x,y)方格被删除，ans=(min(m,n)+1)/2;
　　删除(x,y)后，若 m=n且n为奇数，且(x,y)在中心点，ans=ans-1;
　　否则如图：

　　与(x,y)上下左右相邻点，只能往三个方向建公寓，对于这四个点
　　分别取对应的三个方向建公寓的最小面积s=min(s1,s2,s3);
　　ans=max(ans,s);

参考代码：

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define INF 999999999
 4 const int dirX[4]={0,0,-1,1};
 5 const int dirY[4]={1,-1,0,0};
 6 using namespace std;
 7 int main()
 8 {
 9     int n,m,x,y;
10     while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){
11         int ans=(min(m,n)+1)/2;
12         if(n%2&&m==n&&x==y&&x==(n+1)/2){
13             printf("%d
",ans-1);
14             continue;
15         }
16         for(int i=0;i<4;i++){
17             int row=x+dirX[i];
18             int col=y+dirY[i];
19             int temp=INF;
20             if(row>=1&&row<=n&&col>=1&&col<=m){
21                 if(row-1!=x)
22                     temp=min(temp,row);
23                 if(row+1!=x)
24                     temp=min(temp,n-row+1);
25                 if(col-1!=y)
26                     temp=min(temp,col);
27                 if(col+1!=y)
28                     temp=min(temp,m-col+1);
29                 ans=max(ans,temp);
30             }
31         }
32         printf("%d
",ans);
33     }
34     return 0;
35 }

View Code

Hdu 5303 Delicious Apples

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5303

题意：一个环形道上有n个苹果树，第i棵树与仓库的顺时针距离为xi,树上有ai个苹果，仓库在位置0
　　你有一个容量为k的篮子，要从仓库出发去摘苹果，篮子装满后要回到起点清空篮子，
　　问你从起点出发，摘完所有苹果所走的最短路程。

思路：从起点可以顺时针或逆时针出发，最后的结果肯定是
　　顺时针取一定的苹果所走的最短路与逆时针走的最短路的和。

　　对于每棵树上的苹果，肯定是能现整取的先取完，然后回到原点，预处理一下，然后每棵树的苹果数就是原来的苹果数%k；

　　对于剩下的每个苹果离散化，每个苹果自成一个分量，

　　用sl表示左半圈苹果总数，用sr表示右半圈苹果总数。

　　用pl[]表示左半圈各个苹果距离远点的最短距离，pr[]表示右半圈苹果距离远点的最短距离。

　　用dpl[i]表示取左半圈的第i个苹果要走的最短路径，同理dpr[i]表示取右半圈的第i个苹果要走的最短路径。

　　ans=(dpl[sl-1]+dpr[sr-1])*2;//左边的都往左边运，右边的都往右边运得到的路程总和。

　　因为最多存在走一圈比分别走两边的短的情况，所以枚举每一个走全圈的情况，和ans比较大小，取小的那个；

参考代码：

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 using namespace std;
  5 struct node
  6 {
  7     long long dis,x;
  8 } left[100001],right[100001];
  9 long long pl[100001],pr[100001];
 10 long long dpl[100001],dpr[100001];
 11 int cmp(node x,node y)
 12 {
 13     return x.dis<y.dis;
 14 }
 15 int main()
 16 {
 17     int T;
 18     int L,n,k;
 19     long long sum;
 20     long long ans;
 21     scanf("%d",&T);
 22     while(T--)
 23     {
 24         sum=0;
 25         long long a,b;
 26         int l=0,r=0;
 27         scanf("%d%d%d",&L,&n,&k);
 28         memset(pl,0,sizeof(pl));
 29         memset(pr,0,sizeof(pr));
 30         memset(dpl,0,sizeof(dpl));
 31         memset(dpr,0,sizeof(dpr));
 32         for(int i=0; i<n; i++)
 33         {
 34             scanf("%I64d%I64d",&a,&b);
 35             if(a*2<=L)
 36             {
 37                 left[l].dis=a;
 38                 left[l++].x=b;
 39             }
 40             else
 41             {
 42                 right[r].dis=L-a;
 43                 right[r++].x=b;
 44             }
 45         }
 46         sort(left,left+l,cmp);
 47         sort(right,right+r,cmp);
 48         for(int i=0; i<l; i++)
 49         {
 50             sum+=(left[i].dis)*(left[i].x/k)*2;
 51             left[i].x=left[i].x%k;
 52         }
 53         for(int i=0; i<r; i++)
 54         {
 55             sum+=(right[i].dis)*(right[i].x/k)*2;
 56             right[i].x=right[i].x%k;
 57         }
 58         //剩余的苹果离散化
 59         int sl=1;//左边苹果总数
 60         int sr=1;//右边苹果总数
 61         for(int i=0; i<l; i++)
 62         {
 63             if(left[i].x)
 64             {
 65                 for(int j=0; j<left[i].x; j++)
 66                 {
 67                     pl[sl++]=left[i].dis;
 68                 }
 69             }
 70         }
 71         for(int i=0; i<r; i++)
 72         {
 73             if(right[i].x)
 74             {
 75                 for(int j=0; j<right[i].x; j++)
 76                 {
 77                     pr[sr++]=right[i].dis;
 78                 }
 79             }
 80         }
 81         for(int i = 1; i < sl; i++)
 82         {
 83             if(i<=k)
 84                 dpl[i]=pl[i];
 85             else
 86                 dpl[i]=dpl[i-k]+pl[i];
 87         }
 88         for(int i = 1; i < sr; i++)
 89         {
 90             if(i<=k)
 91                 dpr[i]=pr[i];
 92             else
 93                 dpr[i]=dpr[i-k]+pr[i];
 94         }
 95         ans=(dpl[sl-1]+dpr[sr-1])*2;//左边的往左边运，右边的网友边运
 96         for(int i=0; i<=sl-1&&i<=k; i++)
 97         {
 98             int p1=sl-i-1;
 99             int p2=max(0,sr-1-(k - i));
100             if(2*(dpl[p1] + dpr[p2])+L<ans)
101                 ans=2*(dpl[p1] + dpr[p2])+L;
102         }
103         printf("%I64d
",ans+sum);
104     }
105     return 0;
106 }

View Code

另一种方法更好理解：从起点可以顺时针或逆时针出发，最后的结果肯定是
　　顺时针取一定的苹果所走的最短路与逆时针走的最短路的和。
　　那么设dp[2][i]，0代表顺时针，1代表逆时针，i代表取的苹果数，
　　值为取完i个苹果回到原点的最短路程。x[i]为第i个苹果所在的位置。
　　以顺时针为例，如果2x[i] <L，那么后来走的路程为2x[i]，反之，为L；
转移方程：
　　dp[0][i] = min(dp[0][i],dp[0][i-j]+(2*x[i] <L ? 2*x[i] : L)) (1 <= j <= k)
　　因为dp[0][i]是非递减的,所以优化方程：
　　dp[0][i] = dp[0][i-k]+(2*x[i] <L ? 2*x[i] : L)

参考代码：

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define INF 0x3fffffffffffffff
 4 const int N=100010;
 5 using namespace std;
 6 struct stu{
 7     long long x,num;
 8 }app[N];
 9 long long L;
10 int n,k,sum;
11 long long dp[2][N];
12 int cmp(stu a,stu b)
13 {
14     return a.x<b.x;
15 }
16 long long solve()
17 {
18     dp[0][0]=dp[1][0]=0;
19     int cnt=1;
20     for(int i=1;i<=n;i++){     //顺时针
21         for(int j=1;j<=app[i].num;j++){
22             int t=cnt>k?cnt-k:0;
23             dp[0][cnt++]=dp[0][t]+min(app[i].x*2,L);
24         }
25     }
26     cnt=1;
27     for(int i=n;i>=1;i--){     //逆时针
28         for(int j=1;j<=app[i].num;j++){
29             int t=cnt>k?cnt-k:0;
30             dp[1][cnt++]=dp[1][t]+min((L-app[i].x)*2,L);
31         }
32     }
33     long long ans=INF;
34     for(int i=0;i<=sum;i++)
35         ans=min(ans,dp[0][i]+dp[1][sum-i]);
36     return ans;
37 }
38 int main()
39 {
40     int T;
41     scanf("%d",&T);
42     while(T--){
43         scanf("%I64d%d%d",&L,&n,&k);
44         sum=0;
45         for(int i=1;i<=n;i++){
46             scanf("%I64d%I64d",&app[i].x,&app[i].num);
47             sum+=app[i].num;
48         }
49         sort(app+1,app+n+1,cmp);
50         long long ans=solve();
51         printf("%I64d
",ans);
52     }
53     return 0;
54 }

View Code

Hdu 5305 Friends

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5305

题意：有n个人，m组关系，表示谁和谁是朋友关系
　　朋友分为线上朋友和线下朋友，
　　求满足每个人的线上朋友数和线下朋友数相同
　　有多少种的情况

思路：题中n<=8，m<=n(n-1)/2，对于每组朋友关系
　　要么为线上，要么为线下，dfs加剪枝
　　要保证每个人线上朋友和线下朋友人数相等，
　　则每个人的朋友数都为偶数，且总边数m为偶数，否则输出0

参考代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<stdio.h>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 using namespace std;
 7 int n,m,sum;
 8 struct node
 9 {
10     int x,y;
11 } fri[100];
12 int num[10];
13 int lf[10];
14 int rf[10];
15 void dfs(int p)
16 {
17     if(p==m)
18     {
19         sum++;
20         return;
21     }
22     int x=fri[p].x;
23     int y=fri[p].y;
24     if(lf[x]&&lf[y])
25     {
26         lf[x]--;
27         lf[y]--;
28         dfs(p+1);
29         lf[x]++;
30         lf[y]++;
31     }
32     if(rf[x]&&rf[y])
33     {
34         rf[x]--;
35         rf[y]--;
36         dfs(p+1);
37         rf[x]++;
38         rf[y]++;
39     }
40 }
41 void work()
42 {
43     int flag=0;
44     for(int i=1; i<=n; i++)
45     {
46         lf[i]=num[i]/2;
47         rf[i]=num[i]/2;
48         if(num[i]%2)
49         {
50             flag=1;
51             break;
52         }
53     }
54     if(flag)
55     {
56         puts("0");
57     }
58     else{
59         dfs(0);
60         printf("%d
",sum);
61     }
62 }
63 void input()
64 {
65     int a,b;
66     scanf("%d%d",&n,&m);
67     for(int i=0; i<m; i++)
68     {
69         scanf("%d%d",&a,&b);
70         fri[i].x=a;
71         fri[i].y=b;
72         num[a]++;
73         num[b]++;
74     }
75 }
76 int main()
77 {
78     int T;
79     scanf("%d",&T);
80     while(T--)
81     {
82         sum=0;
83         memset(num,0,sizeof(num));
84         input();
85         work();
86     }
87     return 0;
88 }

View Code

Hdu 5308 I Wanna Become A 24-Point Master

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5308

题意：有n个数a1,a2…an,它们的值都为n
　　每次操作可以选两个未进行操作的数进行 “+”,”-“,”*”,”/“
　　第i次操作为a b c:其中a,c为数组下标，b为操作符，则A[n+i]=A[a] b A[c];
　　要进行 n-1 次操作,使得最后数组2n-1的值为24
　　需要满足的条件：每个数都有且仅能用一次(包括新生成的数)
　　除法为小数除法，允许得到分数
　　若能找到满足条件的操作,输出这n-1次操作，否则输出-1

思路：

参考代码：

  1 #include<stdio.h>
  2 int main()
  3 {
  4     int N;
  5     while(scanf("%d",&N)!=EOF)
  6     {
  7         if(N<=3)
  8             printf("-1
");
  9         else if (N == 4)
 10         {
 11             printf("1 * 2
5 + 3
6 + 4
");
 12         }
 13         else if(N == 5)
 14         {
 15             printf("1 / 2
");
 16             printf("6 / 3
");
 17             printf("4 - 7
");
 18             printf("5 * 8
");
 19         }
 20         else if(N==6)
 21         {
 22             printf("1 + 2
");
 23             printf("3 + 7
");
 24             printf("4 + 8
");
 25             printf("9 // 5
");
 26             printf("10 * 6
");
 27         }
 28         else if(N == 7)
 29         {
 30             printf("1 + 2
");
 31             printf("3 + 8
");
 32             printf("9 / 4
");
 33             printf("5 / 6
");
 34             printf("11 + 7
");
 35             printf("10 * 12
");
 36         }
 37         else if(N == 8)
 38         {
 39             printf("1 + 2
");
 40             printf("3 + 9
");
 41             printf("4 - 5
");
 42             printf("11 * 6
");
 43             printf("12 * 7
");
 44             printf("13 * 8
");
 45             printf("10 + 14
");
 46         }
 47         else if(N == 9)
 48         {
 49             printf("1 + 2
");
 50             printf("3 + 4
");
 51             printf("11 + 5
");
 52             printf("12 + 6
");
 53             printf("13 + 7
");
 54             printf("14 + 8
");
 55             printf("15 / 9
");
 56             printf("10 + 16
");
 57         }
 58         else if(N == 10)
 59         {
 60             printf("1 + 2
");
 61             printf("11 / 3
");
 62             printf("4 + 12
");
 63             printf("6 + 5
");
 64             printf("14 + 7
");
 65             printf("8 + 15
");
 66             printf("9 + 10
");
 67             printf("16 / 17
");
 68             printf("13 * 18
");
 69         }
 70         else if(N == 11)
 71         {
 72             printf("1 + 2
");
 73             printf("12 / 3
");
 74             printf("4 / 5
");
 75             printf("6 + 14
");
 76             printf("7 - 8
");
 77             printf("16 * 9
");
 78             printf("17 * 10
");
 79             printf("18 * 11
");
 80             printf("13 * 15
");
 81             printf("20 + 19
");
 82         }
 83         else if(N == 12)
 84         {
 85             printf("1 + 2
");
 86             printf("3 - 4
");
 87             printf("14 * 5
");
 88             printf("6 * 15
");
 89             printf("7 * 16
");
 90             printf("8 * 17
");
 91             printf("9 * 18
");
 92             printf("10 * 19
");
 93             printf("11 * 20
");
 94             printf("12 * 21
");
 95             printf("13 + 22
");
 96         }
 97         else
 98         {
 99             if(N%2==0)
100             {
101                 printf("1 + 2
");
102                 int p=3,q=N+1;
103                 for(int i=1; i<3; i++)
104                 {
105                     printf("%d + %d
",p++,q++);
106                 }//加三次N
107                 printf("%d / %d
",q++,p++);//除以N得到4
108                 printf("%d + %d
",p,p+1);//得到2倍的N
109                 int cnt1=q++;
110                 p+=2;
111                 for (int i=1; i<5; i++)
112                 {
113                     printf("%d + %d
",p++,q++);
114                 }//得到6倍的N
115                 printf("%d / %d
",q++,p++);//得到6
116                 int cnt2=q++;
117                 while (p<N)
118                 {
119                     printf("%d / %d
",p,p+1);//得到0
120                     p+=2;
121                     q++;
122                     printf("%d * %d
",q-1,cnt1);
123                     cnt1=q++;
124                 }
125                 printf("%d * %d
",cnt1,cnt2);//4*6=24
126             }
127             else
128             {
129                 printf("1 + 2
");
130                 int p=3,q=N+1;
131                 for (int i=1; i<2; i++)
132                 {
133                     printf("%d + %d
",p++,q++);
134                 }
135                 printf("%d / %d
",q++,p++);//得到3
136                 printf("%d + %d
",p,p+1);
137                 int cnt1=q++;
138                 p+=2;
139                 for (int i=1; i<7; i++)
140                 {
141                     printf("%d + %d
",p++,q++);
142                 }
143                 printf("%d / %d
",q++,p++);//得到8
144                 int cnt2=q++;
145                 while (p<N)
146                 {
147                     printf("%d / %d
",p,p+1);
148                     p+=2;
149                     q++;
150                     printf("%d * %d
",q-1,cnt1);
151                     cnt1=q++;
152                 }
153                 printf("%d * %d
",cnt1,cnt2);//3*8=24
154             }
155         }
156     }
157     return 0;
158 }

View Code