高精度乘法-17南宁区域赛F -The Chosen One

佚名 7年前 (2019-04-10) 随笔 1397人围观抢沙发百度已收录

题目大意：给你一个n，然后从1~n隔一个选一个，挑出一个集合然后从集合中继续隔一个挑一个，直到只有一个数，问最后一个数是多少？2<=n<=10⁵⁰

例如n=5,先选出2，4最后选择4。n=12,先选出2，4，6，8，10，12，再选出4，8，12在选出8。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

可以发现这个数字一定是偶数，并且是比n小中被2除最多次的一个数，所以发现就是找一个2的幂次的小于n的最大的数。代码如下：

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream>
using namespace std; string a[100005]; int t[1000005]; bool judge(string n,string a) { if(n.size()<a.size()) return true; else if(n.size()==a.size()) { for(int i=0; i<a.size(); i++) { if(n[i]<a[i]) return true; if(n[i]>a[i]) return false; } } return false; } string fun(string a) { memset(t,0,sizeof(t)); for(int i=1; i<=a.size(); i++) t[i]=(a[a.size()-i]-'0')*2; for(int i=1; i<=a.size(); i++) if(t[i]>=10) { t[i+1]+=t[i]/10; t[i]=t[i]%10; } int len=a.size()+1; string a1; while(t[len]==0) { len--; } for(int i=len; i>=1; i--) { a1+=('0'+t[i]); } return a1; } int main() { int t; cin>>t; string n; a[1]+='2'; while(t--) { cin>>n; for(int i=1;; i++) { if(judge(n,a[i])) { cout<<a[i-1]<<endl; break; } else { if(a[i+1].size()==0) a[i+1]=fun(a[i]); } } } }