2015 Hdu 多校赛第二场

发表于   |   分类于

Hdu 5301 Buildings

链接

Buildings

题意

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

分析

相当于用矩形填充nm的矩阵，且矩形至少有一条边在nm矩阵的边界上
若不考虑(x,y)方格被删除，ans=(min(m,n)+1)/2;
删除(x,y)后，若 m=n且n为奇数，且(x,y)在中心点，ans=ans-1;
否则 如图
5301
与(x,y)上下左右相邻点，只能往三个方向建公寓，对于这四个点
分别取对应的三个方向建公寓的最小面积s=min(s1,s2,s3);
ans=max(ans,s);

参考代码

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

Hdu 5303 Delicious Apples

链接

Delicious Apples

题意

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

分析

从起点可以顺时针或逆时针出发，最后的结果肯定是
顺时针取一定的苹果所走的最短路与逆时针走的最短路的和。
那么设dp[2][i]，0代表顺时针，1代表逆时针，i代表取的苹果数，
值为取完i个苹果回到原点的最短路程。x[i]为第i个苹果所在的位置。
以顺时针为例，如果2*x[i] <L，那么后来走的路程为2*x[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<algorithm>
#define INF 0x3fffffffffffffff
const int N=100010;
using namespace std;
struct stu{
    long long x,num;
}app[N];
long long L;
int n,k,sum;
long long dp[2][N];
int cmp(stu a,stu b)
{
    return a.x<b.x;
}
long long solve()
{
    dp[0][0]=dp[1][0]=0;
    int cnt=1;
    for(int i=1;i<=n;i++){     //顺时针
        for(int j=1;j<=app[i].num;j++){
            int t=cnt>k?cnt-k:0;
            dp[0][cnt++]=dp[0][t]+min(app[i].x*2,L);
        }
    }
    cnt=1;
    for(int i=n;i>=1;i--){     //逆时针
        for(int j=1;j<=app[i].num;j++){
            int t=cnt>k?cnt-k:0;
            dp[1][cnt++]=dp[1][t]+min((L-app[i].x)*2,L);
        }
    }
    long long ans=INF;
    for(int i=0;i<=sum;i++)
        ans=min(ans,dp[0][i]+dp[1][sum-i]);
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%d%d",&L,&n,&k);
        sum=0;
        for(int i=1;i<=n;i++){
            scanf("%I64d%I64d",&app[i].x,&app[i].num);
            sum+=app[i].num;
        }
        sort(app+1,app+n+1,cmp);
        long long ans=solve();
        printf("%I64d\n",ans);
    }
    return 0;
}

Hdu 5305 Friends

题意

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

分析

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
#include<string.h>
const int N=10;
struct stu{
    int x,y;
}edge[N*N];
int n,m,du[N],on[N],off[N];
int dfs(int pos)
{
    if(pos==m+1)
        return 1;
    int x=edge[pos].x,y=edge[pos].y;
    int ans=0;
    if(on[x]<du[x]/2&&on[y]<du[y]/2){
        on[x]++,on[y]++;
        ans+=dfs(pos+1);
        on[x]--,on[y]--;
    }
    if(off[x]<du[x]/2&&off[y]<du[y]/2){
        off[x]++,off[y]++;
        ans+=dfs(pos+1);
        off[x]--,off[y]--;
    }
    return ans;
}
int solve()
{
    if(m&1) return 0;
    for(int i=1;i<=n;i++){
        if(du[i]&1) return 0;
        on[i]=off[i]=0;
    }
    int ans=dfs(1);
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(du,0,sizeof(du));
        for(int i=1;i<=m;i++){
            scanf("%d%d",&edge[i].x,&edge[i].y);
            du[edge[i].x]++;
            du[edge[i].y]++;
        }
        int ans=solve();
        printf("%d\n",ans);
    }
    return 0;
}

Hdu 5308 I Wanna Become A 24-Point Master

链接

I Wanna Become A 24-Point Master

题意

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

分析

