「BZOJ3991」[SDOI2015] 寻宝游戏
Description
小B最近正在玩一个寻宝游戏，这个游戏的地图中有N个村庄和N-1条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化，有时某个村庄中会突然出现宝物，有时某个村庄内的宝物会突然消失，因此小B需要不断地更新数据，但是小B太懒了，不愿意自己计算，因此他向你求助。为了简化问题，我们认为最开始时所有村庄内均没有宝物
Input
第一行，两个整数N、M，其中M为宝物的变动次数。
接下来的N-1行，每行三个整数x、y、z，表示村庄x、y之间有一条长度为z的道路。
接下来的M行，每行一个整数t，表示一个宝物变动的操作。若该操作前村庄t内没有宝物，则操作后村庄内有宝物；若该操作前村庄t内有宝物，则操作后村庄内没有宝物。
Output
M行，每行一个整数，其中第i行的整数表示第i次操作之后玩家找到所有宝物需要行走的最短路程。若只有一个村庄内有宝物，或者所有村庄内都没有宝物，则输出0。
Sample Input
4 5
1 2 30
2 3 50
2 4 60
2
3
4
2
1
1 2 30
2 3 50
2 4 60
2
3
4
2
1
Sample Output
0
100
220
220
280
100
220
220
280
HINT
1<=N<=100000
1<=M<=100000
对于全部的数据，1<=z<=10^9
Source
题意：给定一棵树，每次将某个点设为关键点或取消关键点，求虚树中边长总和的二倍
插入or删除一个结点时就把其dfs序在set中插入or删除
每次答案就是当前set中相邻结点的距离和，再加上根到最后一个结点的距离
QAQ
为什么我会把ans写成int看不出来
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define mod 10000007 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int bin[20],fac[20],a[5005]; ll ans; bool check(int x,int k) { for(int i=1;i<bin[k];i++)if(a[x+i]!=a[x+i-1]+1)return 0; return 1; } void swap(int x,int y,int k) { for(int i=0;i<bin[k];i++) swap(a[x+i],a[y+i]); } void dfs(int k,int now) { if(k==n+1) { for(int i=1;i<=bin[n];i++) if(a[i]<a[i-1])return; ans+=fac[now]; return; } int t1=0,t2=0; for(int i=1;i<=bin[n];i+=bin[k]) if(!check(i,k)) { if(!t1)t1=i; else if(!t2)t2=i; else return; } if(!t1&&!t2)dfs(k+1,now); else if(t1&&!t2) { swap(t1,t1+bin[k-1],k-1); dfs(k+1,now+1); swap(t1,t1+bin[k-1],k-1); } else { for(int x=0;x<=1;x++) for(int y=0;y<=1;y++) { swap(t1+x*bin[k-1],t2+y*bin[k-1],k-1); if(check(t1,k)&&check(t2,k)) { dfs(k+1,now+1); swap(t1+x*bin[k-1],t2+y*bin[k-1],k-1); break; } swap(t1+x*bin[k-1],t2+y*bin[k-1],k-1); } } } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; fac[0]=1;for(int i=1;i<=12;i++)fac[i]=fac[i-1]*i; n=read(); for(int i=1;i<=bin[n];i++)a[i]=read(); dfs(1,0); printf("%lld",ans); return 0; } |
计数器 9850932
OI 课件=>
OI 课件=>
这个代码还是错的。。。
那个人乱顶别人名字在这里瞎搞。
已删
学长您这个wa30啊QAQ
= =打错，wa15
不明觉厉
跪求学长指点迷津
贴错代码了。。。