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>
