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])

每天一句叨叨

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

点击查看

本文标题:Python写字符串模拟真香_算法日常[3/100]

文章作者:单林敏

发布时间:2019年08月04日 - 14:14:04

最后更新:2019年10月17日 - 21:44:06

原始链接:https://www.wolfdan.cn/算法日常-3-100/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%