POJ 3378 (大整数加法+树状数组)-白红宇

POJ 3378 (大整数加法+树状数组)

阅读量：5222 次

发布时间：2019-06-14

本文共 3431 字，大约阅读时间需要 11 分钟。

　　题意：给一个长度为N(N < 50000)的序列，求这个序列中长度为5的递增子序列的个数。

思路：对于长度为5的子序列，先考虑长度为1的子序列，第i个位置以i结尾长度为1的子序列个数为1。第i个位置以i结尾长度为2的子序列个数为i之前并且小于a[i]的长度为1的子序列的个数。同理，第i位置长度为3的子序列个数为i之前小于a[i]的长度为2的子序列的个数。。。依次往后推。

比如原序列为：(1, 2, 4, 6, 3) 推： -> (1, 1, 1, 1, 1)₁ -> (0, 1, 2, 3, 2)₂ -> (0, 0, 1, 3, 1)₃ -> (0, 0, 0, 1, 0)₄ -> (0, 0, 0, 0, 0)₅

每次统计用树状数组就可以，中间过程和结果都有可能出现超long long的情况。所以用大整数加法。

ps：加法最后一次进位忘了。。。wa了无数次。。。

//#pragma comment(linker,"/STACK:327680000,327680000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for((i) = 0; (i) < (n); ++(i))#define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))#define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define Read() freopen("data.in", "r", stdin)#define Write() freopen("data.out", "w", stdout);typedef long long LL;const double eps = 1e-8;const double PI = acos(-1.0);const int inf = ~0u>>2;using namespace std;const int N = 50010;const int Base = 10000;int a[N], b[N];class BigNum {public: int num[7], len; BigNum():len(0) {} BigNum(int n):len(0) { for( ; n > 0; n /= Base) num[len++] = n%Base; } BigNum Bigvalueof(LL n) { len = 0; while(n) { num[len++] = n%Base; n /= Base; } return *this; } BigNum operator + (const BigNum& b) { //++ BigNum c; int i, carry = 0; for(i = 0; i < this->len || i < b.len || carry > 0; ++i) { if(i < this->len) carry += this->num[i]; if(i < b.len) carry += b.num[i]; c.num[i] = carry%Base; carry /= Base; } c.len = i; return c; } BigNum operator += (const BigNum& b) { //+= *this = *this + b; return *this; } void Print() { if(len == 0) {puts("0"); return ;} printf("%d", num[len - 1]); for(int i = len - 2; i >= 0; --i) { for(int j = Base/10; j > 0; j /= 10) { printf("%d", num[i]/j%10); } } puts(""); }};class TreeArray : public BigNum{public: BigNum c[N]; int n; TreeArray() {} ~TreeArray() {} void init(int x) { n = x; CL(c, 0); } int lowbit(int i) { return i&(-i);} void add(int p, const BigNum& val) { while(p <= n) { c[p] += val; p += lowbit(p); } } BigNum sum(int p) { BigNum res; res.Bigvalueof(0); while(p > 0) { res += c[p]; p -= lowbit(p); } return res; }};int bsearch(int b[], int m, int key) { int l = 0, r = m, mid; while(l <= r) { mid = (r + l) >> 1; if(b[mid] == key) return mid + 1; else if(b[mid] < key) l = mid + 1; else r = mid - 1; } return -1;}int main() { //freopen("data.in", "r", stdin); int n, m, p, i, j; BigNum ans, tmp; TreeArray ta[6]; while(~scanf("%d", &n)) { REP(i, n) { scanf("%d", a + i); b[i] = a[i]; } sort(b, b + n); m = 0; for(i = 1; i < n; ++i) { if(b[m] != b[i]) b[++m] = b[i]; } ++m; REP(i, 6) ta[i].init(m + 5); for(i = 0; i < n; ++i) { //printf("%d ", a[i]); a[i] = bsearch(b, m, a[i]); //printf("%d\n", a[i]); } ans = ans.Bigvalueof(0); for(i = 0; i < n; ++i) { p = a[i]; ta[1].add(p, tmp.Bigvalueof(1)); for(j = 2; j <= 5; ++j) { tmp = ta[j-1].sum(p - 1); if(tmp.len) ta[j].add(p, tmp); if(j == 5) ans += tmp; } } ans.Print(); } return 0;}

转载于:https://www.cnblogs.com/vongang/archive/2013/01/18/2866672.html

你可能感兴趣的文章