程序员进阶之算法练习（九十九）

题目1

题目链接 题目大意： 有三个长度为n的字符串a、b、c，字符串都是小写字符； 有一个长度为n的模版t，模版会与字符串a、b、c匹配，匹配规则如下： 1、假如模版的字符为小写字母，则对应位置必须是相同字符才算匹配； 2、假如模版的字符为大写字母，则对应位置则不能是相同字符才算匹配； 比如说模板abc和字符串abc是匹配的，模板ABC和字符串def也是匹配的，模板ABC和字符串abc是不匹配的；

现在已知字符串a、b、c，问是否能够构造一个模板t，要求字符串a和b是匹配的，字符串c是不匹配的。

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例4行 第一行，整数𝑛(1≤𝑛≤20)，字符串长度 第2、3、4行，分别是字符串a、b、c；

输出： 每个样例第一行，有解则输出YES，无解则输出NO；

Examples input 4 1 a b c 2 aa bb aa 10 mathforces luckforces adhoccoder 3 acc abd abc

output YES NO YES NO

样例解释： 样例1，直接用模板C 样例3，可以用模板CODEforces

题目解析： 题目的意思比较绕，但是匹配规则还是比较清晰的，可以先简化题目。

先考虑字符串a和b，对于某个位置的字符： 如果a和b相同（假设都是字符x），那么模版可以字符x，也可以是字符X以外的大写字符； 如果a和b相同（假设是字符x和字符y），那么模版必须是字符X、Y以外的大写字符；

我们发现，不管字符串a和b的取值，总是可以找到满足要求的模版；

那么再考虑字符串c，要使得模版至少有一个配置是不匹配的，也就是至少有一个位置，字符串c该位置的字符与前面的都不同。

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            string a, b, c;
            cin >> a >> b >> c;
            int ans = 0;
            for (int i = 0; i < n; ++i) if (a[i] != c[i] && b[i] != c[i]) ans = 1;
            cout << (ans > 0 ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目2

题目链接 题目大意： 有n个棍子，长度分别为2^𝑎𝑖； 从这些棍子里面挑出3个，组成一个三角形； 想知道，一共有多少种选择。 （三个棍子，顺序不同算一个组合，比如说1、2、3 和 3、2、1）

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行 第一行 整数𝑛，表示n个棍子(1≤𝑛≤20) 第二行 n个整数，𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤𝑛 ).

输出： 每个样例第一行，输出能够组合成三角形的数量。

Examples input 4 7 1 1 1 1 1 1 1 4 3 2 1 3 3 1 2 3 1 1

output 35 2 0 0

题目解析： 先分析题目的数据特点。 由题目知道，三个不同的数字是无法组合成三角； 那么，有且仅有两种可能： 1、三个数字相同；（这种情况就是组合数，C(x, 3) 从x个相同数组中选择3个） 2、两个数字相同，剩下一个更小的数字；

将整数排序，从小到大。情况2的数量，就可以选定当前数字的2个棍子，再乘以前面的所有数字的数量。

typedef long long lld;
 
class Solution {
    static const int N = 301010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            map<int, int> h;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                h[a[i]]++;
            }
            lld ans = 0, sub = 0;
            for (map<int, int>::iterator it = h.begin(); it != h.end(); ++it) {
                int cnt = it->second;
                if (cnt >= 3) {
                    ans += 1LL * cnt * (cnt - 1) * (cnt - 2) / 6;
                }
                if (cnt >= 2) {
                    ans += 1LL * cnt * (cnt - 1) / 2 * sub;
                }
                sub += cnt;
            }
            cout << ans << endl;
        }
    }
}
ac;

题目3

题目链接 题目大意： 有一个整数数组a，数组每个元素的乘积是2023； 数组移除了k个整数，剩下长度为n的数组b；

现在已知数组长度n和数组b，问能否找到原来的数组a。

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例2行 第一行，整数𝑛和k (1≤𝑛,𝑘≤5) 第二行，n个整数𝑏1,𝑏2,…,𝑏𝑛(1≤𝑏𝑖≤2023)

输出： 每个样例第一行，无解输出NO，有解输出YES； 如果有解，则第二行再输出被移除的k个整数；

Examples input 7 2 2 5 2 3 1 7 17 7 4 2 1 289 1 1 3 1 7 17 17 1 1 289 1 1 2023 1 3 1

output 1 1 0 0 0 1 3 0

题目解析： 题目的要求比较明确，当我们给出整数数组b时，假设最终的数组b乘积为m； m能够被2023整数时，剩余的k个数组就可以是[2023/m, 1， 1， 1】这样的数组来组成。 如果m不能被整数，那么就无解了。

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            int ans = 2023, ok = 1;
            for (int i = 0; i < n; ++i) {
                int x;
                cin >> x;
                if (ans % x == 0) ans /= x;
                else ok = 0;
            }
            if (ok) {
                cout << "YES\n" << ans;
                while (k > 1) {
                    k--;
                    cout << " " << 1;
                }
                cout << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    }
}
ac;

题目4

题目链接 题目大意： 给出两个整数a和b，现在要找到整数x，满足条件： 1、1≤𝑎<𝑏<𝑥，且1≤𝑥≤1e9； 2、a和b是x的因数，且是因数（x不算）中最大的两个；

比如说12 的因数有 [1,2,3,4,6]，那么a和b就是4和6；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，整数𝑎 , 𝑏 (1≤𝑎<𝑏≤1e9)

