清北刷题冲刺班p,1归结强化刷题葡京娱乐场官网

一道图论好题(graph)

一道图论好题

(graph)

Time Limit:1000ms   Memory Limit:128MB

 

题材叙述

LYK有一张无向图G={V,E},那张无向图有n个点m条边组成。并且那是一张带权图,不仅有边权还有点权。

LYK给出了一个子图的概念,一张图G’={V’,E’}被称作G的子图,当且仅当

·G’的点集V’包含于G的点集V。

·对于E中的任意三个点a,b∈V’,当(a,b)∈E时,(a,b)一定也属于E’,并且连接那七个点的边的边权是同样的。

LYK给一个子图定义了它的价值,它的市值为:点权之和与边权之和的比。

LYK想找到一个市值最大的非空子图,所以它来找你帮忙啦。

 

输入格式(graph.in)

    第一行多个数n,m表示一张n个点m条边的图。

    第二行n个数ai表示点权。

   
接下去m行每行多少个数u,v,z,表示有一条连接u,v的边权为z的无向边。数据有限协助自由五个点之间最多一条边相连,并且不存在自环。

 

输出格式(graph.out)

你需求输出那些市值最大的非空子图的市值,由于它是一个浮点数,你只要求保留小数点后两位有效数字。

 

输入样例

3 3

2 3 4

1 2 3

1 3 4

2 3 5

 

出口样例

1.67

 

样例解释

慎选1,2三个点,则价值为5/3=1.67。

 

对于20%的数据n=2

对于50%的数据n<=5

对于100%的数据1<=n,m<=100000,1<=ai,z<=1000。

葡京娱乐场官网 1葡京娱乐场官网 2

/*
    最优比率环??根本不会
    经过证明,最终答案是只选择一条边,求一个最大值 
*/
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <complex>
#include <string>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
double ans;
int A,B,C,n,m,a[100005],i;
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; i++) scanf("%d",&a[i]);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&A,&B,&C);
        ans=max(ans,(a[A]+a[B])/(C+0.0));
    }
    printf("%.2f\n",ans);
    return 0;
}

AC代码

 

Time Limit:1000ms   Memory Limit:128MB

拍照

(photo)

Time Limit:1000ms   Memory Limit:128MB

 

题材叙述

    假若那是一个二次元。

LYK召集了n个小伙伴一起来照相。他们分别有谈得来的身高Hi和幅度Wi。

为了放下那个照片并且每个小伙伴都完全的暴露来,必须需求一个小幅为ΣWi,长度为max{Hi}的相框。(因为无法叠罗汉)。

LYK为了省去相框的上空,它有了精粹的idea,让有些人躺着!一个人躺着一定于是身高变成了Wi,宽度变成了Hi。可是洋洋人躺着欠赏心悦目,于是LYK规定最七只有n/2个人躺着。(也就是说当n=3时最三唯有1个人躺着,当n=4时最六唯有2个人躺着)

LYK现在想问您,当其中有的人躺着后,相框的面积最少是不怎么。

 

输入格式(photo.in)

    第一行一个数n。

    接下去n行,每行三个数分别是Wi,Hi。

 

出口格式(photo.out)

你要求输出那个相框的面积最少是有些。

 

输入样例

3

3 1

2 2

4 3

 

输出样例

21

 

样例解释

若果没人躺过来,需求27的面积。

俺们只要让第1个人躺过来,就只需求21的面积!

 

对于30%的数据n<=10。

对于60%的数据n<=1000,Wi,Hi<=10。

对于100%的数据1<=n,Wi,Hi<=1000。

葡京娱乐场官网 3葡京娱乐场官网 4

