日历
网志分类
· 所有网志 (15)
· 水牛小屋 (4)
· 算法学习 (6)
· ACM/ICPC (3)
· WEB开发 (0)
· 桌面开发 (0)
· 未分类 (2)
最新的评论
站内搜索
友情链接
· ZJU
· HDU
· PKU
· TC
· UVA
· SPOJ
· SGU
· URAL
· EL
· ProjectEuler
· Mathpuzzle
· CodeProject
· Algorithmist

订阅 RSS

0003864

歪酷博客

丁丁


saintqdd @ 2010-03-15 22:33

Central Europe 1995
 
1008
Central Europe 1995
1011
Central Europe 1995
1012
Central Europe 1995
1025
Central Europe 1995
1026
Central Europe 1995
1039
Central Europe 1995
1040
Central Europe 1995
1041
Central Europe 1995
 
CE1995的题目简单点评:
 
PKU1008:
题目类型:直接做
可能取模的时候会有点小麻烦,注意一下就OK了
 
PKU1011:
题目类型:搜索+适当剪枝
简单的说是个划分问题,一堆数字,num1,num2,num3….
将他们划分成尽可能多的堆,每堆的和是相等的
 
PKU1012:
题目类型:数学
约瑟夫的数学模型,此处使用的是弹出的人的顺序的数学模型。
 
PKU1025:
题目类型:模拟
可能有点麻烦,我的想法:一切按照时间来安排,时间是一秒一秒的递增,可能有点慢。POJ测速是32ms
 
PKU1026:
题目类型: 直接做
可能会TLE,在求循环点的时候,求每个位的循环点,即可
 
PKU1039:
题目类型:计算几何
刘汝佳黑书上有指点,我就用的笨方法,最终光线都是连接在拐点的地方
 
PKU1040:
题目类型:搜索
有点类似背包问题,不过需要先排序,这样会快很多
 
PKU1041:
题目类型:搜索
求欧拉回路的,而且按照字典序最小的输出。利用欧拉回路的性质判断有无欧拉回路
然后从要求点开始搜索。此题图的存贮,采用边为下标,即G[edg][2]



 
saintqdd @ 2010-03-15 09:34

Qsort,这是我经常用的排序函数,因为是快排,速度还是可以的。但是就是这样也会有被陷害的时候。看下面代码
#include <stdio.h>
#include <stdlib.h>
 
int cmp(const void *a,const void *b)
{
    int r = (*(int*)a) - (*(int*)b);      (1)
    int r = (*(int*)a) > (*(int*)b);      (2)
    int r = (*(int*)a) > (*(int*)b)?1:-1; (3)
    return r;
}
 
int main()
{
    int i,a[9]={8,7,6,5,4,3,2,1,9};
    qsort(a,9,sizeof(a[0]),cmp);
    for(i=0;i<9;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    system("pause");
    return 0;
}
 
能够被正确执行排序任务的是(1)和(3).
原来这个比较函数,不是用1和0来区分的,而是正负。像(3)的写法就能正确的比较了



 
saintqdd @ 2010-03-05 21:21

 
#include <stdio.h>
#include <stdlib.h>
 
int arr[1000001];
 
void quicksort(int *A,int left,int right)
{
    int i = left,j = right,x=A[left],t;
    if(left<right)
    {
        while(1)
        {
            while(A[++i]>x);
            while(A[--j]<x);
            if(i>=j) break;
            t=A[i];
            A[i]=A[j];
            A[j]=t;
        }
        A[left]=A[j];
        A[j]=x;
        quicksort(A,left,j);
        quicksort(A,j+1,right);
    }
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",arr+i);
    quicksort(arr,0,i);
    for(i=0;i<n;i++)
        printf("%d ",arr[i]);
    printf("\n");
    return 0;
}


 
saintqdd @ 2010-03-05 20:25

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
#include <functional>
#include <queue>
#include <vector>
using namespace std;
 
int main()
{
    priority_queue< int,vector<int>,greater<int> > qi;
    int n,i,t,a,b,c,sum;
    while(scanf("%d",&n)!=-1)
    {
        while(!qi.empty()) qi.pop();
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            qi.push(t);
        }
        sum = 0;
        while(qi.size()!=1)
        {
            a = qi.top();qi.pop();
            b = qi.top();qi.pop();
            c = a+b;
            sum += c;
            qi.push(c);
        }
        printf("%d\n",sum);
    }
    return 0;
}
 