输出： 每个样例一行，输出满足要求的x；（题目保证有解）

Examples input 8 2 3 1 2 3 11 1 5 5 10 4 6 3 9 250000000 500000000

output 6 4 33 25 20 12 27 1000000000

题目解析： 先从小样例开始分析，容易知道当a=1的时候，答案是b^2； 当a=2的时候 [2, 3]=6 [2, 4]=8 [2, 5]=10 [2, 6]无解；（12的时候，3、4因子更大）

当a=3的时候 [3, 4]=12 [3, 5]=15 [3, 6]无解；（12的时候，因子4更大）

当a=4的时候 [4, 5]=20 [4, 6]=12 [4, 7]=28 [4, 8]=16 [4, 9]无解；（36的时候，因子3x12=36，12更大）

我们发现，有解/无解的时候，与a、b的因子有一个强关联，

比如说[2, 6]无解，实际上6=2x3，那不管乘以任何数字k，都容易产生2 * k、3 * k这样的因子，一定比2要大； [4, 9]无解，也是同理4=2x2, 9=3x3，理论上的有4、9因子的最小值就是2x2x3x3=36，但是会产生很多较大因子。

比如说有解的时候，大多数值都是最小公倍数。 但是有例外是[2, 4]和[4, 8]，当他们b整除a的时候，最小公倍数是b，但是题目要求是x>b，所以x要乘以一个值k。 下面说明k的取值关系。

假设k=b/a，那么b=k * a, b * (b/a)=b * k=(a * k) * k 假如是b * 2的话，b * 2=a * k * 2，那么因子里面就会多出来一个2 * a，此时如果一旦b/a != 2，那么必会有一个2 * a的因子 大于原来的因子a； 假如是b * (b/a)的话，只会产生一个k * k的因子，a * k是等于b的，并且我们可以知道有解的条件是k * k<a

这样题目的大体思路就有了。 注意：最小公倍数的求法，可以用最大公约数来算。（我自己忘了，竟然尝试用因数分解去做，结果超时了）

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    long gcd(lld a, lld b){
        if (b==0) return a;
        return gcd(b, a%b);
    }
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int a, b;
            cin >> a >> b;
            int n = a, m = b;
            if (m % n == 0) {
                // 表示b是a的倍数，此时只需要将m*(m / n)就行
                // 假设k=m/n，那么m=k*n, m*(m/n)=m*k=(n*k)*k
                // 假如是m*2的话，m*2=n*k*2，那么因子里面就会多出来一个2*n，此时如果一旦m/n != 2，那么必然会有一个2*n的因子 大于原来的因子n；
                // 假如是m * (m/n)的话，只会产生一个k*k的因子，n*k是等于m的，并且我们可以知道有解的条件是k*k<n
                cout << m * (m / n) << endl;
            }
            else {
                lld ans = a * 1LL * b / gcd(a, b);
                cout << ans << endl;
            }
        }
}
ac;

题目5

题目链接 题目大意： 有n个整数的数组a，现在有Alice和Bob两个人玩游戏，Alice先手。 游戏规则如下： 1、数组中只有一个元素时结束游戏，当前数字为最终结果； 2、每次可以选择数组2个整数，移除对应整数；然后将整数相加再除以2，向下取整，再乘以2，最终将数字重新加回去数组；（比如说[1,3]=4, [2,3]=4)

Alice的目标是让结果尽可能大，Bob的目标是让结果尽可能小。 现在想知道，当只有数组前k个数字参与游戏时（𝑘=1,2,…,𝑛），最终的游戏结果是什么。

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行 第一行，整数𝑛(1≤𝑛≤1e5) 第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)

输出： 每个样例一行，共n个整数；第k个数字，表示只有前k个数字参与游戏时，最终的结果。

Examples input 4 1 31 6 6 3 7 2 5 4 3 3 10 11 5 7 13 11 19 1

output 31 6 8 16 18 22 26 3 12 24 7 20 30 48 50

题目解析： 先不考虑k的取值情况，只看整个数组都参与游戏。 数组中的数字，我们可以分为奇数和偶数，已知偶数+偶数、奇数+奇数的操作只会合并数字，不会有任何变化。只有奇偶数相加，此时最终结果会-1。 这样， 我们假设有x个奇数； 先手每次优先消耗2个奇数，产出1个偶数； 后手每次优先消耗1个奇数+1个偶数，产出1个偶数；（偶数必然存在，因为先手会产出偶数） 这样我们就可以得到一个策略： n=1，ans=sum（用sum来表示前n项和） n=2，ans=sum n=3=2+1，ans=sum-1 n=4=2+1 +1, ans=sum-2 n=5=2+1 +2, ans=sum-1 n=6=2+1 + 2+1, ans=sum-2 n=7=2+1 + 2+1 +1, ans=sum-3 ... 依次类推，我们知道3个奇数是一个循环，最终ans= sum - (n + 2) / 3 + ((n + 1) % 3 == 0)

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            vector<lld> ans;
            lld sum = 0, cnt = 0;;
            for (int i = 0; i < n; ++i) {
                int k;
                cin >> k;
                sum += k;
                if (k % 2) ++cnt;
                if (i == 0) ans.push_back(sum);
                else {
                    ans.push_back(sum - (cnt + 2) / 3 + ((cnt + 1) % 3 == 0));
                }
            }
            for (int i = 0; i < n; ++i) {
                cout << ans[i] << " ";
            }
            cout << endl;
        }
    }
}
ac;