2009年06月15日 星期一 22:03
TopCoder挺好玩的，代码量不大，题目也比较有意思。
这道div2 的1000分的题，比赛当时不会，没写。据说是道很不错的dp，于是ym了一下别人的代码，再自己敲了一下。高中竞赛培训时没学懂dp，因此有了阴影，现在看来dp其实就是那么个思想，并不复杂，关键自己能提取出转移的公式，往往有意思的题目都是dp的题目，希望借此题能摆脱对dp的阴影-,-;;;
题目大意是有一组正整数，把它们分成两组，要求每组的和一样大，可以有丢弃的数，如果没有这样的分组，返回-1，若有，返回那个相同的和。
用数组记录“两组间差为x”这种状态下，两组数和的最大值，这道题解法巧妙的一点就是不用去在意具体每组里有哪些数，只需要记录两组数的和，最后取“两组间差为0”的状态下记录的值再除以2就是答案了
对于每个数，他都有三种去向
1，丢弃；
2，放到和较大的那组，差增大，相应差的数组元素记录有可能变化；
3，放到和较小的那组，计算新差（增大减小不变未知），相应差的数组元素记录有可能变化。
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <cmath>
using namespace std;
#define MAXN 500001
int last[MAXN], cur[MAXN]; // at last get the ans from cur[0]
// [x], the shorter tower need more x
// every element of the arr is the max sum height of the two tower
class EqualTowers {
public:
int height(vector <int> bricks) {
unsigned int N = bricks.size();
if( N==1 ) return -1;
// N!=-1
int maxSum = 0;
memset(last, -1, sizeof(last));
memset(cur, -1, sizeof(cur));
last[0]=0; cur[0]=0;
for(int i=0; i<N; ++i)
{
if(i==3)
i=3;
for(int j=0; j<=maxSum; ++j)
{
if(last[j] < 0) continue; // this sum is not possible
if(cur[ j + bricks[i] ] < last[j] + bricks[i])
cur[ j + bricks[i] ] = last[j] + bricks[i];
if(cur[ abs(j - bricks[i]) ] < last[j] + bricks[i])
cur[ abs(j - bricks[i]) ] = last[j] + bricks[i];
}
maxSum += bricks[i];
memcpy(last, cur, sizeof(cur));
}
if(cur[0]!=0)
return (cur[0]/2);
else
return -1;
}
}
|
2009年05月31日 星期日 02:02
coding太弱了
百度和有道的比赛，充分认识到自己coding太鹾太鹾了
以后争取每天都做题，哪怕是水题也好
coding是一种熟练度，和算法什么的无关，嗯。。。 |
2009年03月14日 星期六 18:34
慢慢适应了天天实验室的生活
而且现在有种什么都想学的欲望
ai。。。。想来本科四年太堕落了 |
2009年02月19日 星期四 23:37
今天接到家里的电话说奶奶走了
过年时还好好的，这么突然就走了，生命。。。。
四个祖辈都没了，我还不存在爷爷就去了，3岁还怎么懂事时姥爷走了，小学5年级姥姥走了，奶奶算最长寿的，活到了八十，去年十一刚过的八十大寿，可惜的是我当时没回家给奶奶过生日。。。。 |
2008年12月28日 星期日 18:49
没怎么看过星光，只是知道有这么个选手
最近伊出专辑了，下了听听看。
发现相当赞啊，有周蕙和彭佳慧混合体的感觉，专辑里的几首慢歌都很耐听。 |
2008年12月16日 星期二 23:40
coding还是太弱了啊，思路早就有了就是敲不出来。。。
/*
ID: tossens1
PROG: beads
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
//#define USACO
using namespace std;
#ifndef USACO
ifstream myin("beads.in");
ofstream myout("beads.out");
#else
#define myin cin
#define myout cout
#endif
struct info
{
int cnt;
char color;
};
info necklaceinfo[130];
int main()
{
int n,i,j;
int ans = 0;
myin >> n;
string necklace;
myin >> necklace;
int cnt=1;
int rec_no=0;
//将项链读出来rrwwwb -> 1r 3w 1b; rrbbwr -> 3r 2b 1w;
for(i=0; i!=n; ++i){
if ((i == n-1) || (necklace[i] != necklace[i+1])){
necklaceinfo[rec_no].color = necklace[i];
necklaceinfo[rec_no].cnt = cnt;
cnt = 1;
++rec_no;
}
else
++cnt;
}
if((rec_no > 1) && (necklaceinfo[rec_no-1].color == necklaceinfo[0].color)){
necklaceinfo[0].cnt += necklaceinfo[rec_no-1].cnt;
--rec_no;
}
if(rec_no <= 3){
myout << n << endl;//项链按颜色分少于或等于三部分，那么整个项链都可以被选中
return 0;
}
//枚举包含两种颜色的串，这种串里最长的长度就是答案
for(i=0; i!=rec_no; ++i){
if (necklaceinfo[i].color=='w' && necklaceinfo[(i+n-1)%rec_no].color==necklaceinfo[(i+1)%rec_no].color)
continue;//如bwb这种形式，肯定不必在w这里开始
int numberOfColor = 0;
int tempans = 0;
char lastcolor='@';
j = i;
while(necklaceinfo[j].color == 'w' || necklaceinfo[j].color == lastcolor || numberOfColor < 2){
if(necklaceinfo[j].color != 'w' && necklaceinfo[j].color != lastcolor){
lastcolor = necklaceinfo[j].color;
++numberOfColor;
}
tempans += necklaceinfo[j].cnt;
++j;
j %= rec_no;
}
if (tempans > ans)
ans = tempans;
}
myout << ans << endl;
return 0;
}
|
2008年12月16日 星期二 23:30
如果x月k号是星期a，那么x+1月k号就是星期((a + x月的天数)%7)
/*
ID: tossens1
PROG: friday
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
//#define USACO
using namespace std;
#ifndef USACO
ifstream myin("friday.in");
ofstream myout("friday.out");
#else
#define myin cin
#define myout cout
#endif
inline bool isleap(const int& year)
{
if (year % 4)
return false;
else
if ((year % 100 == 0) && (year % 400))
return false;
return true;
}
const int daysInAMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
int res[8] = {0,0,0,0,0,0,0,0};
int year = 1900;
int month = 1;
int dayOfTheWeek = 6; //1900-1-13 is Saturday
int n;
myin >> n;
while(n--){
for (int month=1; month<=12; ++month){
++res[dayOfTheWeek];
if (month == 2)
if (isleap(year))
dayOfTheWeek += daysInAMonth[month]+1;
else;
else
dayOfTheWeek += daysInAMonth[month];
dayOfTheWeek %= 7;
if (dayOfTheWeek == 0)
dayOfTheWeek = 7;
}
++year;
}
myout << res[6] << " " << res[7];
for(int i=1; i<=5; ++i)
myout << " " << res[i];
myout << endl;
return 0;
}
|
2008年12月04日 星期四 01:08
第十五章最后15.9的这个例子
反复看了好几遍都不理解
里面Query句柄类的构造函数怎么就能创建WordQuery对象了呢？
后来看了一眼习题才发现，原来Query类并没实现完，书留给读着自己去解决呢。。。。
google了一下，发现了一位仁兄的blog里有一篇文章有实现这个例子的代码http://blog.chinaunix.net/u/18517/showart.php?id=242298
其实就在WordQuery的实现后面再加一行就行了哈：
inline Query::Query(const std::string& word): q(new WordQuery(word)), use(new std::size_t(1)){} |
2008年11月25日 星期二 02:07
偶然发现了USACO，一个循序渐进的自我训练的地方，做做看，哈哈。
由于刚开始，所以肯定都是简单题，这道题就是。
数据量不大，本来用数组直接搜索人名再算钱就行，不过我就借机用用stl的map吧，哈哈，这算不算杀鸡用牛刀呢:)
由于题目的输出要求按照输入时的人名顺序，一开始想当然的以为用iterator从begin()到end()遍历就行了，结果发现这样是按照人名的字母序输出的，想想也是哦，map是用平衡检索二叉树实现的。
/*
ID: tossens1
PROG: gift1
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <map>
//#define USACO
using namespace std;
#ifndef USACO
ifstream myin("gift1.in");
ofstream myout("gift1.out");
#else
#define myin cin
#define myout cout
#endif
#define MAXN 15
int main()
{
map<string, int> guys;
int n,i,j;
string tmp, nameorder[MAXN];
myin >> n;
for(i=0; i!=n; ++i){
myin >> tmp;
guys[tmp] = 0;
nameorder[i] = tmp;
}
string aguy;
for(i=0; i!=n; ++i){
int givemoney, ng;
myin >> aguy;
myin >> givemoney >> ng;
if(ng==0)
guys[aguy] -= 0;
else
{
guys[aguy] -= givemoney - (givemoney % ng);
for(j=0; j!=ng; ++j){
myin >> aguy;
guys[aguy] += givemoney / ng;
}
}
}
for(i=0; i!=n; ++i){
myout << nameorder[i] << " " << guys[nameorder[i]] << endl;
}
return 0;
}
|
2008年11月20日 星期四 19:45
其实自己一直对算法编程挺感兴趣的，高中时参加过noip，不过水平很一般，当时只会一些基本的数据结构和一些最基本最典型的算法题。本科四年浑浑噩噩，现在想想没弄弄acm挺遗憾的，毕竟自己感兴趣的东西不多-,-;;;。由于考研考到计算机专业，复试需要上机做题，于是又重新做起了题，也认识了zoj。
在zoj上做题已经有一段时间了，目前已经把论坛里标明的Beginner's Problem都切掉了，这些题没什么算法含量，可以当作语言的练习题，呵呵。（帖子地址http://acm.zju.edu.cn/forum/viewtopic.php?t=1060）
然后开始做非Beginners的题喽，也当作自己再次开始算法学习之旅吧。做题的收获，心得和教训就放在blog上面吧，这是第一篇，就从最近做的一道题开始。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=74
01 //枚举相邻的行(从每个单行，每个相邻的两行，...一直到相邻的n行即整个矩阵)，每个枚举项中都把所有行加到一行，转换为最大子序列和问题
02 #include <iostream>
03 #include <fstream>
04 using namespace std;
05 #ifdef ONLINE_JUDGE
06 #define myin cin
07 #else
08 ifstream myin("in.txt");
09 #endif
10
11 #define MAXN 110
12 int sumlist[MAXN][MAXN][MAXN];//sumlist[row_from][row_to]
13 int findMaxSum(const int *arr,const int &n)//最大子序列和
14 {
15 int res=-100000, sum=0;
16 for (int i=0; i!=n; ++i){
17 if(sum<0)
18 sum = 0;
19 sum += arr[i];
20 if(sum > res)
21 res = sum;
22 }
23 return res;
24 }
25
26 int main()
27 {
28 int n,i,j,row,col,ans=-100000;
29 int data[MAXN][MAXN];
30 myin >> n;
31 for(i=0; i!=n; ++i)
32 for(j=0; j!=n; ++j)
33 myin >> data[i][j];
34 row = col = n;
35
36 /*
37 for(i=0; i!=row; ++i)
38 for(j=i; j!=row; ++j){
39 for(k=0, memset(tempsum,0,sizeof(tempsum)); k!=col; ++k)
40 for(l=i; l<=j; ++l)
41 tempsum[k] += data[l][k];
42 int tmp = findMaxSum(tempsum, col);
43 if(tmp > ans)
44 ans = tmp;
45 }
46 O(nnnn)
47 重复的加法太多 不过能ac 100+还是200+ms来着 下面的方法避免了许多重复计算，10ms ac
48 */
49 memset(sumlist, 0, sizeof(sumlist));
50 for(i=0; i!=row; ++i){
51 for(j=0; j!=col; ++j){
52 sumlist[i][i][j] = data[i][j];
53 }
54 }
55 for(int span=1; span!=row; ++span){
56 for(i=0; i+span!=row; ++i){
57 for(j=0; j!=col; ++j){
58 sumlist[i][i+span][j] = sumlist[i][i+span-1][j] + data[i+span][j];
59 }
60 }
61 }
62 for(i=0; i!=row; ++i){
63 for(j=i; j!=row; ++j){
64 int tmp = findMaxSum(sumlist[i][j], col);
65 if(tmp > ans)
66 ans = tmp;
67 }
68 }
69 cout << ans << endl;
70 return 0;
71 }
|
2008年09月24日 星期三 13:44
天堂，天堂nmb
都九月底了睡觉还得扇扇子，早上没等闹钟响已经被热醒了，去趟教室就汗流浃背
我可爱的地球啊。。 |
2008年09月14日 星期日 23:02
啊，一年多没录歌了，今天室友回家过节了，趁机过过瘾，哈哈。
这首歌起伏比较大，已经尽最大努力了到了高峰那里还是有点过载，ai。。。设备不行额
孤独慵懒的风格，不知唱出来了没有~
还有，最低音还是低不下去-,-;;;
http://tossense.ys168.com/ |
2008年09月07日 星期日 23:56
随着银行信用卡的不断普及,使用信用卡进行透支消费的人越来越多,但利用信用卡的免息期投资货币基金的妙用,也许知道的人还不多。
现在,我们就向您介绍一种结合华安基金的网上电话交易、货币市场基金和兴业银行的借记卡、信用卡,巧用信用卡免息期买基金的好办法。
比如说,您用信用卡买了5000元的东西,你要在免息期快到前归还银行5000元。如果您在还款之前先将5000元现金通过兴业借记卡买成华安现金富利,免息期快到的时候,通过电话或网上交易赎回华安现金富利,归还信用卡的透支金额。这样您的5000元就可额外获得货币市场基金的收益(货币基金的收益一般在2.7%左右,相当于现在三年定期存款的税后利息,高过活期存款利息近4倍),等于用银行的钱消费,用自己的钱赚钱,这个收益可谓不拿白不拿。 |
2008年09月07日 星期日 15:31
常函数和指数函数 e的 x次方走在街上，远远看到微分算子，常函数吓得慌忙躲藏，说：“被它微分一下，我就什么都没有啦！”
指数函数不慌不忙道：“它可不能把我怎么样，我是e的x次方！”
指数函数与微分算子相遇。指数函数自我介绍道：“你好，我是e的x次方。”
微分算子道：“你好，我是d/dy！” |
2008年09月05日 星期五 19:19
开始了解个人理财，嗯嗯
发信人: roseindesert (沙漠玫瑰), 板面: Financing
标 题: 10分钟让你懂得基金是什么
发信站: 飘渺水云间 (Wed Nov 30 10:15:31 2005), 转信
本文为理财投资知识系列科普读物之一，主要面向缺乏基本的金融知识和理财知识
的人群，并非专业性文章，所以为了通俗易懂，其中部分概念表述并不保证完全合
乎专业要求，但欢迎朋友们批评斧正，以便改进。
近期看到有很多网友常常提问基金是怎么回事，感到基金是个很复杂难懂的东西。
我常想如何让这些朋友在最短的时间内理解基金是什么，为大家展示一下这些并不
神秘的基金，所以萌生想法，试着尽可能用通俗的语言解释下什么是基金，希望对
这些朋友尽快了解基金有所帮助。
假设您有一笔钱想投资债券、股票啦这类证券进行增值，但自己又一无精力二无专
业知识，三呢钱也不算多，就想到与其他１０个人合伙出资，雇一个投资高手（理
论上比我还高点的），操作大家合出的资产进行投资增值。但这里面，如果10多个
投资人都与投资高手随时交涉，那事还不乱套，于是就推举其中一个最懂行的牵头
办这事。定期从大伙合出的资产中按一定比例提成给他，由他代为付给高手劳务费
劳务费，当然，他自己牵头出力张罗大大小小的事，包括挨家跑腿，有关风险的事
向高手随时提醒着点，定期向大伙公布投资盈亏情况等等，不可白忙，提成中的钱
也有他的劳务费。上面这些事就叫作合伙投资。
将这种合伙投资的模式放大１００倍、１０００倍，就是基金。
这种民间私下合伙投资的活动如果在出资人间建立了完备的契约合同，就是私募基
金（在我国还未得到国家金融行业监管有关法规的认可）。
如果这种合伙投资的活动经过国家证券行业管理部门（中国证券监督管理委员会）
的审批，允许这项活动的牵头操作人向社会公开募集吸收投资者加入合伙出资，这
就是发行公募基金，也就是大家现在常见的基金。
基金公司是什么角色？基金公司就是这种合伙投资的牵头操作人，不过它是个公司
法人，资格要经过中国证监会审批的。基金公司与其他基金投资者一样也是合伙出
资人之一，另一方面由于它牵头操作，要从大家合伙出的资产中按一定的比例每年
提取劳务费（称基金管理费），替投资者代雇代管理负责操盘的投资高手（就是基
金经理），还有帮高手收集信息搞研究打下手的人，定期公布基金的资产和收益情
况。当然基金公司这些活动是证监会批准的。
为了大家合伙出的资产的安全，不被基金公司这个牵头操作人偷着挪用，中国证监
会规定，基金的资产不能放在基金公司手里，基金公司和基金经理只管交易操作，
不能碰钱，记帐管钱的事要找一个擅长此事又信用高的人负责，这个角色当然非银
行莫属。于是这些出资（就是基金资产）就放在银行，由银行管帐记帐，称为基金
托管。当然银行的劳务费（称基金托管费）也得从大家合伙的资产中按比例抽一点
按年支付。所以，基金资产相对来说只有因那些高手操作不好而被亏损的风险，基
本没有被偷挪走的风险。
如果这种公募基金在规定的一段时间内募集投资者结束后宣告成立（国家规定至少
要达到1000个投资人和2亿元规模才能成立），就停止不再吸收其他的投资者了，并
约定大伙谁也不能中途撤资退出，但以后到某年某月为止我们大家就算帐散伙分包
袱，中途你想变现，只能自己找其他人卖出去，这就是封闭式基金。
如果这种公募基金在宣告成立后，仍然欢迎其他投资者随时出资入伙，同时也允许
大家随时部分或全部地撤出自己的资金和应得的收益，这就是开放式基金。
不管是封闭式基金还是开放式基金，如果为了方便大家买卖转让，就找到交易所（
证券市场）这个场所将基金挂牌出来，按市场价在投资者间自由交易，就是上市的
基金。
现在我们再来读下面的基金的概念，就不太晕头了吧。
作为一种投资工具,证券投资基金把众多投资人的资金汇集起来,由基金托管人(例如
银行)托管,由专业的基金管理公司管理和运用,通过投资于股票和债券等证券,实现
收益的目的。
专家理财是基金投资的重要特色。基金管理公司配备的投资专家,一般都具有深厚的
投资分析理论功底和丰富的实践经验,以科学的方法研究股票、债券等金融产品,组
合投资,规避风险。相应地,每年基金管理公司会从基金资产中提取管理费,用于支付
公司的运营成本。另一方面,基金托管人也会从基金资产中提取托管费。此外,开放
式基金持有人需要直接支付的有申购费、赎回费以及转换费。上市封闭式基金和上
市开放式基金的持有人在进行基金单位买卖时要支付交易佣金。
附带解释下基金有关的部分问题。
什么是基金的认购费和申购费？
就是你投资入伙时要交的费用，因为基金公司宣传吸收投资人的活动是要费不少钱
的，这些费用自然不能他一家出，另外通过提高你入伙的成本，降低你入伙不久就
想离开的欲望。
什么是基金的赎回费？
就是你撤回投资和收益是要交的费用，原因与上面类似。还有一条，就是有人撤资
走的时候，为了还给你现金，基金可能不得不卖掉一些债券股票，这是对基金资产
不利的动作，对其他不撤资的合伙人的利益有不良影响，所以让你留下点费用作补
偿。
什么是基金的转换费？
就是同一家基金公司操作着多个基金，你持有其中一个基金，想把这个基金按同等
资产数量换成该基金公司操作的另一种基金，应向基金公司交付转换的费用，原因
也与上两条同理，主要为了提高你变动的成本，不愿让你频繁变动。
什么是基金交易佣金？
就是上市的基金在交易所市场转让时，为你提供交易服务的证券公司营业部向你收
的劳务费。
基金为什么有那么多种？
这是因为不同的基金自己规定的主要投资方向投资对象有区别，股票型基金就是绝
大部分资金都投在股票市场上的基金；债券型基金就是绝大部分资金都投在债券市
场上的基金；混和型基金就是根据情况将部分资金投在股票上而另一部分资金投在
债券上的基金（当然这种投资比例是可变化调整的），甚至根据事先的规定也可以
部分投资在其他品种上；货币市场基金就是全部资产只投在风险很低但收益也低的
货币市场上的基金。这些基金的投资风险由高到低的顺序大致是，股票型基金、混
和型基金、债券型基金、货币市场基金。由于风险高低不同，所以投资者应根据自
己对风险的承受能力来选择风险水平适合自己的基金投资入伙，也可以通过低风险
基金、中等风险基金和高风险基金都投资一部分的办法来分散风险和平衡收益水平
，这种行为就叫作投资组合。
不同的基金在自己的名称上冠以什么“增长”、“价值”、“行业”、“蓝筹”、
“小盘”、“周期”、“消费品”等等的字号，是将自己的主要投资策略风格标在
名称上以便投资者一目了然，当然也不排除部分基金只是当初为了找个好名头切入
点以便中国证监会容易批准成立。
基金还有专门投资于房地产的房地产基金，投资于期货期权的期货和期权基金，投
资于黄金市场的黄金基金，投资于实业的产业基金。这些基金对我们初涉基金投资
的人来说投资机会不多，先搞通上面几种最常见的基金后再说。 |
|
|
|