/*
    贪心
    枚举最终状态最高身高为x
    分三种情况
    1.身高>x,宽度<=x,一定躺 
    2.身高<=x,宽度>x,一定不躺
    3.身高,宽度<=x
        1)身高>宽度 不能躺 
        2)身高<=宽度 只能让部分人躺,(宽度-身高)越大,越要躺 
*/
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
using namespace std;
set<int> ::iterator sit;
int ans,sum,p[1005],i,a[1005],b[1005],cnt,CNT,j,ANS,n;
int cmp(int i,int j) {return i>j;}
bool FLAG;
int main()
{
    freopen("photo.in","r",stdin);
    freopen("photo.out","w",stdout);
    ANS=1000000000;
    scanf("%d",&n);
    for (i=1; i<=n; i++)
      scanf("%d%d",&a[i],&b[i]);
    for (i=1; i<=1000; i++)
    {
        sum=0; FLAG=true; cnt=0; CNT=0;
        for (j=1; j<=n; j++)
          if (b[j]<=i && (a[j]<=b[j] || a[j]>i)) sum+=a[j]; else
            if (a[j]>i && b[j]>i) {FLAG=false; break;} else
              if (b[j]>i) {cnt++; sum+=b[j];} else
              {
                  p[++CNT]=a[j]-b[j];
                  sum+=a[j];
              }
        if (!FLAG) continue;
        if (cnt>n/2) continue;
        sort(p+1,p+CNT+1,cmp);
        for (j=1; j<=min(n/2-cnt,CNT); j++) sum-=p[j];
        ANS=min(ANS,sum*i);
    }
    cout<<ANS;
    return 0;
}

AC代码 贪心

 

 

或和异或

(xor)

Time Limit:2000ms   Memory Limit:128MB

 

难题叙述

LYK近期在研讨位运算,它研商的机要有多个:or和xor。(C语言中对于|和^)

为了更好的刺探那三个运算符,LYK找来了一个2^n长度的数组。它首先次先对富有相邻三个数执行or操作,获得一个2^(n-1)长度的数组。也就是说,假设一开始时a[1],a[2],…,a[2^n],执行完第一回操作后,会赢得a[1]
or a[2],a[3] or a[4] ,…, a[(2^n)-1] or a[2^n]。

其次次操作,LYK会将享有相邻四个数执行xor操作,获得一个2^(n-2)长度的数组,假使第三次操作后的数组是b[1],b[2],…,b[2^(n-1)],那么执行完本次操作后会变成b[1]
xor b[2], b[3] xor b[4] ,…, b[(2^(n-1))-1] xor b[2^(n-1)]。

其两遍操作,LYK依旧将实施or操作,第三遍LYK执行xor操作。如此交替举办。

最终那2^n个数一定会化为1个数。LYK想了然最终那个数是有些。

为了让这一个游乐更好玩,LYK还会执行Q次修改操作。每趟修改原先的2^n长度的数组中的某一个数,对于每一次修改操作,你必要输出n次操作后(最终一定只剩余唯一一个数)剩下的百般数是稍微。

 

输入格式(xor.in)

    第一行多少个数n,Q。

接下去一行2^n个数ai表示一开头的数组。

接下去Q行,每行八个数xi,yi,表示LYK本次的改动操作是将a{xi}改成yi。

 

出口格式(xor.out)

Q行,表示每一次修改操作后执行n次操作后剩下的这些数的值。

 

输入样例

2 4

1 6 3 5

1 4

3 4

1 2

1 2

 

出口样例

1

3

3

3

 

样例解释

率先次修改,{4,6,3,5}->{6,7}->{1}

其次次修改,{4,6,4,5}->{6,5}->{3}

其一遍修改,{2,6,4,5}->{6,5}->{3}

第四次修改,{2,6,4,5}->{6,5}->{3}

对于30%的数据n<=17,Q=1。

对于其它20%的数额n<=10,Q<=1000。

对此再其余30%的数据n<=12,Q<=100000。

对于100%的数据1<=n<=17,1<=Q<=10^5,1<=xi<=2^n,0<=yi<2^30,0<=ai<2^30。

葡京娱乐场官网 5葡京娱乐场官网 6

