1. 首页
  2. 文章中心
  3. 经验

本地AC在线WA?RE？来个栗子帮助你。

72 阅读 0 评论
我是靠谱客的博主 醉熏自行车，这篇文章主要介绍本地AC在线WA?RE？来个栗子帮助你。，现在分享给大家，希望可以做个参考。

题目是模板题树链剖分

至于我为什么把树剖当模板题，别问我，我就是这个题出了错。

可以不懂代码什么意思，毕竟不是关于树剖的博客

第一次打，样例过了，交80分，感到莫名其妙，看了半天没看出哪里错了。问一个已经AC的大佬，他跟我说我没开long long 。我看看题面，除了n和m的数据范围，什么都没有。可能确实要开long long。但是开了longlong我还是WA80，不想把int改成long long 了，于是define 了一下，把scanf改成%lld。

以下是第一次代码（WA80）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010 ;
struct edge{
int to,next ;
}e[N<<1];
int head[N],a[N];
int f[N];
//i的父亲
int dep[N];
//i的深度
int size[N]; //i的子树大小 
int son[N];
//重儿子 
int rk[N];
//i的dfs值，与dfn相反
int top[N];
//i所在链的顶端
int dfn[N];
//dfs序，时间戳 
int n,m,p,r,rt,tot,cnt ;
inline void add(int x,int y){
e[++cnt].to=y;
e[cnt].next=head[x] ;
head[x]=cnt ;
}
void dfs1(int rt,int fa,int depth){ //主要处理深度，父亲和儿子 
f[rt]=fa;dep[rt]=depth;size[rt]=1;//一些初始化 
for (int i=head[rt];i;i=e[i].next){
int to=e[i].to ;
if (to==fa) continue ;//保证不是父亲 
dfs1(to,rt,depth+1) ;
size[rt]+=size[to] ;//rt的大小+子树的大小 
if (size[son[rt]]<size[to]) son[rt]=to ;//改变重儿子 
}
}
void dfs2(int rt,int t){ //主要处理链，dfs序 
top[rt]=t;dfn[rt]=++cnt;rk[cnt]=rt;//初始化
if (!son[rt]) return ;//该点没有重儿子 
dfs2(son[rt],t) ;//rt的重儿子也是和rt一样处于以t为顶端的重链 
for (int i=head[rt];i;i=e[i].next){
int to=e[i].to ;
if (to!=f[rt] && to!=son[rt]) dfs2(to,to) ;//一个点位于轻链底端，那么它的top必然是它本身
}
}
struct seg{ //线段树 
int ls,rs,lazy,l,r,sum ;
}tree[N<<1];
inline void pushup(int rt){
tree[rt].sum=(tree[tree[rt].ls].sum+tree[tree[rt].rs].sum+
tree[rt].lazy*(tree[rt].r-tree[rt].l+1))%p;
}
void build(int ll,int rr,int rt){ //create
if (ll==rr){
tree[rt].l=tree[rt].r=ll ;
tree[rt].sum=a[rk[ll]] ;
return ;
}
else {
int mid=(ll+rr)>>1;
tree[rt].ls=cnt++ ;
tree[rt].rs=cnt++ ;
build(ll,mid,tree[rt].ls) ;
build(mid+1,rr,tree[rt].rs) ;
tree[rt].l=tree[tree[rt].ls].l ;
tree[rt].r=tree[tree[rt].rs].r ;
pushup(rt) ;
}
}
void update(int l,int r,int rt,int c){ //l~r +c 
if (l<=tree[rt].l && tree[rt].r<=r) {
tree[rt].sum=(tree[rt].sum+c*(tree[rt].r-tree[rt].l+1))%p ;
tree[rt].lazy=(tree[rt].lazy+c)%p ;
}
else {
int mid=(tree[rt].l+tree[rt].r)>>1 ;
if (l<=mid) update(l,r,tree[rt].ls,c) ;
if (mid<r) update(l,r,tree[rt].rs,c) ;
pushup(rt) ;
}
}
int query(int l,int r,int rt){
if (l<=tree[rt].l && tree[rt].r<=r) return tree[rt].sum ;
int tot=(tree[rt].lazy*(min(r,tree[rt].r)-max(l,tree[rt].l)+1)%p)%p ;//初始值
//int tot=node[cur].lazy*(min(node[cur].r,ri)-max(node[cur].l,li)+1)%p ;
int mid=(tree[rt].l+tree[rt].r)>>1 ;
if (l<=mid) tot=(tot+query(l,r,tree[rt].ls))%p ;
if (mid<r)
tot=(tot+query(l,r,tree[rt].rs))%p ;
return tot%p ;
}
inline int sum(int x,int y){
int ans=0,fx=top[x],fy=top[y] ;
while (fx!=fy){
if (dep[fx]>=dep[fy]) {
ans=(ans+query(dfn[fx],dfn[x],rt))%p ;
x=f[fx],fx=top[x] ;
}
else {
ans=(ans+query(dfn[fy],dfn[y],rt))%p ;
y=f[fy],fy=top[y] ;
}
}
if (dfn[x]<=dfn[y]) ans=(ans+query(dfn[x],dfn[y],rt))%p ;
else ans=(ans+query(dfn[y],dfn[x],rt))%p ;
return ans%p ;
}
inline void UPDATE(int x,int y,int c){
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]>=dep[fy]){
update(dfn[fx],dfn[x],rt,c) ;
x=f[fx],fx=top[x];
}
else {
update(dfn[fy],dfn[y],rt,c) ;
y=f[fy],fy=top[y];
}
}
if (dfn[x]<=dfn[y]) update(dfn[x],dfn[y],rt,c) ;
else update(dfn[y],dfn[x],rt,c) ;
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&p) ;
for (int i=1;i<=n;i++) scanf("%d",&a[i]) ;
for (int i=1;i<n;i++){
int x,y ;
scanf("%d%d",&x,&y) ;
add(x,y);
add(y,x) ;
}
cnt=0 ;
dfs1(r,0,1) ;
dfs2(r,r) ;
cnt=0;
rt=cnt++ ;
build(1,n,rt);
//
cout<<"!!"<<endl ;
//
for (int i=1;i<=n;i++)
// printf("i=%d f[i]=%lld dep[i]=%d size[i]=%d son[i]=%d rk[i]=%d top[i]=%d dfn[i]=%dn",i,f[i],dep[i],size[i],son[i],rk[i],top[i],dfn[i]) ;
//
for (int i=1;i<=cnt;i++){
//
printf("%lld %lld %lld %lld %lld %lldn",tree[i].l,tree[i].r,tree[i].ls,tree[i].rs,tree[i].lazy,tree[i].sum) ;
//
}
for (int i=1;i<=m;i++){
int x,y,z,op ;
scanf("%d",&op);
if (op==1){
scanf("%d%d%d",&x,&y,&z) ;
UPDATE(x,y,z) ;
}
else if (op==2){
scanf("%d%d",&x,&y) ;
printf("%dn",sum(x,y)) ;
}
else if (op==3){
scanf("%d%d",&x,&z) ;
update(dfn[x],dfn[x]+size[x]-1,rt,z) ;
}
else{
scanf("%d",&x) ;
printf("%dn",query(dfn[x],dfn[x]+size[x]-1,rt)) ;
}
}
}

