16 条题解

  • 1
    @ 2020-03-08 22:24:44

    好怀念啊,我记得自己出过FFF模拟赛的有一道题就是5、2、0表示来的...
    值得注意的是用4、7表示与用0、1表示的区别是每一位上4、7的贡献都多1,也就是1和2
    顺便一提,长度只是装饰,julao们是(故意装作)不会懂的()

    #include <iostream>
    using namespace std;
    
    int main()
    {
        const long long mo=1000000007;
        int ch, ans=0;
        cin>>ch;
        getchar();
        while(isdigit(ch=getchar()))
            ans=(ans*2+(ch=='7'?2:(ch=='4'?1:0)))%mo;
            //空间O(1),不存储字符串,直接由高位到低位计算
        cout<<ans;
    }
    

    以下是某在线IDE特供版:

    #include <iostream>
    using namespace std;
    
    int main()
    {
        const long long mo=1000000007;
        int ch, ans=0;
        ch=getchar();
        while(isdigit(ch))  ch=getchar();   //扔掉长度
        while(!isdigit(ch)) ch=getchar();   //扔掉换行符
        //大费周章是因为某在线IDE用的是\n\r,真的太屑了
        while(isdigit(ch))
            ans=(ans*2+(ch=='7'?2:(ch=='4'?1:0)))%mo, ch=getchar();
        cout<<ans;
    }
    
    
  • 0
    @ 2017-07-02 19:35:32

    wok水爆了,3星差不多

    #include<stdio.h>
    #define N 1000000007
    char s[100010];
    int main(){
        int n; scanf("%d%s",&n,s+1);
        for(int i=1;i<=n;++i) 
            s[i]=(s[i]=='4'?1:2);
        unsigned q=1,ans=0;
        for(int i=n;i;--i){
            ans+=q*s[i]; q<<=1;
            if(ans>N) ans%=N;
            if(q>N) q%=N;
        }
        printf("%u\n",ans);
    }
    
  • 0
    @ 2017-06-16 20:19:58

    把4、7换成1、2就很明显了
    1 4 1 1 = 1
    2 7 2 2 = 2*1
    3 44 11 3 = 2 + 1
    4 47 12 4 = 2 + 2*1
    5 74 21 5 = 2*2 + 1
    6 77 22 6 = 2*2 + 2*1
    7 444 111 7 = 4 + 2 + 1
    ......
    20 4747 1212 20 = 8 + 2*4 + 2 + 2*1

    所以直接快速幂

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    typedef long long LL;
    
    const int L=100005;
    const int mod=1000000007;
    int a[L],len;
    
    inline LL pow(int n)
    {
        LL ret=1,x=2;
        while (n)
        {
            if (n&1) ret=(ret*x)%mod;
            x=(x*x)%mod,n>>=1;
        }
        return ret;
    }
    
    int main()
    {
        scanf("%d",&len);
        getchar();
        for (int s=0;s<len;s++) a[len-s-1]=getchar()=='7'?2:1;
        LL ans=0;
        for (int s=0;s<L;s++) ans=(ans+a[s]*pow(s))%mod;
        printf("%I64d",ans);
    }
    
    
  • 0
    @ 2016-03-23 07:45:46

    我给正确率提高了1%
    49%==》50%

  • 0
    @ 2016-03-20 00:24:07

    水题一道。因为只有4和7,很容易让人想到二进制。考虑所有长度为 L 的数字(设这些数字的集合为S(L)): 如果我们把所有4换成0,所有7换成1,那么转换成的01串所代表的十进制,等于它在S(L)中的编号。例如
    \(
    \underbrace {44\cdots 44}_L \to \underbrace {00\cdots 00}_L = 0 \\
    774 \to 110 = 5
    \)

    确定数字在 S 中的编号后,只需加上所有长度小于 L 的数字的总数即可。总数由下式给出:
    \(
    \sum_{i=1}^{len-1} 2^i = 2^{len}-2
    \)

  • 0
    @ 2015-08-24 16:01:33

    总算是ac了,一句话 数学方法+找规律+二进制
    弱弱的代码参考如下
    var n,i:longint;s:ansistring;sum,k:int64;

    begin

    readln(n);readln(s);sum:=0;k:=1;

    for i:=1 to n-1 do

    begin

    k:=(k*2)mod 1000000007;

    sum:=(sum+k) mod 1000000007;

    end;

    k:=1;

    for i:=n downto 1 do

    begin

    if s[i]='7' then sum:=(sum+k) mod 1000000007;

    k:=(k*2)mod 1000000007;

    end;

    writeln(sum+1);

    end.

  • 0
    @ 2015-04-21 09:35:19

    数学研究每一位给予总ans的贡献。我们列举前6 或者更多的数研究,不难发现。每一位上的(第i位)4贡献2^(i-1),7贡献2^i

    例如4747

    贡献是2的1次方(第一位是7)+2的一次方+2的3次方+2的三次方,就是2+2+8+8=20

    那么怎么快速计算2的次幂的最大的问题
    如果我们每算一位就从1次方开始上去,时间复杂度大到o(n^2 / 2)肯定要爆。只能有4 50分

    我们不难发现。第一位无论是4还是7,要么是2的0次要么是1次。二第二位要么是1次,要么是2次。
    因此可以得出n的算法
    从个位枚举到最后一位。然后用一个sum记录当前的2的次幂。刚开始是2的0次、如果第一位是4.那么ans先+上sum,然后sum再乘2,因为下一位跟2的0次方没关系。可以放心乘。如果是7那么先乘后ans+sum(注意都要取模)。

    由此推广到所有的位。如果是4先+后乘,是7先乘后加,因此轻松秒杀此题

    ###pascal code
    program P1922;
    var len,ans,sum:int64;
    n:ansistring;
    i:longint;
    begin
    readln(len); read(n);
    sum:=1; ans:=0;
    for i:=len downto 1 do
    begin
    if n[i]='4' then
    begin
    ans:=(ans+sum) mod 1000000007; sum:=(sum shl 1) mod 1000000007;
    end;
    if n[i]='7' then
    begin
    sum:=(sum shl 1) mod 1000000007; ans:=(ans+sum) mod 1000000007;
    end;
    end;

    write(ans);
    end.

  • 0
    @ 2015-04-15 00:50:07

    ###block code
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define maxn 100005
    #define mod 1000000007
    char str[maxn];
    long long f[maxn],s[maxn];
    int main() {
    long long ans = 0;
    int len ,i = 0;scanf("%d",&len);
    f[1] = 2;
    for(int i=2;i<=len;i++) {
    f[i] = f[i-1]*2 % mod;
    }
    for(int i=1;i<=len;i++) {
    s[i] = (f[i]+s[i-1]) % mod;
    }
    //f[0] = 1;
    //f[i]表示长度为i+1的4串是第几个
    scanf("%s",str);
    ans = (s[len-1]+1)%mod;
    for(int i=0;i<len;i++)
    {
    if(str[i]=='7') {
    ans = (ans + f[len-i-1])%mod;
    if((len-i-1)==0)ans = (ans+1)%mod;
    }
    }
    if(str[0]=='7'&&len==1)printf("2\n");
    else printf("%lld\n",ans);
    return 0;
    }

  • 0
    @ 2015-04-15 00:47:48

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define maxn 100005
    #define mod 1000000007

    char str[maxn];
    long long f[maxn],s[maxn];

    int main() {
    long long ans = 0;
    int len ,i = 0;scanf("%d",&len);
    f[1] = 2;
    for(int i=2;i<=len;i++) {
    f[i] = f[i-1]*2 % mod;
    }
    for(int i=1;i<=len;i++) {
    s[i] = (f[i]+s[i-1]) % mod;
    }
    //f[0] = 1;
    //f[i]表示长度为i+1的4串是第几个
    scanf("%s",str);
    ans = (s[len-1]+1)%mod;
    for(int i=0;i<len;i++)
    {
    if(str[i]=='7') {
    ans = (ans + f[len-i-1])%mod;
    if((len-i-1)==0)ans = (ans+1)%mod;
    }
    }
    if(str[0]=='7'&&len==1)printf("2\n");
    else printf("%lld\n",ans);
    return 0;
    }
    //ans = (ans+1)%mod;

  • 0
    @ 2015-02-21 00:19:37

    P1922木姑娘的生日
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1922 木姑娘的生日
    递交时间 2015-02-21 00:18:48
    代码语言 C++
    评测机 VijosEx
    消耗时间 60 ms
    消耗内存 380 KiB
    评测时间 2015-02-21 00:18:50

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 380 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 380 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 376 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 380 KiB, score = 10

    测试数据 #4: Accepted, time = 15 ms, mem = 380 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 380 KiB, score = 10

    测试数据 #6: Accepted, time = 15 ms, mem = 376 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 380 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 380 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 376 KiB, score = 10

    Accepted, time = 60 ms, mem = 380 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>

    using namespace std;

    int len;
    char s[ 100000 + 10 ];
    const int modd = 1000000007;
    long long present;
    long long ans;
    int i;

    int main()
    {
    scanf( "%d" , &len );
    scanf( "%s" , s );
    present = 1;
    for( i = len - 1 ; i >= 0 ; i-- )
    {
    if( s[i] == '4' )
    ans += present;
    else
    ans += present * 2;
    ans %= modd;
    present *= 2;
    present %= modd;
    }
    cout << ans << endl;
    return 0;
    }

  • 0
    @ 2015-02-17 21:10:29

    #include<cstdio>
    int tot=1,sum=0;
    int len,a[100100]={0};
    int main()
    {
    scanf("%d",&len);
    for(int i=1;i<=len;i++) scanf("%1d",&a[i]);
    for(int i=1;i<len;i++)
    {
    tot*=2;tot%=1000000007;
    sum+=tot;sum%=1000000007;
    }
    int x=1;
    for(int i=len;i>=1;i--){
    if(a[i]==7) sum+=x,sum%=1000000007;
    x*=2;x%=1000000007;
    }
    printf("%d",sum+1);
    return 0;
    }

  • 0
    @ 2015-02-17 16:24:31

    直接考虑每一位的4或者7对这个数的index所产生的贡献,
    从最高位开始扫,若第k位是4,则ans+=2^(k-1),若第k位是7,则ans+=2*2^(k-1),

    ###Code
    #include<cstdio>
    const int MOD=1000000007;
    char s[100005];
    int main()
    {
    int n;
    scanf("%d",&n);
    scanf("%s",s);
    int ans=0;
    for(int i=0;i<=n-1;i++)
    {
    if(s[i]=='4')
    {
    ans=(ans*2+1)%MOD;
    }
    else
    {
    ans=(ans*2+2)%MOD;
    }
    }
    printf("%d",ans);
    }

  • 0
    @ 2015-02-16 23:11:46

    二进制数(递推)+2^1en-1即可

    Pascal Code

    var
    i,len,t,ans:longint;
    n:array[1..100000] of longint;
    c:char;
    begin
    readln(len);
    for i:=1 to len do
    begin
    read(c);
    if c='4' then n[i]:=0 //4对应0
    else n[i]:=1; //7对应1
    end;
    t:=1;
    ans:=0;
    for i:=len downto 1 do
    begin
    ans:=(ans+n[i]*t) mod 1000000007;

    t:=t<<1 mod 1000000007; //递推
    end;
    ans:=(ans+t) mod 1000000007;
    writeln((ans-1) mod 1000000007);
    end.

  • 0
    @ 2015-02-16 01:12:31

    显然位数为k的幸运数共有2^k个, 且44...4(k个4)是k位的幸运数中最小的, 它的编号为2+2^2+...+2^(k-1)+1=2^k-1. 然后对随便一个k位幸运数而言, 只要把4看成0把7看成1得出来的二进制数即为它与k个4的编号之差. 所以就拿k个4的编号加上这个二进制数即可. 弄个2的快速幂就行了. 底下那位估计是忘了用64位整数...

    • @ 2015-02-16 23:09:04

      k最大是100000,真的要用快速幂吗?

  • 0
    @ 2015-02-15 23:44:24

    谁发下题解,为什么我只有20分。- -不明白。

    擦,到底是哪里有问题,求大神告诉下吧。。。

  • 0
    @ 2015-02-13 21:50:14

    1234

  • 1

信息

ID
1922
难度
3
分类
其他 | 数学 点击显示
标签
(无)
递交数
267
已通过
130
通过率
49%
被复制
1
上传者