/*
    倍增表
    st[j][i]表示i次操作后,j位置的数字是什么 
*/
#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
long long st[131073][18];
int next[18][131073],i,j,n,m,now,k,A,B;
int main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=(1<<n); i++) cin>>st[i][0];
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=(1<<n); j+=(1<<i))
        {
            if (i % 2==1) st[j][i]=st[j][i-1]|st[j+(1<<(i-1))][i-1]; else
              st[j][i]=st[j][i-1]^st[j+(1<<(i-1))][i-1];
        }
    }
    for (i=1; i<=n; i++)
      for (j=1; j<=(1<<n); j+=(1<<i))
      {
          for (k=j; k<=j+(1<<i)-1; k++)
            next[i][k]=j;
      }
    for (i=1; i<=m; i++)
    {
        scanf("%d%d",&A,&B);
        st[A][0]=B;
        for (j=1; j<=n; j++)
        {
            now=next[j][A];
            if (j % 2==1) st[now][j]=st[now][j-1]|st[now+(1<<(j-1))][j-1]; else
                st[now][j]=(st[now][j-1]^st[now+(1<<(j-1))][j-1]);
        }
        cout<<st[1][n]<<endl;
    }
    return 0;
}

AC代码 倍增表

 

难题叙述

LYK有一张无向图G={V,E},那张无向图有n个点m条边组成。并且那是一张带权图,不仅有边权还有点权。

LYK给出了一个子图的定义,一张图G’={V’,E’}被称作G的子图,当且仅当

·G’的点集V’包含于G的点集V。

·对于E中的任意八个点a,b∈V’,当(a,b)∈E时,(a,b)一定也属于E’,并且总是那四个点的边的边权是同等的。

LYK给一个子图定义了它的市值,它的价值为:点权之和与边权之和的比。 看

LYK想找到一个市值最大的非空子图,所以它来找你辅助啦。

 

输入格式(graph.in)

第一行多个数n,m表示一张n个点m条边的图。

其次行n个数ai表示点权。

接下去m行每行五个数u,v,z,表示有一条连接u,v的边权为z的无向边。数据保险自由几个点时期最多一条边相连,并且不设有自环。

 

出口格式(graph.out)

你需求输出那些市值最大的非空子图的市值,由于它是一个浮点数,你只要求保留小数点后两位有效数字。

 

输入样例

3 3

2 3 4

1 2 3

1 3 4

2 3 5

 

输出样例

1.67

 

样例解释

慎选1,2七个点,则价值为5/3=1.67。

 

对于20%的数据n=2

对于50%的数据n<=5

对于100%的数据1<=n,m<=100000,1<=ai,z<=1000。

 

70分做法:
 那些题老师似乎讲过,老师马上说这几个题是一个脑筋急转弯的题,最优的情景自然为多少个点+一条边,正确性注明??

咱俩选3个点的标准一定是边缘那五个点的点权一定比中间那些点的点权大,不然选他干嘛、、这样的话我们设a>c>b,然后大家来看我们剩下的是要相比(a+b)*B
 
,c*A或者是(b+c)*A,a*B的大小,如果(b+c)*A<a*B,那么c*A一定小于a*B,一定也低于(a+b)*B,即c*A<(a+b)*B,也就是说即便(a+b+c)/A+B>(b+c)/B,大家也足以推出(a+b+c)/A+B<(a+b)/A,反之同理,也就是说无论我们让他们的和超出其中的一个,也必将能推出来她小于另一个,也就是说含有多少个点的自然比含有多少个点比值小,即最有动静自然是八个点+一条边。

啊啊啊,ans<(double)(q/z)那个样子比较大小会wa多个点,改成那样ans<(q*1.0/z)就足以博得90分、、

葡京娱乐场官网 7葡京娱乐场官网 8

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
using namespace std;
double ans;
int n,m,x,y,z,q,v[N];
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 main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        q=v[x]+v[y];
        if(ans<(double)(q/z)) ans=(double)q/z;
    }
    printf("%.2lf",ans);
}

