题解：P17216 [ICPC 2017 Nanning R] The Chosen One
Bobi2014
·
·
题解
前置知识
思路
首先注意到数非常大，所以需要使用高精度。
然后我们思考，每次删除人，没被删除的人的下标会变成什么，假设这个人的下标为 x，那么经过一次操作后下标就会变成 \frac{x}{2}，又因为 x 为奇数的 x 肯定都被删光了，所以 \frac{x}{2} 肯定是正整数。
接着我们思考，什么数可以撑到最后，也就是能除以 2 最多的数，那么肯定是 \le n 的最大的二的次幂，所以我们统计二进制下的 n 一共有几位，这样就可以算出答案了。
```cpp
void div2(){
int carry = 0;
for(int i = p + 1;i <= len;i ++){
int num = carry * 10 + str[i] - '0';
str[i] = (num >> 1)+ '0';
carry = num & 1;
}
while(p < len and str[p + 1] == '0'){
p ++;
}
}
```
答案的高精度：
```cpp
void mul2(){
int carry = 0;
for(int i = anslen - 1;i >= 0;i --){
int num = (carry + (ans[i] - '0') * 2);
ans[i] = (num % 10) + '0';
carry = num / 10;
}
while(carry > 0){
anslen ++;
ans = (char)((carry % 10) + '0') + ans;
carry /= 10;
}
}
```
多测记得清空。
### Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int Q,len,p,anslen;
string str,ans;
void div2(){
int carry = 0;
for(int i = p + 1;i <= len;i ++){
int num = carry * 10 + str[i] - '0';
str[i] = (num >> 1)+ '0';
carry = num & 1;
}
while(p < len and str[p + 1] == '0'){
p ++;
}
}
void mul2(){
int carry = 0;
for(int i = anslen - 1;i >= 0;i --){
int num = (carry + (ans[i] - '0') * 2);
ans[i] = (num % 10) + '0';
carry = num / 10;
}
while(carry > 0){
anslen ++;
ans = (char)((carry % 10) + '0') + ans;
carry /= 10;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> Q;
while(Q --){
cin >> str;
len = str.length();
str = " " + str;
p = 0;
ans = "1";
anslen = 1;
while(p != len and (p < len - 1 or str[len] != '1')){
mul2();
div2();
}
for(int i = 0;i < anslen;i ++){
cout << ans[i];
}
cout << "\n";
}
return 0;
}
```