文章/答案/技术大牛

发布

社区首页 >专栏 >程序员进阶之算法练习（九十四）

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

落影

发布于 2023-12-23 00:33:00

10600

代码可运行

文章被收录于专栏：落影的专栏落影的专栏

运行总次数：0

代码可运行

题目1

题目链接 题目大意： 有n个整数组成的数组a，现在可以对数组a的元素任意打乱顺序，要求满足：假设打乱后的数组是b，要满足：𝑏1+𝑏2=𝑏2+𝑏3=…=𝑏𝑛−1+𝑏𝑛=k 也就是相邻两个数字的和相同。

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

输出： 每个样例一行，通过打乱顺序生成满足要求的数组，如果有解，则输出YES；如果无解，则输出NO；

Examples input 5 2 8 9 3 1 1 2 4 1 1 4 5 5 2 3 3 3 3 4 100000 100000 100000 100000

output Yes Yes No No Yes

题目解析： 将两两相邻的数字相加，a1+a2, a2+a3... 全部累加，得到(a1+a2)+(a2+a3)+(a3+a4)... 最终就是a1+2x(a2+a3+...+a[n-1])+an 这样只要枚举a1和an的值，就可以通过数组和sum，快速得到(a2+a3+...a[n-1])=sum-a1-an；那么两数相加和k = (a1 + 2x(sum-a1-an) + an) / (n - 1)；

a1是枚举，那么a2=k-a1，以此类推枚举a3，在这个过程中如果发现数组b不存在当前的数字，那么则无解。但是走到这步的时候，发现了数组的规律： a1, k - a1, a1, k-a1 其实不用复杂计算，最终数组结果必然只有2个数字。那么只需要统计数组a的元素，如果大于2个元素则必然无解。只有1个元素，或者2个元素的数量相差不超过1，就有解。

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int sum = 0;
            map<int, int> h;
            vector<int> vec;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                sum += a[i];
                h[a[i]]++;
                if (h[a[i]] == 1) vec.push_back(a[i]);
            }
            int ans = 0;
            if (vec.size() == 1) ans = 1;
            else if (vec.size() == 2) {
                if (abs(h[vec[0]] - h[vec[1]]) <= 1) ans = 1;
            }
            cout << (ans ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目2

题目链接 题目大意： 有两个0、1组成的字符串s和t，长度分别为n和m；如果字符串a满足对所有的 all 𝑖=1,2,…,𝑘−1 ，有 𝑎𝑖≠𝑎𝑖+1，则可以认为字符串a是good；

现在允许在字符串s中任意位置插入若干次字符串t，问最终能否生成一个good的字符串；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例3行第1行整数𝑛 and 𝑚 (1≤𝑛,𝑚≤50 ) 第2、3行分别是字符串s和t

输出： 每个样例一行，如果可以生成good字符串，则输出YES；否则输出NO；

Examples input 5 1 1 1 0 3 3 111 010 3 2 111 00 6 7 101100 1010101 10 2 1001001000 10

output Yes Yes No No No

题目解析： 按照题目要求，good字符串就是字符0和1交替的字符串，比如说10101或者0101；那么字符串中如果存在00或者11，就表示不满足要求；

由于题目可以插入字符串t，那么首先对字符串t做同样的检查，要求不含有00和11；字符串t要插入到字符串s中，且只会插入到00和11，那么必然字符串首尾必然相同，要么都是0、要么都是1；

字符串s如果仅存在00或者11，那么可以考虑插入符合要求的字符串t； 00只会插入首尾都是1的good字符串t； 11只会插入首尾都是0的good字符串t；

class Solution {
    static const int N = 201010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, m;
            cin >> n >> m;
            string s, t;
            cin >> s >> t;
            int flag[2] = {0};
            for (int i = 1; i < n; ++i) {
                if (s[i] == s[i - 1]) flag[s[i] - '0'] = 1;
            }
            int ans = 0;
            if (flag[0] + flag[1] == 0) ans = 1;
            else if (flag[0] + flag[1] == 2) ans = 0;
            else {
                int sec[2] = {0};
                for (int i = 1; i < m; ++i) if (t[i] == t[i - 1]) sec[t[i] - '0'] = 1;
                if (sec[0] + sec[1] == 0 && t[0] == t[m - 1] && (flag[t[0] - '0']== 0)) {
                    // 不含00和11，并且头尾相同，并且互补
                    ans = 1;
                }
            }
            cout << (ans ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目3

题目链接 题目大意： 有一堆石子，初始的时候有若干个；有两个人在玩游戏，每个人轮流移除石子，每次可以移除a个石子或者b个石子，无法移除者失败；假设两个都采用了理想最优策略，现在已知a和b，问最初的时候有多少个石子，能够保证后手者胜利。

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

输出： 每个样例一行，输出初始化状态的石子数量𝑛 (1≤𝑛≤1e6 )；

Examples input 3 1 4 1 5 9 26

output 2 6 3

题目解析： 只要让先手者不能取，那么后手者胜利。 a>1，则直接n=1，先手无解； a=1，则n=a+b，先手不管取a或者b，后手跟着取b或者a即可；

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int x, y;
            cin >> x >> y;
            if (x > 1) cout << 1 << endl;
            else cout << x + y << endl;
        }
    }
}
ac;

