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

XTU 1185 暴力打表+二分

题目连接: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今天碰到一个问题,他想知道x3+y3 = c 是否存在正整数解?

输入

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

输出

每行输出一个样例的结果,如果存在,输出“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

题目描述

Bob今天碰到一个问题,他想知道x3+y3 = c 是否存在正整数解?

输入

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

输出

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

样例输入

2
28
27

样例输出

Yes
No


Source

XTU OnlineJudge

XTU 1185 暴力打表+二分