好久没写博客了,也可以说好久没有怎么刷题了,本来就是一个不怎么善于表达的人。。。上次和钢牛一块做topcoder竟然写的代码一直没有过编译器,无语了!最近一直在忙于考试复习,直到今天终于到一段落了,所以在想起来了cf上不会做的题,说实话,一看是大数据怎么也没想出来,后来看了别人的代码页看不懂到底为什么要这么写的,后来的后来看到说打表找规律,我想我最近真的是很不在状态,最基本的都忘了,所以打表找到规律一切就可以解决了,算了,贴下代码吧!不然都不知道该说些甚么了,还有,就是最近实在太热啦~
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<vector> #include<climits> using namespace std; #define rep(i,n) for(int i=0; i<(n); i++) #define repf(i,n,m) for(int i=(n); i<=(m); i++)//正循环的 #define repd(i,n,m) for(int i=(n); i>=(m); i--) //负循环的 #define fab(a) ((a)>0?(a):(0-(a))) #define ll long long #define arc(a) ((a)*(a)) #define inf 1000000007 //最大值的 #define exp 0.0000001 //浮点型的 #define N 105 //记录开的数组 ll a[N]; char s[N]; int main() { a[0]=1; repf(i,1,100) a[i]=a[i-1]*2%inf; while(cin>>s) { int len=strlen(s); ll ans=0; ll temp=0; int j=0; repd(i,len-1,0) { if(s[i]=='1') ans=(ans+a[j]*a[len-1]%inf)%inf; ++j; } cout<<ans<<endl; } return 0; }
下面的是dp的思路,确实dp不怎么样,对于一个字符串S,如果s的前面加上字符'0',则1与其异或为1,0与其异或为1,所以就是只会在原来的基础上加倍,所以s[n+1]=s[n]*2;
如果在其前面加上字符'1',0与其异或为1,1与其异或为0,则说明在原来的基础上又增加了一部分,则与其异或的数开头为0的数的结果都比开头为1的数大,而开头为0的书的个数为2^n个,开头为1的数的个数为2^n个,所以总数为4^n个,所以s[n+1]=s[n]*2+4^n;
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<vector> #include<climits> using namespace std; #define rep(i,n) for(int i=0; i<(n); i++) #define repf(i,n,m) for(int i=(n); i<=(m); i++)//正循环的 #define repd(i,n,m) for(int i=(n); i>=(m); i--) //负循环的 #define fab(a) ((a)>0?(a):(0-(a))) #define ll long long #define arc(a) ((a)*(a)) #define inf 1000000007 //最大值的 #define exp 0.0000001 //浮点型的 #define N 100 //记录开的数组 int main() { char s[N+10]; ll a[N+10]; a[0]=1; repf(i,1,100) a[i]=a[i-1]*4%inf; while(cin>>s) { int len=strlen(s); ll ans=0; int j=0; repd(i,len-1,0) { if(s[i]=='0') ans=ans*2%inf; else ans=(ans*2+a[j])%inf; ++j; } cout<<ans<<endl; } return 0; }