Archive for acm

用python进行排列组合生成

在做f4ck上的游戏时,第三题需要生成字典的,就到网上搜索现成的排列组合的例子,找个一个,(链接找不到了)。那篇文章用了很多种方法,并比较了执行时间,很好。我找了一种感觉很好的,记录一下。 字典生成,共五位,已知四个字母,然后另一位是数字。这五位排列组合,共有5!*10中排列。 先上算法:
#-*-coding:utf-8-*-
str1 = 'f9ck'

def permute(seq):
    new_list = []
    seqn = [seq.pop()]
    while seq:
        newseq = []
        new = seq.pop()
        #print "seq:",seq,'seqn', seqn ,'new', new
        for i in range(len(seqn)):
            item = seqn[i]
            for j in range(len(item)+1):
                #print u'left:',item[:j],u'midle:',new,u'right:',item[j:]
                #print ''.join([item[:j],new,item[j:]])
                newseq.append(''.join([item[:j],new,item[j:]]))
        seqn = newseq
        #print 'newseq',newseq
    return  seqn

file2 = open('p00.txt','w+')
for i in range(10):
    str2 = str1 + str(i)
    seq = list(str2)
    thelist = permute(seq)

    passwdlist = []
    for passwd in thelist:
        newpasswd = passwd + '\n'
        passwdlist.append(newpasswd)
    file2.writelines(passwdlist)
    print len(passwdlist)

#file1.close()
file2.close()
分析一下, 第一步,取一位,放入seqn,这个列表用于保存过程中生成的序列。 第二步,从剩下的中再取一位,放入new。 第三步,for循环,将new中的字母插入到seqn列表元素的每一位中。生成的新序列赋值seqn。 for循环解释一下:作者当时就是举了个例子,如果想得到1,2,3这三个数的排列组合,通过下面的方法。 如图: [caption id="attachment_532" align="alignnone" width="122" caption="排列选择"]排列选择[/caption]
Read more...

USACO Training--Friday the Thirteenth学习笔记

