算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
吐槽:
   现在分数涨不动了。。。。。。

A. About Bacteria

    给出 k,b,n,t(均为大于0,小于1,000,000的正整数)。 对数x ,每次执行 x = x*k + b。 当x = 1时, 执行n次之后得到数z 。 问当x = t时,至少执行多少次大于等于数z。

算法分析:

    当k = 1时,是等差数列,不多说了。
    当k > 1时,根据特递推公式推导通项公式。得到
        (k-1)*t + b >= k^(n-m) *(k-1+b)
    可见 n-m一定很小,直接枚举就可以了。
 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 ll k,b,n,t;
 5 int main(){
 6     while(cin>>k>>b>>n>>t){
 7         if(k==1) {
 8             ll ans = n-(t-1)/b ;
 9             if(ans >= 0) cout<<ans<<endl;
10             else cout<<0<<endl;
11         }
12         else {
13             ll mx = (k-1) * t + b;
14             ll r = k-1+b;
15             int d =  0;
16             while(mx >= r){
17                 d++;
18                 r *= k;
19             }
20             d --;
21             if(n-d > 0)cout<<n-d<<endl;
22             else cout<<0<<endl;
23         }
24     }
25 }
26 
B. Jumping on Walls:

    有两个等长(100,000)的01串,1代表禁止的位置。一开始你在A串的最左端,每次允许执行3个操作:
        1. 右移一个单位
        2. 左移一个单位
        3. 跳到另一个串上同时右移k个单位
    每次还有某不明生物会摧毁两个串的最左端。。。
    请问是否可以移动到最右端。

算法分析:

    利用广搜求最短路
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int N = 100005;
 6 int vis[N][2], Q[N][2] ;
 7 string ch[2];
 8 int head , tail;
 9 bool flag;
10 int n,k;
11 void chk(int u,int p ,int v){
12     if(u < v) return ;
13     if(u >=n) {flag = 1; return;}
14     if(vis[u][p]!=-1) return ;
15     if(ch[p][u] == 'X') return ;
16     vis[u][p] = v;
17     Q[tail][0] = u;
18     Q[tail][1] = p;
19 //    cout<<"v: "<<u<<" "<<p<<endl;
20     tail ++;
21 }
22 bool bfs(){
23     Q[0][0] = 0;
24     Q[0][1] = 0;
25     memset(vis, -1 ,sizeof(vis));
26     vis[0][0] = 0;
27     head = 0, tail = 1;
28     while(head < tail){
29         int u = Q[head][0], p = Q[head][1];
30         head ++;
31         int stp = vis[u][p]+1;
32 //        cout<<"u: "<<u<<" "<<p<<endl;
33         flag = 0;
34         chk(u-1,p,stp);
35         chk(u+1,p,stp);
36         chk(u+k,p^1,stp);
37         if(flag) return 1;
38     }
39     return 0;
40 }
41 int main(){
42     while(cin >> n>> k){
43         cin >> ch[0] >> ch[1];
44         puts(bfs() ? "YES" : "NO");
45     }
46 }
47 
posted on 2012-06-23 11:33 西月弦 阅读(257) 评论(0)  编辑 收藏 引用

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