2015 Hdu 多校赛第八场

发表于   |   分类于

Hdu 5386 Cover

链接

Cover

题意

给定n*n的初始矩阵A,和目标矩阵B,以及m次操作
H x y 将A矩阵第x行的数都变为y，L x y 将A矩阵第x列的数都变为y
输出m次操作的顺序使得最后得到矩阵B

分析

初始矩阵其实没有什么用，对于某一行或某一列可能会进行多次操作，而最终状态与对它的最后一次操作一致，即前面的操作被覆盖了，我们只要每次找一行或一列颜色除了0都相同的，然后如果有对应的操作，逆序记录下这次操作，并把这行这列都赋值成0，表示状态已确定，直到m次操作都完成即可

参考代码

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
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int N = 105;
const int M = 505;
int n, m, a[N][N], ans[M];
struct stu {
    int x, y;
    char s[2];
} ope[M];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a[i][j]);
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        for (int i = 1; i <= m; i++)
            scanf("%s%d%d", ope[i].s, &ope[i].x, &ope[i].y);
        int cnt = m;
        while (cnt) {
            for (int i = 1; i <= m; i++) {
                if(ope[i].x==0) continue;
                int x = ope[i].x, y = ope[i].y;
                if (ope[i].s[0] == 'H') {
                    bool flag = true;
                    for (int j = 1; j <= n; j++) {
                        if (a[x][j] && a[x][j] != y) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        for (int j = 1; j <= n; j++)
                            a[x][j] = 0;  //将这一行都赋为0
                        ope[i].x=0; //标记这个操作已完成
                        ans[cnt--] = i;
                    }
                }
                else if (ope[i].s[0] == 'L') {
                    bool flag = true;
                    for (int j = 1; j <= n; j++) {
                        if (a[j][x] && a[j][x] != y) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        for (int j = 1; j <= n; j++)
                            a[j][x] = 0;
                        ope[i].x=0;
                        ans[cnt--] = i;
                    }
                }
            }
        }
        for (int i = 1; i < m; i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[m]);
    }
    return 0;
}

Hdu 5387 Clock

链接

Clock

题意

给一个时间(hh:mm:ss),分别求时针和分针，时针和秒针，分针和秒针的夹角(小于等于180度)

分析

根据时间算出每根针离原点(12点)的角度大小，然后减一下即可，要注意处理钝角.
注意时间为24小时制，若hh>=12，hh要减12。若角度不是整数要输出的分数形式
为了保证精度，将每个值都扩大3600倍处理

参考代码

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
#include<stdio.h>
#include<stdlib.h>
const int mul=3600;
int hh,mm,ss;
int hm,hs,ms;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
void solve()
{
    if(hh>=12)
        hh-=12;
    hh*=mul,mm*=mul,ss*=mul;
    int aglH=30*(hh+mm/60+ss/3600);
    int aglM=6*(mm+ss/60);
    int aglS=ss*6;
    hm=abs(aglH-aglM);
    hs=abs(aglH-aglS);
    ms=abs(aglM-aglS);
    if(hm>180*mul) hm=360*mul-hm;
    if(hs>180*mul) hs=360*mul-hs;
    if(ms>180*mul) ms=360*mul-ms;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d:%d:%d",&hh,&mm,&ss);
        solve();
        int ghm=gcd(hm,mul);
        int ghs=gcd(hs,mul);
        int gms=gcd(ms,mul);
        if(ghm==mul)
            printf("%d ",hm/mul);
        else
            printf("%d/%d ",hm/ghm,mul/ghm);
        if(ghs==mul)
            printf("%d ",hs/mul);
        else
            printf("%d/%d ",hs/ghs,mul/ghs);
        if(gms==mul)
            printf("%d \n",ms/mul);
        else
            printf("%d/%d \n",ms/gms,mul/gms);
    }
    return 0;
}