提交上去，RE80.更加匪夷所思。把数据下下来，本地机测了一下，AC。？？？？怀疑oj有bug，但是听说以前也有什么BZOJAC洛谷WA啦，RE啦等等的，还是去洛谷在线IDE评测一下，RE，还是Segmentation Fault，心想这种鬼畜的错误我也赶得上。

re

因为前面是WA80，没有RE，所以肯定与long long 有关。后来发现define写太后面了，写在 const int N = 100010 后面了， 可能挂，于是改了一下，依然RE。。。。

检查scanf,发现了问题:

aaa

光标这一处用了%d读入，

正好读入有不少op=4的，

bbb

就RE了

改完了就AC了，还是蛮喜悦的。

顺便发一波AC代码，。。。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
using namespace std;
const int N = 100010 ;
#define int long long
struct edge{
int to,next ;
}e[N<<1];
int head[N],f[N],dep[N],size[N],son[N],rk[N],top[N],dfn[N];
int a[N];
//f[i]:i的父亲,dep[i]:i的深度,size[i]:i的子树大小,son[i]:重儿子 ,rk[i]:i的dfs值，与dfn相反
//top[i]:i所在链的顶端,dfn[i]:dfs序，时间戳 
int n,m,rt,tot,cnt;
int p,r ;
inline void add(int x,int y){
e[++cnt].to=y;
e[cnt].next=head[x] ;
head[x]=cnt ;
}
void dfs1(int rt,int fa,int depth){ //主要处理深度，父亲和儿子 
f[rt]=fa;dep[rt]=depth;size[rt]=1;//一些初始化 
for (int i=head[rt];i;i=e[i].next){
int to=e[i].to ;
if (to==fa) continue ;//保证不是父亲 
dfs1(to,rt,depth+1) ;
size[rt]+=size[to] ;//rt的大小+子树的大小 
if (size[son[rt]]<size[to]) son[rt]=to ;//改变重儿子 
}
return ;
}
void dfs2(int rt,int t){ //主要处理链，dfs序 
top[rt]=t;dfn[rt]=++cnt;rk[cnt]=rt;//初始化
if (!son[rt]) return ;//该点没有重儿子 
dfs2(son[rt],t) ;//rt的重儿子也是和rt一样处于以t为顶端的重链 
for (int i=head[rt];i;i=e[i].next){
int to=e[i].to ;
if (to!=f[rt] && to!=son[rt]) dfs2(to,to) ;//一个点位于轻链底端，那么它的top必然是它本身
}
return ;
}
struct seg{ //线段树 
int ls,rs,lazy,l,r;
int sum ;
}tree[N<<1];
inline void pushup(int rt){
tree[rt].sum=(tree[tree[rt].ls].sum+tree[tree[rt].rs].sum+
tree[rt].lazy*(tree[rt].r-tree[rt].l+1))%p;
return ;
}
void build(int ll,int rr,int rt){ //create
if (ll==rr){
tree[rt].l=tree[rt].r=ll ;
tree[rt].sum=a[rk[ll]] ;
return ;
}
else {
int mid=(ll+rr)>>1;
tree[rt].ls=cnt++ ;
tree[rt].rs=cnt++ ;
build(ll,mid,tree[rt].ls) ;
build(mid+1,rr,tree[rt].rs) ;
tree[rt].l=tree[tree[rt].ls].l ;
tree[rt].r=tree[tree[rt].rs].r ;
pushup(rt) ;
}
return ;
}
void update(int l,int r,int rt,int c){ //l~r +c 
if (l<=tree[rt].l && tree[rt].r<=r) {
tree[rt].sum=(tree[rt].sum+c*(tree[rt].r-tree[rt].l+1))%p ;
tree[rt].lazy=(tree[rt].lazy+c)%p ;
}
else {
int mid=(tree[rt].l+tree[rt].r)>>1 ;
if (l<=mid) update(l,r,tree[rt].ls,c) ;
if (mid<r) update(l,r,tree[rt].rs,c) ;
pushup(rt) ;
}
return ;
}
int query(int l,int r,int rt){
if (l<=tree[rt].l && tree[rt].r<=r) return tree[rt].sum ;
int tot=(tree[rt].lazy*(min(r,tree[rt].r)-max(l,tree[rt].l)+1)%p)%p ;//初始值
int mid=(tree[rt].l+tree[rt].r)>>1 ;
if (l<=mid) tot=(tot+query(l,r,tree[rt].ls))%p ;
if (mid<r)
tot=(tot+query(l,r,tree[rt].rs))%p ;
return tot%p ;
}
inline int sum(int x,int y){
int ans=0;
int fx=top[x],fy=top[y] ;
while (fx!=fy){
if (dep[fx]>=dep[fy]) {
ans=(ans+query(dfn[fx],dfn[x],rt))%p ;
x=f[fx],fx=top[x] ;
}
else {
ans=(ans+query(dfn[fy],dfn[y],rt))%p ;
y=f[fy],fy=top[y] ;
}
}
if (dfn[x]<=dfn[y]) ans=(ans+query(dfn[x],dfn[y],rt))%p ;
else ans=(ans+query(dfn[y],dfn[x],rt))%p ;
return ans%p ;
}
inline void UPDATE(int x,int y,int c){
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]>=dep[fy]){
update(dfn[fx],dfn[x],rt,c) ;
x=f[fx],fx=top[x];
}
else {
update(dfn[fy],dfn[y],rt,c) ;
y=f[fy],fy=top[y];
}
}
if (dfn[x]<=dfn[y]) update(dfn[x],dfn[y],rt,c) ;
else update(dfn[y],dfn[x],rt,c) ;
return ;
}
main(){
scanf("%lld%lld%lld%lld",&n,&m,&r,&p) ;
for (int i=1;i<=n;i++) scanf("%lld",&a[i]) ;
for (int i=1;i<n;i++){
int x,y ;
scanf("%lld%lld",&x,&y) ;
add(x,y);
add(y,x) ;
}
cnt=0 ;
dfs1(r,0,1) ;
dfs2(r,r) ;
cnt=0;
rt=cnt++ ;
build(1,n,rt);
for (int i=1;i<=m;i++){
int x,y,op ;
int z ;
scanf("%lld",&op);
if (op==1){
scanf("%lld%lld%lld",&x,&y,&z) ;
UPDATE(x,y,z) ;
}
else if (op==2){
scanf("%lld%lld",&x,&y) ;
printf("%lldn",sum(x,y)) ;
}
else if (op==3){
scanf("%lld%lld",&x,&z) ;
update(dfn[x],dfn[x]+size[x]-1,rt,z) ;
}
else {
scanf("%lld",&x) ;
printf("%lldn",query(dfn[x],dfn[x]+size[x]-1,rt)) ;
}
}
}

