Seter @ 2013-01-28 20:10:32

代码明显有问题，你本机是怎么A的。。

Seter @ 2013-01-29 12:32:26

原来你的逻辑是样例过了就是A了啊。。。自己看看原题数据范围。。。再不懂就别做了吧 = =+

newworld @ 2013-01-29 14:08:10

@Seter
数据范围的话数组大小我试过用50000，变量我能想到的只有long int也不行所以上面程序才用的int和y[50]；
我整个程序虽然现在无法AC但逻辑并没有错，我诚心诚意地发问了，你不说也就算了，用个puts吐槽我又是要作甚？

newworld @ 2013-01-29 17:55:29

@vfleaking
不是我BS，他说的那种puts那叫性质恶劣，你可以指责我的代码，但你不能嘲讽我的诚心。。。
至于你说线段树。。。实话说，我没学过；但是就这题，我给出的这个答案而言，我并没有用到线段树的知识；如果我这个程序在逻辑上有考虑不周或者错误的地方，烦请指出，感激不尽；
我在这里发帖，只是想请教下我错在哪里导致无法AC而已。。。

SpiritBreaker @ 2013-01-29 18:23:54

还有，RP真心可有可无。

newworld @ 2013-01-29 22:28:04

@testSeter
多谢指教。。。
数组大小和数据类型我尝试改过了结果没有用，结果手一抖复制来的就是原先那个版本。。。发完才想起C吧吧规【要缩进】但居然没人吐槽这个。。。不管怎么说我下次会注意的，多谢了。。。
“本机AC”的话，我自己是改过几个值试过能用的只是前面没说而已，然后年份为负数这我想着应该不会这么坑然后就没判定，看了你给的数据以后我发现我错了。。。输入的X可能不存在给定的y[i]中我没考虑到，是我测试数据没考虑到，万分感谢，明天我再改下程序试试。。。
还有就是，请教下【下载了数据】还有【和标准程序对拍】是哪里搞的？这还有测试数据可以下载么。。。题目的答案的话，可能是太简单了百度不到。。。

newworld @ 2013-02-03 22:39:19

可还有人看这帖子么。。。我还没搞定- -|||没人看到我只能重发了。。提交还是RE
这回本机是应该真的通过了。。。后附我的测试样例
先是代码 我有缩进的说 别抽了
#include<iostream>
using namespace std;
long int y[50001],r[50001];
long int n,m;

long int rmax(long int c,long int d)
{
long int i,maxr;
maxr=0;
for(i=c;i<=d;i++)
{ if(r[i]>maxr) maxr=r[i]; }
return maxr;
}

long int rmin(long int c,long int d)
{
long int i,minr;
minr=r[c];
for(i=c;i<=d;i++)
{ if(r[i]<minr) minr=r[i]; }
return minr;
}

int main()
{
long int X,Y,a,b,c,d,e,i,i2,j,k,l,k2,l2,s,p,q;
cin>>n;
for(i=0;i<n;i++)
{ cin>>y[i]>>r[i]; }
cin>>m;
for(i=0;i<m;i++)
{
a=-1;
b=-1;
cin>>Y>>X;
for(j=0;j<n;j++)
{
if(y[j]==X) a=j;
if(y[j]==Y) b=j;
}
if(a==-1&&b==-1) { cout<<"maybe"<<endl; continue; }
if(a!=-1&&b==-1)
{
p=0;
for(k=Y;k<X;k++)
{
for(l=0;l<a;l++)
{ if(y[l]==k) { p=1; break; } }
if(p==1) break;
}
c=rmax(l,a);
if(c>r[a]) { cout<<"false"<<endl; continue; }
else { cout<<"maybe"<<endl; continue; }
}
if(a==-1&&b!=-1)
{
q=0;
for(k2=X;k2>Y;k2--)
{
for(l2=n;l2>b;l2--)
{ if(y[l2]==k2) { q=1; break; } }
if(q==1) break;
}
d=rmin(b+1,l2);
if(d>r[b]) { cout<<"false"<<endl; continue; }
else { cout<<"maybe"<<endl; continue; }
}
if(a!=-1&&b!=-1)
{
if(r[a]>r[b]) { cout<<"false"<<endl; continue; }
e=rmax(b+1,a-1);
if(e>=r[a]) { cout<<"false"<<endl; continue; }
s=0;
for(i2=b;i2<a;i2++)
{ if(y[i2]+1<y[i2+1]) { s=1; break; } }
if(s==1) { cout<<"maybe"<<endl; continue; }
cout<<"true"<<endl;
}
}
return 0;
}