参考资料:
在优先队列中,优先级高的元素先出队列。
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
优先队列的第一种用法,也是最常用的用法:
priority_queue<int> qi;
通过<操作符可知在整数中元素大的优先级高。
故示例1中输出结果为:9 6 5 3 2

第二种方法:
在示例1中,如果我们要把元素从小到大输出怎么办呢?
这时我们可以传入一个比较函数,使用functional.h函数对象作为比较函数。
priority_queue<int, vector<int>, greater<int> >qi2;
其中
第二个参数为容器类型。
第二个参数为比较函数。
故示例2中输出结果为:2 3 5 6 9

第三种方法:
自定义优先级。
struct node
{
    
friend bool operator< (node n1, node n2)
    {
        
return n1.priority < n2.priority;
    }
    
int priority;
    
int value;
};
在该结构中,value为值,priority为优先级。
通过自定义operator<操作符来比较元素中的优先级。
在示例3中输出结果为:
优先级 
9          5
8          2
6          1
2          3
1          4
但如果结构定义如下:
struct node
{
    
friend bool operator> (node n1, node n2)
    {
        
return n1.priority > n2.priority;
    }
    
int priority;
    
int value;
};
则会编译不过(G++编译器)
因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
而且自定义类型的<操作符与>操作符并无直接联系,故会编译不过。

//
代码清单
 
#include<iostream>
#include<functional>
#include<queue>
using 
Namespace stdnamespace std;
struct node
{
    
friend bool operator< (node n1, node n2)
    {
        
return n1.priority < n2.priority;
    }
    
int priority;
    
int value;
};
int main()
{
    
const int len = 5;
    
int i;
    
int a[len] = {3,5,9,6,2};
    //
示例1
    priority_queue<
int> qi;
    
for(i = 0; i < len; i++)
        qi.push(a[i]);
    
for(i = 0; i < len; i++)
    {
        cout<<qi.top()<<" ";
        qi.pop();
    }
    cout<<endl;
    //
示例2
    priority_queue<
int, vector<int>, greater<int> >qi2;
    
for(i = 0; i < len; i++)
        qi2.push(a[i]);
    
for(i = 0; i < len; i++)
    {
        cout<<qi2.top()<<" ";
        qi2.pop();
    }
    cout<<endl;
    //
示例3
    priority_queue<node> qn;
    node b[
len];
    b[0].priority = 6; b[0].value = 1; 
    b[1].priority = 9; b[1].value = 5; 
    b[2].priority = 2; b[2].value = 3; 
    b[3].priority = 8; b[3].value = 2; 
    b[4].priority = 1; b[4].value = 4; 

    
for(i = 0; i < len; i++)
        qn.push(b[i]);
    cout<<"
优先级"<<'\t'<<""<<endl;
    for(i = 0; i < len; i++)
    {
        cout<<qn.top().priority<<
'\t'<<qn.top().value<<endl;
        qn.pop();
    }
    
return 0;
}

 



 
saint623 @ 2008-08-13 09:13

java.util.regex的帮助文档 
Dana Nourie 
Mike McCloskey所写的Regular Expressions and the Java™ Programming Language 
需要更多的第三方正则表达式资源以及基于它们所开发的应用程序请看http://www.meurrens.org/ip-Links/java/regex/index.html 
Java's java.util.regex 包包括:Pattern类、Matcher类、MatchResult接口和PatternSyntaxException异常:
  • Pattern 对象代表了编译了的正则表达式(A compiled representation of a regular expression.)。
  • Matcher An engine that performs match operations on a character sequence by interpreting a Pattern.
  • MatchResult接口:The result of a match operation.
  • PatternSyntaxException对象,描述非法的regex patternsUnchecked exception thrown to indicate a syntax error in a regular-expression pattern.
 同时还需要了解是CharSequenceJDK 1.4定义的新的接口,它提供了StringStringBuffer这两个类的字符序列的抽象
interface CharSequence {
 charAt(int i);
 length();
 subSequence(int start, int end);
 toString();
}
为了实现这个新的CharSequence接口,StringStringBuffer以及CharBuffer都作了修改,很多的正则表达式的操作都要拿CharSequence作参数。
Matcher类的几个重要的方法:
  • boolean matches()Pattern匹配整个字符串
  • boolean lookingAt()Pattern匹配字符串的开头
  • boolean find():发现CharSequence里的,与pattern相匹配的多个字符序列
    boolean find(int start)
    :告诉方法从参数start位置开始查找
