2017ICPC沈阳区域赛 F

简介: 2017ICPC沈阳区域赛 F


这题目有点恶心,推出来公式:

s = t ∗ ( s q r t ( 3 ∗ ( t − 2 ) ∗ ( t + 2 ) ) / 4 s=t*(sqrt(3*(t-2)*(t+2))/4s=t(sqrt(3(t2)(t+2))/4

通过 打表知道规律:

ans[i]=4*ans[i-1]-ans[i-2];

因为数据4–10^30 3030

所以用高精度或者int128;

高精度代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
vector<int>ans[N];
string n;
int T;
vector<int> sub(vector<int>a,vector<int>b)
{
  int t=0;
  vector<int>res;
  for(int i=0;i<a.size();i++)
  {
    t=a[i]-t;
    if(i<b.size()) t-=b[i];
    res.push_back((t+10)%10);
    if(t<0) t=1;
    else t=0; 
  }
  while(res.size()>1&&res.back()==0) res.pop_back();
  return res;
}
vector<int>mul(vector<int>&a,int b)
{
  int t=0;
  vector<int>res;
  for(int i=0;i<a.size()||t;i++)
  {
    if(i<a.size()) t+=a[i]*b;
    res.push_back(t%10);
    t/=10;
  }
  while(res.size()>1&&res.back()==0) res.pop_back();
  return res;
}
bool compare(vector<int>&a,vector<int>&now)
{
  if(a.size()!=now.size()) return a.size()<now.size();
  for(int i=a.size()-1;i>=0;i--)
  {
    if(a[i]<now[i]) return 1;
    else if(a[i]>now[i]) return 0;
  }
  return 0;
}
int main()
{
  cin>>T;
  ans[1].push_back(4);
  ans[2].push_back(4);
  ans[2].push_back(1);
  for(int i=3;i<=105;i++)
  {
    ans[i]=sub(mul(ans[i-1],4),ans[i-2]);
  }
  while(T--)
  {
      cin>>n;
      vector<int>now;
      for(int i=n.size()-1;i>=0;i--) now.push_back(n[i]-'0');
      int i=1;
      while(compare(ans[i],now))
      {
        i++;
      }
      for(int j=ans[i].size()-1;j>=0;j--)
      {
        cout<<ans[i][j];
      }
      cout<<endl;
  }
  return 0;
}

__int128版本:

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
__int128 f[N],n;
int T;
__int128 read() {
  __int128 x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-')ch = getchar();
  if (ch == '-')f = -1;
  while (isdigit(ch))x = x * 10 + ch - '0', ch = getchar();
  return f * x;
}
inline void print(__int128 x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
int main()
{
  cin>>T;
  f[1]=4;
  f[2]=14;
  for(int i=3;i<=105;i++)
  {
    f[i]=4*f[i-1]-f[i-2];
  }
  while(T--)
  {
    n=read();
    int i=1;
    while(f[i]<n) i++;
      print(f[i]);
      cout<<"\n";
  }
  return 0;
}
目录
相关文章
|
定位技术 Go
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(银川),签到题5题
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(银川),签到题5题
88 0
|
机器学习/深度学习 人工智能 BI
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南),签到题5题
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南),签到题5题
73 0
|
机器学习/深度学习 人工智能
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(澳门),签到题4题
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(澳门),签到题4题
140 1
|
6月前
|
人工智能 NoSQL 机器人
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京),签到题4题
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京),签到题4题
107 0
|
人工智能 BI
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南),签到题2题
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南),签到题2题
73 2
|
6月前
|
机器学习/深度学习 人工智能
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明),签到题4题
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明),签到题4题
70 0
|
人工智能 移动开发 分布式计算
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京),签到题5题
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京),签到题5题
227 0
|
人工智能
2023河南萌新联赛第(四)场:河南大学(一)
2023河南萌新联赛第(四)场:河南大学
86 0
|
机器学习/深度学习 测试技术 容器
2023河南萌新联赛第(四)场:河南大学(二)
2023河南萌新联赛第(四)场:河南大学
176 0
|
机器学习/深度学习 物联网 BI
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明),签到题3题
第 46 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明),签到题3题
142 0