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

落影

发布于 2023-10-18 10:30:50

19700

代码可运行

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

运行总次数：0

代码可运行

题目1

题目链接 题目大意： 给出一个整数的数组，长度为n；现在可以进行以下的操作：选择长度不小于2的区间[l, r]，将区间内的整数依次进行异或操作，然后将得到的整数替换区间所有的数字；

比如说数组[1,5,4,1,4,7]，当我们选择区间[1,5,4]进行异或操作，得到结果是4，然后替换原来的区间内所有数字得到： [1,5,4,1,4,7]→[4,4,4,1,4,7]

问，如何找到一个操作，使得数组所有元素都为0；

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

输出： 每个样例第一行输出操作次数m，接下来m行，每行2个整数表示操作区间；（m不能大于8）

Examples input 3 1 100000 2 1 1 3 10 3 3

output 1 2 1 1 3 2

题目解析： 当n=偶数时，令l=1，r=n，我们可以得到一个元素相同的数组；再重复一次这样的操作，由于偶数个一样的数字进行异或，结果就全部是0；当n=奇数时，类似偶数的做法，我们可以先对偶数长度的区间[1, n-1]进行上述操作，使得区间归零；再对区间[2, n]进行相同操作即可；

stdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
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;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
            }
            if (n % 2) {
                printf("4\n%d %d\n%d %d\n", 1, n - 1, 1, n - 1);
                printf("%d %d\n%d %d\n", 2, n, 2, n);
            }
            else {
                printf("%d\n%d %d\n%d %d\n", 2, 1, n, 1, n);
            }
        }
    }
}
ac;
 
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ac.solve();
    
    return 0;
}

题目2

题目链接 题目大意： 有一个整数n，现在有无限个整数1到k；现在需要从整数1-k中选择任意个数字，要求满足： 1、这些整数的和等于n； 2、这些整数不包括整数x；

问，是否存在这样的组合；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例一行整数𝑛,𝑘 and 𝑥 (1≤𝑥≤𝑘≤𝑛≤100 ).

输出： 每个样例，如果无解直接输出NO；如果有解，则先输出YES；然后下一行输出组合的整数个数m，接下来一行输出m个整数；

Examples input 5 10 3 2 5 2 1 4 2 1 7 7 3 6 1 1

output YES 6 3 1 1 1 1 3 NO YES 2 2 2 YES 1 7 NO

题目解析： 分类讨论，假设x!=1，那么必然可以用1来组合所有的数字；如果 x=1，那么整数1不能选： 1、如果k=1，无解； 2、如果k=2，偶数有解（全部是2），奇数无解； 3、如果k=3，偶数有解（全部是2），奇数有解（去掉一个3变成偶数，剩下全部是2）；

扩展思路：这个题目还有个实现方式，采用动态规划，我们用dp[i]表示整数i是否有解，同时用pre[i]记录整数i有解的上一个整数（用于输出）；用提供的整数分别去计算所有状态，最终看dp[n]是否有解。

#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
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, x;
            cin >> n >> k >> x;
            if (x != 1) {
                cout << "YES" << endl;
                cout << n << endl;
                while (n--) {
                    cout << "1 ";
                }
                cout << endl;
            }
            else {
                if (k == 1) {
                    cout << "NO" << endl;
                }
                else if (k == 2) {
                    if (n % 2) {
                        cout << "NO" << endl;
                    }
                    else {
                        cout << "YES" << endl;
                        cout << n / 2 << endl;
                        while (n) {
                            cout << 2 << " ";
                            n -= 2;
                        }
                        cout << endl;
                    }
                }
                else {
                    // 2 & 3
                    cout << "YES" << endl;
                    cout << n / 2 << endl;
                    if (n % 2) {
                        cout << 3 << " ";
                        n -= 3;
                    }
                    while (n) {
                        cout << 2 << " ";
                        n -= 2;
                        }
                    cout << endl;
                }
            }
            
        }
    }
}
ac;
 
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ac.solve();
    
    return 0;
}

题目3

