558C

题意：给你n个数，可对每一个数进行操作（乘2或者除以2）。求最少的操作使得全部的数都相等。

思路 : dp[ t ] 表示全部的数转化到 t 所需的最少操作， vis[ t ] 表示有多少数能够转化成 t 。

对于一个数 num ， 把它所能到达的数用上述的数组记录下即可了（详细看代码）。

注意 ：

输入：

3

5 4 4

输出 ： 2  （5/2*2=4）

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=100010;

int n,vis[maxn],num[maxn];

void initial()

{

    memset(num,0,sizeof(num));

    memset(vis,0,sizeof(vis));

}

void deal(int op)

{

    int tp=op,ct=0;

    while(tp)

    {

        vis[tp]++;

        num[tp]+=ct;

        if(tp%2==1 && tp!=1)

        {

            int yp=tp/2*2,cnt=ct+2;

            while(yp<maxn)

            {

                vis[yp]++;

                num[yp]+=cnt;

                yp*=2;

                cnt++;

            }

        }

        tp/=2;

        ct++;

    }

    tp=op*2,ct=1;

    while(tp<maxn)

    {

        vis[tp]++;

        num[tp]+=ct;

        tp*=2;

        ct++;

    }

}

void input()

{

    int u;

    for(int i=0;i<n;i++)

    {

        scanf("%d",&u);

        deal(u);

    }

}

void solve()

{

    int Min=1<<30;

    for(int i=0;i<maxn;i++)  if(vis[i]==n)  Min=min(Min,num[i]);

    cout<<Min<<endl;

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        initial();

        input();

        solve();

    }

    return 0;

}

558D

题意：给出n条信息。要你推断信息是否矛盾。或是否有多个出口，或是否有唯一出口。

信息有两种类型，一个是出口的若干区间，一个不是出口若干区间。

思路： 先通过出口的若干区间找出出口所在的树中根节点的区间。

然后在通过不是出

口的若干区间来推断。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#define ll long long

using namespace std;

struct node

{

    ll l,r;

    node(){}

    node(ll _l,ll _r):l(_l),r(_r){}

};

vector <node> G;

int n,m;

ll st,ed;

bool cmp(node p,node q)

{

    if(p.l==q.l)  return p.r<q.r;

    return p.l<q.l;

}

void initial()

{

    G.clear();

    st=(ll)1<<(n-1);

    ed=((ll)1<<n)-1;

}

void input()

{

    int tp,t;

    ll u,v;

    for(int i=0;i<m;i++)

    {

        scanf("%d %I64d %I64d %d",&tp,&u,&v,&t);

        u=u<<(n-tp);

        for(int j=0;j<n-tp;j++)  v=v<<1|1;

        if(t)

        {

            st=max(st,u);

            ed=min(ed,v);

        }

        else  G.push_back(node(u,v));

    }

    G.push_back(node(ed+1,ed+1));

}

void solve()

{

    ll ans=-1;

    sort(G.begin(),G.end(),cmp);

    for(int i=0;i<G.size();i++)

    {

        if(st>ed)  break;

        if(st<G[i].l)

        {

            if(ans!=-1 || st+1<G[i].l)

            {

                cout<<"Data not sufficient!"<<endl;

                return ;

            }

            ans=st;

        }

        st=max(st,G[i].r+1);

    }

    if(ans==-1)  cout<<"Game cheated!"<<endl;

    else cout<<ans<<endl;

}

int main()

{

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        initial();

        input();

        solve();

    }

    return 0;

}

558E

题意：给你一个长度为n的字符串（下标从1開始），然后给你m个操作。每一个操作有三个值 l,r,t。

假设t=1。表示将字符串中[ l ,r ]的部分依照升序排列。

假设t=0。表示将字符串中[
l ,r ]的部分依照降序排列。

最后要你输出原字符串经过m次操作后所形成的新的字符串。

