2014-01-14

UVa 11988 Broken Keyboard (a.k.a. Beiju Text)——字符串

这题是我最喜欢的字符串处理。。。。。

题目大意是给你一个字符串，字符串是模拟键盘的记录的，其中[代表Home键，]代表End键。求这样按下键盘后的屏幕输出。

按照题目要求模拟一下即可。

本题最直接的思路就是模拟一下这个过程，但是这需要在一串字符之前加上另一个串，所以这里用了双向队列。

双向队列是可以在前边和后边插入元素的数据结构。在这里，双向队列仅仅记录一下字符串的“指针”（←，就是下标），而不真正的移动字符串，等到要输出的时候，按照指针顺序输出字符串。

AC代码如下：

#include <iostream> 
#include <deque> 
using namespace std; 
int main(int agrc, char *agrv[]) { 
    string str; 
    while(getline(cin, str)) { 
        deque<int> output; 

        //记录起点 
        output.push_back(0); 
        for(int i=0; i < str.length(); i++) 
        //在检测到按下Home后，把当前指针记录在双向队列前端。 
            if(str[i] == '[') output.push_front(i + 1); 
        //在检测到按下End后，把当前指针记录在双向队列末端。 
            else if(str[i] == ']') output.push_back(i + 1); 
        //按照双向队列中记载的输出顺序分段输出。 
        for(deque<int>::iterator it = output.begin(); it != output.end(); it++) 
            for(int i = (*it); str[i] && str[i] != '[' && str[i] != ']'; i++) cout.put(str[i]); 
        cout<<endl; 
    } 
}

2014-01-14

HDU 4715 Difference Between Primes——素数筛选，二分查找(STL)

这是HDU 4715 Difference Between Primes。由于这几天HDU有些问题，我这里打不开网页，所以我也就不贴链接了。

题目大意是说：对于每个偶数x，都能找到一个两个素数a b，使得a-b=x。

让你验证这个结论，给出x，求出a和b。（x≤1000000）

方法很简单，就是先打个素数表，对于每个给定的数，枚举小的数，二分查找大数即可。

这篇文章中的素数筛选法参考了kuangbin大神和shu_mj的写法，这是一个十分神奇的筛选法。在筛选过程中，每个非质数平均只被访问标记一次，所以效率非常高。

关于题目中的“如果不能查找到则输出FAIL”。其实可以证明，这种情况是不可能出现的。我们把这个程序运行一遍，遍历1~1000000间的所有偶数，都没有出现一个FAIL。所以代码里边这部分内容就略过了。

关于STL的binary_search和lower_bound两者的实现都是二分查找，但是lower_bound会返回一个迭代器，告诉你找到的位置，而binary_serach是返回一个布尔型告诉你有没有找到。

这两种方法一般来说有着不同的作用。这里显然是用binary_serach更好一些。

今天还发现binary_serach有着更为强大的功能：一般来说，binary_serach要求随机访问迭代器，可是在一些没有随机访问迭代器的数据结构上，比如map和list，binary_serach将自动降级为线性搜索算法完成搜索。（←，可见STL确实强大。。。。）

以下为AC代码：

#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 

vector<int> getPrime(int n) { 
    vector<int> prime; 
    bool *vis=new bool[n](); 
    for(int i=2;i<n;i++){ 
        if(!vis[i]) 
            prime.push_back(i); 
        for(int j=0;j<prime.size();j++) { 
            if(i*prime[j]>=n) break; 
            vis[i*prime[j]]=true; 
            if(i%prime[j]==0) break; 
        } 
    } 
    return prime; 
} 
int main(int agrc, char *agrv[]) { 
    vector<int> prime=getPrime(20000000); 

    int caseNum; 
    cin>>caseNum; 
    while(caseNum--){ 
        int x; 
        cin>>x; 

        bool sign; 
        if(x>=0) sign=true; 
        else sign=false,x=-x; 

        int a,b; 
        for(int i=0;i<prime.size();i++){ 
            b=prime[i]; 
            a=b+x; 
            if(binary_search(prime.begin(),prime.end(),a)){ 
                sign&&(cout<<a<<" "<<b<<endl)(cout<<b<<" "<<a<<endl); 
                break; 
            } 
        } 
    } 
}

2014-01-12

FeelyBlog 自动保存的更新

终于可以自动保存了。。。。。

虽然这么说，但是我已经被无法自动保存损失过很多数据了。。。

比如昨天那一次，当我写好几百个字的解题报告之后，按下“发布”按钮，之后浏览器告诉我——

该页无法显示

那时候直接心都凉了。。

于是我迫切的做了这个功能。

当然，这次的更新不止是自动保存。