我的测试样例：
测试样例：
13
10 5
11 9
12 4
13 3
14 8
15 12
16 9
20 11
21 10
22 3
23 4
25 13
26 5

建议测试输入：
30（随意，方便测试）
（X,Y均未知和均已知的情况可以自由测试）
（1>已知X，Y不知道：）
9 10 ->M
9 13 ->F
9 22 ->F
9 25 ->M
17 25 ->M
17 23 ->F
（2>已知Y，X不知道：）
10 17 ->M
15 18 ->M
11 24 ->M
25 27 ->M
13 17 ->F
14 17 ->F
13 21 ->F

newworld @ 2013-02-03 22:46:01

@Seter
@testSeter
@所有人
思路是
假设X、Y都不知道，那么显然是Maybe；
假设X知道Y不知道，那么二分找出晚于Y的最早知道的年，看中间这一段的最大值，
如果大于X，则False；
否则Maybe；
假设X不知道Y知道，一样的，看区间最小值小于Y则Maybe，否则false；
假设X，Y都知道，
如果X>Y，则False；
否则看区间最大值，
如果>=X则False;
否则看区间中是否有某一年不知道，
如果有年不知道，则Maybe；
否则True。

感谢 pearfish16 来自他百度空间的思路。。。

vfleaking @ 2013-02-04 11:48:10

= =.........
其实你即使最后不RE了，也会TLE了。
不知道你有没有学过“时间复杂度”？没学过就问问你老师吧。。
现在你的程序的时间复杂度就是O(n^2)，你这样会超时的对不对～
所以不能这么做对不对……
去学学线段树或者平衡树吧……
不想学的话是A不掉这题的……顶多最后是个TLE
哦……你是不是不知道TLE是啥：“Time Limit Exceed”……

你的思路的话……我也不知道是不是对的……这题我已经忘光了……

newworld @ 2013-02-04 13:00:15

@lydrainbowcat
LZ承认自己智商拙计 官方数据啥的找不到啊。。。网上的代码我找过也都是RE的，你说的自己生成随机数据我不知道咋弄。。。
@vfleaking
@Seter
LZ基本是自学，乃们科班出身满脑袋高级算法的要不要这么嘲讽。。。时间复杂度听说过，每一层for()算一个O(n)吧。。。那也就是区间内最值的搜寻要用更高效的算法是吧。。。但是我对于每组输入用的for(i;i<m;i++)就已经消耗了一个O(n)这么说可对。。。LZ回去试试二分- -|||，再不行我再去看看你那什么树。。。

Seter @ 2013-02-04 14:30:55

身处乱世，谁不是自学？ = =

vfleaking @ 2013-02-04 15:13:17

我什么时候成北大的了……

newworld @ 2013-02-04 22:24:02

见9楼。。。
不要说PKU不是Peking University - -

Riatre @ 2013-02-05 12:54:03

算了我来当回好人发下数据下载地址
http://ncpc.idi.ntnu.no/ncpc2005/all_NCPC2005.tar.gz
楼主要找的是weather那题。


BTW, 我很想说一句楼主naive怎么办……

vfleaking @ 2013-02-05 18:55:15

给Seter跪了！！！（求模仿）
@newworld
我是来澄清事实的。
Seter目前所取得的成就与PKU没什么关系。
为什么呢？
因为Seter是凭借自己的努力，顽强拼搏，被北大优录的。
因为Seter是神犇，且Seter被北大优录，所以才被称为PKU神犇～
这样误会就澄清鸟～

