题目链接https://codeforces.com/contest/2261/problem/A题目大意把 1..n 通过 01 串分给两人。两人轮流把自己拥有的一个数字交给对方苏夫拉基先手共进行 10^100 轮。最后苏夫拉基的得分是他所持数字的“最大值减最小值”前者想最大化、后者想前者最小化求前者最优结果。题目思路因为总回合数10^100是偶数那么sou的初始拥有数字个数和结束时一定相同假设sou初始有cnt个数字如果cnt1那么结果一定为0如果cnt2,sou为了最大化kal为了sou最小化sou的最终的2个数字一定是相邻的那么结果就是1cnt3时sou最初的mi-ma就是最终答案因为sou只会把mi和ma中间的数给kal以保证最大化,而kal不可能给sou可以增大答案的数字时间复杂度O(n)代码如下#include bits/stdc.h using namespace std; #define endl \n using ll long long; using ld long double; /* https://codeforces.com/contest/2261/problem/A Div.1Div.2 CF1128A题(博弈论数学) 题目大意把 1..n 通过 01 串分给两人。两人轮流把自己拥有的一个数字交给对方苏夫拉基先手 共进行 10^100 轮。最后苏夫拉基的得分是他所持数字的“最大值减最小值”前者想最大化、后者想前者最小化求前者最优结果。 题目思路因为总回合数10^100是偶数那么sou的初始拥有数字个数和结束时一定相同假设sou初始有cnt个数字如果cnt1那么结果一定为0如果cnt2,sou 为了最大化kal为了sou最小化sou的最终的2个数字一定是相邻的那么结果就是1cnt3时sou最初的mi-ma就是最终答案因为sou只会把mi和ma中间的数给kal 以保证最大化,而kal不可能给sou可以增大答案的数字 */ //时间复杂度O(n) void solve() { int n; string s; cin n s; s s;//数字与字符串下标对齐 int cnt 0; //初始化最大最小值 int mn 100; int mx 2; for (int i 1; i n;i){ if(s[i]1){ cnt; mn min(mn, i); mx max(mx, i); } } if(cnt1){ cout 0 endl; }else if(cnt2){ cout 1 endl; }else{ cout mx - mn endl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T ; cin T; while (T--) { solve(); } return 0; }