比如更加严格的提交成功的判定，提交的时候不会随意跳转了。而且弹出的提示现在有“确定”和“取消”两个按钮，只有按下“确定”的时候，才会跳转。

还有手动保存。界面上并没有保存的按钮，也没有草稿箱功能。

不过如果每分钟一次的自动保存满足不了你。Ctrl+S随时欢迎你。

这个对于我这种写代码的时候经常按Ctrl+S的人简直是必要的东西。。。

以前总是弹出的“另存为”简直难受。。。嗯，它提醒着我这是网页不是编辑器。。。不过，凭什么网页就不能用Ctrl S保存呢。。

其他的更新还包括增加了删除博文的功能。

以及上一篇/下一篇链接的智能化。现在上一篇/下一篇链接不是简单的取id+1/id-1的文章名称，而是真正在数据库中查找发表时间排序的上一篇和下一篇。

更多的更新请参见Feelyblog GitHub主页。

另外，由于今天在学校机房上网，发现GitHub速度简直不能忍，于是我在开源中国放了一份备份代码，地址是http://git.oschina.net/zyzsdy/Feelyblog 。

2014-01-12

CodeForces 381B Sereja and Stairs——贪心

From CodeForces Contests #223 Div. 2 Problem B

话说这次CF两道水题啊。。。可惜没有把握好机会。

按照这样的趋势，我已经预感到了我的排名会继续往下掉，直到无尽的灰色。。。。。

感觉这题是Special Judge的（←所以我连最后的空格都没删）。。。。我觉得我完全没读懂题目是如何要求最后输出的就根据题目要求做了几个字符串输出居然就AC了。。。

方法更是简单粗暴：先排个序，然后建一张表，把数组中的数字当作键名，出现次数作为值。然后按照键名从大到小输出两次，分别存入两个表里。

然后判断顶部是不是相同，如果相同就弹掉一个。

然后把其中一个表倒序。两个表合并。输出。

如果使用C++来写这题，用和我相同的方法可以使用STL的map容器。map容器是自动按照键名从小到大排序的，所以并不需要处理排序的问题。

<?php 
//处理输入 
$in=fgets(STDIN); 
$in=intval($in); 
$str=fgets(STDIN); 
$arr=explode(" ", $str); 
foreach ($arr as &$va) { 
    $va=intval($va); 
} 

//倒序排列$arr数组 
rsort($arr); 

//根据$arr整理出表（←表的含义如上分析） 
$ans=array(); 
foreach($arr as $v){ 
    if(empty($ans[$v])){ 
        $ans+=array($v=>1); 
    }else{ 
        $ans[$v]++; 
    } 
} 

//把每个不同的元素输出，第一次。 
$i=0; 
$tar=array(); 
foreach ($ans as $k=>&$v) { 
    if($v!=0){ 
        $tar[$i]=$k; 
        $v--; 
        $i++; 
    } 
} 

//把每个不同的元素输出，第二次。注意如果某个值已经为0，则不输出。 
$i=0; 
$car=array(); 
foreach ($ans as $k=>&$v) { 
    if($v!=0){ 
        $car[$i]=$k; 
        $v--; 
        $i++; 
    } 
} 
//$arr中剩下的值都是我们不需要的，我们只需要这两次输出的元素就可以构造出符合题意的解。 

//判断两次输出顶部元素是否相同，如果相同就弹出其中一个。 
if($tar[0]==$car[0]) unset($tar[0]); 
//反序其中一个输出，因为我是从大到小排列的，所以这个反序后的数组将会排到前面。 
$car=array_reverse($car); 

//根据题意构造输出。 
$num=count($tar)+count($car); 
echo $num."n"; 
foreach ($car as $v) { 
    echo $v." "; 
} 
foreach ($tar as $v) { 
    echo $v." "; 
} 

?>

2014-01-12

CodeForces 381A Sereja and Dima——贪心

CodeForces Contests #223 Div. 2 Problem A

这次-83分，成功降级到了浅绿色。。。。

本题一开始错误理解了题意。直到半个小时才反应过来不是排序。之后没有把PHP的字符串转换为整数。于是错误两次，54分钟通过。

只要按照题目的过程模拟计算，最后输出结果就可以了。没有其他特殊的算法。

以下为代码：

<?php 
$in=fgets(STDIN); 
$str=fgets(STDIN); 
$arr=explode(" ", $str); 

$flag=true; 
$a=0;$b=0; 
$l=0;$r=intval($in)-1; 
foreach ($arr as &$va) { 
    $va=intval($va); 
} 
while($l<=$r){ 
    if($arr[$l]>$arr[$r]){ 
        if($flag){ 
            $a+=$arr[$l]; 
            $l++; 
            $flag=!$flag; 
        }else{ 
            $b+=$arr[$l]; 
            $l++; 
            $flag=!$flag; 
        } 
    }else{ 
        if($flag){ 
            $a+=$arr[$r]; 
            $r--; 
            $flag=!$flag; 
        }else{ 
            $b+=$arr[$r]; 
            $r--; 
            $flag=!$flag; 
        } 
    } 
} 
echo $a." ".$b; 
?>

