日历
网志分类
· 所有网志 (54)
· 随便说说 (8)
· TopCoder (17)
· 心情自语 (4)
· ACM-ICPC (10)
· UNIX/LINUX (2)
· 我看影视剧 (1)
· 生活记录 (5)
· 我的学习 (5)
· 未分类 (2)
最新的评论
站内搜索
友情链接
· 我的歪酷 非非共享界

订阅 RSS

0010035

歪酷博客

Saga's blog

不知道未来确切在哪
只能努力做好最近的事情


acsaga @ 2014-09-16 02:18

我很奇怪究竟是哪里来的2000+的点击量,按理说我也没把这个blog特意告诉给谁啊。。
所以。。来看见这个blog的,认识的不认识的,都在这里留个言吧。。
想知道是谁来看的-_-



 
acsaga @ 2008-06-04 19:38

同样按照POJ上的题号来说吧

1517 u Calculate e

简单题。按照题目要求就可以写出程序了,注意格式。

1518 Problem Bee

几何题?不做。。

1519 Digital Roots

简单题。直接做。

1520 Scramble Sort

排序题。记录每一个位置上的东西是单词还是数字,把字母和数字分别排序,然后再根据前面的顺序一个一个输出。

1521 Entropy

huffman tree。

1522 N-Credible Mazes

并查集。要注意的是把n维向量通过map<vector<int>, int>转化成数字。

1523 SPF

图论。其实也不是什么图论,暴力去掉每一个点然后floodfill就行。。。

1911 A Well-Formed Problem

模拟题。还有处理字符串。。




 
acsaga @ 2008-06-03 11:26

前些日子在TOJ virtual contest上有人放的一套题,把能做的做了,今天写一下简单题目的做法。 
这套题是比较简单的。。要是难的我就不会了。。>_<

按照POJ上面的序号来说。

2845 01000001

高精度加法,二进制。

2846 The Bank of Kalii

日期计算。分别考虑日期相同,日期在前,日期在后的各种情况。注意DAY的单复数和跨年的情况。

2847 The Cubic End

数学题。从最后一位开始,逐位的计算每一个数字。计算的方法是从1到9验证。。看当前的数的立方%(10^n)方是不是等于所给的后n个数。要注意要求的数是10位数的时候,结果可能超过long long所能表示的范围,所以要进行特别处理。由于只需要最后10位相同就可以,所以在算10位数的立方的时候,只需要考虑每次计算对最后10位的贡献就可以,不用算出完整的结果。具体的操作方法是,比如要算十位数ABCDEFGHIJ^3的后10位,只需要算BCDEFGHIJ^3的后10位 + 3*A000000000*(BCDEFGHIJ^2)。当然中间要不停的进行取模处理。具体的推导过程就不写了,稍微想一下就能明白。

2848 Kindergarten Graduation

这是一个构造的题目。做法是,找几个小的例子找规律。首先注意到,要让移动次数比较少,B只能向左移动,G只能向右移动。然后考虑在不同的情况下应该采取哪种移动方式。这个从题目给的GG_BB的例子就可以看出来了。假如遇到的是_BB,那么就移动成B_B。假如有GB_,就移动成_BG。假如有GG_,就移动成G_G。假如有_GB,就移动成BG_。注意当’_'的位置靠近两边的时候要特别处理,可以在两端分别添上G和B来简化处理方法,规律是一样的。各种操作之间的优先级试一下就可以找到了。

2849 brainf*ck 2852 Model Rocket Height

模拟题。写一个简单的brainf*ck编译器。按照题意实现每一个操作就可以了。数据很弱。

2850 Stacking Cylinders

貌似是几何题,不做。

2851 No Fold’em Hold’em

扑克题,没看懂。。我非常不会打扑克。。

2852 Model Rocket Height

貌似又是几何题,不做。

2853 Sequence Sum Possibilities

数学题。我的方法是枚举分解中数的个数。所给的sum=n*avg,n是一种分解中,数的个数。从2开始枚举n,计算avg,假如avg是整数的话,那么这种分解就是可行的,ans++。需要注意两点,第一,如果n是偶数,那么带有0.5的avg也是可行的,这个判断一下就可以了。第二,枚举的n的上限是sqrt(sum),如果n超过sqrt(sum),那么这个分解的最小数会<1,不是合法的分解。题目的时间复杂度是sqrt(sum),不会TLE。




 
acsaga @ 2008-05-30 00:54

读过题以后就会发现是个背包问题。

与简单的背包不同的是,这个背包要建立字母和数字的对应关系。

