XTU 1185 暴力打表+二分

首页 > 代码库 > XTU 1185 暴力打表+二分

2024-08-01 01:10:41 223人阅读

题目连接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1185

Bob‘s Problem
Accepted : 105		Submit : 550
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述

Bob今天碰到一个问题，他想知道x³+y³ = c 是否存在正整数解？

输入

第一行是一个整数K(K≤20000)，表示样例的个数。以后每行一个整数c(2≤c≤10⁹)

输出

每行输出一个样例的结果，如果存在，输出“Yes”，否则输出“No”。（引号不用输出）

样例输入

2
28
27

样例输出

Yes
No

Source

XTU OnlineJudge

思路：可以先确定x,y最大取值是1000，然后我的想法是对x从1到1000遍历一遍，然后二分y,但是这样超时了，我就纳闷了，O（n*logn）也超~（忽略了打表）

如果把1000*1000中结果打表出来，然后在二分不就更快了~还省却了中间的计算所用的时间。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
const int N=1e6+100;
using namespace std;
int cnt[N],ct;

bool find(int i)
{
 int l=1,r=ct;
 while(l<r)
 {
  int mid=(l+r)/2;
  if(cnt[mid]>i)r=mid;
  else if(cnt[mid]==i)return true;
  else l=mid+1;
 }
 return false;
}

int main()
{
  ct=0;
  for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++)
    {
      if(i*i*i+j*j*j<=1e9)
      cnt[++ct]=i*i*i+j*j*j;
     
    }
  sort(cnt+1,cnt+1+ct);
  int T;
  cin>>T;
  while(T--)
  {
   int c;
   scanf("%d",&c);
  
   
   bool flag=find(c);
   if(flag)printf("Yes\n");
   else printf("No\n");
  }
  return 0;
}

Bob‘s Problem
Accepted : 105		Submit : 550
Time Limit : 1000 MS		Memory Limit : 65536 KB