70分,一个点TLE,wa两个点

葡京娱乐场官网 9葡京娱乐场官网 10

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
using namespace std;
double ans;
int n,m,x,y,z,q,v[N];
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 main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        q=v[x]+v[y];
        if(ans<(q*1.0/z)) ans=q*1.0/z;
    }
    printf("%.2lf",ans);
}

AC代码

 

 

 

 

拍照(photo)

Time Limit:1000ms   Memory Limit:128MB

 

难点叙述

要是那是一个二次元。

LYK召集了n个小伙伴一起来拍照。他们各自有谈得来的身高Hi和幅度Wi。

为了放下那么些照片并且每个小伙伴都完全的揭破来,必须须要一个升幅为ΣWi,长度为max{Hi}的相框。(因为不可以叠罗汉)。

LYK为了省去相框的空间,它有了可以的idea,让有些人躺着!一个人躺着相当于是身高变成了Wi,宽度变成了Hi。可是洋洋人躺着糟糕看,于是LYK规定最几唯有n/2个人躺着。(也就是说当n=3时最多唯有1个人躺着,当n=4时最四唯有2个人躺着)

LYK现在想问您,当其中有些人躺着后,相框的面积最少是稍稍。

 

输入格式(photo.in)

首先行一个数n。

    接下去n行,每行几个数分别是Wi,Hi。

 

出口格式(photo.out)

你必要输出那一个相框的面积至少是有点。

 

输入样例

3

3 1

2 2

4 3

 

输出样例

27

 

样例解释

即使没人躺过来,要求27的面积。

咱俩只要让第1个人躺过来,就只要求21的面积!

 

对于30%的数据n<=10。

对于60%的数据n<=1000,Wi,Hi<=10。

对于100%的数据1<=n,Wi,Hi<=1000。

 

 n^2枚举,本以为会TLE的、、、

现将每一组数按高度排序,然后大家枚举大家当下相框的莫大,然后看看我们是n/2个人躺下之后是还是不是会满意条件,倘诺满足条件更新ans,否则继续枚举,大家对此h<w&&w<当前大家枚举的h的处境,并且大家还有让这厮躺下的时机,大家让此人躺下。借使此人的身高超越大家枚举得h的话,大家一贯让这厮躺下,然后在计算w判断是还是不是足以革新答案。

葡京娱乐场官网 11葡京娱乐场官网 12

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1010
#define LL long long
using namespace std;
LL ans;
bool flag;
int n,s,h,w,sum,b[N];
struct Node
{
    int w,h;
}a[N];
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 cmp(Node a,Node b){return a.h<b.h;}
int main()
{
    freopen("photo.in","r",stdin);
    freopen("photo.out","w",stdout);
    n=read();s=n/2;
    for(int i=1;i<=n;i++) 
    {
        a[i].w=read(),a[i].h=read();
        for(int j=1;j<i;j++)
         if(a[i].h>a[j].h) b[a[j].h]++;
    }
    ans=0x7fffffff;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        h=a[i].h;
        flag=false,w=0;sum=b[h];
        if(sum>s) continue;
        for(int j=1;j<=n;j++)
        {
            if(a[j].h<=h) 
            {
                if(a[j].w>a[j].h&&a[j].w<=h&&sum<s) w+=a[j].h,sum++;
                else w+=a[j].w;
            }
            else 
            {
                if(a[j].w<=h) w+=a[j].h;
                else {flag=true;break;}
            }
        }
        if(!flag) ans=min(ans,(LL)h*w);
    }
    printf("%lld",ans);
    return 0;
}

90分代码,wa一个点

 一直以为要按中度排序,结果wa掉一个点,将排序方法改成按低度与幅度的差值就能够A掉了,正确性表明??

 (对于一个莫大满意的人,你要认清是是还是不是撂倒他必然首先落魄能使照片尽量小的人,也就是说你要保管落魄他后,他本来的宽在限制内,且她倒后,暴发的熏陶就是改变的宽的和,尽量使和小所以你要求给中度和跨度差排序)

