30号下午有道难题第一题分析

今天下午的有道难题参加了,3题做了2道,而且全部没AC,第一个是WA,第二个是TLE。很郁闷,感觉自己还有好多要加强,这里废话也不多说,下午和群里朋友讨论了下,k发了一个很强悍的代码,个人感觉很好,但是不好理解,这里把代码和分析贴出来和大家一起学习。

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 <iostream>
#include <stdio.h>
#include <cstring>
#include<algorithm>
using namespace std;
 
int main()
{
	int n,k,tem,i,ans;
	char c;
 
	scanf("%d",&n);
	scanf("%c",&c);
	getchar();//这个很精辟的空格 用了2个接收字符
	for(i=0;i<n;i++)
	{
		ans=0;
		tem=0;
 
		while(scanf("%c",&c)&&c!='\n')
		{
			tem=tem&0x0f;       //取上一次c转换后的后四位
			tem=tem<<8;         //左移8位,使上次的后四位移至12~8位,这里大家可以考虑为什么是4位?
			tem=tem|c;          //与c抑或
			if((tem&0x00000fc0)==0x00000840)
				ans++;
			if((tem&0x000003f0)==0x00000210)
				ans++;
			if((tem&0x000000fc)==0x00000084)
				ans++;
			if((tem&0x0000003f)==0x00000021)
				ans++;
		}
		printf("%d\n",ans);
	}
 
	return 0;
}
/*这里给大家说下为什么是4位:
因为上一字符最后可能为da,这样此次字符开头是o就可以了*/
/*
上面的fc是11111100, 3f是00111111,
tem&0x00000fc0的作用就是去掉不相干的位,这个地方不好说,大家好好理解下.
0840 = 0000 1000 0100 0000
0210 = 0000 0010 0001 0000
0084 = 0000 0000 1000 0100
0021 = 0000 0000 0010 0001
大家看出来了吧。
里面全部包括了100001,这就是dao.

以下是题目:
描述
‘道’是中国古代哲学的重要范畴。用以说明世界的本原、本体、规律或原理。在不同的哲学体系中,其涵义有所不同。老子所写的《道德经》是关于‘道’的经典著作。

道的原始涵义指道路、坦途,以后逐渐发展为道理,用以表达事物的规律性。这一变化经历了相当长的历史过程。《易经》中有“复自道,何其咎”(《小畜》),“履道坦坦”(《履》),“反复其道,七日来复”(《复》),都为道路之义。

《尚书•洪范》中说:“无有作好,遵王之道;无有作恶,遵王之路。无偏无党,王道荡荡;无党无偏,王道平平;无反无侧,王道正直”。这里的道,已经有正确的政令、规范和法度的意思,说明“道”的概念已向抽象化发展。

—- 节选自有道词典(http://dict.youdao.com)

  Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一。它把每三个8Bit的字节转换为四个6Bit的字节(3*8 = 4*6 = 24),然后把6Bit再添两位高位0,组成四个8Bit的字节,也就是说,转换后的字符串理论上将要比原来的长1/3。

有道的工程师闲暇之余,将Base64编码改成了Base4编码,即把每个8Bit的字节转换成4个2Bit的字节,然后以4个字符来代替。编码和字符的对应方案如下:
00 —- a
01 —- o
10 —- d
11 —- 空格
这样,编码后的字符串就只会含有字符‘d’,’a’,’o’和空格。

例如字符y ,其ASCII码是121,对应的二进制串是01111001,这样分成 01 11 10 01四块后,用Base4编码后的字符串为”o do”。

有道的工程师很好奇,按照这种编码方式,编码后的字符串中含有多少个完整的dao呢?一个完整的dao由连续的‘d’,’a’,’o’三个字符组成。
输入
第一行有一个正整数n,代表接下来有n个待编码的原串。(1 <= n <= 10) 接下来有n行,每行有一个长度不超过106的原串,原串中的字符可能为ASCII码中除换行符以外的任意可见字符。 输出 共有n行,每行为一个整数k, 表示输入数据中对应的原串用Base4编码后含有多少个完整的dao。 样例输入 2 www.youdao.com dict.youdao.com 样例输出 1 1 提示 Java时限是标准时限的3倍,而且对于每个输入文件都有100ms的额外IO时间

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《30号下午有道难题第一题分析》有232个想法

  1. 而且全部没AC,第一个是WA,第二个是TLE,
    原来专业词汇在你这出现,
    我知道AC的意思,不知道WA,TLE的意思,
    加油做题。

发表评论

电子邮件地址不会被公开。 必填项已用*标注