吐槽：
现在分数涨不动了。。。。。。
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
西月弦 阅读(260)
评论(0) 编辑 收藏 引用