发表于 | 更新于 |

这题是二分+贪心，关键在于贪心策略，移走石头即合并线段，从左向右扫描一个坐标区间，如果长度合适（大于等于二分的答案）就移动左端点，不合适就固定左端点同时进行一次合并（计数器加一），如果合并次数在m以内就认为存在一个方案。

阅读全文 »

发表于 | 更新于 |

笔记主要参考：Python网络爬虫与信息提取

bs4库的基本元素

概念 解释
Tag 标签
Name 标签名 .name
Attributes 属性 .attrs 返回值为字典类型
NavigableString 字符串 .string
Comment 注释 .comment

标签树的遍历

向上遍历

  • .parent < Tag >
  • .parents < Generator >

    向下遍历

  • .contents < list > 只会列出下一层孩子节点
  • .children < list_Iterator >用于for循环遍历，只会遍历下一层孩子节点
  • .descendants < Generator >用于for循环遍历，会递归遍历子树所有孩子节点

    平行遍历（遍历同一颗子树中的兄弟节点，兄弟节点可以是标签也可以是独立的字符串，包括换行符）

  • .next_sibling < Tag >
  • .previous_sibling
  • .next_siblings < Generator >
  • .previous_siblings

信息的标记

  • XML是一种标签标记语言
    • 标签 < name > … < /name > 或 < name / >
    • 注释 < !– Comments – >

  • JSON是一种用有类型的键值对表达信息的方式（如ss的配置文件）

    1
    2
    3
    "key" : "value"
    "key" : ["value1", "value2"]
    "key" : { "subkey" : "subvalue"  }

  • YAML是一种用无类型键值对表达信息的形式（如hexo的_config.yml）

    1
    2
    3
    4
    5
    6
    key : value
    key : #comment
    - value1
    - value2
    key:
    subkey: subvalue

  • 各自特点

    • XML Internet上的信息交互与传递（如html）
    • JSON 移动应用云端和节点的信息通信，无注释 （如ss的配置文件，它可以作为程序的一部分执行）
    • YAML 各类系统的配置文件，有注释易读（如hexo）

信息的搜索与提取

  • <>.get() 获取某个Tag下某项属性的值
  • <>.find_all(name, attrs, recursive, string, \*\*kwargs)
  • name 标签名，如果要搜索多个名字可以用列表类型，如[‘a’, ‘b’]
  • attrs 属性值（可以是部分属性，注意是用字典类型表示）
  • recursive 是否递归搜索，默认为True
  • string 搜索NavigableString，可以配合正则表达式使用
  • **kwargs 允许像id = 'link1'这样直接搜索属性
  • 允许这样用：<>.find_all('p', string = 'Python Course')
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    <>.find_all()等价于<>()
    <>.find()搜索且只返回一个结果
    <>.find_parents() < list >
    <>.find_parent() < Tag >
    <>.find_next_sibling()
    <>.find_next_siblings()
    <>.find_previous_sibling()
    <>.find_previous_siblings()
    <>.find_next() 搜索HTML文本中下个位置出现的结果
    <>.find_all_next()

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·

发表于 | 更新于 |

笔记中的解释出处：Python网络爬虫与信息提取

reponse对象

构造一个response对象

r = requests.get("http://www.google.com", timeout = 30)

response对象的属性

对象成员 解释
r.status_code HTTP请求的返回状态，200表示连接成功，404表示失败
r.text HTTP响应内容的字符串形式，即，url对应的页面内容
r.encoding 从HTTP header中猜测的响应内容编码方式，如果header中不存在charset，则认为编码方式为ISO-8859-1
r.apparent_encoding 从内容中分析出的响应内容编码方式（备选编码方式）这种方法比较慢
r.content HTTP响应内容的二进制形式

Requests库的异常

异常名称 解释
requests.ConnectionError 网络连接错误异常，如DNS查询失败，拒绝连接等
requests.HTTPError HTTP错误异常
requests.URLRequired URL缺失异常
requests.TooManyRedirects 超过最大重定向次数，产生重定向异常
requests.ConnectTimeout 连接远程服务器超时异常
requests.Timeout 请求URL超时，产生超时异常
r.raise_for_status() 如果r.status_code不是200，会引发异常requests.HTTPError

Requests库的7个主要方法

方法 解释
requests.request() 构造一个请求，支撑以下各方法的基础方法
requests.get() 获取HTML网页的主要方法，对应于HTTP的GET
requests.head() 获取HTML网页头信息的方法，对应于HTTP的HEAD
requests.post() 向HTML网页提交POST请求的方法，对应于HTTP的POST
requests.put() 向HTML网页提交PUT请求的方法，对应于HTTP的PUT
requests.patch() 向HTML网页提交局部修改求求，对应于HTTP的PATCH
requests.delete() 向HTML页面提交删除请求，对应于HTTP的DELETE

HTTP协议对资源的操作

操作 解释
GET 请求获取URL位置的资源
HEAD 请求获取URL位置资源的响应消息报告，即获得该资源的头部信息
POST 请求向URL位置的资源后附加新的数据
PUT 请求向URL位置存储一个资源，覆盖原URL位置的资源
PATCH 请求局部更新URL位置的资源，即改变该处资源的部分内容
DELETE 请求删除URL位置存储的资源

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·

发表于 | 更新于 |

果然Python和C/C++系的语法差别很大。。在学了C/C++之后再学Python，有种当初从Pascal转C++的既视感，相比之下C/C++转Java感觉就简单多了。
这里记录一下学习Python的笔记，其中标注了部分Python与C/C++明显差别的用法。
其中大部分Python语法解释来源于Python语言程序设计

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1207

这题一开始考虑过用时间和坐标作为状态来着，不过没有必要，直接用地鼠的序号做状态就行了，状态转移时判断一下坐标距离是否满足条件即可。

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1391
根据仔细分析题意后可以找出n和坐标x, y有如下关系：

n%4 x y
0 n/2 n/2
1 n/2+1 n/2+1
2 n/2+1 n/2-1
3 n/2+2 n/2

枚举n求出对应的x, y并用二维的map建立索引就可以了。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1285
题目给定战胜关系，求每队的排名，看起来与POJ3660很像，但前者是求出每队的排名（可能不唯一），后者是判断每一队的排名是否唯一。
这题可以用拓扑排序做，但要特别注意输出的次序是从小到大的，这里把拓扑排序的队列修改为优先队列，就能按顺序输出了。

阅读全文 »