wolfdan's blog

0%

Python写字符串模拟真香_算法日常[3/100]

发表于 更新于 分类于 Valine：
Python写字符串模拟真香_算法日常[3/100]

题目

链接

2019牛客多校第6场B题

描述

解法

解法一

把8段中每段都处理成为一个整数,然后找出最长的连续0,相同的长度的话就让0放前面的段(因为0的ASCII码是48,比:的58小),然后进行判断性输出(数字用%x可以实现以16进制输出)

详见代码注释

C++版AC代码

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
/*"%x"以16进制的形式输出,是我孤陋寡闻了*/
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[10];
int main(){
    int T,t;
    scanf("%d",&T);
    for(int ii=1;ii<=T;ii++){
        int f=0,l=0,nl=0;
        /*观察下面的代码容易知道,只有最前面为0的时候是f=1,
        其他地方为0,f为i-nl(减掉了0的长度即为0开始的地方)

        综上:
        f是最长连续0开始的位置
        然后l是保存维护最长连续0的长度
        nl是当前的最长连续0的长度*/
        for(int i=1;i<=8;i++){
            a[i]=0;
            for(int j=1;j<=16;j++){
                scanf("%1d",&t);
                a[i]=a[i]*2+t;
            }
            if(!a[i]) nl++;
            else{
                /*判断现在的连续0的数目是否超过之前的连续0的数目*/
                if(nl>=l&&nl>1){
                    f=i-nl;l=nl;
                }
                nl=0;
            }
            if(i==8&&nl>1){
                if(nl>l){
                    f=i-nl+1;l=nl;
                }
                /*末尾有0，但是末尾的连续0和最前面的连续0相同
                所以考虑字典序最小，由于'0'-48,':'-58
                所以优先让前面输出0,后面就输出':'*/
                if(nl==l&&f==1){
                    f=i-nl+1;l=nl;
                }
            }
        }
        printf("Case #%d: ",ii);
        if(f==1)printf(":");
        for(int i=1;i<=8;i++){
            if(i==f){
                printf(":");
                i+=l;
            }
            if(i>8)puts("");
            else printf("%x%c",a[i],":\n"[i==8]);
        }
    }
    return 0;
}

解法二

通过枚举每种有0的串，然后统一加到一个列表中，之后通过sort(优先长度然后优先字典序)，最后输出

详见我的Python注释代码

Python_AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
T=int(input())
for t in range(T):
    b=input()
    a=[]
    for i in range(8):
        # 这个[2:]是去掉'0x'
        a.append(hex(int(b[i*16:i*16+16],2))[2:])
    s=[]
    s.append(':'.join(a))
    for i in range(8):
        for j in range(i+1,8):
            # 对每个i中的后缀长a[i:j+1]判断各元素是否都是等于0的
            # 是就直接把字符串丢进去,比C++AC版本中的记录长度简单很多
            if all(map(lambda x:x=='0',a[i:j+1])):
                # 用':'分隔的a[i]串
                s.append(':'.join(a[:i])+'::'+':'.join(a[j+1:]))
    # 优先用长度排序,其实是同长度按照字典序排序
    s.sort(key=lambda x:(len(x),x))
    print('Case #%d:'%(t+1),s[0])

每天一句叨叨

岁月还漫长总会有人陪你骑马喝酒走四方

相关文章