葡京娱乐场官网 13葡京娱乐场官网 14

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1010
#define LL long long
using namespace std;
LL ans;
bool flag;
int n,s,h,w,sum,b[N],maxn;
struct Node
{
    int w,h;
}a[N];
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 cmp(Node a,Node b){return a.w-a.h>b.w-b.h;}
int main()
{
    freopen("photo.in","r",stdin);
    freopen("photo.out","w",stdout);
    n=read();s=n/2;
    for(int i=1;i<=n;i++) 
    {
        a[i].w=read(),a[i].h=read(),maxn=max(maxn,max(a[i].w,a[i].h));
        for(int j=1;j<i;j++)
         if(a[i].h>a[j].h) b[a[j].h]++;
    }
    ans=0x7fffffff;
    sort(a+1,a+1+n,cmp);
    for(int h=1;h<=maxn;h++)
    {
        flag=false,w=0;sum=b[h];
        if(sum>s) continue;
        for(int j=1;j<=n;j++)
        {
            if(a[j].h<=h) 
            {
                if(a[j].w>a[j].h&&a[j].w<=h&&sum<s) w+=a[j].h,sum++;
                else w+=a[j].w;
            }
            else 
            {
                if(a[j].w<=h) w+=a[j].h;
                else {flag=true;break;}
            }
        }
        if(!flag) ans=min(ans,(LL)h*w);
    }
    printf("%lld",ans);
    return 0;
}

AC代码

 

 

或和异或(xor)

Time Limit:2000ms   Memory Limit:128MB

 

难题叙述

LYK方今在商量位运算,它研讨的严重性有两个:or和xor。(C语言中对于|和^)

为了更好的打听那多少个运算符,LYK找来了一个2^n长度的数组。它首先次先对具有相邻多个数执行or操作,获得一个2^(n-1)长度的数组。也就是说,假设一开始时a[1],a[2],…,a[2^n],执行完第四遍操作后,会获取a[1] or
a[2],a[3] or a[4] ,…, a[(2^n)-1] or a[2^n]。

其次次操作,LYK会将装有相邻多个数执行xor操作,获得一个2^(n-2)长度的数组,要是第两回操作后的数组是b[1],b[2],…,b[2^(n-1)],那么执行完这一次操作后会变成b[1] xor
b[2], b[3] xor b[4] ,…, b[(2^(n-1))-1] xor b[2^(n-1)]。

其一遍操作,LYK如故将实施or操作,第四遍LYK执行xor操作。如此交替进行。

最后这2^n个数一定会化为1个数。LYK想清楚最终那几个数是稍微。

为了让这些游乐更好玩,LYK还会履行Q次修改操作。每回修改原先的2^n长度的数组中的某一个数,对于每一回修改操作,你须要输出n次操作后(最终必将只剩余唯一一个数)剩下的相当数是有些。

 

输入格式(xor.in)

首先行八个数n,Q。

接下去一行2^n个数ai表示一初始的数组。

接下去Q行,每行四个数xi,yi,表示LYK这一次的改动操作是将a{xi}改成yi。

 

出口格式(xor.out)

Q行,表示每回修改操作后举办n次操作后剩余的百般数的值。

 

输入样例

2 4

1 6 3 5

1 4

3 4

1 2

1 2

 

出口样例

1

3

3

3

 

样例解释

第三次修改,{4,6,3,5}->{6,7}->{1}

第二次修改,{4,6,4,5}->{6,5}->{3}

其三遍修改,{2,6,4,5}->{6,5}->{3}

第五次修改,{2,6,4,5}->{6,5}->{3}

对于30%的数据n<=17,Q=1。

对于其它20%的数据n<=10,Q<=1000。

对此再别的30%的数码n<=12,Q<=100000。

