C++博客-AClayton's ACM/ICPC Life 只切菜题菜鸟乱飞 -最新评论

re: PKU POJ 1142 Smith Numbers 一道简单的题

lolihunter — Sat, 06 Feb 2010 23:43:00 GMT

@wsk
if ((result==re(w))&&(r!=w))
r!=w就能剔除素数

lolihunter 2010-02-07 07:43 发表评论

re: ACM PKU　题目分类(完整整理版本)

蓝牙 — Sun, 24 Jan 2010 09:27:00 GMT

集合了不少版本..呵

蓝牙 2010-01-24 17:27 发表评论

re: ACM PKU 1675 Happy Birthday!

Hi — Thu, 21 Jan 2010 13:48:00 GMT

你的Ac不了，下面这个才行
#include
#include
int main()
{
int r,x[4],y[4],t;
int i,j;
double a[4],PI,m,b1,b2,b3,p,max;
PI=2*acos(0);p=2*PI/3;
scanf("%d",&t);
while(t--)
{
scanf("%d",&r);
for(i=1;i<4;i++)scanf("%d%d",&x[i],&y[i]);
if((x[1]==0&&y[1]==0)||(x[2]==0&&y[2]==0)||(x[3]==0&&y[3]==0)){printf("No\n");continue;}
for(i=1;i<4;i++)
{
a[i]=acos(x[i]/sqrt(x[i]*x[i]+y[i]*y[i]));
if(y[i]<0)a[i]=2*PI-a[i];
}
for(i=1;i<4;i++)
for(j=i+1;j<4;j++)
if(a[i]>a[j]){m=a[i];a[i]=a[j];a[j]=m;}
if((a[1]-a[2])*(a[2]-a[3])*(a[3]-a[1])==0){printf("No\n");continue;}
b1=a[2]-a[1];b2=a[3]-a[2];b3=2*PI-(a[3]-a[1]);
max=b1>b2?b1:b2;
max=max>b3?max:b3;
if(max>=p&&max<2*p)printf("Yes\n");
else printf("No\n");
}
return 0;
}

Hi 2010-01-21 21:48 发表评论

re: ACM PKU 1663 Number Steps 小学数奥...

CRonaldo — Thu, 21 Jan 2010 02:17:00 GMT

提示: 作者被禁止或删除内容自动屏蔽

CRonaldo 2010-01-21 10:17 发表评论

re: ACM PKU 1468 Rectangles 暴力搜索

CRonaldo — Wed, 06 Jan 2010 08:42:00 GMT

@Pope
既然已经知道被覆盖，就没有必要继续循环下去了。

CRonaldo 2010-01-06 16:42 发表评论

re: PKU POJ 1014 Dividing

CRonaldo — Thu, 31 Dec 2009 03:52:00 GMT

@zhao
这是程序的一个bug.

根据你给出的"2 0 0 0 0 0",

尽管第44行中给opt[mid]赋值true,但程序却执行不到36行了.

可以做如下更正:
36                if (opt[mid])              //判断是否已经求出结果
37                {
38                    printf("Can be divided.\n\n");
39                    return;
40                }
41                for (int k=1;k<=stone[i];k++)         //在刚找到的可行j基础上加石头.
42                {
43                    if (j+k*i>mid || opt[j+k*i]) break; //如果已经大于总价值的一半mid，或opt[j+k*i]已计算，跳出循环
44                    opt[j+k*i]=true;
45                }

将上述的if语句和for循环对换.

@黄河勇者
@lymfs
opt[j+k*i]. 这里j初始化为max,并不断减小.
我们注意到,下一次循环中max实际上是由上一次的价值×数量(i*stone[i])累计而成;
而在累计过程中,opt相应位置不断赋值true.
刚开始j==max的时候,opt[j+k*i]显然不可能成立,

∵max是以前所有价值的和(排除max>mid的情况),

此时j+k*i显然大于max,即opt[j+k*i]从未被赋值过.
这就是说opt[j+k*i]==true成立的情况是在j不断减小的过程中发生的.
此时,分两种情况:
①j+k*i≥max.

除了opt[max],opt[j+k*i]是本次for(int j=max;j>=0;j--)循环中被赋值true,

即不存在opt[j+k*i]==true的情况.

②j+k*i

可以将j+k*i看做小于max的j'.

显然j'是由max不断减小得到,j由j'不断减小得到,