解决问题的方法真的有好多种,有的可以用很少的代码实现,好佩服。 自己写的代码:
/*
ID:
LANG:C
TASK:friday
*/
#include
int main()
{
int i,j,n,a[7]={0},t;//t
FILE *fin=fopen("friday.in","r");
FILE *fout=fopen("friday.out","w");
fscanf(fin,"%d",&n);
for(i=0;i

看到蔡勒公式,感觉有意思 记录一下,说不定会用到
    蔡勒公式是一种计算任何一日属一星期中哪一日的算法,由蔡勒(Julius Christian Johannes Zeller)推算出。


公式都是基于公历的置闰规则来考虑。
公式中的符号含义如下:

    w:星期
    c:世纪(前两位数)
    y:年(后两位数)
    m:月(m 的取值范围为 3 至 14,即在蔡勒公式中,某年的 1、2月要看作上一年的 13、14月来计算,比如2003年1月1日要看作2002年的13月1日来计算)
    d:日
    [ ]:称作高斯符号,代表取整,即只要整数部份。
    mod:‎‎同余‎(这里代表括号里的答案除以 7 后的余数)(请注意前面是负数取模的情况,取模只可以是正数)

若要计算的日期是在1582年10月4日或之前,公式则为

(因罗马教皇修改历法,把1582年10月4日的下一天改为1582年10月15日) 

              
Read more...

USACO Training--Greedy Gift Givers学习笔记

今天做完百度acm的题,群里几个人在讨论各个学校的acm队伍、学习等。说到一起做USACO Training上的题目。我遍开始做了,以为这个网站是训练,是一个循序渐进的过程。做到Greedy Gift Givers这个题目,学到很多东西,记录一下。 这个题目很简单,不需要神马高深的算法,主要学到许多c语言的用法,先上我自己写的代码。
/*
ID:
LANG:C
TASK:gift1
*/
#include
struct gift
{
char name[15];
int get;
int give;
}g[10];
int main()
{FILE *fin=fopen("gift1.in","r");
FILE *fout=fopen("gift1.out","w");
int i,np;
fscanf(fin,"%d",&np);
for(i=0;i
这里学到的几点:
结构体里的get和give可以只用一个最后结果表示就行。
我自己写的查找字符串的操作遍历了结构图数组所有元素,可以直接break退出循环,看别人写的代码用while很好,记录下。
j=0;
while(strcmp(a[j],b)) j++;
Read more...

做了几个百度之星比赛的acm题目

做了白天一整天,就做出了7个题,下午就做出两个。一起做过几个acm的题目,太难了,半天做不出一个,就没兴趣继续做了。这次百度的题目有几个很简单,就做了几个,其中有群里说的思路,还有从网上找到的算法做的。准备将学到的知识总结一下。 今天上网看了一下,各个题目的最好代码占用的内存和代码长度,都好牛比的说。实在是不知道他们是怎么写出来的。 ABCD题是几个公式就搞定了。 E:C++ 与Java 这个题目也比较简单,就是开始的时候,题目上说“长度不超过100”,然后就定义了一个长度为一百的字符串变量,结果当为C++的时候,添加“_”后就会越界了,直接就“Runtime Error”。 G:聊天就是Repeat 这个题用到了一个scanf的格式化,以前没用过但是却知道,开始不知道行不行,试了下成功了。
scanf("%[^EOF]",s);
J:百度的新大厦 这个题是先看到群里说了以后才坐的,没怎么思考。
Read more...

介绍几个比较出名的编程acm题库

几个比较大的在线提交系统(Online Judge)里面有大量历年的竞赛题目,注册一个ID,然后用自己熟悉的语言(一般有Pascal/C /C++/Java)写好源代码提交即可,会实时返回信息告诉你是否正确。采用黑箱测试,系统里有一套标准的输入输出数据(对外保密,而且通常数据很多很 怪),你的程序的输出和标准输出完全符合即可。常见的返回信息有AC(Accepted,通过)WA(Wrong Answer,输出有错 误)TLE(Time Limit Exceeded,超时)MLE(Memory Limit Exceeded,内存溢 出)RE(Runtime Error,发生实时错误)等,只有AC了才算做对一题。这里只是一个简要介绍,请大家在做题时先看看各网站上的 FAQ,Enjoy it~~~ 杭电acm http://acm.hdu.edu.cn 编程爱好者ACM题库 http://www.programfan.com/acm/ Enjoy ACM Life http://acm.asus.com.cn 清华ACM http://acm.lib.tsinghua.edu.cn 浙江大学 Online Judge(ZOJ) http://acm.zju.edu.cn 国内最早也是最有名气的OJ,有很多高手在上面做题。特点是数据比较刁钻,经常会有你想不到的边界数据,很能考验思维的全面性,现在我主要在这个OJ上做题 北京大学 Online Judge(POJ) http://acm.pku.edu.cn/JudgeOnline/ 建立较晚,但题目加得很快,现在题数和ZOJ不相上下,特点是举行在线比赛比较多,数据比ZOJ上的要弱,有时候同样的题同样的程序,在ZOJ上WA,在POJ上就能AC 西班牙Valladolid大学 Online Judge(UVA) http://online-judge.uva.es/problemset/ 世界上最大最有名的OJ,题目巨多而且巨杂,数据也很刁钻,全世界的顶尖高手都在上面。据说如果你能在UVA上AC一千道题以上,就尽管向IBM、微软什么的发简历吧,绝对不会让你失望的。 俄罗斯Ural立大学 Online Judge(URAL) http://acm.timus.ru/ 也是一个老牌的OJ,题目不多,但题题经典。 UsacoGate Online Judge(USACO) http://ace.delos.com/usacogate 全美计算机奥林匹克竞赛(USACO)的训练网站,特点是做完一关才能继续往下做,与前面的OJ不同的是测试数据可以看到,并且做对后可以看标准解答,所 以如果大家刚开始的时候在上面那些OJ上总WA却找不到原因的话,可以试着来这里做做,看看测试数据一般是从什么地方阴你的。
Read more...

1