暑假训练(UVALive 5789-5799)(线段树+并查集+dp+桥)

By | 09月30日
Advertisement

A :http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83308#problem/A
题意:将区间(l,r)的人杀掉,并且输出左边和右边第一个没死的人
思路:线段树,或者并查集

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
const int maxm=1010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int N,M;
struct IntervalTree{
    int setv[maxn<<2];
    int sum[maxn<<2];
    void build(int o,int l,int r){
        setv[o]=0;
        if(l==r){
            sum[o]=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);

        pushup(o);
    }
    void pushup(int o){
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
    void update(int o,int l,int r,int q1,int q2){
        if(q1<=l&&r<=q2){
            setv[o]=1;
            sum[o]=0;
            return ;
        }
        pushdown(o);
        int mid=(l+r)>>1;
        if(q1<=mid)update(o<<1,l,mid,q1,q2);
        if(q2>mid)update(o<<1|1,mid+1,r,q1,q2);
        pushup(o);
    }
    void pushdown(int o){
        if(setv[o]){
            setv[o<<1]=setv[o<<1|1]=setv[o];
            sum[o<<1]=sum[o<<1|1]=0;
            setv[o]=0;
        }
    }
    int getsum(int o,int l,int r,int q1,int  q2){
        if(q1<=l&&r<=q2){
            return sum[o];
        }
        pushdown(o);
        int mid=(l+r)>>1;
        int ans=0;
        if(q1<=mid)ans+=getsum(o<<1,l,mid,q1,q2);
        if(q2>mid)ans+=getsum(o<<1|1,mid+1,r,q1,q2);
        return ans;
    }
    int getL(int o,int l,int r,int x){
        if(l==r){
            return l;
        }
        int mid=(l+r)>>1;
        if(sum[o<<1]>=x){
            return getL(o<<1,l,mid,x);
        }
        return getL(o<<1|1,mid+1,r,x-sum[o<<1]);
    }
    int getR(int o,int l,int r,int x){
        if(l==r)return l;
        int mid=(l+r)>>1;
        if(sum[o<<1|1]>=x){
            return getR(o<<1|1,mid+1,r,x);
        }
        return getR(o<<1,l,mid,x-sum[o<<1|1]);
    }
}tree;
int main(){

    int l,r;
    while(scanf("%d%d",&N,&M)!=EOF,N+M){
        tree.build(1,1,N);

        int ans1,ans2,sum1,sum2,sum3;
        while(M--){
            scanf("%d%d",&l,&r);
            tree.update(1,1,N,l,r);
            if(l==1){
                ans1=-1;
            } else {
                sum1=tree.getsum(1,1,N,1,l-1);
                if(sum1<=0)ans1=-1;
                else ans1=tree.getL(1,1,N,sum1);
            }
            if(r==N){
                ans2=-1;
            } else {
                sum2=tree.getsum(1,1,N,r+1,N);
                if(sum2<=0)ans2=-1;
                else ans2=tree.getR(1,1,N,sum2);
            }
            if(ans1==-1)printf("* ");
            else printf("%d ",ans1);
            if(ans2==-1)printf("*\n");
            else printf("%d\n",ans2);

        }
        printf("-\n");
    }
    return 0;
}

H: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83308#problem/H
题意:给出一个图,然后是一些查询,每次输出uv之间是否存在唯一的一条路,这条路经过的点是唯一的
思路:因为路唯一,并且点不重复,也就是两个点之间的边都是桥,那么本题的解法也就是找出所有的桥,然后根据桥建图,判断两个点是不是可达就行了,这里可达也就是在一个联通集合中,所以可以用并查集维护

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=10010;
const int maxm=100010;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int R,C,Q;

int low[maxn],dfn[maxn],dfs_clock;
struct Edge{
    int from,to,id;
    Edge(int f=0,int t=0,int _id=0):from(f),to(t),id(_id){}
};
vector<Edge> g[maxn],G[maxn];
int pre[maxn];
int find(int x){
    if(x==pre[x])return x;
    return pre[x]=find(pre[x]);
}
int tarjan(int u,int fa){
    int lowu=dfn[u]=++dfs_clock;
    int child=0;
    int len=g[u].size();
    for(int i=0;i<len;i++){
        Edge e=g[u][i];
        int v=e.to;
        if(!dfn[v]){
            child++;
            int lowv=tarjan(v,u);
            lowu=min(lowv,lowu);
            if(lowv>dfn[u]){
                 pre[find(e.from)]=e.to;
             }
        }
        else if(dfn[v]<dfn[u]&&v!=fa)
            lowu=min(lowu,dfn[v]);
    }
    low[u]=lowu;
    return lowu;
}
bool vis[maxn];
bool dfs(int u,int d,int fa){
    if(vis[u])return false;
    if(u==d)return true;
    vis[u]=1;
    int len=G[u].size();
    for(int i=0;i<len;i++){
        int v=G[u][i].to;
        if(v==fa)continue;
        if(dfs(v,d,u))return true;
    }
    return false;
}
int main(){
    int u,v;
    while(scanf("%d%d%d",&R,&C,&Q)!=EOF,R+C+Q){
        for(int i=0;i<=R;i++){
            g[i].clear();
            G[i].clear();
            pre[i]=i;
            dfn[i]=0;
        }
        dfs_clock=0;
        for(int i=1;i<=C;i++){
            scanf("%d%d",&u,&v);
            g[u].push_back(Edge(u,v,i));
            g[v].push_back(Edge(v,u,i));
        }
        for(int i=1;i<=R;i++){
            if(!dfn[i])tarjan(i,-1);
        }
        while(Q--){
            scanf("%d%d",&u,&v);

            if(find(u)==find(v)){
                printf("Y\n");
            } else {
                printf("N\n");
            }

        }
        printf("-\n");
    }
    return 0;
}

J:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83308#problem/J

题意:给出一个hash函数,有两种操作,将位置i上的数变成x,输出区间的hash值
思路:树状数组维护一个所有数的hash,也就是Bi∗fj,那么区间查询的时候,直接减去之后,除以一个多出来的B的次方就可以了

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long LL;

const int MAXN=100010;
const int INF=0x3f3f3f3f;
const LL MOD=3221225473LL;

int B,P,L,N;
LL p[MAXN],c[MAXN];
int s[MAXN];

int lowbit(int x){
    return x&(-x);
}

LL sum(int x){
    LL ret=0;
    while(x>0){
        ret=(ret+c[x])%P;
        x-=lowbit(x);
    }
    return ret;
}

void add(int x,LL v){
    while(x<=L){
        c[x]=(c[x]+v)%P;
        x+=lowbit(x);
    }
}

LL bigpow(LL x,LL n,LL MOD){
    LL ret=1,t=x%MOD;
    while(n){
        if(n&1) ret=ret*t%MOD;
        t=t*t%MOD;
        n>>=1;
    }
    return ret;
}

int main(){
    while(scanf("%d%d%d%d",&B,&P,&L,&N)!=EOF&&(B||P||L||N)){
        p[0]=1;
        for(int i=1;i<=L;i++) p[i]=p[i-1]*B%P;
        memset(c,0,sizeof(c));
        memset(s,0,sizeof(s));
        int a,b;
        char str[10];
        while(N--){
            scanf("%s%d%d",str,&a,&b);
            if(str[0]=='E'){
                a=L-a+1;
                add(a,((b-s[a])*p[a-1]%P+P)%P);
                s[a]=b;
            }
            else if(str[0]=='H'){
                a=L-a+1;
                b=L-b+1;
                LL ans=(sum(a)-sum(b-1)+P)%P*bigpow(p[b-1],P-2,P)%P;
                printf("%lld\n",ans);
            }
        }
        printf("-\n");
    }
    return 0;
}

Similar Posts:

