A

题目：

存在 n 个技能， 第 i 个技能的类型为 a[i] ， 伤害为 b[i]

我们可以任意调整技能的输出顺序，当前技能上一个技能是与当前不同类型的，那么伤害加倍。

找出最大的顺序使得技能的伤害总和最大

思路：

最优解是两个不同类型的技能相间释放。如果说两个技能的数量不相通。

那么最终数量较少的那个技能的个数如果为 len1

模拟发现，两个技能各有 len1 个技能会两倍释放。

那么降序排列所有的技能。根据数量分成三种情况。

代码

void solved()
{
    cin >> n;

    int minn = 0x3f3f3f3f;

    for(int i = 1; i <= n; i++) cin >> ty[i];
    for(int i = 1; i <= n; i++) cin >> w[i];

    vector<int>w0, w1;

    for(int i = 1; i <= n; i++)
    {
        if(ty[i] == 0)
        {
            w0.push_back(w[i]);
        }else w1.push_back(w[i]);

        minn = min(minn, w[i]);
    }

    sort(w0.begin(), w0.end(), bmp);
    sort(w1.begin(), w1.end(), bmp);

    int len0 = w0.size();
    int len1 = w1.size();
    int sum = 0;

    if(len0 > len1)
    {
        for(int i = 0; i < len1; i++)
        {
            sum += 2 * (w0[i] + w1[i]);
        }

        for(int i = len1; i < len0; i++)
        {
            sum += w0[i];
        }
    }else if(len1 > len0)
    {
        for(int i = 0; i < len0; i++)
        {
            sum += 2 * (w0[i] + w1[i]);
        }

        for(int i = len0; i < len1; i++)
        {
            sum += w1[i];
        }
    }else
    {
        for(int i = 0; i < len1; i++)
        {
            sum += 2 * (w0[i] + w1[i]);
        }

        sum -= minn;
    }

    cout << sum << endl;

}

B

题目：

存在一个 a 数组里面为非降序的数字排列。

存在一个 s 数组，s数组是 a 数组的前缀和数组。

给出一个 长度为 k 的 s数组的后 k 个数字。

问能否构成一个 合法的 a 数组。

思路：

根据前缀数组，我可以把后 k - 1个数组表示出来。然后判断这部分是否不合法。

之后第一个数字为前面数字的和，因为 a 数组可以是任意整数，所以只需要找到前面所有数字和的上限。

那么根据非降序，找到第 n - k + 2 个数字，最大值是前面都放这个数字

那么最大和为(n - k + 1) * a[n - k + 2]

只需要判断一下s[n - k + 1] 是否 <= 这个和。

需要特判的点

如果当 k == 1 时候， 遵循上面的思路那么我们会找到不到 n - k + 2 这个数字。

特判当 k 为1 是毫无以为是合法的

代码

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

    for(int i = n; i >= n - k + 2; i--)
    {
        a[i] = b[i] - b[i - 1];
    }

    if(k == 1)
    {
        cout << "Yes" <<endl;
        return ;
    }
    for(int i = n - 1; i >= n - k + 2; i--)
    {
        if(a[i] > a[i + 1])
        {
            cout << "No" << endl;
            return;
        }
    }

    int sum = (n - k + 1) * a[n - k + 2];

    if(b[n - k + 1] > sum)
    {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;

}

C：

题目：

Alice 和 Bob 在长度为 n 的序列上玩游戏。 他们轮流移动，Alice先移动。

在每个玩家的回合中，每个人选择一个整数从序列中删除它，当序列中没有整数时，游戏结束。

最终如果 Alice 的和是 偶数， 那么 Alice 反之 Bob赢

思路：

记忆化搜索。

如果单纯的搜索每个人选择的数字毫无疑问会超时。

但是因为本题为博弈论，对于每个当前的状态来说，先选或者后选并无区别，所以们对于重复的状态不再搜索

对于本题来说，数字的奇偶的选择会对和造成影响，所以每次统计选择的是奇数还是偶数。

所以对于 f[该谁选][Alice 和的状态][剩余偶数的个数][剩余奇数的个数]

对于Alice选取一个偶数，不会改变和的状态，如果选择一个奇数那么状态取反。

对于当前人的输赢，通过下一回合对手的输赢来判断，如果对手输了，那么本手就可以赢

因为Alice先手，所以每次搜索所有Alice赢的可能性，之后返回输，除非状态都是对手赢，否则本手就可以赢。

代码

int dfs(int u, int s0, int sum2, int sum1)
{
    if(sum1 + sum2 == 0)
    {
        if(s0 == 1)
        {
            if(u == 0)
                return 0;

            return 1;
        }else
        {
            if(u == 0) return 1;

            return 0;
        }
    }

   if(f[u][s0][sum2][sum1] != -1) return f[u][s0][sum2][sum1];

    if(sum2)
    {
        if(!dfs(u ^ 1, s0, sum2 - 1, sum1)) return f[u][s0][sum2][sum1] = 1;

    }

    if(sum1)
    {

        if(u == 0)
        {
            if(!dfs(u ^ 1, s0 ^ 1, sum2, sum1 - 1))
                return f[u][s0][sum2][sum1] = 1;

        }

        if(u == 1)
        {
            if(!dfs(u ^ 1, s0, sum2, sum1 - 1))
                return f[u][s0][sum2][sum1] = 1;
        }

    }

        return f[u][s0][sum2][sum1] = 0;

}

void solved()
{

    memset(f, -1 ,sizeof f);

    cin >> n;
    int sum1, sum2;
    sum1 = sum2 = 0;

    for(int i = 0; i < n; i++)
    {
        cin >> d[i];
        if(d[i] % 2 == 0) sum2++;
        else sum1++;
    }

    if(dfs(0, 0, sum2, sum1)) cout << "Alice" <<endl;
    else cout << "Bob" << endl;
}