我以前一直以为强省的OIer是老师手把手教出来的，直到有一天我膝盖中了某湖南神犇的鄙视之箭。
几乎所有OI界的大牛，都是靠自学成就的自己。
我绝对没有鄙视LZ的意思，越看越觉得LZ很像当年的我。
当年没有人告诉我NOIP与NOI的一个“P”字母的难度相差究竟有多大，我不希望LZ也因此走弯路。希望LZ能尽快从NOIP过渡到NOI，看清楚数据范围，勿轻敌。

好啦就说这么多……估计这话LZ也不很爱听吧……= =

lydrainbowcat @ 2013-02-05 20:16:46

这贴已经Hot了唉！
@Seter@vfleaking 求PKU神犇指点指点我这个弱菜吧。

newworld @ 2013-02-05 21:41:24

@vfleaking
被提前扣了个不爱听的帽子- - 这个。。。LZ还没这么坑。。。
LZ应该怎么说呢。。。让我组织下语言。。。
首先，LZ是条渣渣大学狗。。。
其次，关于ACM这东西，LZ并不是很了解；什么竞赛啊，什么高考加分啊，LZ在变成大学狗之前从来就没有听说过；我当初只知道高考要加20分，只有数学/物理/生物/航模省一等奖才有救。。。当初LZ只拿过一个生物。。县一等奖。。然后LZ就完全不管这方面的东西了，高中这之类的课什么的更加没有了，连LZ自己生物的复习什么也都是靠平时的知识，没有什么竞赛培训什么的。。。说回ACM，LZ只是在读大学的过程中，听说有这么个玩意儿可以用来练习编程，然后就想着来做做看。。。
LZ知道自己的大学有多坑爹，更知道自己的编程水平有多坑爹，所以楼上说啥LZ阿玛依的LZ妥妥的认了。。。并没有什么话爱听不爱听的说法。。。但LZ阿玛依的是编程，这狗头自认还是有点用处的。
LZ对你们的环境和知识渠道并不了解，也不知道你们是怀揣着怎样的一种态度，一种目的来做ACM，但是楼上几位很明显，你们已经达到了自己的目的。。。LZ来做ACM，目的只是提升自己的编程水平，虽说是渣渣大学狗，也不至于出去以后编程啥都不懂，那就坑了。。。vfleaking你真的以为LZ是想ACM一条道走到黑么？不现实的事情，LZ会努力，但是LZ面临的压力，现实的压力，绝对比你们这种重点高中，名牌大学的要重得多；你们相对于我来说，有充足的时间，精力和天分，环境和动力来做你们想做的事情；你们或许现在还想着再多切几道题，再多学几个算法，LZ却必须为今后考量，考虑怎样才能不饿死。LZ想学，LZ会自己想办法学，但是现在就用LZ的钛合金狗眼这么看下去，LZ切个两年的题，除非LZ今后卖切糕，不然ACM的题不能带给LZ任何现实的收益，我不可能为了一些短时间内不能挣饭吃的知识赌上LZ紧迫的时间；
那你又要问LZ：既然你觉得ACM没用，你还做他作甚？ LZ前面已经说了，我的目的在于通过做ACM，提升自己的编程水平；为啥要提升自己的编程水平？很显然，LZ专业是计算机，接下来LZ面临着毕业设计，分配实习等一系列大麻烦，就LZ现在这水平，你们也看得见。LZ并不指望以后能靠编程挣饭吃，更不指望切几道ACM就能一下变成高手；LZ只是想在有限的时间里，有限地提升自己的编程水平，能应付下来毕业设计和实习的起步要求，LZ已经满足了；以后？以后，LZ可能会学，也可能不会学，这是后话，LZ无法看到LZ未来太远的影像。。。
若是再扯远一点，什么不好好学习愧对父母，什么颓废的大学，不想扯这么多。放在这里都是废话。

wyl8899 @ 2013-02-05 22:03:31

这帖好多人 = = 我也凑个热闹
这题啊...
我bzoj上WA啊!
我poj上WA啊!
但是我能A掉原题的数据啊!
坑爹死了!