  • UVALive 4730 Kingdom 线段树+并查集

    题目链接:点击打开链接 题意见白书P248 思路: 先把读入的y值都扩大2倍变成整数 然后离散化一下 用线段树来维护y轴 区间上每个点的 城市数量和联通块数量, 然后用并查集维护每个联通块及联通块的最大最小y值,还要加并查集的秩来记录每个联通块的点数 然后就是模拟搞.. T^T绝杀失败题..似乎数组开小了一点就过了,== #include<stdio.h> #include<math.h> #include<vector> #include<string.h>

  • sicily 1876. Basic Graph Problem 线段树+并查集+路径压缩

    线段树或者RMQ都可以做,虽然是不是动态变化的,但是用线段树做也不错,,而且最近才开始弄线段树,当练练手... 一定要路径压缩的并查集,,不然线性的话,耗时过高... 而且不能写递归的路径压缩,我猜得... 因为n<=100000,一般20000就会栈爆的,,,, #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n; int w[100100]; stru

  • Help with Intervals 线段树并查集

    Time Limit: 6000MS Memory Limit: 131072K Total Submissions: 9784 Accepted: 2320 Case Time Limit: 2000MS Description LogLoader, Inc. is a company specialized in providing products for analyzing logs. While Ikki is working on graduation design, he is a

