之前一直考試，沒有更新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
西月弦 閱讀(249)
評論(0) 編輯 收藏 引用