POJ - 2549 Sumsets-白红宇

POJ - 2549 Sumsets

阅读量：6305 次

发布时间：2019-06-22

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

条件a+b == d-c，O(n*n)枚举出所有的形如a+b的和，然后从大到小枚举d，在枚举c，二分找d-c。

主要是要用容斥排除c和d出现在和中，详细的过程见注释。

复杂度为O(n^2log(n^2))。

/**********************************************************            ------------------                          **   author AbyssalFish                                   ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;/*容斥原理去重复左边是枚举出来的,保证不等可能出现重复的情况有：d 和 c同时出现case 1 d+c == d-c -> c == 0其中一个出现前提a or b != c or dcase2 a+d == d-c, -> a == -c , 必要条件 a != c -> c != 0 如果不满足这个条件：找到的可能是d == dcase3 d+b == d-c, -> b == -ccase 2 3互斥case4 a+c == d-c, -> a == d-2*c, 必要条件 a != d -> c != 0case5 c+b == d-c -> b == d-2*ccase 4 5互斥case (2,3,4,5) 1互斥*/const int maxn = 1e3, INF = 536870911+5;int n;int e[maxn+1], tab[maxn*maxn>>1];bool vis[maxn];int solve(){ sort(e,e+n); int i, j, a, c, d, k; int sz = 0; for(i = 1; i < n; i++){ a = e[i]; for(j = 0; j < i; j++){ tab[sz++] = a+e[j]; } } sort(tab,tab+sz); e[n] = e[n]-1; for(j = 0; j < n; j++) { c = -e[j]; vis[j] = (*lower_bound(e,e+n,c) == c); // c == 0 || -c == a or b } tab[sz+1] = tab[sz] = tab[sz-1]-1; for(i = n; i--; ){ d = e[i]; for(j = 2; j < n; j++)if(i!=j){ c = e[j]; a = d-c; k = lower_bound(tab,tab+sz,a)-tab; if(c){ if(vis[j]) k++; if(*lower_bound(e,e+n,a-c) == a-c) k++; } else k++; if(a == tab[k]) return d; } } return INF;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif while(scanf("%d",&n),n){ for(int i = 0; i < n; i++) scanf("%d", e+i); int res = solve(); if(res < INF) printf("%d\n", res); else puts("no solution"); } return 0;}

伪二分O(n^3) ???

int solve(){    sort(e,e+n);    int i, j, sum, lb, ub, tsum;    for(i = n; i--; ){        for(j = 2; j < n; j++)if(i!=j){            sum = e[i]-e[j];            for(lb = 0,ub = j-1; lb < ub; ){ //状态是DAG                tsum = e[lb]+e[ub];                if(tsum == sum) return e[i];                tsum > sum ? ub--:lb++; //O(n)            }        }    }    return INF;}

转载于:https://www.cnblogs.com/jerryRey/p/4975779.html

你可能感兴趣的文章

last_insert_id()获取mysql最后一条记录ID

Richard M. Stallman 给《自由开源软件本地化》写的前言

查看>>

oracle数据库密码过期报错

查看>>