牛客小白月賽9 A、B、C、D、E、H

傳送門

被砸到的機率 = 1 - 不被砸到的機率

而不被砸到的機率很容易計算。

代碼：

#include<cstdio>
using namespace std;
 
typedef long long ll;
const ll mod=1e9+7;
const int maxn=100000+100;
 
ll mypow(ll a,ll b){
    ll sum=1;
    while(b){
        if(b&1) sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
 
ll fz[maxn],fm[maxn];
 
int main(){
    int n;
    scanf("%d",&n);
    ll ans=1;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&fz[i],&fm[i]);
        ll tmp=mypow(fm[i],mod-2);
        ans=(ans*(fm[i]-fz[i])%mod*tmp)%mod;
    }
    printf("%lld\n",(1-ans+mod)%mod);
}

代碼：

#include<cstdio>
using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        long long n;
        scanf("%lld",&n);
        if(n<=2) printf("1\n");
        else printf("0\n");
    }
}

線段樹很容易做出來。

代碼：

#include<cstdio>
using namespace std;

typedef long long ll;
const int maxn=100000+100;

struct Tree{
  ll val;
  int Xor;
  int num;
  int bit[20];
}tree[maxn<<2];

int val[maxn];

void build(int rt,int l,int r){
  if(l==r){
      for(int i=0;i<20;i++) if((val[l]>>i)&1) tree[rt].bit[i]=1;
      tree[rt].val=val[l];
      tree[rt].num=1;
      tree[rt].Xor=0;
    return ;
  }
  int mid=(l+r)>>1;
  build(rt<<1,l,mid);
  build(rt<<1|1,mid+1,r);
  for(int i=0;i<20;i++) tree[rt].bit[i]=(tree[rt<<1].bit[i]+tree[rt<<1|1].bit[i]);
  tree[rt].num=(r-l+1);
  tree[rt].Xor=0;
  tree[rt].val=(tree[rt<<1].val+tree[rt<<1|1].val);
}

void updateDown(int rt,int l,int r,int mid){
  int Xor=tree[rt].Xor;
  tree[rt<<1].Xor^=Xor;
  tree[rt<<1|1].Xor^=Xor;
  for(int i=0;i<20;i++){
    if((Xor>>i)&1){
      tree[rt<<1].bit[i]=tree[rt<<1].num-tree[rt<<1].bit[i];
      tree[rt<<1|1].bit[i]=tree[rt<<1|1].num-tree[rt<<1|1].bit[i];
    }
  }
  if(l==mid) tree[rt<<1].val^=Xor;
  else{
    tree[rt<<1].val=0;
    for(int i=0;i<20;i++)  tree[rt<<1].val+=((1LL*tree[rt<<1].bit[i])<<i); 
  }
  if(mid+1==r) tree[rt<<1|1].val^=Xor;
  else{
    tree[rt<<1|1].val=0;
    for(int i=0;i<20;i++)  tree[rt<<1|1].val+=((1LL*tree[rt<<1|1].bit[i])<<i);
  }
  tree[rt].Xor=0;
}

void update(int rt,int l,int r,int L,int R,int Xor){
  if(L<=l && R>=r){
    tree[rt].Xor^=Xor;
    for(int i=0;i<20;i++){
      if((Xor>>i)&1){
        tree[rt].bit[i]=tree[rt].num-tree[rt].bit[i];
      }
    }
    tree[rt].val=0;
    for(int i=0;i<20;i++) tree[rt].val+=((1LL*tree[rt].bit[i])<<i);
    return ;
  }
  int mid=(l+r)>>1;
  if(tree[rt].Xor) updateDown(rt,l,r,mid);
  if(L<=mid) update(rt<<1,l,mid,L,R,Xor);
  if(R>mid) update(rt<<1|1,mid+1,r,L,R,Xor);
  for(int i=0;i<20;i++) tree[rt].bit[i]=(tree[rt<<1].bit[i]+tree[rt<<1|1].bit[i]);
  tree[rt].val=(tree[rt<<1].val+tree[rt<<1|1].val);
}

ll query(int rt,int l,int r,int L,int R){
  if(L>r || R<l) return 0;
  if(L<=l && R>=r) return tree[rt].val;
  int mid=(l+r)>>1;
  if(tree[rt].Xor) updateDown(rt,l,r,mid);
  return query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R);
}

int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&val[i]);
  build(1,1,n);
  for(int i=1;i<=m;i++){
    int type,l,r,k;
    scanf("%d",&type);
    if(type==1){
      scanf("%d%d",&l,&r);
      printf("%lld\n",query(1,1,n,l,r));
    }
    else{
      scanf("%d%d%d",&l,&r,&k);
      if(k) update(1,1,n,l,r,k);
    }
  }
}

由于都是在某一棵子樹上操作，是以并不一定需要使用樹鍊剖分，隻要根據樹鍊剖分的思想進行重編号，記錄每棵子樹的編号範圍即可，再用線段樹維護。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn=100000+100;
const int mod=23333;

struct Tree{
  ll add;
  ll two;
  ll mul;
}tree[maxn<<2];
int id[maxn],maxid[maxn],rev[maxn],id_cnt;
bool vis[maxn];

struct Edge{
  int to,next;
}edge[maxn<<1];
int head[maxn],tot;

int val[maxn];

void init(){
  memset(head,-1,sizeof(head));
  memset(vis,false,sizeof(vis));
  tot=id_cnt=0;
}

