0928练习题解

练习链接：https://vjudge.net/contest/397573

B - Game of Credit Cards

题意

给出字符串的长度以及两个字符串a, b，第二个字符串b可以自由变换组合，如果a[i] < b[i]， 二傻子就可以揍一下大傻子，反之会被大傻子揍一下（如果a[i] == b[i]不会）， 问二傻子最少会被揍几下，最多能揍大傻子多少下

题解

这题就是一个田忌赛马贪心的模板题

求最大输出量

1. 如果大傻子最大的数字比二傻子最大的大，那么二傻子就注定要被锤一下，因此二傻子应该使用自己最小的数字来和大傻子最大的数比较
2. 如果大傻子最大的数字比二小子最大的数字小，那么二傻子就用最大的数字来干掉大傻子最大的数字
3. 如果大傻子最大的数字和二傻子最大的数字一样大，并且二傻子的最小数比大傻子的最小数大，那么就用二傻子的最小值干掉大傻子的最小值
4. 如果大傻子最大的数字和二傻子最大的数字一样大，但是二傻子的最小数比大傻子的最小数小或者相等， 那么就用二傻子的最小值干掉大傻子的最大值

求最小被锤量

1. 大致原理和第一个一样，但是要注意的是，为了避免被锤，当大傻子最大的数字和二傻子最大的数字一样大，并且二傻子的最小数和大傻子的最小数小相等， 那么就用二傻子的最小值干掉大傻子的最小值（不求胜利，只求不被锤）

AC代码

/*
* ===============================================
* Filename: B.cpp
* Description: 
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int count1(char king[], char tian[], int n);
int count2(char king[], char tian[], int n);

int main()
{
    int n;
    char king[N], tian[N];
    cin >> n >> king >> tian;
    sort(king, strlen(king) + king);
    sort(tian, strlen(tian) + tian);
    
    count2(king, tian, n);
    count1(king, tian, n);
    

    return 0;

}

int count1(char king[], char tian[], int n)
{
    int sum = 0, fuckMe = 0, fuckKing = 0;
    int tbest = n - 1, tlow = 0;
    int kbest = n - 1, klow = 0;

    while (tlow <= tbest)
    {
        if (tian[tbest] > king[kbest])
        {
            // 田忌最好的马比王的好
            // 用自己最好的马消耗王的好马
            fuckKing ++;
            tbest--;
            kbest--;
        }
        else if (tian[tbest] < king[kbest])
        {
            // 最好的马比不过王的好马
            // 用最坏的马消耗王的好马
            kbest--;
            tlow ++;
        }
        else if (tian[tbest] == king[kbest] && tian[tlow] > king[klow])
        {
            fuckKing ++;
            tlow ++;
            klow ++;
        }

        else if (tian[tbest] == king[kbest] && tian[tlow] <= king[klow])
        {
            tlow ++;
            kbest --;
        }
    }

    cout << fuckKing << endl;
    return 0;
}

int count2(char king[], char tian[], int n)
{
    int sum = 0, fuckMe = 0, fuckKing = 0;
    int tbest = n - 1, tlow = 0;
    int kbest = n - 1, klow = 0;

    while (tlow <= tbest)
    {
        if (tian[tbest] > king[kbest])
        {
            // 田忌最好的马比王的好
            // 用自己最好的马消耗王的好马
            tbest--;
            kbest--;
        }
        else if (tian[tbest] < king[kbest])
        {
            // 最好的马比不过王的好马
            // 用最坏的马消耗王的好马
            fuckMe ++;
            kbest--;
            tlow ++;
        }
        else if (tian[tbest] == king[kbest] && tian[tlow] > king[klow])
        {
            tlow ++;
            klow ++;
        }

        else if (tian[tbest] == king[kbest] && tian[tlow] < king[klow])
        {
            if (tian[tlow] < king[kbest])
            {
                fuckMe ++;
            }
            tlow ++;
            kbest --;
        }
        else if (tian[tbest] == king[kbest] && tian[tlow] == king[klow])
        {
            tlow ++;
            klow ++;
        }
    }

    cout << fuckMe << endl;
    return 0;
}

运行结果

C - Alyona and Spreadsheet

AC代码

/*
* ===============================================
* Filename: C_tmp.cpp
* Description: 
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];


int main()
{
    int n, m, k, l, r, x;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        b[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        c[i] = i;
        for (int j = 1; j <= m; j++)
        {
            cin >> x;
            if (x < a[j])
                b[j] = i;
            a[j] = x;

            if (b[j] < c[i])
            {
                c[i] = b[j];
            }
        }
    }
    cin >> k;
    while (k--)
    {
        cin >> r >> l;
        if (c[l] <= r)
        {
            cout  << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}