吐槽：
現(xiàn)在分?jǐn)?shù)漲不動(dòng)了。。。。。。
A. About Bacteria
給出 k,b,n,t(均為大于0,小于1,000,000的正整數(shù))。 對(duì)數(shù)x ，每次執(zhí)行 x = x*k + b。 當(dāng)x = 1時(shí)， 執(zhí)行n次之后得到數(shù)z 。 問當(dāng)x = t時(shí)，至少執(zhí)行多少次大于等于數(shù)z。
算法分析：
當(dāng)k = 1時(shí)，是等差數(shù)列，不多說了。
當(dāng)k > 1時(shí)，根據(jù)特遞推公式推導(dǎo)通項(xiàng)公式。得到
(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:
有兩個(gè)等長(zhǎng)(100,000)的01串，1代表禁止的位置。一開始你在A串的最左端，每次允許執(zhí)行3個(gè)操作：
1. 右移一個(gè)單位
2. 左移一個(gè)單位
3. 跳到另一個(gè)串上同時(shí)右移k個(gè)單位
每次還有某不明生物會(huì)摧毀兩個(gè)串的最左端。。。
請(qǐng)問是否可以移動(dòng)到最右端。
算法分析：
利用廣搜求最短路
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
西月弦 閱讀(282)
評(píng)論(0) 編輯 收藏 引用