group的概念
Group是指里用括号括起来的,能被后面的表达式调用的正则表达式。
Group 0 表示整个表达式,group 1表示第一个被括起来的group,以此类推。所以;
A(B(C))D
里面有三个groupgroup 0ABCD group 1BCgroup 2C
你可以用下述Matcher方法来使用group
  • public int groupCount( )返回matcher对象中的group的数目。不包括group0
  • public String group( ) 返回上次匹配操作(比方说find( ))group 0(整个匹配)
  • public String group(int i)返回上次匹配操作的某个group。如果匹配成功,但是没能找到group,则返回null
  • public int start(int group)返回上次匹配所找到的group的开始位置。
  • public int end(int group)返回上次匹配所找到的group的结束位置,最后一个字符的下标加一。
  • split( ) 是指将以正则表达式为界,将字符串分割成String数组,如果带有limit参数,split( )会限定分割的次数。
  • replaceFirst(String replacement)将字符串里,第一个与模式相匹配的子串替换成replacement
  • replaceAll(String replacement),将输入字符串里所有与模式相匹配的子串全部替换成replacement
  • appendReplacement(StringBuffer sbuf, String replacement)sbuf进行逐次替换,而不是像replaceFirst( )replaceAll( )那样,只替换第一个或全部子串。这是个非常重要的方法,因为replacement(replaceFirst( )replaceAll( )只允许用固定的字符串来充当replacement)。有了这个方法,你就可以编程区分group,从而实现更强大的替换功能。
  • 调用完appendReplacement( )之后,为了把剩余的字符串拷贝回去,必须调用appendTail(StringBuffer sbuf, String replacement)
 
使用group可以做到逐步缩小匹配的范围,直至精确匹配的目的。
start( )end( ):如果匹配成功,start( )会返回此次匹配的开始位置,end( )会返回此次匹配的结束位置,即最后一个字符的下标加一。如果之前的匹配不成功(或者没匹配),那么无论是调用start( )还是end( ),都会引发一个IllegalStateException
二、4大使用方法:
查询
String str="abc efg ABC";
String regEx="a|f"; //表示af
Pattern p=Pattern.compile(regEx);
Matcher m=p.matcher(str);
boolean rs=m.find();
如果str中有regEx,那么rstrue,否则为flase。如果想在查找时忽略大小写,则可以写成Pattern p=Pattern.compile(regEx,Pattern.CASE_INSENSITIVE);
提取
String regEx=".+\(.+)$";
String str="c:\dir1\dir2\name.txt";
Pattern p=Pattern.compile(regEx);
Matcher m=p.matcher(str);
boolean rs=m.find();
for(int i=1;i<=m.groupCount();i++){
System.out.println(m.group(i));
}
以上的执行结果为name.txt,提取的字符串储存在m.group(i)中,其中i最大值为m.groupCount();
 
分割
String regEx="::";
Pattern p=Pattern.compile(regEx);
String[] r=p.split("xd::abc::cde");
执行后,r就是{"xd","abc","cde"},其实分割时还有跟简单的方法:
String str="xd::abc::cde";
String[] r=str.split("::");
 
替换或者删除
String regEx="a+"; //表示一个或多个a
Pattern p=Pattern.compile(regEx);
Matcher m=p.matcher("aaabbced a ccdeaa");
String s=m.replaceAll("A");
  结果为"Abbced A ccdeA"
  如果写成空串,既可达到删除的功能,比如:
String s=m.replaceAll("");
  结果为"bbced ccde"
 
