题解 - Vijos

2

^ambition LV 8 @ 2019-02-10 11:58:30

公式很容易推出来，主要是在n=3的时候容易超时，因此对于n=3的情况要用快速幂。整个程序套高精度模板即可。代码比较长，主要是高精度那块长。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=10005;/*精度位数,自行调整*/
//1.如果需要控制输出位数的话，在str()里面把len调成需要的位数
//2.很大的位数是会re的，所以如果是幂运算的话，如 计算x^p的位数n, n=p*log(10)x+1;(注意要加一）
//3.还可以加上qmul，取模的过程也就是str()，c_str()再搞一次
class bign
{
    //io*2 bign*5*2 bool*6
    friend istream& operator>>(istream&,bign&);
    friend ostream& operator<<(ostream&,const bign&);
    friend bign operator+(const bign&,const bign&);
    friend bign operator+(const bign&,int&);
    friend bign operator*(const bign&,const bign&);
    friend bign operator*(const bign&,int&);
    friend bign operator-(const bign&,const bign&);
    friend bign operator-(const bign&,int&);
    friend bign operator/(const bign&,const bign&);
    friend bign operator/(const bign&,int&);
    friend bign operator%(const bign&,const bign&);
    friend bign operator%(const bign&,int&);
    friend bool operator<(const bign&,const bign&);
    friend bool operator>(const bign&,const bign&);
    friend bool operator<=(const bign&,const bign&);
    friend bool operator>=(const bign&,const bign&);
    friend bool operator==(const bign&,const bign&);
    friend bool operator!=(const bign&,const bign&);
public:
    int len,s[maxn];
    bign()
    {
        memset(s,0,sizeof(s));
        len=1;
    }
    bign operator=(const char* num)
    {
        int i=0,ol;
        ol=len=strlen(num);
        while(num[i++]=='0'&&len>1)
            len--;
        memset(s,0,sizeof(s));
        for(i=0; i<len; i++)
            s[i]=num[ol-i-1]-'0';
        return *this;
    }
    bign operator=(int num)
    {
        char s[maxn];
        sprintf(s,"%d",num);
        *this=s;
        return *this;
    }
    bign(int num)
    {
        *this=num;
    }
    bign(const char* num)
    {
        *this=num;
    }
    string str() const
    {
        string res="";
        for(int i=0; i<len; i++)
            res=char(s[i]+'0')+res;
        if(res=="")
            res="0";
        return res;
    }
};
bool operator<(const bign& a,const bign& b)
{
    int i;
    if(a.len!=b.len)
        return a.len<b.len;
    for(i=a.len-1; i>=0; i--)
        if(a.s[i]!=b.s[i])
            return a.s[i]<b.s[i];
    return false;
}
bool operator>(const bign& a,const bign& b)
{
    return b<a;
}
bool operator<=(const bign& a,const bign& b)
{
    return !(a>b);
}
bool operator>=(const bign& a,const bign& b)
{
    return !(a<b);
}
bool operator!=(const bign& a,const bign& b)
{
    return a<b||a>b;
}
bool operator==(const bign& a,const bign& b)
{
    return !(a<b||a>b);
}
bign operator+(const bign& a,const bign& b)
{
    int up=max(a.len,b.len);
    bign sum;
    sum.len=0;
    for(int i=0,t=0;t||i<up; i++)
    {
        if(i<a.len)
            t+=a.s[i];
        if(i<b.len)
            t+=b.s[i];
        sum.s[sum.len++]=t%10;
        t/=10;
    }
    return sum;
}
bign operator+(const bign& a,int& b)
{
    bign c=b;
    return a+c;
}
bign operator*(const bign& a,const bign& b)
{
    bign res;
    for(int i=0; i<a.len; i++)
    {
        for(int j=0; j<b.len; j++)
        {
            res.s[i+j]+=(a.s[i]*b.s[j]);
            res.s[i+j+1]+=res.s[i+j]/10;
            res.s[i+j]%=10;
        }
    }
    res.len=a.len+b.len;
    while(res.s[res.len-1]==0&&res.len>1)
        res.len--;
    if(res.s[res.len])
        res.len++;
    return res;
}
bign operator*(const bign& a,int& b)
{
    bign c=b;
    return a*c;
}
//只支持大数减小数
bign operator-(const bign& a,const bign& b)
{
    bign res;
    int len=a.len;
    for(int i=0; i<len; i++)
    {
        res.s[i]+=a.s[i]-b.s[i];
        if(res.s[i]<0)
        {
            res.s[i]+=10;
            res.s[i+1]--;
        }
    }
    while(res.s[len-1]==0&&len>1)
        len--;
    res.len=len;
    return res;
}
bign operator-(const bign& a,int& b)
{
    bign c=b;
    return a-c;
}
bign operator/(const bign& a,const bign& b)
{
    int i,len=a.len;
    bign res,f;
    for(i=len-1; i>=0; i--)
    {
        f=f*10;
        f.s[0]=a.s[i];
        while(f>=b)
        {
            f=f-b;
            res.s[i]++;
        }
    }
    while(res.s[len-1]==0&&len>1)
        len--;
    res.len=len;
    return res;
}
bign operator/(const bign& a,int& b)
{
    bign c=b;
    return a/c;
}
bign operator%(const bign& a,const bign& b)
{
    int len=a.len;
    bign f;
    for(int i=len-1; i>=0; i--)
    {
        f=f*10;
        f.s[0]=a.s[i];
        while(f>=b)
            f=f-b;
    }
    return f;
}
bign operator%(const bign& a,int& b)
{
    bign c=b;
    return a%c;
}
bign& operator+=(bign& a,const bign& b)
{
    a=a+b;
    return a;
}
bign& operator-=(bign& a,const bign& b)
{
    a=a-b;
    return a;
}
bign& operator*=(bign& a,const bign& b)
{
    a=a*b;
    return a;
}
bign& operator/=(bign& a,const bign& b)
{
    a=a/b;
    return a;
}
bign& operator++(bign& a)
{
    a=a+1;
    return a;
}
bign& operator++(bign& a,int)
{
    bign t=a;
    a=a+1;
    return t;
}
bign& operator--(bign& a)
{
    a=a-1;
    return a;
}
bign& operator--(bign& a,int)
{
    bign t=a;
    a=a-1;
    return t;
}
istream& operator>>(istream &in,bign& x)
{
    string s;
    in>>s;
    x=s.c_str();
    return in;
}
ostream& operator<<(ostream &out,const bign& x)
{
    out<<x.str();
    return out;
}