题目4

题目链接 题目大意： 首先定义MEX，对于一个区间，这个区间内未出现过的最小正整数就是这个区间的MEX值； [2,3,1,5,4]的MEX值就是6；

现在需要构造一个的整数数组，要求满足： 1、数组的元素是由1到n的排列组成； 2、数组所有的子区间，MEX值是素数的尽可能多；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，整数𝑛 (1≤𝑛≤200000).

输出： 每个样例一行，输出1到n的n个整数。

Examples input 3 2 1 5

output 2 1 1 5 2 1 4 3

题目解析： 根据题目的要求，如果某个区间中，数字1没有出现，那么必然MEX值为1，1不是素数；那么1必然要被包括在区间内；

想要让区间的MEX为素数，那么这个区间内就不要包括某个素数，这里选择2和3；（因为最小，最容易满足）只要2不出现在区间中，那么区间的MEX值必然为2；比如说1xxx2，区间1x 1xx 1xxx都满足要求；

为了让结果尽可能大，应该要让数字均匀分布在1的左右两边；形成 2 xxxx 1 xxxxx 3这样的布局，就可以让结果尽可能的多。

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        for (int i = 2; i < N; ++i) {
            int m = sqrt(i) + 1, find = 0;
            for (int j = 2; j <= m && j < i; ++j) {
                if (i % j == 0) find = 1;
            }
            a[i] = !find;
        }
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            if (n == 1) cout << "1" << endl;
            else if (n == 2) cout << "2 1" << endl;
            else {
                vector<int> ans;
                ans.push_back(2);
                for (int i = 0; i < (n - 3) / 2; ++i) ans.push_back(4 + i);
                ans.push_back(1);
                for (int i = (n - 3)/ 2; i < n - 3; ++i) ans.push_back(4 + i);
                ans.push_back(3);
                //            for (int i = 2; i <= n; ++i) if (!a[i]) ans.push_back(i);
                for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
                cout << endl;
            }
        }
    }
}
ac;

题目5

题目链接 题目大意： 有n个整数的数组，现在可以对数组进行操作： 1、选择某个位置的元素； 2、移除该元素； 3、如果该元素原来左右两边均有数字，那么这两个数字也会移除，合并成一个新的数字；（如果左右两边只有1个数字，则不会触发合并）如下图所示：

现在想知道，经过若干次操作后，数组剩下一个元素时，这个元素最大值为多少？

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数𝑛 (1≤𝑛≤20000). 接下来n个整数 𝑐1,…,𝑐𝑛(−1e9≤𝑐𝑖≤1e9).

输出： 每个样例一行，输出结果的最大值。

Examples input 3 6 -3 1 4 -1 5 -9 5 998244353 998244353 998244353 998244353 998244353 1 -2718

output 9 2994733059 -2718

