A題
求字符串ASCII碼之和，遍歷即可。
B題
我的方法是先猜一個(gè)數(shù)，然后向兩邊遞推，用long double剛好卡過~
B
1 #include<cmath>
2 #include<cstdio>
3 #include<iostream>
4 using namespace std;
5 const int M = 200005*2;
6 double lg[M];
7 double work(double p,int n){
8 double s = (n+1) * log(p);
9 double ans = n*exp(s);
10 for(int k = 1; k <= n; k++) {
11 s += log(1-p) + lg[n + k] - lg[k];
12 ans += (n-k) * exp(s);
13 //cout<<ans<<endl;
14 }
15 return ans;
16 }
17 int main(){
18 int n,tst=1; double p;
19 for(int i = 1; i < M; i++) lg[i] = log(i);
20 while (~scanf("%d%lf",&n,&p)){
21 double ans = work(p,n) + work(1-p,n);
22 printf("Case %d: %.6lf\n",tst++,ans);
23 }
24 }
25 C題
對(duì)于長(zhǎng)度len，我們要知道len所有的因子 fac，可以分解成的三邊互質(zhì)的三角形種類數(shù)，和len/fac的分組種類。
后者是2^(len/fac)，也就是插板問題...
前者我的方法是預(yù)處理：
先不管互質(zhì)的問題，如果我們就針對(duì)一個(gè)長(zhǎng)度 L求他可以分解成的三角形種類數(shù)。我們可以枚舉最長(zhǎng)邊Lmax。
然后以Lmax為最長(zhǎng)邊的三角形一共有 Lmax - ceil((L-Lmax)/2) + 1個(gè)。也就是枚舉次長(zhǎng)邊。
這樣的話，對(duì)于每個(gè)L，最長(zhǎng)邊可取范圍一定是一個(gè)區(qū)間，我們可以通過L-1的區(qū)間來推出L的區(qū)間。
我們可以看出，L增加1的話，對(duì)于不變的Lmax，Lmax - ceil((L-Lmax)/2) + 1要么不變，要么變化了1。和奇偶性有關(guān)。
于是這個(gè)我們也可以維護(hù)了。。。。
于是非互質(zhì)的問題求出來了。
接下來，假設(shè)f(L)是非互質(zhì)的情況，那么互質(zhì)的性況應(yīng)該是g(L) = f(L) - sum(g(K));其中K是L的因子。
這個(gè)東西可以用篩法來搞，復(fù)雜度O(nlogn)。
問題解決。
C
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int n;
5 const int N = 5000005;
6 const int mod = (int)1e9+7;
7 typedef long long ll;
8 int dp[N],flag[N];
9 inline int cal(int len,int r){
10 int a = r - (len/2 + len%2) + 1;
11 return a;
12 }
13 int main(){
14 int l = 1,r = 1; int s = 1;
15 for(int i = 3; i < N; i++){
16 flag[i] = s;
17 int even,odd;
18 if((l&1)!=(r&1)) {
19 even = odd = (r-l+1)/2;
20 } else {
21 if((l&1) == (i&1)) even = (r - l + 1) / 2 + 1, odd = even - 1;
22 else odd = (r - l + 1) /2 + 1, even = odd - 1;
23 }
24 s = (s - even + mod ) % mod;
25 if(~i&1) { r++;
26 s = (s + cal(i+1-r,r)) % mod;
27 }
28 if(i%3==0) {
29 s = (s - cal(i+1-l,l) + mod) % mod;
30 l++;
31 }
32 }
33 for(int i = 3; i < N; i++)
34 for(int j = i+i; j < N; j+=i)
35 flag[j] = (flag[j] - flag[i] + mod) % mod;
36 dp[1] = 1;
37 for(int i = 2;i < N; i++) {
38 dp[i] = 2*dp[i-1]%mod;
39 }
40 //return 0;
41 int cas = 0;
42 while(~scanf("%d",&n)){
43 printf("Case %d: ",++cas);
44 ll ans = 0;
45 for(int i = 1; i*i <= n; i++) if(n%i==0){
46 ans = (ans + 1LL*flag[i] * dp[n/i])%mod;
47 if(i * i != n){
48 ans = (ans + 1LL*flag[n/i] * dp[i]) % mod;
49 }
50 }
51 printf("%d\n", (int)ans);
52 }
53 }
54 DEFGHJ不會(huì)
I題
還是枚舉因子，遞推預(yù)處理。。。
I
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 const int N = 1001;
5 const int mod = (int)1e9+7;
6 int ans[N];
7 int main(){
8 int n;
9 ans[1] = 1;
10 for(int i = 2; i < N; i++) {
11 int v = i - 1;
12 for(int j = 1; j * j <= v; j++) if(v % j == 0) {
13 ans[i] = (ans[i] + ans[j]) % mod;
14 if(j*j!=v) ans[i] = (ans[i] + ans[v/j]) % mod;
15 }
16 }
17 int tst = 1;
18 while(~scanf("%d",&n)) {
19 printf("Case %d: %d\n",tst++,ans[n]);
20 }
21 }
22 K題
大陳題。。。 根據(jù)剩余類建圖廣搜。。。
posted on 2012-11-17 23:04
西月弦 閱讀(1137)
評(píng)論(6) 編輯 收藏 引用 所屬分類:
解題報(bào)告