int main(){
    int n,k,mask=1,l3;
    char s[maxn];
    bign l,tot,cur,b;
    scanf("%d %s",&n,s);
    tot = n; l = s; k = 1; b = 2;
    if(n==1){
        if(l==1) cout<<1;
        else cout<<-1;
        return 0;
    }else if(n==2){
        if(l<=3) cout<<l;
        else cout<<-1;
        return 0;
    }else if(n==3){
        l3 = 0;
        for(int i=l.len-1;i>=0;i--){
            l3 *= 10;
            l3 += l.s[i];
        }
        k = (l3-1)/3;
        b = 2; tot = 1;
        while(mask<=k){
            if(mask&k) tot *= b;
            b = b*b;
            mask <<= 1;
        }
        tot *= 2;
        tot = tot-2+l3-3*k;
        cout<<tot;
        return 0;
    }
    while(tot<l){
        ++k;
        tot += b*n-(b-1)*3;
        b *= 2;
    }
    k--; b /= 2;
    tot -= b*n-(b-1)*3;
    cout<<l-tot+b*2-2;
    return 0;
}

2

jsydtc LV 3 @ 2008-11-10 10:51:07

推公式……

设第k个集合第一个元素是h(k)，最后一个元素是t(k)，显然第k个集合元素总数s(k)=t(k)-h(k)+1,又有t(k)=t(k-1)+t(k-1)-1=2t(k-1)-1;hk=2h(k-1)+1;所以通项t(k)=2^(k-1)*(n-1)+1;h(k):=2^k-1;s(k)=t(k)-h(k)+1;带入整理。

然后设sum(k)=s(1)+s(2)……s(k);2sum(k):=2s(1)+2s(2)……2s(k);

两边做差，整理得sum=(n-3)*2^k+3*(k+1)-n;