opt[j]==true, opt[j']==true, j' - j == k*i.

j''==j+(k+1)*k, opt[j'']=?

还是无法用数学证明.继续研究...还请博主指点下.

CRonaldo 2009-12-31 11:52 发表评论

re: ACM PKU 2663 Tri Tiling 简单的动态规划有趣

sleepycat — Sat, 12 Dec 2009 02:53:00 GMT

T(2*k)=3*T(2*k-2)+2*(T(2*k-4)+T(2*k-6)+..+T(2) )掉了
T（0）
应该是
T(2*k)=3*T(2*k-2)+2*(T(2*k-4)+T(2*k-6)+..+T(2) +T(0) )

sleepycat 2009-12-12 10:53 发表评论

re: ACM PKU 1011 Sticks 深度优先搜索

CRonaldo — Thu, 10 Dec 2009 07:08:00 GMT

s调用search，search调用s，继续研究……

CRonaldo 2009-12-10 15:08 发表评论

re: ACM PKU 1323 Game Prediction 贪心算法[未登录]

zc — Fri, 04 Dec 2009 01:39:00 GMT

用动归的思路是什么啊？

zc 2009-12-04 09:39 发表评论

re: ACM　PKU 1013 Counterfeit Dollar 以前做了很久都没ａｃ的简单题

jamal — Sun, 22 Nov 2009 13:48:00 GMT

对，我试过了。

jamal 2009-11-22 21:48 发表评论

re: ACM PKU 1455 Crazy tea party 逆序数简单的数学题

carnie — Mon, 02 Nov 2009 06:45:00 GMT

那把偶数当做奇数来算应该是得到同样的结果吧。

carnie 2009-11-02 14:45 发表评论

re: ACM PKU 1316 Self Numbers 简单题

Tarazed — Thu, 22 Oct 2009 13:21:00 GMT

偶然看到这里，跟贴一个简化版本
int sum = -2;
for(a = 0; a <= 9; a++, sum -= 9)
for(b = 0; b <= 9; b++, sum -= 9)
for(c = 0; c <= 9; c++, sum -= 9)
for(d = 0; d <= 9; d++)
s[sum += 2] = 1;

Tarazed 2009-10-22 21:21 发表评论

re: ACM PKU 1411 Brackets Sequence 动态规划

solofancy — Thu, 17 Sep 2009 15:33:00 GMT

第二个WA吧

solofancy 2009-09-17 23:33 发表评论

re: PKU POJ 1014 Dividing

lymfs — Sat, 29 Aug 2009 07:01:00 GMT

博主能不能将43行代码的opt[j+k*i]满足就跳出循环解释一下

lymfs 2009-08-29 15:01 发表评论

re: ACM PKU 1562 Oil Deposits 深度优先搜索

显幻闪过 — Tue, 25 Aug 2009 14:33:00 GMT

@紫恋
for(i=1;i<=m;i++)
{
getchar();//读入回车
for(j=1;j<=n;j++)
{
scanf("%c",&map[i][j]);
visited[i][j]=false;
}
}
还需一个getchar()接受最后一行末尾的回车键

显幻闪过 2009-08-25 22:33 发表评论

re: ACM　PKU 1226 Substrings　较复杂字符串操作（但不繁琐）

Uriel — Tue, 25 Aug 2009 03:17:00 GMT

PKU上string .h 的strrev貌似不让用的？以前做字符串的题用了C++，C，GCC，G++交全部CE。。

Uriel 2009-08-25 11:17 发表评论

re: PKU POJ 1142 Smith Numbers 一道简单的题

wsk — Tue, 25 Aug 2009 00:35:00 GMT

e怎么没有验证是不是素数呢？

wsk 2009-08-25 08:35 发表评论

re: ACM PKU 1562 Oil Deposits 深度优先搜索

紫恋 — Sun, 23 Aug 2009 01:38:00 GMT

for(i=1;i<=m;i++)
{
getchar();//读入回车
for(j=1;j<=n;j++)
{
scanf("%c",&map[i][j]);
visited[i][j]=false;
}
}
这样就可以用scanf了

紫恋 2009-08-23 09:38 发表评论

re: 在微软亚洲研究院实习，暂停做算法。实习生活博客http://sixsix.net.ms

付翔 — Wed, 05 Aug 2009 08:50:00 GMT

谢谢你的写出这样好的文章给我有很大的鼓舞作用你对于算法而言肯定有自己的看法能否指教一二而对于已经学了一年多的C的我我主要学习的事算法和C++ 应该说掌握了基本的语言的用法请问我还需要在哪些方面进阶

付翔 2009-08-05 16:50 发表评论

re: ACM PKU 1054 The Troublesome Frog　　学会剪枝[未登录]

123 — Tue, 04 Aug 2009 14:04:00 GMT

有编译错误

123 2009-08-04 22:04 发表评论

re: ACM PKU 1775 Sum of Factorials 又是一个做男人不容易系列

yuech — Sat, 01 Aug 2009 09:07:00 GMT

你这样会超时的吧

yuech 2009-08-01 17:07 发表评论

re: ACM PKU 1828 Monkeys' Pride

幻风 — Sat, 01 Aug 2009 01:33:00 GMT

明显过不了吧？
4
3 1
3 2
3 0
2 2

幻风 2009-08-01 09:33 发表评论

re: ACM PKU 1011 Sticks 深度优先搜索

筱驀釹 — Mon, 27 Jul 2009 09:35:00 GMT

看了你的解题程序，对我帮助挺大的，不过文字性的类容少了点
总之非常谢谢你哈！！！！！

筱驀釹 2009-07-27 17:35 发表评论

re: ACM PKU 2244 Eeny Meeny Moo 约瑟夫问题

solofancy — Sun, 05 Jul 2009 03:53:00 GMT

子函数跟约瑟夫一样的嘛。。。。主函数写成y(n-1,m)==1就好了吧，16ms

solofancy 2009-07-05 11:53 发表评论

re: ACM PKU 1675 Happy Birthday!

篮子 — Thu, 04 Jun 2009 14:52:00 GMT

请问为什么max>=120时，就输出“Yes”呢？~

篮子 2009-06-04 22:52 发表评论

re: ACM PKU 1088 滑雪　经典的动态规划备忘录方法（记忆化搜索／Memory function ）

大师傅啥的 — Thu, 04 Jun 2009 12:58:00 GMT

dfs不会超时的帅哥

大师傅啥的 2009-06-04 20:58 发表评论

re: ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列一维动态规划

大师傅啥的 — Wed, 03 Jun 2009 09:42:00 GMT

我的runtime error 是怎么回事。。。。晕

大师傅啥的 2009-06-03 17:42 发表评论

re: 腾讯2009年重庆笔试附加题[未登录]

lyx — Sun, 31 May 2009 16:13:00 GMT

第一个递归算法必须要保证刚刚好能装满背包，否则就会死循环了。

lyx 2009-06-01 00:13 发表评论

re: ACM PKU 1125 Stockbroker Grapevine 图论 Floyd算法

zx — Wed, 13 May 2009 16:09:00 GMT

果然是WA，楼主，要改改啦！

zx 2009-05-14 00:09 发表评论

re: ACM PKU 1125 Stockbroker Grapevine 图论 Floyd算法

朱一帆 — Sun, 10 May 2009 05:12:00 GMT

我说楼主啊，你能不能不要那么自大啊，你的程序的结果是WA啊！！！

朱一帆 2009-05-10 13:12 发表评论

re: PKU POJ 1006 Biorhythms 从“韩信点兵”中想到的[未登录]

菜鸟 — Sat, 02 May 2009 09:05:00 GMT

看懂了……报告中的错误也太“低级”了，苦了菜鸟我啊

菜鸟 2009-05-02 17:05 发表评论

re: PKU POJ 1006 Biorhythms 从“韩信点兵”中想到的[未登录]

菜鸟 — Sat, 02 May 2009 08:50:00 GMT

6,19,2是怎么得到的啊

菜鸟 2009-05-02 16:50 发表评论

re: PKU POJ 1014 Dividing

黄河勇者 — Fri, 17 Apr 2009 12:02:00 GMT

博主能不能将43行代码的opt[j+k*i]满足就跳出循环解释一下，小弟认为在当该条件满足时不一定要跳出循环（此处可能博主有误），因为opt[j+k*(i+1)]不一定计算出，所以循环有必要进行下去，如小弟理解有误，望博主指点。小弟的AC代码（算法思想按博主所写）：http://hi.baidu.com/黄河勇者

黄河勇者 2009-04-17 20:02 发表评论

re: PKU POJ 1014 Dividing

黄河勇者 — Fri, 17 Apr 2009 08:53:00 GMT

上面的提到状态数组最大为60000，是根据题意得出的，题意说最多有20000块石头，则一个人的最大价值为60000

黄河勇者 2009-04-17 16:53 发表评论

re: ACM PKU 1664 放苹果类似整数划分问题的递归

dream — Fri, 17 Apr 2009 01:54:00 GMT

错的

dream 2009-04-17 09:54 发表评论

re: ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列一维动态规划

冰雪女孩 — Sat, 04 Apr 2009 07:33:00 GMT

我刚刚学会了

冰雪女孩 2009-04-04 15:33 发表评论

re: 在微软亚洲研究院实习，暂停做算法。实习生活博客http://sixsix.net.ms

依天照海 — Mon, 30 Mar 2009 07:48:00 GMT

今天看到你的博客内容非常好赞一个

依天照海 2009-03-30 15:48 发表评论

re: PKU POJ 1014 Dividing

allen — Mon, 23 Mar 2009 14:17:00 GMT

您好，我是刚接触ACM的菜鸟，拜读了您的解题思想，有个问题想请教一下，就是那个状态数组最大为60000个，这个数据有什么根据吗？

allen 2009-03-23 22:17 发表评论

re: ACM PKU 1936 All in All 字符串处理

acmer — Mon, 23 Mar 2009 13:48:00 GMT

超时我想是因为每次循环都调用了strlen,如果你把strlen计算的结果存在一个变量里，就不会超时了

acmer 2009-03-23 21:48 发表评论

re: ACM基本算法分类、推荐学习资料和配套pku习题

Lovfawth — Sun, 15 Mar 2009 15:00:00 GMT

DDDDDDDDDDDDDDDDDDD~~~

Lovfawth 2009-03-15 23:00 发表评论

C++博客-AClayton's ACM/ICPC Life 只切菜题 菜鸟乱飞 -最新评论

re: PKU POJ 1142 Smith Numbers 一道简单的题

re: ACM PKU 题目分类(完整整理版本)

re: ACM PKU 1675 Happy Birthday!

re: ACM PKU 1663 Number Steps 小学数奥...

re: ACM PKU 1468 Rectangles 暴力搜索

re: PKU POJ 1014 Dividing

re: ACM PKU 2663 Tri Tiling 简单的动态规划 有趣

re: ACM PKU 1011 Sticks 深度优先搜索

re: ACM PKU 1323 Game Prediction 贪心算法[未登录]

re: ACM PKU 1013 Counterfeit Dollar 以前做了很久都没ａｃ的简单题

re: ACM PKU 1455 Crazy tea party 逆序数 简单的数学题

re: ACM PKU 1316 Self Numbers 简单题

re: ACM PKU 1411 Brackets Sequence 动态规划

re: PKU POJ 1014 Dividing

re: ACM PKU 1562 Oil Deposits 深度优先搜索

re: ACM PKU 1226 Substrings 较复杂字符串操作（但不繁琐）

re: PKU POJ 1142 Smith Numbers 一道简单的题

re: ACM PKU 1562 Oil Deposits 深度优先搜索

re: 在微软亚洲研究院实习，暂停做算法。实习生活博客http://sixsix.net.ms

re: ACM PKU 1054 The Troublesome Frog 学会剪枝[未登录]

re: ACM PKU 1775 Sum of Factorials 又是一个做男人不容易系列

re: ACM PKU 1828 Monkeys' Pride

re: ACM PKU 1011 Sticks 深度优先搜索

re: ACM PKU 2244 Eeny Meeny Moo 约瑟夫问题

re: ACM PKU 1675 Happy Birthday!

re: ACM PKU 1088 滑雪 经典的动态规划备忘录方法（记忆化搜索／Memory function ）

re: ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列 一维动态规划

re: 腾讯2009年重庆笔试附加题[未登录]

re: ACM PKU 1125 Stockbroker Grapevine 图论 Floyd算法

re: ACM PKU 1125 Stockbroker Grapevine 图论 Floyd算法

re: PKU POJ 1006 Biorhythms 从“韩信点兵”中想到的[未登录]

re: PKU POJ 1006 Biorhythms 从“韩信点兵”中想到的[未登录]

re: PKU POJ 1014 Dividing

re: PKU POJ 1014 Dividing

re: ACM PKU 1664 放苹果 类似整数划分问题的递归

re: ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列 一维动态规划

re: 在微软亚洲研究院实习，暂停做算法。实习生活博客http://sixsix.net.ms

re: PKU POJ 1014 Dividing

re: ACM PKU 1936 All in All 字符串处理

re: ACM基本算法分类、推荐学习资料和配套pku习题

C++博客-AClayton's ACM/ICPC Life 只切菜题菜鸟乱飞 -最新评论

re: ACM PKU　题目分类(完整整理版本)

re: ACM PKU 2663 Tri Tiling 简单的动态规划有趣

re: ACM　PKU 1013 Counterfeit Dollar 以前做了很久都没ａｃ的简单题

re: ACM PKU 1455 Crazy tea party 逆序数简单的数学题

re: ACM　PKU 1226 Substrings　较复杂字符串操作（但不繁琐）

re: ACM PKU 1054 The Troublesome Frog　　学会剪枝[未登录]

re: ACM PKU 1088 滑雪　经典的动态规划备忘录方法（记忆化搜索／Memory function ）

re: ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列一维动态规划

re: ACM PKU 1664 放苹果类似整数划分问题的递归

re: ACM PKU 1887 Testing the CATCHER 最长下降(上升)子序列一维动态规划