请选择 进入手机版 | 继续访问电脑版

12360技术网 - 专业IT技术发表平台

 立即注册  找回密码
查看: 7696|回复: 4

Crazy Thairs POJ - 3378(10000进制加法 树状数组)

[复制链接]

21

主题

26

帖子

178

积分

注册会员

Rank: 2

积分
178
发表于 2020-1-26 13:55:06 | 显示全部楼层 |阅读模式
These days, Sempr is crazed on one problem named Crazy Thair. Given N (1 ≤ N ≤ 50000) numbers, which  are no more than 109, Crazy Thair is a group of 5 numbers {i, j, k, l, m} satisfying:

  • 1 ≤ i < j < k < l < m ≤ N
  • Ai < Aj < Ak < Al < Am
For example, in the sequence {2, 1, 3, 4, 5, 7, 6},there are four Crazy Thair groups: {1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 3, 4, 5, 7} and {2, 3, 4, 5, 7}.
Could you help Sempr to count how many Crazy Thairs in the sequence?
Input
Input contains several test cases. Each test case begins with a line containing a number N, followed by a line containing N numbers.
Output
Output the amount of Crazy Thairs in each sequence.
Sample Input
5
1 2 3 4 5
7
2 1 3 4 5 7 6
7
1 2 3 4 5 6 7
Sample Output
1
4
21
题意:
寻找上升五元组的个数
思路:
本质上是树状数组优化dp。
状态就是dp[j],到了第j个数字的i元上升组。
从比j小的i - 1元上升组转移过来,那么这个求和的过程可以用树状数组维护。
比较坑的就是得用大整数,而且复杂度卡的很死,得用10000进制加法,于是找了个10000进制加法的代码改了一下。
[code]#pragma GCC optimize(2)#include #include #include #include #include using namespace std;const int maxn = 10;const int BASE = 10000;struct bign{    int d[maxn], len;        void clean() { while(len > 1 && !d[len-1]) len--; }//    bign()             { memset(d, 0, sizeof(d)); len = 1; }//    bign(int num)     { *this = num; }//    bign(char* num) { *this = num; }        bign():len(0) {}    bign(int n):len(0) {        for( ; n > 0; n /= BASE)    d[len++] = n%BASE;    }        bign operator = (const char* num){        memset(d, 0, sizeof(d)); len = strlen(num);        for(int i = 0; i < len; i++) d = num[len-1-i] - '0';        clean();        return *this;    }    bign operator = (int num){        char s[20]; sprintf(s, "%d", num);        *this = s;        return *this;    }        //    bign operator + (const bign& b){    //        bign c = *this; int i;    //        for (i = 0; i < b.len; i++){    //            c.d += b.d;    //            if (c.d >= BASE) c.d%=BASE, c.d[i+1]++;    //        }    //        while (c.d >= BASE) c.d[i++]%=BASE, c.d++;    //        c.len = max(len, b.len);    //        if (c.d && c.len len || i < b.len || carry > 0; ++i) {            if(i < this->len)   carry += this->d;            if(i < b.len)   carry += b.d;            c.d = carry%BASE;            carry /= BASE;        }        c.len = i;        return c;    }        bign operator - (const bign& b){        bign c = *this; int i;        for (i = 0; i < b.len; i++){            c.d -= b.d;            if (c.d < 0) c.d+=10, c.d[i+1]--;        }        while (c.d < 0) c.d[i++]+=10, c.d--;        c.clean();        return c;    }    bign operator * (const bign& b)const{        int i, j; bign c; c.len = len + b.len;        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)            c.d[i+j] += d * b.d[j];        for(i = 0; i < c.len-1; i++)            c.d[i+1] += c.d/10, c.d %= 10;        c.clean();        return c;    }    bign operator / (const bign& b){        int i, j;        bign c = *this, a = 0;        for (i = len - 1; i >= 0; i--)        {            a = a*10 + d;            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;            c.d = j;            a = a - b*j;        }        c.clean();        return c;    }    bign operator % (const bign& b){        int i, j;        bign a = 0;        for (i = len - 1; i >= 0; i--)        {            a = a*10 + d;            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;            a = a - b*j;        }        return a;    }    bign operator += (const bign& b){        *this = *this + b;        return *this;    }        bool operator = 0; i--)            if(d != b.d) return d < b.d;        return false;    }    bool operator >(const bign& b) const{return b < *this;}    bool operator=(const bign& b) const{return !(*this < b);}    bool operator!=(const bign& b) const{return b < *this || *this < b;}    bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}        string str() const{        char s[maxn]={};        for(int i = 0; i < len; i++) s[len-1-i] = d+'0';        return s;    }        void Print() {        if(len == 0)    {cout > s;    x = s.c_str();    return in;}ostream& operator  nodes.x;            nodes.id = i;        }        sort(nodes + 1,nodes + 1 + n,cmp);        int cnt = 0;        a[nodes[1].id] = ++cnt;        for(int i = 2;i




上一篇:Android多个Activity共享socket,实现一个页面连接WIFI,其他页面也能传输
下一篇:Effective Objective-C 2.0读书笔记 Ⅱ
回复

使用道具 举报

0

主题

27

帖子

577

积分

高级会员

Rank: 4

积分
577
发表于 2020-1-28 16:44:31 | 显示全部楼层
这东西我收了!谢谢楼主![www.12360.co]
回复

使用道具 举报

0

主题

15

帖子

325

积分

中级会员

Rank: 3Rank: 3

积分
325
发表于 2020-2-5 04:06:11 | 显示全部楼层
楼主发贴辛苦了,谢谢楼主分享![www.12360.co]
回复

使用道具 举报

0

主题

28

帖子

598

积分

高级会员

Rank: 4

积分
598
发表于 2020-2-9 01:49:31 | 显示全部楼层
楼主,我太崇拜你了![www.12360.co]
社区不能没有像楼主这样的人才啊!
回复

使用道具 举报

15

主题

26

帖子

286

积分

中级会员

Rank: 3Rank: 3

积分
286
发表于 7 天前 | 显示全部楼层
感谢楼主的无私分享![www.12360.co]
回复

使用道具 举报

懒得打字嘛,点击右侧快捷回复 【右侧内容,后台自定义】
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

12360技术网

GMT+8, 2020-2-29 21:36 , Processed in 0.097460 second(s), 40 queries .

本网站内容收集于互联网,Www.12360.Co不承担任何由于内容的合法性及健康性所引起的争议和法律责任。 欢迎大家对网站内容侵犯版权等不合法和不健康行为进行监督和举报。

© 2019-2020 Www.12360.Co

快速回复 返回顶部 返回列表