Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

折半枚举 47ms 还没人家暴力快,可能是STL比较慢吧···

Posted by 947186602 at 2020-09-11 18:18:15 on Problem 1543
数据:
100
Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)
Cube = 25, Triple = (4,17,22)
Cube = 27, Triple = (3,18,24)
Cube = 28, Triple = (18,19,21)
Cube = 29, Triple = (11,15,27)
Cube = 30, Triple = (15,20,25)
Cube = 36, Triple = (4,24,32)
Cube = 36, Triple = (18,24,30)
Cube = 38, Triple = (6,20,36)
Cube = 40, Triple = (14,28,34)
Cube = 41, Triple = (2,17,40)
Cube = 41, Triple = (6,32,33)
Cube = 42, Triple = (21,28,35)
Cube = 44, Triple = (16,23,41)
Cube = 45, Triple = (5,30,40)
Cube = 46, Triple = (3,36,37)
Cube = 46, Triple = (27,30,37)
Cube = 48, Triple = (24,32,40)
Cube = 50, Triple = (8,34,44)
Cube = 53, Triple = (29,34,44)
Cube = 54, Triple = (6,36,48)
Cube = 54, Triple = (12,19,53)
Cube = 54, Triple = (27,36,45)
Cube = 56, Triple = (36,38,42)
Cube = 57, Triple = (9,30,54)
Cube = 58, Triple = (15,42,49)
Cube = 58, Triple = (22,30,54)
Cube = 60, Triple = (21,42,51)
Cube = 60, Triple = (30,40,50)
Cube = 63, Triple = (7,42,56)
Cube = 66, Triple = (33,44,55)
Cube = 67, Triple = (22,51,54)
Cube = 69, Triple = (36,38,61)
Cube = 70, Triple = (7,54,57)
Cube = 71, Triple = (14,23,70)
Cube = 72, Triple = (8,48,64)
Cube = 72, Triple = (34,39,65)
Cube = 72, Triple = (36,48,60)
Cube = 75, Triple = (12,51,66)
Cube = 75, Triple = (38,43,66)
Cube = 76, Triple = (12,40,72)
Cube = 76, Triple = (31,33,72)
Cube = 78, Triple = (39,52,65)
Cube = 80, Triple = (28,56,68)
Cube = 81, Triple = (9,54,72)
Cube = 81, Triple = (25,48,74)
Cube = 82, Triple = (4,34,80)
Cube = 82, Triple = (12,64,66)
Cube = 82, Triple = (19,60,69)
Cube = 84, Triple = (28,53,75)
Cube = 84, Triple = (42,56,70)
Cube = 84, Triple = (54,57,63)
Cube = 85, Triple = (50,61,64)
Cube = 87, Triple = (20,54,79)
Cube = 87, Triple = (26,55,78)
Cube = 87, Triple = (33,45,81)
Cube = 87, Triple = (38,48,79)
Cube = 88, Triple = (21,43,84)
Cube = 88, Triple = (25,31,86)
Cube = 88, Triple = (32,46,82)
Cube = 89, Triple = (17,40,86)
Cube = 90, Triple = (10,60,80)
Cube = 90, Triple = (25,38,87)
Cube = 90, Triple = (45,60,75)
Cube = 90, Triple = (58,59,69)
Cube = 92, Triple = (6,72,74)
Cube = 92, Triple = (54,60,74)
Cube = 93, Triple = (32,54,85)
Cube = 95, Triple = (15,50,90)
Cube = 96, Triple = (19,53,90)
Cube = 96, Triple = (48,64,80)
Cube = 97, Triple = (45,69,79)
Cube = 99, Triple = (11,66,88)
Cube = 100, Triple = (16,68,88)
Cube = 100, Triple = (35,70,85)
//共81条

代码:
#include<cstdio>
#include<string.h>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> P;
struct Cube
{
    int a,b,c,d;
    bool operator < (const Cube& x) const
    {
        if(a == x.a)
            return b < x.b;
        else return a < x.a;
    }
} cube[1005];

int getN3(int x)
{
    return x*x*x;
}
int num[105],N,index = 0;
void init()
{
    for(int i = 0; i <= 100; ++i)
    {
        num[i] = getN3(i);
    }
    index = 0;
    map<int,vector<P> > ab;
    for(int i = 2;i <= 100;++i){
         for(int j = 2; j <= i;++j){  // j <= i a^3 - b^3
              ab[num[i]-num[j]].push_back(P(i,j));
         }
    }

    //枚举c^3 + d^3
    for(int i = 2;i <= 100;++i){  // c <= d
         for(int j = i;j <= 100;++j){ 
              if(ab.find(num[i]+num[j]) != ab.end() ){
                   for(int k = 0;k < ab[num[i]+num[j]].size();++k){
                        P p = ab[num[i]+num[j]][k];
                        if(p.second <= i && p.second <= j){
                             cube[index].a = p.first;
                             cube[index].b = p.second;
                             cube[index].c = i;
                             cube[index++].d = j;
                        }
                   }
              }
         }
    }
    sort(cube,cube+index);
    for(int i = 0;i < index && cube[i].a <= N;++i){
         printf("Cube = %d, Triple = (%d,%d,%d)\n",cube[i].a,cube[i].b,cube[i].c,cube[i].d);
    }
}

int main()
{
    scanf("%d",&N);
    init();
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator