算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
之前一直考试,没有更新Blog,今天把考离散前一天做的CF总结一下。

A
问[l,r]区间内,有多少个数的首位和末位相等。l,r < 10 ^ 18。
算法分析:
    
    子问题是求小于X的这样的数。
    枚举构造数位的长度,数的首末位。 然后验证是否小于X。 难点在于边界,不太好写。
 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 ll base[20];
 5 int n,tp,ed,flag;
 6 int count(ll x){
 7     int ans = 0;
 8     ed = x% 10;
 9     while(x){
10         tp = x % 10;
11         ans++, x/=10; 
12     }
13     return ans;}
14 ll cal(ll x){
15     x /= 10;
16     ll t = 1;
17     ll ans = 1;
18     while(x > 9) {
19         ans += x%10*t;
20         x/=10; t*=10;
21     }
22 //    cout<<x<<" "<<ans<<endl;
23     return ans;
24 }
25 ll solve(int d, int len, ll x){
26     n = count(x);
27     if(n > len || (tp > d && n==len) ) {
28 //        cout<<len-2<<" "<<base[len-2]<<endl;
29         return base[len-2];
30     }
31     if(len > n || tp < d) { flag = 1; return 0; }
32     if(ed >= d) return cal(x);
33     while( x%10 != tp) x--;
34     return solve(d,len,x);
35 }
36 ll work(ll x){
37     if(x <= 9) return x;
38     ll ans = 9;
39     flag = 0;
40     for(int len = 0; ; len ++){
41         for(int i=1;i<=9;i++){
42             ans += solve(i,len+2,x);
43             if(flag) return ans;
44     //        cout<< debug(i,len)<<endl;;
45 //            cout<<i<<" "<<len<<" "<<ans<<endl;
46         }
47     }
48 }
49 int main(){
50     ll a,b;
51     base[0] = 1;
52     for(int i=1;i<20;i++) base[i] = base[i-1] * 10;
53 //    while(cin >> a) cout<< work(a) <<endl;
54     cin >> a >> b;
55     cout<< work(b) - work(a-1) << endl;
56 }
57 
B
有N(N<100,000)张卡片,每张卡片正反面都有颜色。 请问将卡片翻转后,最多的颜色的比例至少是1/2的最小翻转次数。
算法分析:
    颜色的数量是1,000,000,000。需要离散化。
    
    然后枚举每个颜色O(1)时间判断翻转的代价。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N = 100005;
 6 int hash[N<<1], n, num[N][2], flag[N<<1][2],M,mnt[N<<1];
 7 int find(int v){
 8     int l = 0, r = M;
 9     while(l<r){
10         int mid = l+r >> 1;
11         if(hash[mid] >= v) r = mid;
12         else l = mid + 1;
13     }
14 //    cout<<"find : "<<v<<" "<<l<<endl;
15     return l;
16 }
17 int main(){
18     while(~scanf("%d",&n)){
19         int len = 0;
20         for(int i=0;i<n;i++) {
21             scanf("%d%d",&num[i][0],&num[i][1]);
22             hash[len ++] = num[i][0];
23             hash[len ++] = num[i][1];
24         }
25         sort(hash,hash+len);
26         M = 1;
27         for(int i=1;i<len;i++){
28             if(hash[i]!=hash[i-1])
29                 hash[M++] = hash[i];
30         }
31         for(int i=0;i<M;i++) mnt[i] = flag[i][0] = flag[i][1] = 0;
32         for(int i=0;i<n;i++){
33             int l = find(num[i][0]);
34             int r = find(num[i][1]);
35             if(l==r) mnt[l] ++;
36             else {flag[l][0] ++;
37                   flag[r][1] ++;}
38         }
39         int ans= -1;
40         int suma = n/2 + (n&1);
41 //        cout<< sum<<endl;
42         for(int i=0;i<M;i++){
43             int S,sum = suma-mnt[i];
44 //            cout<<hash[i]<<" " << flag[i][0] <<" "<< flag[i][1] <<endl;
45             if(flag[i][0]+flag[i][1]<sum) continue;
46             if(flag[i][0] >= sum) S = 0;
47             else S = sum - flag[i][0];
48             if(ans == -1 || ans > S) ans = S;
49 //            cout<< hash[i] << " "<< S<<endl;
50         }
51         cout<< ans<<endl;
52     }
53 }
54 
C
有两个长度为 200,000的字符串。每次对两个字符串等概率的取等长的子串a,b。f(a,b)是a[i] == b[i]的数量,求f的期望。
算法分析:
    
    直接用f的总值除以情况数求得期望。
    对于每个b[i],他能贡献的f值,取决于与之相等的a[j]。
        1.如果j<=i,b[i]和a[j]可以贡献的值是(j+1)*(n-i)。
        2.如果j>i, b[i]和a[j]可以贡献的值是(i+1)*(n-j)。
    于是预处理出sum值就可以了
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 const int N = 200000 + 10;
 6 char cha[N], chb[N];
 7 struct node {
 8     ll lcnt,lsum,rcnt,rsum;
 9 } num[N][26];
10 int main(){
11     int n;
12     while(~scanf("%d%s%s",&n, cha, chb)){
13         for(int i=0;i<26;i++) num[n][i].rcnt = num[n][i].rsum = 0;
14         for(int i=0;i<n;i++){
15             int x = cha[i] - 'A';
16             for(int j=0;j<26;j++){
17                 if(j==x) {
18                     num[i][j].lcnt = i == 0 ? 1 : num[i-1][j].lcnt+1;
19                     num[i][j].lsum = i == 0 ? 1 : num[i-1][j].lsum+i+1;
20                 }
21                 else { 
22                     num[i][j].lcnt = i == 0 ? 0 : num[i-1][j].lcnt;
23                     num[i][j].lsum = i == 0 ? 0 : num[i-1][j].lsum;
24                 }
25             }
26         }
27         for(int i=n-1;i>=0;i--){
28             int x = cha[i] - 'A';
29             for(int j=0;j<26;j++){
30                 if(j==x) {
31                     num[i][j].rcnt = num[i+1][j].rcnt+1;
32                     num[i][j].rsum = num[i+1][j].rsum+(n-i);    
33                 }
34                 else { 
35                     num[i][j].rcnt = num[i+1][j].rcnt;
36                     num[i][j].rsum = num[i+1][j].rsum;    
37                 }
38             }
39         }
40         double ans = 0,base = 0;
41         for(int i=0; i< n;i++){
42             base += 1.0*(i+1)*(i+1);
43             int   x = chb[i]-'A';
44             ans += num[i][x].lsum * (n-i) + num[i+1][x].rsum * (i+1); 
45         }
46 //        cout<<ans<<" "<<base<<endl;
47         printf("%.10lf\n", ans / base);
48     }
49 }
50 
posted on 2012-07-15 22:53 西月弦 阅读(233) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理