三、一个实际的例子
下面的函数是一个实际应用的例子,需求是需要将抓取的网页中的<img src=''http://aa.bb.cc.com/images/**.jpg"> 中的地址,保存到一个地址列表中(以供抓取图片使用),并将绝对地址替换成本地的相对地址,即<img src="images/**.jpg">
public static Map<String, String> getImagesURL(String description) {
      Map<String, String> map = new HashMap<String, String>();
        // img
的正则表达式:匹配<img>标签       
        String imgPattern = "<\s*img\s+([^>]+)\s*>";
        Pattern pattern1 = Pattern.compile(imgPattern, Pattern.CASE_INSENSITIVE);
        Matcher matcher = pattern1.matcher(description);
        // img src元素的正则表达式:匹配img标签内的src属性
        String srcPattern = "\s*src\s*=\s*\"([^\"]+)\s*\"";
        Pattern pattern2 = Pattern.compile(srcPattern, Pattern.CASE_INSENSITIVE);
        while (matcher.find()) {
           //group()返回符合表达式的内容
            Matcher matcher2 = pattern2 .matcher(matcher.group());
            //
一定要find(),这是实际的匹配动作
            if (matcher2.find()) {
                String src = matcher2.group();
                log.info(src);
                int i2 = src.lastIndexOf('/');
                int i1 = src.indexOf("http");
                if (i1 != -1) {
                    map.put(src.substring(i2 + 1, src.length() - 1), src
                            .substring(i1, src.length() - 1));
                }
            }
        }
        log.debug("
图片:" + map);
        return map;
    }
 
整体思路是先匹配到img标签,然后匹配src属性,并修改src的属性
"<\s*img\s+([^>]+)\s*>" 的解释:
\s* :0 或多个空格   \s+: 至少一个空格
([^>]+):指的是到>为止的所有的元素,至少一个
 
常用的正则表达式(参考jdkregex文档)
字符集类
.                            表示任意一个字符
[abc]                     表示字符abc中的任意一个(a|b|c相同)
[^abc]                   abc之外的任意一个字符(否定)
[a-zA-Z]                azAZ当中的任意一个字符(范围)
[abc[hij]]              a,b,c,h,i,j中的任意一个字符(a|b|c|h|i|j相同)(并集)
[a-z&&[hij]]          h,i,j中的一个(交集)
\s                          空格字符(空格键, tab, 换行, 换页, 回车)
\S                         非空格字符([^\s])
\d                         一个数字,也就是[0-9]
\D                         一个非数字的字符,也就是[^0-9]
\w                        一个单词字符(word character),即[a-zA-Z_0-9]
\W                       一个非单词的字符,[^\w]
字符类:
B                         字符B
\xhh                    16进制值0xhh所表示的字符
\uhhhh                16进制值0xhhhh所表示的Unicode字符
\t                         Tab
\n                        换行符
\r                         回车符
\f                        换页符
\e                       Escape
逻辑运算符
XY                      X 后面跟着 Y
X|Y                    XY
(X)                     一个"要匹配的组(capturing group)". 以后可以用\i来表示第i个被匹配的组。
边界匹配符
^                      一行的开始
$                      一行的结尾
\b                    一个单词的边界
\B                    一个非单词的边界
\G                   前一个匹配的结束
数量表示符
"数量表示符(quantifier)"的作用是定义模式应该匹配多少个字符。
  • Greedy(贪婪的)除非另有表示,否则数量表示符都是greedy的。Greedy的表达式会一直匹配下去,直到匹配不下去为止。(如果你发现表达式匹配的结果与预期的不符),很有可能是因为,你以为表达式会只匹配前面几个字符,而实际上它是greedy的,因此会一直匹配下去。
  • Reluctant(勉强的)用问号表示,它会匹配最少的字符。也称为lazy, minimal matching, non-greedy, ungreedy
  • Possessive(占有的)目前只有Java支持(其它语言都不支持)。它更加先进,所以你可能还不太会用。用正则表达式匹配字符串的时候会产生很多中间状态,(一般的匹配引擎会保存这种中间状态,)这样匹配失败的时候就能原路返回了。占有型的表达式不保存这种中间状态,因此也就不会回头重来了。它能防止正则表达式的失控,同时也能提高运行的效率。
Greedy                    Reluctant                           Possessive                      匹配
X?                            X??                                      X?+                                  匹配一个或零个X
X*                            X*?                                      X*+                                  匹配零或多个X
X+                           X+?                                      X++                                 匹配一个或多个X
X{n}                        X{n}?                                   X{n}+                               匹配正好nX
X{n,}                       X{n,}?                                 X{n,}+                              匹配至少nX
X{n,m}                   X{n,m}?                                X{n,m}+                           匹配至少n个,至多mX
参考资料
要想进一步学习正则表达式,建议看Mastering Regular Expression, 2nd Edition,作者Jeffrey E. F. Friedl (O’Reilly, 2002)
"Regular Expressions and the Java Programming Language," Dana Nourie and Mike McCloskey (Sun Microsystems, August 2002) presents a brief overview of java.util.regex, including five illustrative regex-based applications:
http://developer.java.sun.com/developer/technicalArticles/releases/1.4regex/