#EDU 150

A:

题目：

现在A 和 B 玩一个游戏，A先手B后手，存在一个全为1的数组。每次操作中，每个人至少选择两个连续的数字变为他们的和。

如果谁不能操作谁就赢了。

思路：

如果 n > 4的 情况，A直接取 n - 2 个，剩下两个给B取，A一定赢。

小于4的情况，手动模拟B一定赢

代码

void solved()
{
    int n; cin >> n;


    if(n > 4)
    {
        cout << "Alice" <<endl;
    }else cout << "Bob" << endl;


}

B：

题目：

现在如果存在一个数组，可以把开头连续的序列，不调换顺序转移到最后仍然是一个非严格上升序列，那么是美丽的。

现在给出 q 个查询，每次会给出一个 x，把 x 放到序列最后，如果满足美丽条件，则放最后，否则不放。

问你每个查询放置的状态。

思路：

维护序列头尾是谁，如果插入到后面满足非严格上升，就插，否则进入了把前缀放到最后，判断当前数字是否满足条件

代码

void solved()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    string ans = "1";
    int l = a[1], r = a[1];
    bool flag = false;

    for(int i = 2; i <= n; i++)
    {

        if(flag == true)
        {

            if(a[i] >= r && a[i] <= l) r = a[i], ans += "1";
            else ans += "0";

            continue;
        }

        if(a[i] >= r) r = a[i], ans += "1";
        else
        {
            if(a[i] <= l)
            {
                r = a[i];
                flag = true;
                ans+= "1" ;
            }else ans += "0";
        }
    }

    cout <<ans << endl;


}

C：

题目：

现在存在一个字符串由A-E构成，每个字母对应一个数值，如果当前字母右边有比他大的字母，那么他是符号，不要求相邻。

现在你可以改变一个字母，问你改变后和的最大值。

思路：

改变一个字母，两种情况： 当前字母数值变大，当前字母数值变小让其他人变大。

情况1：把当前字母变成比他大的字母，我们可以考虑一类字母，因为不同位置上把字母改变，对自己这个字母的值并无影响。

而影响的是其他字母的正负号，所以对于一类字母，如果要把他变大，那么尽可能的不影响其他字母，选择这类字母最靠前的那一个。

反之变小，选择最靠后的去尽可能的减少影响。

做法：

记录每一类字母出现的第一个位置和最后位置。

枚举每一类字母和要变的字母，根据上述判断的情况，暴力枚举所有情况即可

代码

int gett(string s)
{

    int sum = 0;
    int mx = 0;

    for(int i = s.size() - 1; i >= 0; i--)
    {
        if((int)s[i] < mx ) sum += - shu[s[i]];
        else sum += shu[s[i]];

        mx = max(mx, (int)s[i]);
    }

    return sum;
}
void solved()
{
    shu['A'] = 1, shu['B'] = 10, shu['C'] = 100, shu['D'] = 1000, shu['E'] = 10000;
    cin >> s;

    for(int i = 0; i < 5; i++) st[char(i + 'A')] = -1, ed[char(i + 'A')] = -1;

    for(int i = 0; i < s.size(); i++)
    {
        ed[s[i]] = i;
        if(st[s[i]] == -1) st[s[i]] = i;
    }


    int ans = -1e9;

    for(int i = 0; i < 5; i ++)
    {
        if(ed[char('A' + i)] == -1) continue;

        for(int j = 0; j < 5; j++)
        {
            char a = i + 'A';
            char b = j + 'A';


            s[ed[a]] = b;
            ans = max(ans, gett(s));
            s[ed[a]] = a;


            s[st[a]] = b;
            ans = max(ans, gett(s));
            s[st[a]] = a;

        }
    }

    cout <<ans << endl;
}