Ice and Fire

题目连结

感想: 学再多的技巧也怕题目不懂(有在code里讲一下题目意思)

解题

用dp从左至右将答案一个一个存入在一次输出

几个重要的观念:
当测值全是1时 可能获胜的玩家也只有一位(x最大的玩家)
当测值全是0时 可能获胜的玩家也只有一位(x为0的玩家)
关键
所以当测值为0001时 输出会是1 1 1 3
分开来看:

0 只有两人比小，故赢家只有x=100比两次小，故赢家还是只有x=1000比三次小，故赢家还是只有x=10001比三次小后比一次大，因为所有值都大于x=1(除了x=1)故除了x=1其他都有机会赢
(因为前三场会是x=1与未知比决赛，但是比大，x=1一定输)
故得1 1 1 3

还有一个要注意
当测值是0111时输出是1 2 2 2
分开来看:

0 ==>1 ==>输出101==>除了x=1不会赢(x=2与x=3都有机会赢)==>输出2011==>除了x=1，x=2不会赢(x=3与x=4都有机会赢)==>输出 20111==>除了x=1，x=2，x=3不会赢(x=4与x=5都有机会赢)==>输出 2
通过两个範例可以知道当有相同数字排在一起时能赢得数量就会被卡住
当没有连续出现相同值时有机会赢的人数就是binary string的长度

code

#include <iostream>#include <vector>#include <queue>using namespace std;/*//* 题目:ice and fire    题目来源:codeforce    题目连结:https://codeforces.com/problemset/problem/1774/C    解题者:神里绫华的狗    解题语言:C++    解题连结:https://github.com/archie0732/c-solution/blob/main/codeforce/iceansfire.md    使用技巧:dp//* P.S. 首先，要先看得懂题目，其次要找到规律，最后会用dp*//*    题目意思        0==>两人比小(小的晋级，大的滚)        1==>两人比大(大的晋级，小的滚)    比赛人员与出赛表    假如有三人(参赛表)，选手==> a(x=1),b(x=2),c(x=3)         |        ------       |      |     ----     |    |    |    |    a    b    c  (没规定选手要怎么排，也能够bc a、ca b)    分出胜负:0==>分数较低win ; 1==>分数较高win    範例(用测值 4 001举例)    当有测值001(先看最左边0)    选手:a(x=1),b(x=2)    此时:        |     --------  (0，比小)    |        |    |        |    a(x=1)   b(x=2)    不管怎么换边只有a获胜。故输出1(只有一个人有机会赢)    再来看001的00(比赛依序是:比小、比小)    因为是3人[ax(x=1),b(x=2),c(x=3)]，所以参赛表会变成这样            |            | 0         -------        |       |        | 0     |     ------     |    |      |    |    |      |    |    a      b     c    a与b比谁较小(最左边0)，赢的再去与c比小(中间的0)    你会发现不管怎么换a、b、c的位置都只有x=1赢    故有机会获胜的人只有一人(x=1)==>输出1    最后，看001 (比赛依序是:比小、比小、比大)    因为参赛人数是4人a(x=1),b(x=2),c(x=3),d(x=4)    参赛表如下:            | 1         ---------        |         |        | 0       |      ------      |     | 0    |     |    ---     |     |   |   |    |     |   a   b    c     d    最后不管你怎么换位置==>a(x=1)都不可能赢    所以以鸠会赢的为b、c、d共三人输出 ==> 3*//*    ok，终于到解题了    因为怕太长所以放在我的github*/int main(){    int t;    cin >> t;    while (t--)    {        int n;        cin >> n;        string s;        cin >> s;        char c = s.front();        vector<char> v;        v.push_back(c);        s.erase(s.begin());        //存入答案用        queue<int> ans;        //两人一定只有一个人会赢        ans.push(1);        int count = 1;                while (s.length() > 0)        {            //比较用            c = s.front();            //假如发现下一个值相同==>固定答案            if (c == v.back())            {                v.push_back(c);                s.erase(s.begin());                ans.push(v.size() - count);                count++;            }            //没有话或结束重複==>不再固定答案            else            {                v.push_back(c);                s.erase(s.begin());                //变回1                count = 1;                ans.push(v.size());            }        }        //用queue输出答案        while (ans.size() > 0)        {            cout << ans.front() << " ";            ans.pop();        }        cout << endl;    }    return 0;}