然后二分枚举k，计算2^k时再用快速幂就行了。

1

zhh1993 LV 10 @ 2009-09-10 17:07:44

不玩了...用了最直接的模拟.....

写了200+行,都压到1000000000了还那么慢....

ORZ flower 和怪盗基德啊~~

注意：高精运算总计算出来的数值可能不只10^1000....

0

Markiplier LV 8 @ 2020-05-02 09:53:14

n, k = list(map(int, input().strip().split(' ')))
interval = [1, n]
current = 0

while (k - current + interval[0] - 1 > interval[1]):
    if interval[0] == interval[1]:
        print(-1)
        exit()
    current += interval[1] - interval[0] + 1
    interval[0] = interval[0] * 2 + 1
    interval[1] = interval[1] * 2 - 1
    
print(k - current + interval[0] - 1)

0

eh5 LV 7 @ 2018-03-04 23:23:45

虽然推出了算式,但还是无法AC...应该是精度问题..
5,6:10 过不去..

#include <iostream>

typedef unsigned long long int ull;

using namespace std;
ull n,k;

ull sum(ull i){
    return (n-3llu)*((1llu<<i)-1llu) +3llu*i;
}
int main(){
    long long int s_n,s_k; 
    scanf("%lld %lld",&s_n,&s_k);
    if(s_n<1 || s_k <1){

        cout<<-1;
        return 0;
    }
    n = (ull) s_n;
    k = (ull) s_k; 
        if(n <= 2llu) {
        if (k>2llu*n-1llu) 
            cout<<-1;
        else
            cout<<k;
        
        return 0;
    }
    ull i;
    for( i=1llu;;i<<=1llu){
        if(sum(i)>=k) break;
    }
    if(i == 1llu) {;
        cout<<k;
        return 0;
    }
    
    ull l = i/2llu +1llu,mid=i,r=(mid<<2llu)-l;
    while(l<r){
        if(l == mid) break;

        if(sum(mid)>=k){
            if(sum(mid-1)<k){
                l=mid;
                break;
            }else
                r = mid; 
        }
        else
            l = mid;
        mid = (l+r)/2llu;
    }
    i = l;
    cout<<(1llu<<i) -2llu -sum(i-1llu) + k;
    return 0;
}

0

hhdllhflower LV 10 @ 2009-07-07 00:14:46

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

巨猥琐的！！！！！！！！

想吐血

0

怪盗~基德 LV 10 @ 2009-06-19 22:30:12

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 150ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：150ms

VAG真不给面子。。。。。。

一开始用longint压到100000000进制，可恶的VAG竟然给我超时，一气之下用了int64压到了1000000000000000000进制（极限了），VAG终于给AC。。。。。。

我代码比较简短，才138行的3.30KB，输出真是赏心悦目。

write(k[k[0]]);

for i:=k[0]-1 downto 1 do

if k[i]>99999999999999999 then write(k[i]) else

if k[i]>9999999999999999 then write('0',k[i]) else

if k[i]>999999999999999 then write('00',k[i]) else

if k[i]>99999999999999 then write('000',k[i]) else

if k[i]>9999999999999 then write('0000',k[i]) else

if k[i]>999999999999 then write('00000',k[i]) else

if k[i]>99999999999 then write('000000',k[i]) else

if k[i]>9999999999 then write('0000000',k[i]) else

if k[i]>999999999 then write('00000000',k[i]) else

if k[i]>99999999 then write('000000000',k[i]) else

if k[i]>9999999 then write('0000000000',k[i]) else

if k[i]>999999 then write('00000000000',k[i]) else

if k[i]>99999 then write('000000000000',k[i]) else

if k[i]>9999 then write('0000000000000',k[i]) else

if k[i]>999 then write('00000000000000',k[i]) else

if k[i]>99 then write('000000000000000',k[i]) else

if k[i]>9 then write('0000000000000000',k[i]) else

write('00000000000000000',k[i]);

writeln;

0

雷欧纳德 LV 3 @ 2008-11-12 19:11:00

高精减……不熟悉，WA了N次...T_T

0

wxy_huaian LV 3 @ 2008-11-10 21:47:36