Seter @ 2013-02-05 22:12:58

1.我居然看完了
2.作为杭二的重点班居然被吐槽了
3.<del>LZ自称“老娘”？如果LZ是女生的话我表示愿意道歉……</del>大姨夫……妈蛋LZ想闹哪样

yangyue1995 @ 2013-02-05 22:23:35

好火的样子，退役狗来围观

newworld @ 2013-02-05 22:24:10

@wyl8899
就知道有人会掏出这。。。
你觉得是LZ没拿出求助的态度呢，还是出言不逊呢。。。要是你能指出LZ哪里没做到话LZ表示愿意道歉。。。
@Seter
- - 乃是杭二的么。。。能问下哪届哪班的么。。。
还有就是乃为啥要道歉呢。。。

Seter @ 2013-02-05 22:35:20

2013毕业的12班。我不知道为啥要道歉，但是我感觉LZ对我有不满，所以如果LZ是女生的话我应该会选择不回这个贴而不是让LZ产生不满情绪。

yangyue1995 @ 2013-02-05 22:38:40

女神你无时无刻无处不在的在不遗余力的黑我作甚

zjr506 @ 2013-02-05 22:57:57

回LZ
我不觉得这是嘲讽屈辱什么的……这也是必经的一个过程吧……因为我毕竟是什么都不懂 被教育一下也挺正常的……现在也谈不上回报……但是这是屌丝的理想……
其实我心底有一个秘密就是我一直仰慕顾宇宙……因为他我才学习的信息学！他是我的动力！我墙上都是顾宇宙获奖的海报！
为了这个顾宇宙的女朋友丽洁姐姐还曾经到我家来查水表……唉 只是仰慕而已……虽然丽洁姐姐的OI水平也很强！我经常向他请教她说我进步很大！我很高兴！

newworld @ 2013-02-05 23:21:16

@zjr506
恩。。。。。。怎么说呢。
被教育。。。仰慕。。。屌丝。。。LZ怎么看，怎么觉得心痛。怎么说呢，既然你也跟LZ说了自己的个人经历，那LZ也来说说LZ的吧。。。
LZ94年生人，小学初中家里穷没读，高中捡了所私立破烂进去的，现在大学本科即将毕业，人和人真的差的了多少？
LZ高中之前一直在家，天真浪漫小破孩一枚，直接上的垃圾高中，被欺负，群架，泡妞，抽烟喝酒，社会底层的阴暗面LZ亲身经历浸淫三年，每年新学生来，年级对冲的几百人群架，LZ活下来了，到毕业，一多半人混社会，LZ拼死拼活上了本科，嘲讽屈辱？就网上这点？开什么玩笑。。。
你要记住，社会确实是分阶层的，你的努力归根到底是为了更上一个阶层。而不管在什么地方，有一条道理永远不会变，那就是做人的道理，有理有据，进退守节，听起来简单，其实很难，但不管怎样，你要去做，这样的话，到最后你是不会吃亏的；举个例子，某混社会的小头头当面找你“借钱”，你给不给？当然给，必须装孙子，掏出10元大洋主动递出去，但是回头，联系好自己认识的人，学校要好的老师，动用你一切能动用的关系，让他第二次看到你的时候开不了口。具体操作有点麻烦，但是记住，这绝不是理所当然，啊呀，我给钱吧，因为我毕竟比他弱，打又打不过，认识的人又比他多，这次给了吧，老天保佑下次他别问我要。。。。你要这么想，你就完蛋了。
LZ非常不建议你把某个人当成目标，当成偶像。你要有自信，要有自己的操守，你的目标不是成为那个人，而是成为一个能力至少相当于那个人的存在，切记切记。所以哪怕是奥巴马站在你的面前，LZ也希望你能把45度上仰的脑袋变成水平线，必须要正确地审视你对面的人，每个人有每个人自己的生活方式，没必要比高比低，自己活得好就行，一个小办法，你想，你用不着他的时候，他啥都不是，你要这么想，你自然而然地抬起头来了。而如果你对面是一个真正的强者的话，他会喜欢能够直视他的人的。