codeforce二分题目
2156B. Strange Machine
没错就是这道题，我看见二分的标签，但是我的做法完全是暴力模拟。我看不来哪里二分。。。。
可以得到答案但是会超时。
我主要的问题是不知道哪里二分。这个问题我需要解决。
题目的中文翻译------------------------------------------------------------------------------------------------------------
题意很简单 就是一个环，输入一个数num，有n台机器，A机器num--，B机器num/=num;
所以二分哪里？？接着看num的大小会影响ans。num大ans就大了。因为操作的步数量增加了。
ans有单调性质吗？？我操作n步num就等于0了，那n+1步还是0；n-1步就不是0；所以我二分步数。check(步数)==0；check就是我想设计一个函数让这个步数尽量的小。所以l=0;那r=???
这也是我遇到的问题。。现在的我好菜。r=最大的步数。嗯。。。那全是A机器每次就减一，不除二。最多20台机器题目有，输入的数最大是1e9;那r=20*1e9;
AI：—————————————————————————————————————————
优化后的内容：
题意可简化为：在一个环形结构中，给定初始数num和n台机器。机器A执行num--操作，机器B执行num/=2操作。
关于二分法的应用：
- 关键问题在于num的大小会影响最终结果ans。num越大，ans也越大，因为操作步骤会增加。
- 我们需要验证ans是否具有单调性：当操作n步后num=0，那么n+1步时仍为0；但n-1步时则不为0。因此可以采用二分法来验证步数。
- 设计check(步数)==0函数，目标是找到最小的可行步数。初始设置l=0，但如何确定r？
遇到的问题：
- r的取值应为最大可能步数。考虑最坏情况：全部使用A机器（每次仅减1），且题目规定最多20台机器，输入最大值1e9。因此r=20*1e9。
以下是代码——————————————————————————————————————
#include<iostream> #include<string> #include<vector> using namespace std; long long yiquan(long long x,const string& ji,int n){ for(int i=0;i<n&&x>0;i++){ if(ji[i]=='A'){ x--; } else x/=2; } return x; } long long bushu(long long x,long long step,const string& ji,int n){ if(step==0||x==0)return x; long long wan=step/n; long long shen=step%n; for(int i=0;i<wan&&x>0;i++){ long long nex=yiquan(x,ji,n); if(nex==x)break; x=nex; } for(int i=0;i<shen&&x>0;i++){ if(ji[i]=='A')x--; else if(ji[i]=='B')x/=2; } return x; } int main(){ ios::sync_with_stdio(false); int t; cin >> t; while(t--){ int n, q; cin >> n >> q; string ji; cin >> ji; vector<long long> num(q); for(int i = 0; i < q; i++){ cin >> num[i]; } for(int i = 0; i < q; i++){ long long x=num[i]; long long l=0,r=1e12; while(l<r){ long long mid=(l+r)/2; if(bushu(x,mid,ji,n)==0){ r=mid; } else l=mid+1; } cout<<l<<'\n'; } } return 0; }没错超时了哈哈哈---------------------------------------------------------------------------------------------------
为啥会超时：全是A机器md
#include<iostream> #include<string> #include<vector> using namespace std; // 计算经过一圈的效果 void one_cycle(long long& x, const string& ji, int n, long long& cntA_in_cycle) { cntA_in_cycle = 0; for(int i = 0; i < n && x > 0; i++) { if(ji[i] == 'A') { x--; cntA_in_cycle++; } else { x /= 2; } } } long long calc(long long x, long long steps, const string& ji, int n) { if(steps == 0 || x == 0) return x; long long full_cycles = steps / n; int remainder = steps % n; long long cntA; // 关键优化：如果x很大，先快速跳过前面的圈 while(full_cycles > 0 && x > 0) { long long old_x = x; one_cycle(x, ji, n, cntA); full_cycles--; // 如果这一圈全是A if(cntA == n) { // 剩下的全A圈可以直接计算 // 每圈减n，需要 ceil(x/n) 圈变成0 if(x > full_cycles * n) { x -= full_cycles * n; full_cycles = 0; } else { return 0; // 在full_cycles圈内就会变成0 } break; } // 如果值不再变化，跳出 if(x == old_x) break; // 如果x变得很小，继续循环也不会太多次 if(x < n * 100) break; // 小数字直接交给后面的循环处理 } // 处理剩余的完整圈（此时x已经很小，直接模拟） for(long long i = 0; i < full_cycles && x > 0; i++) { one_cycle(x, ji, n, cntA); } // 处理剩余步数 for(int i = 0; i < remainder && x > 0; i++) { if(ji[i] == 'A') x--; else x /= 2; } return x; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while(t--) { int n, q; cin >> n >> q; string ji; cin >> ji; // 统计A的数量 int cntA = 0; for(char c : ji) cntA += (c == 'A'); vector<long long> num(q); for(int i = 0; i < q; i++) { cin >> num[i]; } for(int i = 0; i < q; i++) { long long x = num[i]; // 全A直接输出 if(cntA == n) { cout << x << '\n'; continue; } long long l = 0, r = 1e12; while(l < r) { long long mid = (l + r) / 2; if(calc(x, mid, ji, n) == 0) { r = mid; } else { l = mid + 1; } } cout << l << '\n'; } } return 0; }