24=4*6=3*8
可以构造 6个n相加，再用和除以n,得到6，4个n相加再除以n得到4
然后6*4=24， 这样 n最少为 12
同理构造 8*3，n最少为13
对于剩下未用的数,先让n-n=0，再由0乘上未用的数得到0，最后让0+24=24
所以对于 12+2k (k为自然数)构造 4*6
13+2k 构造 3*8
对于1-3,找不到符合条件的操作，输出-1
4-11,可以手算直接输出
注：n=5时 可以由 5*(5-(5/5)/5) 得到24 (允许小数除法)

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<stdio.h>
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF){
        if(n<=3)
            printf("-1\n");
        else if (n== 4)
            printf("1 * 2\n5 + 3\n6 + 4\n");
        else if(n == 5)
            printf("1 / 2\n6 / 3\n4 - 7\n5 * 8\n");
        else if(n==6) {
            printf("1 + 2\n");
            printf("3 + 7\n");
            printf("4 + 8\n");
            printf("9 / 5\n");
            printf("10 * 6\n");
        }
        else if(n == 7) {
            printf("1 + 2\n");
            printf("3 + 8\n");
            printf("9 / 4\n");
            printf("5 / 6\n");
            printf("11 + 7\n");
            printf("10 * 12\n");
        }
        else if(n == 8) {
            printf("1 + 2\n");
            printf("3 + 9\n");
            printf("4 - 5\n");
            printf("11 * 6\n");
            printf("12 * 7\n");
            printf("13 * 8\n");
            printf("10 + 14\n");
        }
        else if(n == 9) {
            printf("1 + 2\n");
            printf("3 + 4\n");
            printf("11 + 5\n");
            printf("12 + 6\n");
            printf("13 + 7\n");
            printf("14 + 8\n");
            printf("15 / 9\n");
            printf("10 + 16\n");
        }
        else if(n == 10) {
            printf("1 + 2\n");
            printf("11 / 3\n");
            printf("4 + 12\n");
            printf("6 + 5\n");
            printf("14 + 7\n");
            printf("8 + 15\n");
            printf("9 + 10\n");
            printf("16 / 17\n");
            printf("13 * 18\n");
        }
        else if(n == 11) {
            printf("1 + 2\n");
            printf("12 / 3\n");
            printf("4 / 5\n");
            printf("6 + 14\n");
            printf("7 - 8\n");
            printf("16 * 9\n");
            printf("17 * 10\n");
            printf("18 * 11\n");
            printf("13 * 15\n");
            printf("20 + 19\n");
        }
        else if(n%2==0){        //4*6
            printf("1 + 2\n");
            int l=3,r=n+1;
            for(int i=3;i<=4;i++)
                printf("%d + %d\n",l++,r++);
            printf("%d / %d\n",r++,l++);
            int a4=r;
            printf("%d + %d\n",l,l+1);
            l+=2,r++;
            for(int i=3;i<=6;i++)
                printf("%d + %d\n",l++,r++);
            printf("%d / %d\n",r++,l++);
            int a6=r++;
            printf("%d * %d\n",a4,a6);
            int a24=r++;
            if(l<n){
                printf("%d - %d\n",l,l+1);
                l+=2;
                while(l<=n)
                    printf("%d * %d\n",l++,r++);
                printf("%d + %d\n",r,a24);
            }
        }
        else{        //3*8
            printf("1 + 2\n");
            int l=3,r=n+1;
            printf("%d + %d\n",l++,r++);
            printf("%d / %d\n",r++,l++);
            int a3=r;
            printf("%d + %d\n",l,l+1);
            l+=2,r++;
            for(int i=3;i<=8;i++)
                printf("%d + %d\n",l++,r++);
            printf("%d / %d\n",r++,l++);
            int a8=r++;
            printf("%d * %d\n",a3,a8);
            int a24=r++;
            if(l<n){
                printf("%d - %d\n",l,l+1);
                l+=2;
                while(l<=n)
                    printf("%d * %d\n",l++,r++);
                printf("%d + %d\n",r,a24);
            }
        }
    }
    return 0;
}