@[v天下第柒v](/space/show?uid=50202) @[Frank06](/space/show?uid=16343)
不是我BS,他说的那种puts那叫性质恶劣,你可以指责我的代码,但你不能嘲讽我的诚心。。。
至于你说splay。。。实话说,我没学过;但是就这题,我给出的这个答案而言,我并没有用到splay的知识;如果我这个程序在逻辑上有考虑不周或者错误的地方,烦请指出,感激不尽;
我在这里发帖,只是想请教下我错在哪里导致无法AC而已。。。
by Wy12121212 @ 2018-03-11 16:42:28
刚发上去就发现有人发了。。
by Frank06 @ 2018-03-11 16:44:14
呃,C·N·S的确是PKU神犇,但是他说话的确很让人不悦啊。
by qwqKanade @ 2018-03-11 16:44:36
还有,RP真心可有可无。
by qwqKanade @ 2018-03-11 16:44:55
(貌似发错了)
by qwqKanade @ 2018-03-11 16:45:06
明明是你在敷衍我们好不好。。你不把你改到认为没有问题的代码发上来,倒是发个数组大小只有50的,那我一眼看去觉得这种错误都检查不出来简直就是在玩我们这些可能会帮你改的人,换了别人都懒得理你。。再者标题说“本机AC”,本机AC啊,计算不是下载了数据并且全部通过好歹也是和标准程序对拍过的程序吧,你仅仅通过样例就这么说更让我不爽了。
不过既然我都入坑了,就给你组数据吧,你自己看看哪里错了
1 2000 2000
1 1999 2001
输出应该是maybe,你RE了。
by C·N·S @ 2018-03-11 16:45:46
@[C·N·S](/space/show?uid=89953)
多谢指教。。。
数组大小和数据类型我尝试改过了结果没有用,结果手一抖复制来的就是原先那个版本。。。发完才想起C吧吧规【要缩进】但居然没人吐槽这个。。。不管怎么说我下次会注意的,多谢了。。。
“本机AC”的话,我自己是改过几个值试过能用的只是前面没说而已,然后询问节点不为整数这我想着应该不会这么坑然后就没判定,看了你给的数据以后我发现我错了。。。输入的X可能不存在给定的f[i]中我没考虑到,是我测试数据没考虑到,万分感谢,明天我再改下程序试试。。。
还有就是,请教下【下载了数据】还有【和标准程序对拍】是哪里搞的?这还有测试数据可以下载么。。。题目的答案的话,可能是太简单了百度不到。。。
by Wy12121212 @ 2018-03-11 16:47:35
数据我一下子也找不到。题解的话google“[SCOI2007]降雨量”有很多,不过代码貌似都是pascal的。但是有几个分析得很清楚,你自己看看吧。
by C·N·S @ 2018-03-11 16:48:13
---
---
---
---
---
---
---
---
---
---
---
---
---
---
---
by λᴉʍ @ 2018-03-11 16:48:14
可还有人看这帖子么。。。我还没搞定- -|||没人看到我只能重发了。。提交还是RE
这回本机是应该真的通过了。。。后附我的测试样例
先是代码 我有缩进的说 别抽了
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n,q,a[100000],b[100000],root;
int cnt=0,fir[100000];
int depth[100000];
int f[100000][30];
inline int read()
{
int neko=0,para=1;
char nekopara=getchar();
while(nekopara<'0'||nekopara>'9'){if(nekopara=='-')para=-1;nekopara=getchar();}
while(nekopara>='0'&&nekopara<='9'){neko=neko*10+nekopara-'0';nekopara=getchar();}
return neko*para;
}
struct edge
{
int to,next;
}e[1000010];
void insert(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=fir[x];
fir[x]=cnt;
}
void dfs(int x)
{
for(int i=1;i<=20;i++)
{
if(depth[x]<(1<<i))break;
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=fir[x];i;i=e[i].next)
if(!depth[e[i].to])
{
depth[e[i].to]=depth[x]+1;
f[e[i].to][0]=x;
dfs(e[i].to);
}
}
int lca(int a,int b)
{
if(depth[a]<depth[b])swap(a,b);
int t=depth[a]-depth[b];
for(int i=0;i<=20;i++)
if(t&(1<<i))a=f[a][i];
for(int i=20;i>=0;i--)
if(f[a][i]!=f[b][i])
{
a=f[a][i];
b=f[b][i];
}
if(a==b)return a;
return f[a][0];
}
int main()
{
n=read();
q=read();
root=read();
for(int i=1;i<n;i++)
{
int a,b,l;
a=read(),b=read();
insert(a,b);
insert(b,a);
}
root=-1;
depth[root]=1;
dfs(root);
for(int i=1;i<=q;i++)
{
int a,b;
a=read(),b=read();
);
printf("%d\n",lca(a,b));
}
}
```
我的测试样例:
测试样例:
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 Wy12121212 @ 2018-03-11 16:53:13