最近老师把apio的题目拿出来了，然后由于我实在是菜，分数还没三位数......

　----------------我是分割线

1.巴厘岛的雕塑

N个数，分成连续的A-B个组，让每个组的和或起来最小，求最小值。

对于Task1 n<=100   

　　由于涉及到位运算，所以很容易想到按二进制位来做。要让答案最小，显然要从二进制高位到低位判断，能取0就取0。

　　所以我们考虑一个n^3 dp  用 f[i][j] 表示在当前的值之下，前i个分j组能否符合条件，用x表示当前判断的数字。

　　f[i][j]|=f[k][j-1] (k=[0,i-1] , s[k+1..i] or x=x)

　　很显然如果满足第k+1到第i个数的和或上x等于x，那么这个数字和没有一个二进制位比x大。

　　那么就先把所有位设成1，从高位开始，把它设成0，进行dp。如果在f[n][A..B]中有一个true，那么就可以分，不然就把这一位改回1。这样一直做下去就可以得到答案。

复杂度n^3logAi

对于Task 2 n<=2000, A=1

　　n的范围扩大了，但是A＝1很关键，这意味着我不考虑分组是否大等A了，只要<=B即可（显然这样我们就要让分组最小）。

　　那么我们改良一下dp，用f[i]表示前i个数，满足条件的情况下，至少分几组。

　　f[i]=min(f[j])+1;(j=[0,i-1],s[j+1..i] or x=x)

　　最后的答案和B比较一下即可,这样就dp变成了n^2了，其他过程不变。

复杂度n^2logAi。

附很丑的代码

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;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;}bool f[105][105];int f2[2005];int n;ll ans;ll s[2005];int a,b;bool check(ll x){    memset(f,0,sizeof(f));    f[0][0]=1;    for(int i=1;i<=n;i++)        for(int k=1;k<=i;k++)            for(int j=0;j
        
         =0;--i)        {            ans-=(ll)1<
         
          =0;--i)        {            ans-=(ll)1<
         
        
       
      
     

 

 

2.雅加达的摩天楼

有n个点m只doge（0-m-1)，每只doge给定初始位置和跳跃力，每次跳跃，位置为b,跳跃力为p的doge可以跳到b+p或者b-p。

现在doge0有信息要传到doge1 求最少的跳跃数。n,m<=30000

　　网上有其他的最短路的做法，但是我们仔细分析分析，是可以暴力的.....

　　设一个状态(b,p)表示现在信息传到了在b点跳跃力为p的doge上。从出题人卡代码的角度上，显然要状态数最多，只要加上了判重，那么状态数就最多是

　　30000+2*15000+3*10000+....

　　也就是说每个跳跃力状态数最多只有n种，但是对于跳跃力p,每个能增加的状态数辆只有n/p....

　　那么这样数量最多的时候， doge跳跃力从1,2,2,3,3,3,一直到k,  k*(k-1)/2=m，状态数最多n＊k，大约七百多万....

　　所以直接bfs，到达一个没到过的点时候把那里的doge全部入队，加上哈希判重即可。（map跑太慢了，听了一个大佬的建议手写了一个在这道题理论上o(1)的哈希表...)

