A题
求字符串ASCII码之和，遍历即可。
B题
我的方法是先猜一个数，然后向两边递推，用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题
对于长度len，我们要知道len所有的因子 fac，可以分解成的三边互质的三角形种类数，和len/fac的分组种类。
后者是2^(len/fac)，也就是插板问题...
前者我的方法是预处理：
先不管互质的问题，如果我们就针对一个长度 L求他可以分解成的三角形种类数。我们可以枚举最长边Lmax。
然后以Lmax为最长边的三角形一共有 Lmax - ceil((L-Lmax)/2) + 1个。也就是枚举次长边。
这样的话，对于每个L，最长边可取范围一定是一个区间，我们可以通过L-1的区间来推出L的区间。
我们可以看出，L增加1的话，对于不变的Lmax，Lmax - ceil((L-Lmax)/2) + 1要么不变，要么变化了1。和奇偶性有关。
于是这个我们也可以维护了。。。。
于是非互质的问题求出来了。
接下来，假设f(L)是非互质的情况，那么互质的性况应该是g(L) = f(L) - sum(g(K));其中K是L的因子。
这个东西可以用筛法来搞，复杂度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不会
I题
还是枚举因子，递推预处理。。。
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题
大陈题。。。 根据剩余类建图广搜。。。
posted on 2012-11-17 23:04
西月弦 阅读(1125)
评论(6) 编辑 收藏 引用 所属分类:
解题报告