  • HDU 1512 Monkey King 左偏树 + 并查集

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1512 题意:有n个猴子,一开始每个猴子只认识自己.每个猴子有一个力量值,力量值越大表示这个猴子打架越厉害.然后给出两个数字,代表两只猴子有矛盾要决斗,如果2个猴子不认识,他们就会找他们认识的猴子中力量最大的出来单挑,单挑不论输赢,单挑的2个猴子力量值减半,这2拨猴子就都认识了.现在给m组询问,如果2只猴子相互认识,输出-1,否则他们各自找自己认识的最牛叉的猴子单挑,求挑完后这拨猴子力量最大值. 思路:学

  • 线段树题目合集

    下面题目基本有2份代码,一份是比较入门的结构体写法,一份是我现在的写法 单点更新 HDU 2795 Billboard tree[u].n表示第u棵树可用长度,初始化全为最大长度,要更新时就减去要贴上的海报长度,tree[u].l 和 .r为区间,但实际只用到最底层 叶子结点 即 l == r 的结点,那些父结点只起导向作用,所以把父节点更新为左右孩子n的最大.从根起找长度足够的结点.而答案就是tree[u].l或者tree[u].r. h再大,最多也只需要n行就可以贴上(贴的长度大于墙长度除外

  • HDU ACM 1512 Monkey King-&amp;gt;左偏树+并查集

    题意:一开始有N只猴子,,每只都有一个力量值.,并且互不认识,后来 它们之间发生了M次斗争. 每次两次两只猴子a,b斗争是, a和 b都会从他们自己的朋友圈里拉出一个最强的朋友, 之后最强的这两只猴子打, 打完后两只猴子的力量值分别减半..并且 两只猴子的朋友圈的所有人都互相认识(也就是以后不会再打了).问题是对于每次斗争, 若a,b是朋友, 那么输出-1, 否则输出斗争后它们的朋友圈里最强猴子的力量值. 分析:要表示集合的合并查找操作就是并查集最好了:要维护每次的最大值,就可以使用大顶堆,但还

  • POJ 2513 Colored Sticks(欧拉回路+字典树+并查集)

    题意: 给你很多对单词,单词相当于一个点,一对单词相当于一条边,问这么多对的单词能否组成一条欧拉路,要求每条边都要经过. 解析: 题目数据很大,每个单词最多10个字母,据说用map映射会TLE. 所有要改用字典树进行hash. 判断欧拉路径或者回路需要满足两个条件. 图上所有点联通 度数为奇数个的节点只有0个或者2个. 具体做法: 判断连通性就用并查集,判断是否只有1个根节点. 再判断最后奇度节点是否只有0个或者2个. 唯有满足以上两个条件,才能构成欧拉回路,或者欧拉路径. my code #i

  • NYOJ230 彩色棒(欧拉道路+字典树+并查集)

    题目连接:http://acm.nyist.net/JudgeOnline/problem.php?pid=230 大意:给出n个两端染色棍,端点颜色相同的棍可以拼接起来, 给你n个棍, 问能否拼接成一个棍, 可以输出"Possible" 否则输出"Impossible". PS: n为零,输出"Possible"; 读懂题意后就知道是欧拉道路题了, 用欧拉道路的定理有个前提是使这些棍都要能相连接,但是题没说满足条件,所以我们要判断是否都能连接,

  • hdu 1558 线段相交+并查集

    题意:要求相交的线段都要塞进同一个集合里 sol:并查集+判断线段相交即可.n很小所以n^2就可以水过 1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 7 int f[1010]; 8 char ch; 9 int tmp,n; 10 double X1,X2,Y1,Y2; 11 12 #def

  • hdu 3172 字典树+并查集

    题意: 用map+并查集在hdu提交过了,但是在web diy上TLE了... 果断有写了一个字典树 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<set> using namespace std; const int maxn=22;

Tags: