Codeforces Round #253 Tutorial


443A - Anton and Letters

Simple and easy, solved by two lines of python code.

ls = filter(lambda y: y, map(lambda x: x.strip(), raw_input()[1:-1].split(",")))
print len(set(ls))

443B - Kolya and Tandem Repeat

Brute force. Just enumerate the beginning and the end of the substring, and …

more ...

A simple problem - World at War

Background

This problem is from the book "Algorithm 4th edition" (Exersise 4.1.10)

There are N cities and M undirected roads between those cities. People can travel to any city along the roads.

One day, a war breaks out. Our cities are under attack! As we can't defend all …

more ...

How to implement a queue with stack(s)?

This problem is from the book Algorithms, 4th Edition.

Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations.

Warning : high degree of difficulty.

When I search the Internet to find a solution, I find varieties of …

more ...

逗比带你读论文之Barrier

知识共享许可协议

逗比带你读论文之BarrierWizmann 创作

采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。

原文地址

Barrier February 17th, 2007

前言:我艹!好多核!

虽然80核心的浮点数运算巨兽离我们还有些遥远,但是多核处理器已经走进了我们的生活。

其实多核处理器已经不是新鲜名词了,在Power Macintosh 9500中,就使用了多核处理器。

现在让我们深入了理解一下多核心处理器吧。

线程技术

一些名词定义

线程

线程只是 抢占调度的(pre-emptively scheduled) 共享地址空间的 执行上下文。

多线程

用来简化控制流和绕开阻塞的系统调用的方法,并非用来实现程序的并行化

并发多线程

在物理上并发的线程,用来利用多核处理器来优化系统性能

为什么“并发多线程”是个神坑

人人都在说”并发多线程“是个神坑,但这种老生常谈并不是因为自然原因 …

more ...

Codeforces Round #242 (Div. 2) Tutorials and Solutions

A. Squats

Trun x => X or X => x to make the number of 'x' is equal to the number of 'X'.

n = int(raw_input())
hamsters = [c for c in raw_input()]

sits = hamsters.count('x')
stands = hamsters.count('X')

if sits == stands:
    print 0
    print ''.join(hamsters)
else:
    if sits > stands …
more ...


"alloca" vs "placement new"

WHAT?!

For most time, we use malloc or new for memory allocation, which will get it on heap.

However, access memory on heap is not as effective as the memory on stack, because the heap is "free-floating region of memory". To the contrary, memory on stack is managed by CPU …

more ...

Quartile and Normal Distribution

What is Quartile?

Quartile is a concept of descriptive statics. The quartiles of a ranked data set are the three points that divide the data set into four equal groups, each group comprising a quarter of data.

Definitions

first quartile (Q1)

First quartile, also known as lower quartile, splits off …

more ...

破解节操的下限

啥?

节操精选

节操精选是一个没有下限的文字图片聚合类移动应用,现在支持Android/iOS移动平台。

界面

本人是一个非常懒的人,有电脑就不想碰手机。。。于是萌生了一个在PC端使用这个应用的想法。。。

HowTo

从界面上我们可以看出,这个App的逻辑其实比较简单。重要的部分有如下几个:

  • 获取CS通信协议(最重要)

  • 频道间切换(精选 - 热门 - 音频- 阅读)

  • 展示某一条精选

  • 在某一条精选中播放语音

获取通信协议

节操还是非常良心的!并没有在后台数据通信中进行任何加密的措施。

抓包工具我使用的是在Windows环境下的Fiddler

这个工具可以建立一个HTTP代理,手机通过代理上网,在电脑上就可以截获所有的数据包进行分析。

在Linux下,可以使用TinyProxy + Wireshark进行抓包,不过配置小麻烦。不过我一直是在Windows下抓包,然后在Linux下做分析和开发的。=。=。。。

图就不上了,如果大家有兴趣自己来搞的话,可以抓来试试。

简而言之,我们从HTTP包中的Content-type字段中,发现了我们想要的信息 —— application/xprotobuf

我去!真良心~

Protobuf简介 …

more ...

GeoHash算法

GeoHash

Geohash is a latitude/longitude geocode system invented by Gustavo Niemeyer when writing the web service at geohash.org, and put into the public domain. It is a hierarchical spatial data structure which subdivides space into buckets of grid shape.

简单说,GeoHash是一个将经纬度信息编码成一个string的算法。从而便于储存、查找。

GeoHash算法的步骤

GeoHash对经度纬度分别编码,原理是迭代做二分,进而逼近真实值。

我们以纬度举例 …

more ...