题解 - Vijos

1

苛性氢 LV 9 @ 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

!TNT! LV 8 @ 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

HummaS LV 8 @ 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

三次元❤堕天逗比 LV 10 @ 2016-03-23 07:45:46

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

0

wang_yanheng LV 10 @ 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

niyinchen LV 9 @ 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

冲啊小笼包 LV 9 @ 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

民逗公知 LV 8 @ 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

民逗公知 LV 8 @ 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

nzhtl1477 LV 10 @ 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

huyating LV 8 @ 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

quailty LV 9 @ 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

q234rty LV 10 @ 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

o0数学迷0o LV 8 @ 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位整数...

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

k最大是100000，真的要用快速幂吗？

0

冲啊小笼包 LV 9 @ 2015-02-15 23:44:24

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

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

0

yingjiangyu LV 9 @ 2015-02-13 21:50:14

1234

题解

16 条题解

Pascal Code

木姑娘的生日

信息

状态

开发

支持

题解

16 条题解

Pascal Code

木姑娘的生日

信息

状态

开发

支持

还没有账户？

登录