思路：对于26个小写字母（a-z），分别建立线段树，即建26个线段树。

即每次改动 [ l , r ] 区间，则先通过26课线段树分别求出这个区间内的a–z的个数。然后将26课线

段树内的这一区间和置为0。

最后再依据顺序又一次给26课线段树的这一区间赋值即可了。

<span style="font-size:18px;">#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

const int N=100010;

const int M=26;

struct node

{

    int l,r,sum,cover;

} a[M][N*4];

string str;

int n,m;

void build(int cnt,int l,int r,int k)

{

    a[cnt][k].l=l;

    a[cnt][k].r=r;

    a[cnt][k].sum=0;

    a[cnt][k].cover=-1;

    if(l==r)  return ;

    int mid=(l+r)>>1;

    build(cnt,l,mid,2*k);

    build(cnt,mid+1,r,2*k+1);

}

void push_down(int cnt,int k)

{

    if(a[cnt][k].cover!=-1)

    {

        a[cnt][k*2].cover=a[cnt][k*2+1].cover=a[cnt][k].cover;

        a[cnt][k*2].sum=(a[cnt][k*2].r+1-a[cnt][k*2].l)*a[cnt][k*2].cover;

        a[cnt][k*2+1].sum=(a[cnt][k*2+1].r+1-a[cnt][k*2+1].l)*a[cnt][k*2+1].cover;

        a[cnt][k].cover=-1;

    }

}

void update(int cnt,int l,int r,int k,int num)

{

    if(l==a[cnt][k].l && r==a[cnt][k].r)

    {

        a[cnt][k].cover=num;

        a[cnt][k].sum=(a[cnt][k].r+1-a[cnt][k].l)*num;

        return ;

    }

    push_down(cnt,k);

    int mid=(a[cnt][k].l+a[cnt][k].r)>>1;

    if(r<=mid)      update(cnt,l,r,2*k,num);

    else if(l>mid)  update(cnt,l,r,2*k+1,num);

    else

    {

        update(cnt,l,mid,2*k,num);

        update(cnt,mid+1,r,2*k+1,num);

    }

    a[cnt][k].sum=a[cnt][k*2].sum+a[cnt][k*2+1].sum;

}

int query(int cnt,int l,int r,int k)

{

    if(l==a[cnt][k].l && r==a[cnt][k].r)  return a[cnt][k].sum;

    push_down(cnt,k);

    int mid=(a[cnt][k].l+a[cnt][k].r)>>1;

    if(r<=mid)      return query(cnt,l,r,2*k);

    else if(l>mid)  return query(cnt,l,r,2*k+1);

    else    return query(cnt,l,mid,2*k)+query(cnt,mid+1,r,2*k+1);

}

void input()

{

    for(int i=0; i<M; i++)  build(i,1,n,1);

    getchar();

    getline(cin,str);

    for(int i=1; i<=n; i++)  update(str[i-1]-'a',i,i,1,1);

}

void solve()

{

    int l,r,t;

    while(m--)

    {

        int num[M];

        scanf("%d %d %d",&l,&r,&t);

        for(int i=0; i<M; i++)

        {

            num[i]=query(i,l,r,1);

            update(i,l,r,1,0);

        }

        int pos=l;

        if(t==1)

        {

            for(int i=0; i<M; i++)

                if(num[i])

                {

                    update(i,pos,pos+num[i]-1,1,1);

                    pos=pos+num[i];

                }

        }

        else

        {

            for(int i=M-1; i>=0; i--)

                if(num[i])

                {

                    update(i,pos,pos+num[i]-1,1,1);

                    pos=pos+num[i];

                }

        }

    }

    for(int i=1; i<=n; i++)

        for(int j=0; j<M; j++)

            if(query(j,i,i,1))

            {

                printf("%c",j+'a');

                break;

            }

    printf("\n");

}

int main()

{

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        input();

        solve();

    }

    return 0;

}

</span>