涨了经验，下次不要犯同样的教训！！！

最后

以上就是醉熏自行车最近收集整理的关于本地AC在线WA?RE？来个栗子帮助你。的全部内容，更多相关本地AC在线WA内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(48)

相关文章

第三次周赛G题(POJ-1995)
第三次周赛G题(POJ-1995)
2020 CCPC Wannafly Winter Camp Day6 M—自闭——模拟
2020 CCPC Wannafly Winter Camp Day6 M—自闭——模拟
【西南交大峨眉校区INT杯网络赛 --- A. INT比赛排名】模拟
【西南交大峨眉校区INT杯网络赛 --- A. INT比赛排名】模拟
zzuli OJ 1036: 某年某月有多少天
zzuli OJ 1036: 某年某月有多少天
本地AC在线WA?RE？来个栗子帮助你。
本地AC在线WA?RE？来个栗子帮助你。
#19ACM第五次周赛补题赛de题解呐#
#19ACM第五次周赛补题赛de题解呐#
HDU2043，两段代码一模一样，一个AC了，一个WA，不知道为什么密码
HDU2043，两段代码一模一样，一个AC了，一个WA，不知道为什么密码
【ZZULIOJ】1036: 某年某月有多少天ZZULIOJ题解
【ZZULIOJ】1036: 某年某月有多少天ZZULIOJ题解

评论列表共有 0 条评论

立即
投稿
返回
顶部