题目解析： 这个题目最终实现不复杂，但是在分析过程踩了一下坑，这里特意做一个记录，简单回顾下出问题点。

最开始的思路：简化题目，只考虑有正数的情况，是否有简单的策略：每次会发生可能两个行为，数字移除+数字合并，数字移除会减少一个数字并影响最终的和，数字合并不会直接影响最终的和，但是仍然会对结果有影响，因为我们减少了一个可移除的数字选择；比如说【10，5，1，5，10】这样的数组，当我们先选择1时，剩下【10， 10，10】，最终结果是20；如果只选择移除整数5，那么最终结果是21；那么就不能采用简单的从最小开始移除的合并策略（尤其此时还没引入负数）。观察区间的特性，我们知道对于每一个新增的数字，有两个选择： 1、直接移除，此时在最右边，原来区间不会发生任何事情； 2、原区间右边最右整数被移除，当前数字被进行合并；根据两个选择可以得到对应的状态转移方案。

到这里整体思路还算清晰，但是出现一个问题，当进行决策1之后，该位置的数字必须全部摒弃。那么每个位置应该有两个状态： 1、当前数字是被移除；（dp[i][0]) 2、当前数字是保留的状态；(dp[i][1]) dp[i][0]可以由dp[i-1][1]转移，dp[i][1]可以由dp[i-1][0]转移，转移方程： dp[i][0] = dp[i-1][1]; dp[i][1] = max(0LL, dp[i-1][0]) + a[i];

看着一切美好，但是在遇到下面这串样例的时候，问题就出现了： 5 -1 -2 -3 6

这里动态规划会出问题，因为当a[i]=6时，我们选择保留元素6，那么就会remove -3，结果就是-2和6合并了。我们知道最优解是先选择数字-2，生成5 -4 6；再选择-4，得到结果11；因为这里的决策无后效性并不满足。

舍弃动态规划，从题目的操作特性来分析，对于相邻的两个数字，必然不能融合。奇数位置的数字，只能和奇数位置融合；偶数位置的数字，只能和偶数位置融合；

那么是否可以做到任意奇数位置的整数都能融合？首先，连续的奇数位置必然是可以融合，因为只间隔着1个数字，选择remove该整数即可；对于不间断的奇数位置，我们只需考虑间隔1、2个整数的情况皆可，其他间隔情况都可以由这2个情况来推出。间隔1个整数的情况，比如说 [1,-2,-2,-2,1]，奇数位置整数是[1,-2,1]，我们可以选择第一次remove最中间的-2，得到[1, -4, 1]，再选择中间的整数-4，即可得到2；间隔2个整数的情况，比如说 [1,-2,-2,-3,-3,-1,1]，同样的操作，我们一直选择remove最中间的整数，由于每次我们remove1个整数，融合减少1个整数，最终一定会剩下[1, x, 1]这样的结果，也即是必然可以融合得到2；

那么这个题目就比较简单了，只需要考虑奇数位置、偶数位置上选择若干个整数，得到的最小和。

class Solution {
    static const int N = 201010;
    lld dp[N][2], a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
//                if (i == 0) dp[0][1] = a[i];
//                if (i == 1) {
//                    dp[1][0] = dp[0][1];
//                    dp[1][1] = a[1];
//                }
//                if (i >= 2) {
//                    dp[i][0] = dp[i-1][1];
//                    dp[i][1] = max(0LL, dp[i-1][0]) + a[i];
//                }
//                ans = max(ans, dp[i][1]);
//                cout << i << " " << dp[i][0] << " " << dp[i][1] << endl;
            }
            if (n == 1) cout << a[0] << endl;
            else {
                lld ans[2] = {a[0], a[1]};
                for (int i = 2; i < n; ++i) {
                    if (a[i] < 0) ans[i%2] = max(ans[i%2], a[i]);
                    else {
                        ans[i%2] = max(a[i], ans[i%2] + a[i]);
                    }
                }
                cout << max(ans[0], ans[1]) << endl;
                
            }
            
        }
    }
}
ac;