2014-01-11

UVa 11991 Easy Problem from Rujia Liu? ——(STL map)

STL的应用题目：

题目大意：

给出一个数组，找到其中第n个给定的数值，输出它从1开始的下标。

Input

8 4
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2

第一行是两个整数n，m。表示数组有n个元素，下一行给出了这个数组。
接下来的m行每行表示一个查询，包含两个整数k和v。

Output

任务是找出数组中第k个v值的下标（1-based）

这题不用常规思路，而是考虑使用STL的map。

将数组的数字作为map的下标，将这个数在数组中第几次出现作为值记录下来。因为一个数会出现多次，所以考虑采用vector容器，将这些值保存在vector中。

这样本题使用STL容器map<int, vector<int>> Array。

在查询的时候，只需要查询Array[v][k-1]，然后把这个值输出就可以了。

但是由于存在找不到的情况，所以换用at()方法。at方法在越界的时候会抛出out_of_range异常，我们只要接收这个异常，然后输出0即可。

下面是AC代码：

#include <iostream> 
#include <stdexcept> 
#include <vector> 
#include <map> 
using namespace std; 

map<int, vector<int>> x; 
int main(int agrc, char *agrv[]) { 

    int n,m,k,i,v; 
    while(cin>>n>>m) { 
        x.clear(); 
        for(i=1;i<=n;i++) { 
            cin>>k; 
            x[k].push_back(i); 
        } 
        for(i=1;i<=m;i++){ 
            cin>>k>>v; 
            try{ 
                cout<<x[v].at(k-1)<<endl; 
            }catch(out_of_range &exc){ 
                cout<<0<<endl; 
            } 
        } 
    } 
}

PS out_of_range定义在stdexcept头文件中，我曾经因为未包含此头文件结果CE掉的奇怪错误。

2014-01-09

UVa 112 Tree Summing ——字符串处理（大误）

今天写了一道十分有感觉的字符串处理题目。

题目简介

原题：UVa 112 Tree Summing

题目给出了一个十分具有Lisp风格的字符串，来表示一个二叉树，就像这样：

1	(5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))

所要完成的任务是：判断每条从根部到叶子的路径上数的和是否等于一个给定的常数，如果是，则输出“yes”，否则输出“no”。

虽然是二叉树的题目，但是并不需要建立二叉树。只需调用递归函数，由系统来创建基于函数的二叉树。

所以我才说这题是字符串处理嘛~~~~

题目分析

这题有几个坑的点。

空树，就像这样

0 ()

这种东西按照题目要求是要输出”no”的。在有些代码里面不需要特殊判断。

负数

1	5 (18 ( - 13 ( ) ( ))())

如果像我一样自己处理读入的数，就一定要注意负数的问题。这题负数就坑到我一回。在以上的测试样例中应该返回”yes”

叶子结点指的是左子树和右子树都为空的结点。

在我的第一个版本的代码里面，就是在左子树或右子树有一个为空时就输出了当前的和。

1	20 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )

刚好就撞到了上面这组测试数据的枪口上。。。

我的实现

不得不说我还是对C语言十分的喜爱啊。。

虽然打开编译器创建了一个test26.cpp的文档，想写个C++来做这件事情。但是写完之后才发现，我还是只用了#include <stdio.h> 一个头文件。

1. 宏Getchar(x)

计算机读取数据是个十分矛盾的过程，比如我想要读取一个数字，读到左括号那里结束。但是如果我不读取出那个左括号，我就不知道我数字已经读取结束了。如果读出了那个左括号，我又相当于多读了一个东西。

所以我用了一个变量buffer存储这个多读出来的值，用另一个变量bufflag标志有没有使用这个buffer。

在此基础上我重写了getchar，如果buffer正在使用，则返回buffer中的值，否则返回输入流的下一个字符。

代码如下：

if(bufflag) { 
    bufflag = 0; 
    x = buffer; 
} else {
    x = getchar(); 
}

2. 宏jumpSpace(x)

题目要求是这个字符串中间可以有任意的空白字符。于是我写了这个宏用来跳过中间所有的空白字符。

这个宏会循环调用宏Getchar(x)，直到它找到一个不是空白字符的字符，并把结果返回给x。

代码如下：

1
2
3

do { 
    Getchar(x); 
} while (x == ' ' x == '\n' x == '\t' );

3. 宏ispnum(ch)

这个宏只被调用了一次。它用来判断读到的内容是不是一个数字。