对于100%的数据1<=n<=17,1<=Q<=10^5,1<=xi<=2^n,0<=yi<2^30,0<=ai<2^30。

 

哈哈哈,打了个我觉着一定全体TLE的顺序,结果仍然得了50分(准是看本姑娘太可爱了、、)

暴力做法:枚举每次修改,大家强力举行操作,我们判断那是拓展到第五次操作,然后大家开展分拣商讨,要是操作数是奇数的话大家将原数组进行|操作,即使数偶数的话大家开展^操作,对于每三遍操作,我们强力将数组内的每五个数里面展开操作,然后将我们处理出来的数存入一个sum数组里,然后在复制到原来的b数组里。然后再度举办如此的操作,直到大家的数组里只剩余一个数,截止操作

葡京娱乐场官网 15葡京娱乐场官网 16

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 150000
using namespace std;
int n,q,s,c,x,y,cnt,a[N],b[N],sum[N];
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 main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    n=read(),q=read();
    for(int i=1;i<=pow(2,n);i++)
     a[i]=read();
    while(q--)
    {
        cnt=pow(2,n);
        x=read(),y=read(),a[x]=y;
        for(int i=1;i<=cnt;i++) b[i]=a[i];
        while(cnt!=1)
        {
            s++;c=cnt,cnt=0;
            if(s%2==0)
            {
                for(int i=1;i<=c;i+=2)
                 sum[++cnt]=b[i]^b[i+1];
                for(int i=1;i<=cnt;i++)
                 b[i]=sum[i];
            }
            else
            {
                for(int i=1;i<=c;i+=2)
                 sum[++cnt]=b[i]|b[i+1];
                for(int i=1;i<=cnt;i++)
                 b[i]=sum[i];
            }
            if(cnt==1) printf("%d\n",sum[cnt]);
        }
    }
    return 0;
}

50分的武力

 

据说那道题线段树可以做,在前行跟新四伯的时候用|或者^,据说std用的倍增

观看q个询问,每一次修改一个值我们就应该力所能及想到用线段树,并且我们驾驭最终全体统一成一个数的时候即为大家的线条树合并成一个的时候,那么这样的话用线段树就明摆着了(然则蒟蒻表示并没看出来、、),可是大家要怎么用线段树啊??

俺们要求记录当前咱们遍地的层数,大家领会当操作为奇数的话我们举办|操作,也就是大家在创新二伯的时候要求将它的子节点的值|一下,同理若是为偶数的话大家举办^操作

葡京娱乐场官网 17葡京娱乐场官网 18

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 150000
using namespace std;
int n,q,x,y;
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;
}
struct Tree
{
    int l,r,v,f;
}tree[N*4];
void build(int k,int l,int r,int dep)
{
    tree[k].l=l,tree[k].r=r;
    if(l==r)
    {
        tree[k].v=read();
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid,dep+1);
    build(k<<1|1,mid+1,r,dep+1);
    if((n-dep+1)&1) tree[k].v=tree[k<<1].v|tree[k<<1|1].v;
    else tree[k].v=tree[k<<1].v^tree[k<<1|1].v;
}
void change(int k,int dep)
{
    if(tree[k].l==tree[k].r) 
    {
        tree[k].v=y;
        return ;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(x<=mid) change(k<<1,dep+1);
    else change(k<<1|1,dep+1);
    if((n-dep+1)&1) tree[k].v=tree[k<<1].v|tree[k<<1|1].v;
    else tree[k].v=tree[k<<1].v^tree[k<<1|1].v;
}
int main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    n=read(),q=read();
    build(1,1,1<<n,1);
    while(q--)
    {
        x=read(),y=read();
        change(1,1);
        printf("%d\n",tree[1].v);
    }
    return 0;
}

AC代码

 

 

 

                葡京娱乐场官网 19

 

                      距 NOIp2017 还剩 30 天

                               
你可以做的事情还有这么些,纵然到结尾一秒也休想放任,因为不到甘休的那一刻哪个人也不明了结果会怎么样。