基本思路是:把所有单词转化成数字的表示形式,然后用数字去填背包。复杂度是O(背包大小*单词个数*单词长度) = O(100*50000*50)。这个数很大了,会超时,所以需要一点优化。注意到单词是数字的字符串,可以把所有这些单词建立成一个Trie。这样做的话,在填充背包的时候,就不需要枚举每个单词了,只需要在Trie的相应位置查找一遍就可以了。填充的复杂度降到了O(背包大小*每个位置的查找次数) = O(100*100),前面建立Trie的复杂度是O(单词个数*单词长度) = O(50000*50)。所以最终的复杂度不会超过O(50000*50)。

乌龟爬的写了50分钟。不过还好1Y掉了,感觉还不错:)加油提高水平找回状态。。




 
acsaga @ 2008-04-13 11:24

昨晚做srm,花了很长时间把div2 1000做了。也算没有白熬夜。。

题意:
有n块石头,每块石头的重量分别是W1 W2 ... Wn。现在有能装重量为cap的石头的背包m个。问最多可以装多少石头。
其中 n <= 13 , m <= 10, Wi以及cap都小于等于20。

思考过程:
贪心是不对的。每个背包里取的石头,大小不一定是连续的。比如 1 2 3 4 背包大小为5,则要1 4一个包,2 3一个包。
数据范围很小,选取的石头可以用二进制位表示。状态总数是1<<13。
那么要找的就是用m个背包,所能达到的石头数量最多的状态。
要解决m个背包的问题,先解决1个背包的问题。1个背包所能达到的不同的状态,可以通过枚举或搜索来得到。因为石头最多才13个。
然后解决m个背包的问题。m个背包,其实就是1个背包问题的叠加。由于最多只有10背包,所以搜索就可以解决m个背包的问题了。
这样问题就解决了。

注意:
单纯的搜索会超时。需要加一些优化。
在解决1个背包状态问题的时候,只需要保留那些"满的状态"。也就是说不能再放入其他任何一块石头的状态。
在解决m个背包状态问题的时候,可以进行记忆化。memo[x][bitmask]表示还剩下x个背包,并且已经选择了bitmask所表示的石头,所能得到的最优结果。其中bitmask表示的是选择的石头的二进制表示。

是一道好题。




 
acsaga @ 2008-04-01 11:31

首先明确一点,软件开发,其实就是把需求转化成代码。

基本流程:

需求->设计->代码(编码&测试)

理想:

理想的开发过程,应该是在上一步完全完成并经过确认后,再进行下一步。这样做,不同阶段可以被完整的分离。

我们要做的事情就变得简单了:让设计尽量符合需求,然后让代码尽量符合设计。

关于需求:

最原始的需求可能是模糊的定性的。这种需求无法产生精确的抽象的定量的设计。所以需要对需求进行分析,进行明确的定义。

需求是开发的基础,现在项目开发中的大部分问题都是需求不够明确清晰带来的。

制定需求就像定做一件东西。只说“我想要一件漂亮的可以在宴会上穿的衣服”,是没有任何意义的。制定需求的人,必须说出:肩宽多少?袖长多少?颜色是什么?要用什么材料?甚至其他一些更细节的问题。定的越细越准确,自然最后得到的东西也会越符合要求。

关于设计:

需求是给人看的,是没有结构,与计算机无关的。要想把它转化成代码,就需要有一个中间步骤。这就是设计。

设计的目的,是对需求进行处理,得到可以直接转化成代码的结构(数据结构,程序结构,目录结构等。。)。

设计的好,编码甚至以后的维护都会变得简单。

而不好的设计,可能无法完全反映需求,或者给实现带来困难。

关于代码:

最好的编码状态是:所有的思考和分析都已经在设计阶段结束,所有和需求有关的问题都不必考虑。写代码的时候只要小心不犯错。

现实:

需求的不稳定会影响设计,设计的模糊又会影响代码。所以导致的结果是,开发的三个阶段往往混杂在一起,以至于开发人员经常搞不清自己在干什么,应该干什么。所以最后得到的产品也难以令自己满意:即使它实现了所有预定的功能,实现的方式也不是最理想的。

想完全按照 需求 ->设计->代码 的流程进行开发,在现实中是不可能的。针对各种开发中可能出现的问题,人们想出了很多开发模型了解决。

瀑布模型:

其实就是原始的需求 -> 设计 -> 代码的模式,这个模型在需求变更频繁,时间     要求又很紧的现实中是难以奏效的。但是,假如面对的是一个需求稳定时间     充裕的项目,按照这个模型开发其实是最好的。

快速原型模型:

不断开发出产品原型,供用户评估,直到用户形成稳定的明确的需求。才进行实际   的开发,而之前的原型就被丢弃。

这种模型中,强调的最重要的技巧是快速开发产品原型。只有尽快尽好的做出原型   来(有时候甚至要做多个原型),才能又快又准的确定需求。

与其说是软件开发模型,我觉得这种方法说是挖掘用户需求的手段更为合适。

增量模型:

先针对用户最核心最稳定的需求开发系统,然后在这个系统上不断添加功能,直到   满足用户的所有需求。

这个模型中,最重要的技巧是设计:设计的系统必须可以方便的添加新功能,并且   添加的结构不破坏已有的结构。这对设计人员的要求很高,挖掘需求也必须准确   (要得到核心稳定需求)。

这种开发方式和快速原型模型的相同点:他们同样延长了确定全部需求所用的时   间。快速原型模型是把前期大量时间都用来确定需求。增量模型是确定一点需求,   就开发一点。剩下的需求之后再确定。

这样既能保证开发进度,又兼顾了需求。当然对系统设计的要求也就更高了。
还有其他一些混合模型:

其实都没有什么新意,就不说了。

从上面的模型可以看出,软件开发面临的最大问题,就是需求的模糊,不确定和延迟。

这个问题现在还不是技术性的(而设计和编码,相对来讲都是技术性的),只能靠沟通,反复询问等方式来部分解决。什么时候可以找到一种又快又好的方式确定需求了,软件开发也就简单了。

我们的另一个问题是缺少设计。设计大部分存在于开发人员的脑子中,并且是边写代码边想。这样得到的代码是很容易出错,很难以维护的。而且由于过早的开始写代码,脑子里的设计没有经过确认,所以也经常不能很好的对应需求。

我的想法是。

尽量推迟开始写代码的时间,把更多的时间都用在确定需求和设计规划上。甚至宁可花时间写注释,都不要写代码。等到把其他辅助的工作全做好了,最后再写代码。这样写出的代码,用意明确,便于维护修改。而且把重心放在需求和设计上,得到的最终产品质量也更好。




 
acsaga @ 2008-03-25 17:27

想找个地方偷偷记点东西,于是今天又注册了一个blog。
本来想去 无名小站 注册的,结果貌似被屏蔽了,登录不上去-_-
有个叫 下水道 的blog,感觉也不错,不过也没去那里。。
而是选择了一个名气更大也更隐蔽的blog。。。具体是哪家就不说了,哈哈哈哈。。
以后把这个作为技术blog好了。。虽然我也没啥技术。。。




 
acsaga @ 2008-01-13 18:04

250
模拟

500
可以发现从大往小取得到的答案不会比从小往大取得到的答案差,所以是贪心。

1000

动态规划。
dp[i][j]表示用前i个数组合出最大公约数为j的方案的方法数。
最后的答案就是dp[n-1][1];



 
acsaga @ 2008-01-12 19:16

摘自poj1077 的discuss


这里的哈希函数是用能对许多全排列问题适用的方法。
取n!为基数,状态第n位的逆序值为哈希值第n位数.
例如,1 3 7 2 4 6 8 5 9 的哈希值等于: 0*0! + 0*1! + 0*2! + 2*3! + 1*4! + 1*5! + 0*6! + 3*7! + 9*8!
 具体的原因可以去查查一些数学书,其中1 2 3 4 5 6 7 8 9 的哈希值是0 最小,8 7 6 5 4 3 2 1 0 的哈希值是(9!-1)最大,而其他值都在0 到 (9!-1) 中,且均唯一。

摘自原文的Q4: http://cache.baidu.com/c?word=%B0%CB%CA%FD%3B%C2%EB%2C%C4%E6%D0%F2&url=http%3A//www%2Ecnblogs%2Ecom/wingy/archive/2006/12/07/585879%2Ehtml&p=9a3ed316d9c243dd1ebd9b7a594e&user=baidu



 
acsaga @ 2008-01-12 16:08

250
字符串计数,用map。

500
先把三个vector连成一个,然后每相邻的两个判断就行。有个特殊情况就是第一个人第一次就cheat。

1000
要想乘积尽量大,就尽量每次分3个。直到n<=4。
代码很短:
class BestDecomposition {
    public: int maxProduct(int n) {
       n<=4 ? n : 3*maxProduct(n-3)%10007;
    }
};
估计是所有1000中最短的了。。

ps.发现有个handle是anastasov.bg的人每次会在代码里写算法的简单说明:)