forestkeeper

C++博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

2010年1月8日 #

     摘要: 题意是一个覆盖问题,用n个各种边长的小三角形来覆盖一个六边形,基本上可以直接深搜,可以试着覆盖六分之一,三分之一和二分之一至全部,四种覆盖形式有一种达到完全覆盖即可退出,以此来降低复杂度。对三角形坐标的表示上采用了如下的表示法:              &n...  阅读全文
posted @ 2010-01-08 10:32 forestkeeper 阅读(1199) | 评论 (0)编辑 收藏

2010年1月7日 #

     摘要: 这是一题套用并查集(又称不相交集)的题在套用过程中有一个小技巧,可以避免并查集不能删边的缺点(当然,在实际应用中实用性不大)。        题意是说有n个星球组成一个连接的网络,很明显把星球看成点而有通讯连线看成有边相连,接下来有m个操作,有查询操作,添加边的操作和销毁边的操作,同时每个星球有一个权值,即每个点有一个权值,对一...  阅读全文
posted @ 2010-01-07 22:39 forestkeeper 阅读(1054) | 评论 (1)编辑 收藏

2010年1月3日 #

一道套数据结构的题

题意是说,蚂蚁有n个等级(level),每个等级初始都有一定量的蚂蚁,随后有一系列操作,p a b操作表示把level  a的蚂蚁个数转换成b,q  x  表示询问在所有蚂蚁里排名第x的蚂蚁在哪个等级。

首先一共有的蚂蚁数为所有level蚂蚁数量总和,不能为每个蚂蚁都开一个int数组去存它的level(如果数据量很小则这种方法可以是o(n)的)。对存着每个层的蚂蚁可以用求和与x比较来确定它处于哪个level。由于n的数量级,故希望能采用log n级的方法来处理,恰好由线段树实现的子段和,其无论是更新(update)还是查询(query)都是log n级的,同时在查询时可再加一二分,即sort(0,n)开始,于是查询的复杂度为logn*logn,最终280ms AC。附代码,代码中未用线段树,而是使用了树状数组同样是logn的查找及更新复杂度,空间复杂度及编程复杂度比线段树低。

#include <cstring> 
#include
<cstdio>
const int MAXN = 100000
 
inline 
int lowbit(int x) 
    
return (x & (x ^ (x - 1))); 
}
 
 
template
<class elemType> 
class Sum
public
    elemType a[MAXN], c[MAXN], ret; 
    
int n; 
 
    
void init(int i) 
        memset(a, 
0sizeof(a)); 
        memset(c, 
0sizeof(c)); 
        n 
= i; 
    }
 
 
    
void update(int i, elemType v) 
        v 
-= a[i]; 
        a[i] 
+= v; 
        
for (i++; i <= n; i += lowbit(i)) 
            c[i 
- 1+= v; 
        }
 
    }
 
     elemType query(
int i) 
        
for (ret = 0; i; i ^= lowbit(i)) 
            ret 
+= c[i-1]; 
        }
 
        
return ret; 
    }
 
}
;
Sum
<int>sum; 

int Sort(int l,int r,int x)
{
    
if(l>=r-1)
       
return l;
    
int pos = (l+r)/2;
    
if (pos==1)
      
return pos;
    
int p1 = sum.query(pos);
    
int p2 = sum.query(pos-1);
    
if(x>p1&&x<=p2)
      
return pos;
    
int ans;
    
if(x>p2)
      ans 
= Sort(pos,r,x);
    
else ans = Sort(l,pos,x);
     
return ans;
}

int main()
{
    
int n;
    
while(scanf("%d",&n)!=EOF)
    
{
    sum.init(n);
    
for (int i =0; i<n; i++)
    
{
        
int a;
        scanf(
"%d",&a);
        sum.update(i,a);
    }

    
int m;
    scanf(
"%d",&m);
    
for (int i =0; i<m; i++)
    
{
        
char c[20];
        scanf(
"%s",c);
        
if (c[0]=='p')
        
{
            
int a,b;
            scanf(
"%d%d",&a,&b);
            sum.update(a
-1,b);
        }

        
else
        
{
            
int x;
            scanf(
"%d",&x);
            
int ans = Sort(1,n+1,x);
            printf(
"%d\n",ans);
        }

    }

    }

}
posted @ 2010-01-03 11:07 forestkeeper 阅读(1047) | 评论 (0)编辑 收藏

仅列出标题