第5个点cheat

0

pzy3303 LV 10 @ 2008-11-10 19:27:09

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

dragon上测的，效率不错，不过。。代码超级恶心。。6kb。。编的要吐血了

program pro3;

const maxn =1100;

maxnum =10000000; {7}

type node=array[0..1,0..maxn] of int64;

var n :longint;

num,Read_in :array[0..maxn] of int64;

f,g :node;

ans :longint;

Tot,t0 :array[0..maxn] of int64;

n0 :array[1..20,0..maxn*100] of int64;

n1 :array[1..20] of int64;

ans_out,c :array[0..maxn*100] of int64;

function max(i,j:longint):longint;

begin

if i>j then exit(i) else exit(j);

end;

function work(i:longint):longint;

begin

if i mod 7=0 then exit(i div 7)

else exit(i div 7+1);

end;

procedure swap(var i,j:int64);

var t:int64;

begin

t:=i; i:=j; j:=t;

end;

procedure cheng(a,b,c:longint);

var i,j:longint;

begin

for i:=1 to n0 do

for j:=1 to n0[c,0] do

begin

inc(n0[a,i+j-1],n0*n0[c,j]);

inc(n0[a,i+j],n0[a,i+j-1] div maxnum);

n0[a,i+j-1]:=n0[a,i+j-1] mod maxnum;

end;

n0[a,0]:=n0+n0[c,0];

if n0[a,n0[a,0]]=0 then dec(n0[a,0]);

end;

procedure cheng_num(x:longint);

var i,j:longint;

begin

fillchar(c,sizeof(c),0);

for i:=1 to ans_out[0] do

for j:=1 to n0[x,0] do

begin

inc(c,ans_out[i]*n0[x,j]);

inc(c,c div maxnum);

c:=c mod maxnum;

end;

c[0]:=ans_out[0]+n0[x,0];

if c[c[0]]=0 then dec(c[0]);

ans_out:=c;

end;

procedure solve_3(a,b:longint);

var i:longint;

begin

n1[1]:=1; n0[1,1]:=2; n0[1,0]:=1;

for i:=2 to 16 do

begin

n1[i]:=n1*2;

cheng(i,i-1,i-1);

end;

ans_out[1]:=1; ans_out[0]:=1;

while a0 do

begin

for i:=16 downto 1 do

if n1[i]

0

cgy4ever LV 10 @ 2008-11-10 18:33:45

昨天比赛的时候就猜到有

3 90000

就跟本地算出答案贴上去的

不料当时数组开小了,居然要9k位,我就弄到5k位

0

lemon_cn LV 3 @ 2008-11-10 18:28:07

n=3时要特判

其他和题解一模一样，但是我就纳闷TN的程序效率好高...我的就不行，慢的要1s多

Orz tangky...

(话说C++的效率...还是用pascal写好)

0

orz教主_tangky LV 7 @ 2008-11-10 23:32:30

第4题在1422

0

boyzkk LV 10 @ 2008-11-10 14:58:08

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 462ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：462ms

慢了。。。比赛是用QWORD50分！

0

voyagec2 LV 10 @ 2008-11-10 13:52:35

过的比较委琐。。

比赛的时候80分。。

第五个点是3 90000

高精压位很难弄到0S

这点楼下正解

建议Cheat

不过Cheat貌似也有难度

数有几千位长

从汤牛那问来的

第五个点答案是2^30000+1

所以。。。

0

ipip2005 LV 10 @ 2008-11-10 13:46:17

第5点只能快速幂才能0ms

0

wu3412790 LV 10 @ 2008-11-10 13:42:41

我过了，太好了，N=3时套用MASON数的程序，其他简单

0

Honiess LV 6 @ 2008-11-10 14:21:33

让我过去吧……阿门……

0

喷气式纸飞机 LV 7 @ 2008-11-10 13:01:27

数据很弱

第五个点直接蒙出来

0

linshutan LV 3 @ 2008-11-10 11:29:28

LX正解.

　超时的试下这个数据 3 90000

题解

40 条题解

教主的集合序列

信息

状态

开发

支持

题解

40 条题解

教主的集合序列

信息

状态

开发

支持

还没有账户？

登录