关键词:
题解:每个炸弹爆炸影响一个区间,通过二分查找找到
若A爆炸炸到B则连一条A到B的边
线段树优化建图
缩点+DP
因为每个炸弹的答案一定是一个区间,所以记录每个节点的左端点和右端点
合并时取最值
反思:思维定式,以为求解可达点个数不能合并
/************************************************************** Problem: 5017 User: ws_zzyer Language: C++ Result: Accepted Time:5928 ms Memory:390956 kb ****************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #define lo now<<1 #define ro now<<1|1 using namespace std; const int maxn=1600000; const int oo=1000000000; const int mm=1000000007; int n,totn; long long a[maxn]; long long r[maxn]; int tl[maxn],tr[maxn]; int cntedge; int head[maxn]; int to[30000009],nex[30000009]; void Addedge(int x,int y) nex[++cntedge]=head[x]; to[cntedge]=y; head[x]=cntedge; struct SegmentTree int l,r; int u; tree[500009<<2]; void BuildTree(int now,int l,int r) tree[now].l=l;tree[now].r=r; tree[now].u=++totn; for(int i=l;i<=r;++i)Addedge(totn,i); if(l==r)return; int mid=(l+r)>>1; BuildTree(lo,l,mid); BuildTree(ro,mid+1,r); void Updatasec(int now,int ll,int rr,int x) if(tree[now].l>=ll&&tree[now].r<=rr) Addedge(x,tree[now].u); return; int mid=(tree[now].l+tree[now].r)>>1; if(ll<=mid)Updatasec(lo,ll,rr,x); if(rr>mid)Updatasec(ro,ll,rr,x); int dfsclock,scccnt; int pre[maxn],lowlink[maxn],sccno[maxn]; int lb[maxn],rb[maxn]; int S[maxn],top; void Dfs(int u) pre[u]=lowlink[u]=++dfsclock; S[++top]=u; for(int i=head[u];i;i=nex[i]) int v=to[i]; if(!pre[v]) Dfs(v); lowlink[u]=min(lowlink[u],lowlink[v]); else if(!sccno[v]) lowlink[u]=min(lowlink[u],pre[v]); if(lowlink[u]==pre[u]) ++scccnt; for(;;) int x=S[top--]; sccno[x]=scccnt; if(x==u)break; vector<int>G[maxn]; void Tarjan() for(int i=1;i<=totn;++i)if(!pre[i])Dfs(i); for(int i=1;i<=totn;++i) lb[i]=oo;rb[i]=-oo; for(int i=1;i<=n;++i) int x=sccno[i]; lb[x]=min(lb[x],tl[i]); rb[x]=max(rb[x],tr[i]); for(int u=1;u<=totn;++u) for(int i=head[u];i;i=nex[i]) int v=to[i]; if(sccno[u]!=sccno[v]) G[sccno[u]].push_back(sccno[v]); int vis[maxn]; void Dp(int x) if(vis[x])return; vis[x]=1; for(int i=0;i<G[x].size();++i) int v=G[x][i]; Dp(v); lb[x]=min(lb[x],lb[v]); rb[x]=max(rb[x],rb[v]); int main() scanf("%d",&n);totn=n; for(int i=1;i<=n;++i) scanf("%lld%lld",&a[i],&r[i]); BuildTree(1,1,n); for(int i=1;i<=n;++i) tl[i]=lower_bound(a+1,a+1+n,a[i]-r[i])-a; tr[i]=upper_bound(a+1,a+1+n,a[i]+r[i])-a-1; // cout<<tl[i]<<‘ ‘<<tr[i]<<endl; Updatasec(1,tl[i],tr[i],i); Tarjan(); for(int i=1;i<=totn;++i)if(!vis[i])Dp(i); long long ans=0; for(int i=1;i<=n;++i) // cout<<rb[sccno[i]]-lb[sccno[i]]<<endl; ans=(ans+1LL*(1+rb[sccno[i]]-lb[sccno[i]])*i)%mm; printf("%lld\n",ans); return 0;
bzoj5017:[snoi2017]炸弹
Description在一条直线上有N个炸弹,每个炸弹的坐标是Xi,爆炸半径是Ri,当一个炸弹爆炸时,如果另一个炸弹所在位置Xj满足: Xi−Ri≤Xj≤Xi+Ri,那么,该炸弹也会被引爆。 现在,请你帮忙计算一下,先把第i个炸弹引... 查看详情
[bzoj5017][snoi2017]炸弹tarjan缩点+线段树优化建图+拓扑(代码片段)
5017:[Snoi2017]炸弹TimeLimit: 30Sec MemoryLimit: 512MBSubmit: 608 Solved: 190[Submit][Status][Discuss]Description在一条直线上有N个炸弹,每个炸弹的坐标是Xi,爆炸半径是Ri,当一个炸弹爆炸时,如果另一个炸弹 查看详情
p5025[snoi2017]炸弹线段树优化建图+缩点+dag图上dp(代码片段)
...lem/P5025目录题意分析Code题意在一个数轴上有n个点代表n颗炸弹,每颗炸弹引爆会引发r范围内的炸弹爆炸,问每颗炸弹引爆会最终引发多少颗炸弹爆炸,对答案∑i=1ni∗炸弹引爆数量\\sum_i=1^ni*炸弹引爆数量∑i=... 查看详情
bzoj5018[snoi2017]英雄联盟
题解:woc竟然有个小地方没看出错来,WA了半天DP一下注意爆longlong #include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongLint;intn;Lintm;intans=0x7fffffff;L 查看详情
bzoj5015[snoi2017]礼物矩阵乘法
【BZOJ5015】[Snoi2017]礼物Description热情好客的请森林中的朋友们吃饭,他的朋友被编号为1~N,每个到来的朋友都会带给他一些礼物:。其中,第一个朋友会带给他1个,之后,每一个朋友到来以后,都会带给他之前所有人带来的礼... 查看详情
bzoj5018[snoi2017]英雄联盟背包
【BZOJ5018】[Snoi2017]英雄联盟Description正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」。现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个... 查看详情
bzoj_5015_[snoi2017]礼物_矩阵乘法
BZOJ_5015_[Snoi2017]礼物_矩阵乘法Description热情好客的请森林中的朋友们吃饭,他的朋友被编号为1~N,每个到来的朋友都会带给他一些礼物:。其中,第一个朋友会带给他1个,之后,每一个朋友到来以后,都会带给他之前所有人带... 查看详情
bzoj5018:[snoi2017]英雄联盟
10.5重回bzoj。刷了这道背包DP交了10次。不过这个真的是一道好题。(也许是我DP太烂)由于钱数较小,容易想到,f[i]表示花了i元所有的展示策略个数。然而在DP的时候却有一个问题,我们枚举买的皮肤个数维护背包时,有可能同... 查看详情
bzoj5016[snoi2017]一个简单的询问莫队
【BZOJ5016】[Snoi2017]一个简单的询问Description给你一个长度为N的序列ai,1≤i≤N和q组询问,每组询问读入l1,r1,l2,r2,需输出get(l,r,x)表示计算区间[l,r]中,数字x出现了多少次。Input第一行,一个数字N,表示序列长度。第二行,N个数... 查看详情
bzoj5015:[snoi2017]礼物
Description热情好客的请森林中的朋友们吃饭,他的朋友被编号为1~N,每个到来的朋友都会带给他一些礼物:。其中,第一个朋友会带给他1个,之后,每一个朋友到来以后,都会带给他之前所有人带来的礼物个数再加他的编号的K... 查看详情
bzoj5016[snoi2017]一个简单的询问(代码片段)
题面https://www.lydsy.com/JudgeOnline/problem.php?id=5016题解莫队算法因此我们可以用(l,r)表示ask(1,l,1,r)然后就可以了莫队了用num1,num2两个数组记录下当前两个区间中每个数字分别出现多少次Code1#include<bits/stdc++.h>2usingnamespacestd;3typedeflong... 查看详情
bzoj5019:[snoi2017]遗失的答案
Description小皮球在计算出答案之后,买了一堆皮肤,他心里很开心,但是一不小心,就忘记自己买了哪些皮肤了。==|||万幸的是,他还记得他把所有皮肤按照1~N来编号,他买来的那些皮肤的编号(他至少买了一款皮肤),最大公... 查看详情
bzoj5016:[snoi2017]一个简单的询问
Description给你一个长度为N的序列ai,1≤i≤N和q组询问,每组询问读入l1,r1,l2,r2,需输出get(l,r,x)表示计算区间[l,r]中,数字x出现了多少次。Input第一行,一个数字N,表示序列长度。第二行,N个数字,表示a1~aN第三行,一个数字Q,... 查看详情
snoi2017(bzoj5015~5018)泛做(代码片段)
T1:礼物想错方向了,实际上很简单。我想的是:显然题目求的是$\sum_i=1^ni^k2^i$,然后或许可以通过化式子变成与n无关的复杂度?然后就不停往斯特林数反演和下降幂的方向想,最后什么都没想出来。其实想一会就应该意识到:... 查看详情
bzoj5018[snoi2017]英雄联盟背包dp
题目描述正在上大学的小皮球热爱英雄联盟这款游戏,而且打的很菜,被网友们戏称为「小学生」。现在,小皮球终于受不了网友们的嘲讽,决定变强了,他变强的方法就是:买皮肤!小皮球只会玩N个英雄,因此,他也只准备... 查看详情
bzoj5016[snoi2017]一个简单的询问莫队算法
题目描述给你一个长度为N的序列ai,1≤i≤N和q组询问,每组询问读入l1,r1,l2,r2,需输出get(l,r,x)表示计算区间[l,r]中,数字x出现了多少次。输入第一行,一个数字N,表示序列长度。第二行,N个数字,表示a1~aN第三行,一个数字... 查看详情
bzoj5019:[snoi2017]遗失的答案dp+fwt(代码片段)
满足GL的组合一定包含GL每个质因数最大次幂个最小次幂,并且能做限制这些数不会超过600个然后质因数最多8个,所以可以状压f[s1][s2]为选s1集合满足最大限制选s2集合满足最小限制dfs一下预处理出质因数只选一个质因数的初始状... 查看详情
bzoj3590[snoi2013]quare状压dp
【BZOJ3590】[Snoi2013]QuareDescription 4.20四川芦山地震发生后,抗震救灾委员会接到一个紧急任务,四川省给该委员会发了一份地图,这份地图给出了该省一些城市的情况:任两个城市是用一条或多条公路连接起来的,也可以... 查看详情