题目链接 题目大意： 在一个二维的网格上，每次可以走向相邻格子； Alice和Bob在网格位置（xA, yA）上，Bob要前往格子(xB, yB)，Alice要前往格子(xC, yC)；假设Alice和Bob都只会选择到达目的地的最短路径，现在想知道，他们两个可以共同经过的格子数，最大为多少；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例3行第一行整数𝑥𝐴 and 𝑦𝐴 (1≤𝑥𝐴,𝑦𝐴≤1e8 ) 第二行整数𝑥B and 𝑦B (1≤𝑥B,𝑦B≤1e8 ) 第三行整数𝑥C and 𝑦C (1≤𝑥C,𝑦C≤1e8 )

输出： 每个样例一行，输出可以共同经过的最大格子数。

Examples input 3 3 1 1 3 6 4 5 2 2 2 7 2 1 1 4 3 5 5

output 3 1 6

题目解析： 首先以位置A为坐标原点，重新绘制坐标轴，我们得到新的坐标位置B和C。此时两个人都在坐标原点，坐标B、C分别在四大象限或者数轴上。可以分情况讨论2个人坐标位置在相同象限、不同象限的情况，但是这样分析简单，实现起来比较复杂。另外一种做法，就是拆解从原点到坐标B和坐标C的过程。比如说先考虑横坐标X，如果他们两个人方向相同，则得到两个人X坐标较小值为共同距离；再考虑横坐标Y，如果他们两个人方向相同，则得到两个人Y坐标较小值为共同距离；加上在原点的共同格子，就得到答案了。

#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long lld;
 
class Solution {
    static const int N = 201010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            pair<int, int> a, b, c;
            cin >> a.first >> a.second;
            cin >> b.first >> b.second;
            cin >> c.first >> c.second;
            b.first -= a.first;
            b.second -= a.second;
            c.first -= a.first;
            c.second -= a.second;
            
            int ans = 1;
            // 判断x相同的数量
            if (b.first > 0 && c.first > 0) ans += min(abs(b.first), abs(c.first));
            if (b.first < 0 && c.first < 0) ans += min(abs(b.first), abs(c.first));
            // 判断y相同的数量
            if (b.second > 0 && c.second > 0) ans += min(abs(b.second), abs(c.second));
            if (b.second < 0 && c.second < 0) ans += min(abs(b.second), abs(c.second));
            
            cout << ans << endl;
            
        }
    }
}
ac;
 
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ac.solve();
    
    return 0;
}

题目4

题目链接 题目大意： 小明要设置密码，密码长度为m，由数字0到9组成，并且密码不能为字符串s的子序列；同时有字符串l和字符串r，小明设置的密码a要满足 l[i] <= a[i] 且 a[i] <= r[i]; 问，小明是否能够找到满足要求的密码。

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例4行第一行字符串𝑠(1≤|𝑠|≤3⋅1e5) 第二行整数𝑚 ，表示字符串l和m的长度 (1≤𝑚≤10 ) 第三行字符串l 第四行字符串r

输出： 每个样例一行，如果有满足要求的密码，则输出YES；如果不存在则输出NO；

Examples input 5 88005553535123456 2 50 56 123412341234 3 111 444 1234 4 4321 4321 459 2 49 59 00010 2 10 11

output YES NO YES NO YES

题目解析： 如果采用暴力做法，枚举小明可能存在的密码数量，会有比较大的数量，并且判断是否为子序列也有O(N)的复杂度；换一种分析的思路，站在小明的角度，对于第i个密码，他一共有vec若干个选择，也就是区间（l[i]， r[i]）；对于字符串s，我们从左到右遍历，如果某个字符没有出现在vec中，那么这个字符对题目没有影响，可以直接跳过；如果某个字符c在vec中出现，那么可以在vec中移除这个字符，表示小明无法选择这个字符；不断重复这个过程，直到vec为空（进入i+1个密码字符），或者字符串s遍历完。如果最终字符串s遍历完了，vec还有字符，那么存在vec中存在的字符，必然就是字符串s不存在的字符子序列。

