16 条题解
-
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; }
-
02017-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); }
-
02017-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); }
-
02016-03-23 07:45:46@
我给正确率提高了1%
49%==》50% -
02016-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
\) -
02015-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.
-
02015-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. -
02015-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;
} -
02015-04-15 00:47:48@
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 100005
#define mod 1000000007char 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; -
02015-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;
} -
02015-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;
} -
02015-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);
} -
02015-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. -
02015-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位整数...
-
02015-02-15 23:44:24@
谁发下题解,为什么我只有20分。- -不明白。
擦,到底是哪里有问题,求大神告诉下吧。。。
-
02015-02-13 21:50:14@
1234
- 1