@[applese](/space/show?uid=22258)
多谢指教。。。
数组大小和数据类型我尝试改过了结果没有用,结果手一抖复制来的就是原先那个版本。。。发完才想起C吧吧规【要缩进】但居然没人吐槽这个。。。不管怎么说我下次会注意的,多谢了。。。
“本机AC”的话,我自己是改过几个值试过能用的只是前面没说而已,然后年份为负数这我想着应该不会这么坑然后就没判定,看了你给的数据以后我发现我错了。。。输入的X可能不存在给定的y[i]中我没考虑到,是我测试数据没考虑到,万分感谢,明天我再改下程序试试。。。
还有就是,请教下【下载了数据】还有【和标准程序对拍】是哪里搞的?这还有测试数据可以下载么。。。题目的答案的话,可能是太简单了百度不到。。。
by lin_toto @ 2017-05-11 17:32:21
数据我一下子也找不到。题解的话google“[SCOI2007]降雨量”有很多,不过代码貌似都是pascal的。但是有几个分析得很清楚,你自己看看吧。
by Sonorous @ 2017-05-11 17:32:37
可还有人看这帖子么。。。我还没搞定- -|||没人看到我只能重发了。。提交还是RE
这回本机是应该真的通过了。。。后附我的测试样例
先是代码 我有缩进的说 别抽了
```cpp
#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
by lin_toto @ 2017-05-11 17:34:15
OH NO 空格全阵亡了。。。肿么办啊。。。
@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 来自他百度空间的思路。。。
by lin_toto @ 2017-05-11 17:35:05
在本机通过,应该你至少下载到官方数据或者跟人对拍过吧。
你自己造了几组数据可不能算本机通过,这样就拿来代码让别人看是一种不好的行为哦。
对拍就是你找一份别人通过的代码,自己用程序生成随机数据,然后运行,用windows自带的fc命令,看两份程序的结果是否完全相同。用程序执行这个过程很多次(一般执行上万次之后才能说自己的程序没什么问题了)。
by deluxurous @ 2017-05-11 17:35:53
= =.........
其实你即使最后不RE了,也会TLE了。
不知道你有没有学过“时间复杂度”?没学过就问问你老师吧。。
现在你的程序的时间复杂度就是O(n^2),你这样会超时的对不对~
所以不能这么做对不对……
去学学线段树或者平衡树吧……
不想学的话是A不掉这题的……顶多最后是个TLE
哦……你是不是不知道TLE是啥:“Time Limit Exceed”……
你的思路的话……我也不知道是不是对的……这题我已经忘光了……
by deluxurous @ 2017-05-11 17:36:08
我有一个特别好的毒舌句来吐槽LZ,可惜这里空间太小了我写不下
by Sonorous @ 2017-05-11 17:36:13
@[lydrainbowcat](/space/show?uid=8189)
LZ承认自己智商拙计 官方数据啥的找不到啊。。。网上的代码我找过也都是RE的,你说的自己生成随机数据我不知道咋弄。。。
@vfleaking
@Seter
LZ基本是自学,乃们科班出身满脑袋高级算法的要不要这么嘲讽。。。时间复杂度听说过,每一层for()算一个O(n)吧。。。那也就是区间内最值的搜寻要用更高效的算法是吧。。。但是我对于每组输入用的for(i;i<m;i++)就已经消耗了一个O(n)这么说可对。。。LZ回去试试二分- -|||,再不行我再去看看你那什么树。。。
by lin_toto @ 2017-05-11 17:37:06
身处乱世,谁不是自学? = =
by deluxurous @ 2017-05-11 17:37:30
身处乱世,谁不是自学? = =
by Sonorous @ 2017-05-11 17:37:57