证明：这个题目没有想到很好的证明方式，就是在分析题目过程中，突然浮现在脑海中的一种贪心思路。核心思想，字符串想用更少字符区间去覆盖小明能选择的字符。对于第1个字符，假设有若干个选择，那么字符串s最少需要区间[1, pos1]才能覆盖到这么多选择；同理对于第2个字符，我们需要[pos1 + 1, pos2]这样的区间去覆盖； ... 直到第m个字符。假设字符串m能切割出来m个这样的区间，那么必然小明是无解的。

#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long lld;
 
class Solution {
    static const int N = 201010;
    string s;
    char a[20], b[20];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> s;
            int m;
            cin >> m;
            cin >> a >> b;
            
            int ans = 0, pos = 0;
            for (int i = 0; i < m; ++i) {
                vector<char> v;
                for (int j = a[i]; j <= b[i]; ++j) {
                    v.push_back(j);
                }
                while (!v.empty() && pos < s.length()) {
                    vector<char>::iterator it =  find(v.begin(), v.end(), s[pos]);
                    if (it != v.end()) {
                        v.erase(it);
                    }
                    ++pos;
                }
                if (pos == s.length() && !v.empty()) {
                    ans = 1;
                }
            }
            cout << (ans == 1 ? "YES":"NO") << endl;
        }
    }
}
ac;
 
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ac.solve();
    
    return 0;
}

题目5

题目链接 题目大意： 小明在参加比赛，一共做了n道题目；初始状态0分，每道题目有得分a[i]，如果是正数则加分，如果是负数则扣分；现在可以选定一个整数k，在计算得分的过程中，如果小明分数大于等于k，则后续分数不会再小于k分（如果遇到负数，扣分之后最小分为k）；问整数k为多少，才能使得小明最后分数最大。

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例2行第一行整数n ，表示数组长度（1 ≤ n ≤ 3e5) 第二行n个整数，𝑎1,𝑎2,…,𝑎𝑛 (−1e9≤𝑎𝑖≤1e9 ; 𝑎𝑖≠0 )

输出： 每个样例一行，输出使得小明分数最大整数k（区间范围内[−1e18, 1e18])，如果有多个可以输出任意一个；

Examples input 4 4 3 -2 1 2 3 -1 -2 -1 2 4 2 7 5 1 -3 2 -1 -2 2

output 3 0 25 6

题目解析： 如果题目没有负数，则任意选择整数即可；如果题目只有1个负数，那么选择这个负数前面的元素之和作为k，这样就可以抵消该负数的扣分；如果题目有2个负数，假如两个负数连起来能产生更大的负数，那么就用第一个负数前面的元素之和；如果两个负数中间存在正数，并且该正数大于任何一个负数，那么两个负数必然无法产生更大负数，那么选择较大负数前面的元素之和作为整数k；如果题目有更多负数，其实也可以简化为前面的情况，也就是找到一个区间，区间内元素之和是最大的负数，那么这个区间前面的元素之和就是k；

每个位置记录一下sum[i]表示包括第i个元素的区间最小和，对于i+1元素，要么与前面区间和sum[i]合并，得到sum[i]+a[i]；要么就是单独成为一个区间a[i]；遍历一遍就可以得到最大负数的连续区间。

#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long lld;
 
class Solution {
    static const int N = 301010;
    lld 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];
            lld minSum = 0, pos = -1, curSum = 0;
            for (int i = 0; i < n; ++i) {
                curSum = min(0ll, curSum) + a[i];
                if (curSum < minSum) {
                    minSum = curSum;
                    pos = i;
                }
            }
            if (minSum < 0) {
                lld tmp = 0;
                do {
                    tmp += a[pos];
                    --pos;
                } while (tmp != minSum);
                lld ans = 0;
                for (int i = 0; i <= pos; ++i) ans += a[i];
                cout << ans << endl;
            }
            else {
                cout << 0 << endl;
            }
            
        }
    }
}
ac;
 
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ac.solve();
    
    return 0;
}