附上好丑好丑的代码

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;inline 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 n,m,cnt=0,cnt2=0;int head[30005];bool has[30005];int front[9875322];int hx[7300001];int next[7300001];struct edge{    int m,next;}e[30005];int q[3][7300001];int top,tail;inline void push(int b,int p,int f){    q[0][++top]=b;    q[1][top]=p;    q[2][top]=f;}inline void ins(int x,int y){    e[++cnt].next=head[x];    head[x]=cnt;    e[cnt].m=y;}void rel(int num,int f)//释放所有doge {    has[num]=1;    for(int i=head[num];i;i=e[i].next)        push(num,e[i].m,f);}inline void insw(int h,int b){    next[++cnt2]=front[h];    front[h]=cnt2;    hx[cnt2]=b; }bool check(int hash,int b){    for(int i=front[hash];i;i=next[i])        if(hx[i]==b) return false;    insw(hash,b);    return true;}inline void get(int&b,int&p,int&f){    b=q[0][++tail];    p=q[1][tail];    f=q[2][tail];}inline void add(int b,int p,int f){    int hash=(b<<15)+p;hash%=9875321;    if(check(hash,b))    {        push(b,p,f);        if(!has[b]) rel(b,f);    }}int main(){    freopen("skyscraper.in","r",stdin);    freopen("skyscraper.out","w",stdout);    n=read();m=read();int from,to;    for(register int i=1;i<=m;++i)    {        q[0][i]=read();q[1][i]=read();        ins(q[0][i],q[1][i]);    }from=q[0][1];to=q[0][2];    rel(from,0);    if(from==to) return 0*puts("0");    register int b,p,f;    while(top!=tail)    {        get(b,p,f);        if(b+p==to||b-p==to) {printf("%d\n",f+1);return 0;}         if(b>=p)            add(b-p,p,f+1);        if(b+p
       
      
     

 

3.巴邻旁之桥

从前有条河，河旁住着人....

有n个人，每个人有要从一个坐标到另一个坐标，这些位置可能在河的两边。现在你要在河的某些位置修建垂直于河的k座桥，让所有人的路径长之和最短。

对于Task 1  k=1,n<=100000

　　不过河的人直接统计答案。

      剩下的人，很显然，只修一座桥的情况下，一定要修在坐标的中位数那里。（设桥修在x，每个坐标产生的距离为|pos-x|，脑补一下就知道了）。

对于Task 2 k=2 n<=100000

　　

　　这下预算高了一点 要修两座桥了，对于每一个人(x,y)，肯定走离x，y的中点(x+y)/2更近的桥。

　　那么一定会存在一个分割点，使得左边的人走左边的桥，右边的人走右边的桥，距离和最短。这样的话，两边的桥就按照Task1修在中位数就可以了。

　　那么就要考虑枚举分割点。从一段中删掉或者插入一个点，我们发现由于每次都选在中位数，实际上产生影响的只有被操作的那个点。所以我们用两个权值线段树（或者平衡树），维护左右两段的中位数即可啦。

　　复杂度nlogn

　　附上最丑的代码

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;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 T1[800005],T2[800005];inline ll myabs(ll x){    return x<0?-x:x;}struct gg{    int l,r,mid,idl,idr;}home[200005];int n,cnt=0;char c1,c2;ll s[200005];ll ext=0,ans=0,ans2=0,minn,num;int solve1(){     int a,b;    for(int i=1;i<=n;i++)    {        scanf("%c",&c1);a=read();        scanf("%c",&c2);b=read();        if(c1==c2)            ext+=myabs(a-b);        else        {            s[++cnt]=a;            s[++cnt]=b;            ++ext;        }    }    sort(s+1,s+cnt+1);    ll mid=s[(cnt+1)/2];    for(int i=1;i<=cnt;i++)        ans+=myabs(mid-s[i]);    printf("%lld",ans+ext);    return 0;}ll query(int*T,int x,int l,int r,int rk){    if(l==r) return s[l];    if(T[x<<1]>=rk) return query(T,x<<1,l,(l+r)>>1,rk);    else return query(T,x*2+1,(l+r)/2+1,r,rk-T[x<<1]);}void ins(int*T,int x,int p,int l,int r,int ad){    if(l!=r)    {        int mid=(l+r)>>1;        if(x<=mid) ins(T,x,p<<1,l,mid,ad);        else ins(T,x,(p<<1)+1,mid+1,r,ad);    }    T[p]+=ad;}bool cmp(gg x,gg y){
   return x.mid
       
      
     

 

好的就是这样，理解了题目做法后都就不难写了.....

有什么错误请您指出 谢谢咯 ?