zoj1017 The Bermuda Triagle

forestkeeper — Fri, 08 Jan 2010 02:32:00 GMT

摘要: 题意是一个覆盖问题，用n个各种边长的小三角形来覆盖一个六边形，基本上可以直接深搜，可以试着覆盖六分之一，三分之一和二分之一至全部，四种覆盖形式有一种达到完全覆盖即可退出，以此来降低复杂度。对三角形坐标的表示上采用了如下的表示法： &n... 阅读全文

forestkeeper 2010-01-08 10:32 发表评论

zoj3261 Connections in Galaxy War

forestkeeper — Thu, 07 Jan 2010 14:39:00 GMT

摘要: 这是一题套用并查集（又称不相交集）的题在套用过程中有一个小技巧，可以避免并查集不能删边的缺点（当然，在实际应用中实用性不大）。题意是说有n个星球组成一个连接的网络，很明显把星球看成点而有通讯连线看成有边相连，接下来有m个操作，有查询操作，添加边的操作和销毁边的操作，同时每个星球有一个权值，即每个点有一个权值，对一... 阅读全文

forestkeeper 2010-01-07 22:39 发表评论

zoj 3279 Ants

forestkeeper — Sun, 03 Jan 2010 03:07:00 GMT

一道套数据结构的题

题意是说，蚂蚁有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, 0, sizeof(a));
        memset(c, 0, sizeof(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);
        }
    }
    }
}

forestkeeper 2010-01-03 11:07 发表评论

C++博客-forestkeeper

zoj1017 The Bermuda Triagle

zoj3261 Connections in Galaxy War

zoj 3279 Ants