void addEdge(int u,int v){
  edge[tot].to=v;
  edge[tot].next=head[u];
  head[u]=tot++;
  edge[tot].to=u;
  edge[tot].next=head[v];
  head[v]=tot++;
}

void dfs(int u){
  vis[u]=true;
  id[u]=maxid[u]=(++id_cnt);
  rev[id_cnt]=u;
  for(int i=head[u];i!=-1;i=edge[i].next){
    Edge e=edge[i];
    if(!vis[e.to]){
      dfs(e.to);
      maxid[u]=max(maxid[u],maxid[e.to]);
    }
  }
}

void build(int rt,int l,int r){
  if(l==r){
    int v=val[rev[l]];
    tree[rt].mul=v;
    tree[rt].two=v*v;
    tree[rt].add=0;
    return ;
  }
  int mid=(l+r)>>1;
  build(rt<<1,l,mid);
  build(rt<<1|1,mid+1,r);
  tree[rt].mul=(tree[rt<<1].mul+tree[rt<<1|1].mul);
  tree[rt].two=(tree[rt<<1].two+tree[rt<<1|1].two);
  tree[rt].mul%=mod;
  tree[rt].two%=mod;
  tree[rt].add=0;
}

void updateDown(int rt,int l,int r,int mid){
  ll Add=tree[rt].add;
  tree[rt<<1].add+=Add;
  tree[rt<<1|1].add+=Add;
  tree[rt<<1].two+=((mid-l+1)*Add*Add+tree[rt<<1].mul*2*Add);
  tree[rt<<1|1].two+=((r-mid)*Add*Add+tree[rt<<1|1].mul*2*Add);
  tree[rt<<1].mul+=((mid-l+1)*Add);
  tree[rt<<1|1].mul+=((r-mid)*Add);
  tree[rt<<1].add%=mod;
  tree[rt<<1|1].add%=mod;
  tree[rt<<1].mul%=mod;
  tree[rt<<1|1].mul%=mod;
  tree[rt<<1].two%=mod;
  tree[rt<<1|1].two%=mod;
  tree[rt].add=0;
}

void update(int rt,int l,int r,int L,int R,int v){
  if(L<=l && R>=r){
    tree[rt].add+=v;
    tree[rt].two+=(1LL*(r-l+1)*v*v+tree[rt].mul*2*v);
    tree[rt].mul+=(1LL*(r-l+1)*v);
    tree[rt].add%=mod;
    tree[rt].mul%=mod;
    tree[rt].two%=mod;
    return ;
  }
  int mid=(l+r)>>1;
  if(tree[rt].add) updateDown(rt,l,r,mid);
  if(L<=mid) update(rt<<1,l,mid,L,R,v);
  if(R>mid) update(rt<<1|1,mid+1,r,L,R,v);
  tree[rt].mul=(tree[rt<<1].mul+tree[rt<<1|1].mul);
  tree[rt].two=(tree[rt<<1].two+tree[rt<<1|1].two);
  tree[rt].mul%=mod;
  tree[rt].two%=mod;
}

int query(int rt,int l,int r,int L,int R){
  if(L>r || R<l) return 0;
  if(L<=l && R>=r) return tree[rt].two;
  int mid=(l+r)>>1;
  if(tree[rt].add) updateDown(rt,l,r,mid);
  return (query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R))%mod;
}

int main(){
  init();
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&val[i]),val[i]%=mod;
  for(int i=1;i<n;i++){
    int u,v;
    scanf("%d%d",&u,&v);
    addEdge(u,v);
  }
  dfs(1);
  build(1,1,n);
  for(int i=1;i<=m;i++){
    int type,x,y;
    scanf("%d",&type);
    if(type==1){
      scanf("%d%d",&x,&y);
      //printf("%d %d\n",id[x],maxid[x]);
      y%=mod;
      update(1,1,n,id[x],maxid[x],y);
    }
    else{
      scanf("%d",&x);
      printf("%d\n",query(1,1,n,id[x],maxid[x])); 
    }
  }
}

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100000+100;

int n,m;
struct Node{
  int l,r,id,val;
  bool operator <(const Node a)const{
      return a.val>val;
  }
}node[maxn];
struct Val{
  int id,val;
  bool operator <(const Val a)const{
      return a.val>val;
  }
}val[maxn];
int ans[maxn];

int tree[maxn];

int getSum(int x){
  int sum=0;
  while(x>0){
    sum+=tree[x];
    x-=(x&(-x));
  }
  return sum;
}

void update(int x){
  while(x<=n){
    tree[x]++;
  //  printf("%d %d\n",tree[x],x);
    x+=(x&(-x));
  }
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&val[i].val),val[i].id=i;
  for(int i=1;i<=m;i++) scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].val),node[i].id=i;
  sort(val+1,val+n+1);
  sort(node+1,node+m+1);
  for(int i=1,j=1;i<=m;i++){
    for(;j<=n && node[i].val>=val[j].val;j++){
      update(val[j].id);
      //printf("%d %d %d\n",node[i].val,val[j].val,val[j].id);
    }
    //printf("%d\n",getSum(node[i].r));
    ans[node[i].id]=getSum(node[i].r)-((node[i].l==1)?0:getSum(node[i].l-1));
  }
  for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}

#include<cstdio>
using namespace std;
 
int main(){
    long long n;
    scanf("%lld",&n);
    if(n!=1) printf("%lld\n",n+(n-1));
    else printf("2\n");
}

牛客小白月賽9 A、B、C、D、E、H

繼續閱讀

HDU 5344 MZL's xor

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)