注意，由于存在负数，所以如果读到-，也将被视为读到了一个数字，它代表即将读到的数是个负数。

实际上此时ch可能的值只有数字、-和)。其他的值都是不正确的。

代码如下：

1	ch=='-'?1:(ch>='0'&&ch<='9'?1:0)

4. 宏nextNum(ch)

这个宏用来整理接下来即将从输出流中读出的一个整数。

如果ch为一个数字，接下来就会调用这个宏来找出以这个数字开头的完整的整数。这个宏将一直读到遇到第一个不是数字的地方停止。

但是此时它已经从输入流里读出了多余的东西。所以在这个宏的末尾，需要把这个多读出来的东西写入buffer。

代码如下：

if(ch == '-') { 
    scanf("%d", &ch); 
    ch = -ch; 
} else { 
    ch -= '0'; 
    Getchar(k); 
    while(k >= '0' && k <= '9') { 
        ch = ch * 10 + ( k - '0' ); 
        Getchar(k); 
    } 
    buffer = k; 
    bufflag = 1; 
}

完整AC代码如下：

#include <stdio.h> 
#define Getchar(x) if(bufflag){bufflag=0;x=buffer;}else x=getchar() 
#define jumpSpace(x) do{Getchar(x);}while(x==' 'x=='\n'x=='\t') 
#define ispnum(ch) ch=='-'?1:(ch>='0'&&ch<='9'?1:0) 
#define nextNum(ch) if(ch=='-'){scanf("%d",&ch);ch=-ch;}else{ch-='0';\ 
                Getchar(k);while(k>='0'&&k<='9'){ch=ch*10+(k-'0');Getchar(k);}\ 
                buffer=k;bufflag=1;} 
int caseNum; 
int flag; 
int buffer; 
int bufflag=0; 
int Insert(int sum){ 
    int ch; 
    int num; 
    int k; 
    jumpSpace(ch); 
    jumpSpace(ch); 
    if(ispnum(ch)){ 
        nextNum(ch); 
        num=sum+ch; 
        if(Insert(num)&Insert(num)) 
        if(num==caseNum) 
        flag=1; 
    }else return 1; 
    jumpSpace(ch); 
    return 0; 
} 
int main(int agrc, char *agrv[]) { 
    while(scanf("%d",&caseNum)!=EOF) { 
        flag=0; 
        Insert(0); 
        flag?printf("yes\n"):printf("no\n"); 
    } 
    return 0; 
}

2014-01-05

评论区右下小窗视频，bilibili跟进略快啊。

今天在B站看视频的时候想发一条评论，结果发现bilibili已经默默的跟进了“边看边评”。。。。

bilibili右下角的视频小窗

“边看边评”是最近优酷网加入的新功能，即用户在观看视频的时候，如果把页面拉到评论区，则原来正在播放视频的窗口将变成一个mini窗口在右边空白区域展示。

不过bilibili的实现略水啊。。。只是简单的在视频播放器位置从屏幕里消失了之后，把播放器dom搬到右下角的fixed框架内。。。。滚动条回到上面的时候再搬回来。

这种实现的好处是在右下角的小窗内可以实现播放控制。缺点也同样是这个，我一点视频内容就暂停播放了。可以让我拖动的地方很小。

优酷的小窗虽然可以拖动任何位置，但是面积就更小了。基本上像个广告窗格一样。

虽然缺点非常多，但是这确实是很人性化的一个功能。

既然优酷产品经理欢迎“抄袭”，希望更多的视频网站加入这一功能，当然，希望能把用户体验做的更好。

2014-01-04

Feelyblog！？

Feelyblog就是我自己开发的这个博客程序了。。。。

本来开发FeelyBlog的初衷就是，想做一个更依赖前端而不是依靠服务器端的blog。目的大概就是降低服务器压力吧，毕竟自己用的这种特别小的服务器本身就不怎么抗压。

于是，最近被人推荐了Ghost和Typecho。。。。。。。。。。。。。。。。。。。。前者是为了替代Wordpress开发的。因为wordpress越来越走上邪路了。后者是个国产的博客程序。

这两个的官方网站的网址也起的十分有感觉啊。。。分别是它们的名字加上.org。。。。。（←似乎是想吐槽CP？）

关注到这两个博客系统的主要原因还是因为它们都是用Markdown写作的博客。。这是我最想要的。。我怎么早一点的时候没有发现呢。。。

2014-01-02

我有一个好图床

我的博客并不支持上传图片。这一方面是我懒的写，另一方面也是节约服务器空间。

但是我添加图片并不困难。

这是因为——我有一个好图床。

http://weibotuchuang.sinaapp.com/

更新：

2019年开始微博增加反外链图片，因此使用微博作为外链图床的模式已失效