首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >程序员进阶之算法练习(七十七)

程序员进阶之算法练习(七十七)

作者头像
落影
发布于 2023-05-27 06:08:16
发布于 2023-05-27 06:08:16
21400
代码可运行
举报
文章被收录于专栏:落影的专栏落影的专栏
运行总次数:0
代码可运行

题目1

题目链接 题目大意: 给出n个整数的数组a,数组的元素可能是1或者2; 现在想要找到一个最小的位置k满足: 𝑎1⋅𝑎2⋅…⋅𝑎𝑘=𝑎𝑘+1⋅𝑎𝑘+2⋅…⋅𝑎𝑛

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

输出: 每个样例一行,输出最小的位置k;如果不存在k,则输出-1;

Examples input 3 6 2 2 1 2 1 2 3 1 2 1 4 1 1 1 1

output 2 -1 1

题目解析: 由于题目数字取值范围只有1和2,1不影响乘积,那么只需要考虑2; 如果数组中有偶数个整数,那么题目有解; 注意如果是0个数字2,那么答案是1;

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            vector<int> pos;
            for (int i = 1; i <= n; ++i) {
                int tmp;
                cin >> tmp;
                if (tmp == 2) pos.push_back(i);
            }
            int ans = 1;
            if (pos.size() % 2) ans = -1;
            else if (pos.size() > 0) ans = pos[pos.size() / 2 - 1];
            
            cout << ans << endl;
        }
    }
}

题目2

题目链接 题目大意: 给出一个整数n,将整数n拆成两个整数A和B,要求满足: A+B=n; A和B的数字和最多相差1;

数字和的意思就是将整数A的各个位置数字相加,比如说198就是1+9+8=18,208就是2+0+8=10;

输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例1行,第一行整数𝑛 (2≤𝑛≤1e9)

输出: 每个样例一行,输出A和B,题目保证结果存在;

Examples input 5 1 161 67 1206 19 output 1 0 67 94 60 7 1138 68 14 5

题目解析: 当n是偶数的时候,A=B=n/2,必然满足要求; 当n是奇数时,我们可以令A=n/2, B=n - n/2,这样有A和B必然满足A+B=n情况,接下来讨论AB数字和相差1的的情况: 1、当A的个位数小于9时,A和B必然数字和只差1,比如说81和82,78和79; 2、当A的个位数等于9时,由于B会进位,最终A和B的数字和会产生一个差值,比如说9和10,39和40,99和100; 由此我们可以产生一个朴素的做法:令A--,B++,最终肯定能够找到符合要求的数字;

但是这么做的话,会出现超时(TLE)的情况,我们来分析下复杂度。 当数字为999和1000时,数字和相差(9+9+9) - 1 = 26的情况,那么要A的数字和-13,B的数字和+13; 我们知道获得数字和13最快的情况是十位数4+个位数9,那么结果为A=999-49=950,B=1000+49=1049; 如果采用枚举的复杂度,需要枚举49次;

最坏的情况,数字n为199999999,A=99999999,B=100000000,A和B的数字和相差(9 * 8) - 1=71,也就是说A需要减去数字和35,B需要加上数字和36; 最终数字A为 99999999 - 8999 = 99991000,数字和是72-35=37; 最终数字B为100000000 + 8999 = 1000089999,数字和是1+36=37; 枚举的复杂度是10000左右,加上每次计算数字和的复杂度 和 样例数量,最终复杂度为10000 * 10 * 10000 = 1e9,复杂度偏高;

优化方式1:每次在计算A--和B++的时候,直接按照数字和一半进行操作,比如说数字和一半是37,那么A-=37,B+=37,这样效率能加快一些;因为最终数字和会逐步收敛,结果保证是正确的;

优化方式2:直接按照数字和之差,从个位数开始往高位填9,直到数字和小于9,则在当前位数填下剩余数字,比如说37就得到8999,13就得到49;这样可以O(1)得到最优解。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    static const int N = 201010;
    int digSum(int x) {
        int ret = 0;
        while (x) {
            ret += x % 10;
            x /= 10;
        }
        return ret;
    }
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int x = n / 2, y = n - x;
            while (abs(digSum(x) - digSum(y)) > 1) {
                int dif = abs(digSum(x) - digSum(y)) / 2;
                x -= dif;
                y += dif;
            }
            cout << x << " " << y << endl;
        }
    }
}

题目3

题目链接 题目大意: 给出n个整数的数组,从数组中选择两个数字a[i]和a[j],要求满足: i和j不相同; | a[i] - a[j] |的值,等于数组中最大值与最小值的差; 问,最多能选出多少个组合。

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

输出: 每个样例一行,输出满足要求的组合数。

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

样例解释: 样例1,满足要求的有[1, 8]和[8, 1]; 样例1,满足要求的有[2, 10]和[10, 2],其中2可以为第2个数字、第5个数字;

题目解析: 因为选出来的数字要满足差的绝对值最大,那么必然是最大值和最小值的组合。 假设最小值x,最大值y,首先看x和y是否相同。 如果x==y,则看x的总数,答案就是A(n, 2),即是从n个整数中选择2个数字的组合排列数; 如果x!=y,那么结果就是x的数量与y的数量的乘积。

trick: 两个情况都可能超int32。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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];
            }
            sort(a, a + n);
            if (a[0] == a[n - 1]) cout << n * 1LL * (n - 1) << endl;
            else {
                int x = 0, y = 0;
                while (a[x] == a[0]) {
                    ++x;
                }
                while (a[n - 1 - y] == a[n - 1]) {
                    ++y;
                }
                cout << x * 1LL * y * 2 << endl;
            }
        }
    }
}

题目4

题目链接 题目大意: 给出1到n的n个整数的数组,现在需要从数组里面选择新的数组,但是已知有m对整数是不能共存: 比如说整数2和4不能共存,则新的数组里面不能同时存在2和4,比如说整数数组[1,2,3,4,5],其中[2,3]和[3,4]都是合法的,[2,3,4]是不合法的; 现在想知道,能选出多少个子数组,里面不存在不合法的整数对。

输入: 第一行,整数𝑡 表示t个样例𝑡 (1≤𝑡≤2⋅1e4), 每个样例第一行整数 𝑛 and 𝑚 (2≤𝑛≤1e5, 0≤𝑚≤1e5) 接下来m行整数 𝑥𝑖 and 𝑦𝑖 (1≤𝑥𝑖,𝑦𝑖≤𝑛, 𝑥𝑖≠𝑦𝑖),表示两个不能相互相处的整数。

输出: 每个样例一行,输出满足要求的组合数。

Examples input 2 3 2 1 3 2 3 4 2 1 2 2 3 output 4 5 样例解释: 样例1,满足要求的有整数[1],[2],[3],[1,2]; 样例2,满足要求的有整数[1],[2],[3],[4],[3,4];

题目解析: 对于子数组[x, y],我们可以枚举做区间x,再考虑y的取值; 首先y要满足x <= y,考虑所有y的取值,只要包括一个不能相处整数对,那么后续的整数就不用考虑,比如说样例2: x=1,我们考虑y=1,2,3,4的情况,当我们发现整数1和2是不能相处的,那么2以及2后面的整数就不用考虑; 也即是说,我们只需要向右遍历到第一个出现的最小不能相处整数对的右区间y,[x, x]到[x, y-1]的区间都是合法的;

现在的问题变成了,对于选定整数x,如何快速得到右边区间最小的整数对; 假设我们把所有不合法整数对都按照左区间归类,然后从右到左遍历整数数组。 比如说遍历到整数i,那么对于所有做左区间≥i的整数对,都是在i的右边;

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        int tmp = 0;
        while (t--) {
            ++tmp;
            int n, m;
            map<int, vector<int> > mp;
            cin >> n >> m;
            while (m--) {
                int x, y;
                cin >> x >> y;
                if (x < y) {
                    mp[x].push_back(y);
                }
                else {
                    mp[y].push_back(x);
                }
            }
            lld sum = 0;
            int leftMin = n + 1;
            for (int i = n; i > 0; --i) {
                if (mp[i].size()) {
                    sort(mp[i].begin(), mp[i].end());
                    leftMin = min(leftMin, mp[i][0]);
                }
                sum += leftMin - i;
            }
            cout << sum << endl;
        }
    }
}

题目5

题目链接 题目大意: 给出n个整数,询问是否存在两个整数,最大公约数不是1; 如果存在则输出YES,如果不存在则输出NO;

输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e5); 每个样例第一行整数 𝑛 (2≤𝑛≤1e5). 接下来n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9).

输出: 每个样例一行,输出是否满足要求。

Examples input 2 3 32 48 7 3 14 5 9 output YES NO

题目解析: 先不考虑复杂度,最直接的做法,就是求出每个整数的因子,复杂度是O(M),M是整数的大小的根,10^9需要遍历1w+次; 然后用map管理每个整数的因子,遍历每一个整数求是否有相同的因子,整体复杂度在O(NM)左右,map的复杂度可以暂时忽略; 总的复杂度会到达10^5 * 10^5 = 10^10量级,时间上是不允许的。

分析这个里面的优化空间,每个整数的因子最终都可以拆分为若干素数,这样就可以大幅度减少因子数量; 先预处理1-sqrt(10^9)的素数,再用这个素数去筛选n个整数,这样速度会更加快。

trick:这个如果遇到两个相同数字,就会出现异常。 另外在拆解的时候,一定要拆解数字到x = a * b * c这样的形式。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int m = sqrt(1e9) + 1;
        vector<int> vec;
        
        for (int i = 2; i<= sqrt(m); ++i) {
            if (!a[i]) {
                int tmp = i;
                while (tmp <= m) {
                    tmp += i;
                    a[tmp] = 1;
                }
            }
        }
        for (int i = 2; i <= m; ++i) {
            if (!a[i]) {
                vec.push_back(i);
//                cout << i << " ";
            }
        }
        
        int t;
        cin >> t;
        while (t--) {
            int n;
            map<int, int> mp;
            cin >> n;
            bool ok = 0;
            for (int i = 0; i < n; ++i) {
                int k;
                cin >> k;
                vector<int> tmp;
                for (int j = 0; j < vec.size(); ++j) {
                    if (k % vec[j] == 0) {
                        tmp.push_back(vec[j]);
                        while (k % vec[j] == 0) k /= vec[j];
                    }
                }
                if (k != 1) {
                    tmp.push_back(k);
                }
                
                for (int j = 0; j < tmp.size(); ++j) {
                    if (mp[tmp[j]]) ok = 1;
                    mp[tmp[j]] = 1;
                }
            }
            cout << (ok ? "YES" : "NO") << endl;
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-05-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
程序员进阶之算法练习(八十七)
题目链接 题目大意: 给出一个整数的数组,长度为n; 现在可以进行以下的操作: 选择长度不小于2的区间[l, r],将区间内的整数依次进行异或操作,然后将得到的整数替换区间所有的数字;
落影
2023/10/18
2040
程序员进阶之算法练习(八十七)
程序员进阶之算法练习(九十七)
现在光标停留在最左边的数字1处,我们可以进行以下的操作: 1、将当前光标所在位置的数字输出; 2、移动光标到相邻的数字,比如说从1移动到2,从2移动到3;(1的左边不能移动,0的右边不能移动)
落影
2024/02/10
1250
程序员进阶之算法练习(九十七)
程序员进阶之算法练习(七十九)
题目链接 题目大意: 有n个人参加投票,小明是第一个; 投票一共k轮,每轮每个人会做出一个选择,分别用+和-表示,那么一共有三个结果: +的人数大于-的人数,那么-的人出局; -的人数大于+的人数,那么+的人出局; 如果+和-的人数一样多,那么所有人出局; 出局的人,不再参与后续投票。
落影
2023/07/09
1650
程序员进阶之算法练习(七十二)
题目链接 题目大意: 给出一个字符串,由小写字母组成; 现在Alice和Bob在玩游戏,轮流从字符串中移除一个子串,Alice先操作; Alice允许移除偶数长度子串,Bob允许移除奇数长度子串;(也允许不移除) 最终看每个人移除子串的分数总和,字母a是1分,b是2分、、、z是26分; 问最终谁能赢得游戏,以及胜者领先的分数;
落影
2023/03/07
2850
程序员进阶之算法练习(七十八)
题目链接 题目大意: 在二维坐标系中,每次有两个走法: 1、从(𝑥,𝑦) 到 (𝑥+1, 𝑦+1); 2、从(𝑥,𝑦) 到 (𝑥-1, 𝑦);
落影
2023/07/09
1670
程序员进阶之算法练习(一百)
题目链接 题目大意: 给出一个整数,问该整数能否切分为两个数字a和b,满足: 1、a和b都不包括前导零,是一个正常的数字; 2、a和b都大于0; 3、b > a;
落影
2024/03/09
1250
程序员进阶之算法练习(九十五)
题目链接 题目大意: 有n个整数的数组a,现在需要构造一个1到n的排列b; 令𝑐𝑖 = 𝑎𝑖−𝑏𝑖,希望最终𝑐𝑖 出现尽可能多的不同整数。
落影
2024/01/06
1430
程序员进阶之算法练习(九十五)
程序员进阶之算法练习(七十一)
题目链接 题目大意: 给出n个整数,每次可以选择其中两个整数a[i]和a[j],令a[i]=x和a[j]=y,但是需要满足a[i] | a[j] = x | y;(|是或操作) 现在可以进行任意次操作,问n个整数的最小和是多少。
落影
2023/01/01
2290
程序员进阶之算法练习(八十)
题目链接 题目大意: 有一个数组a,仅有整数1和-1组成,我们定义数组a的乘积为: 对于 1≤𝑖<𝑗≤𝑛, 𝑎[𝑖]⋅𝑎[𝑗]=1的数量。
落影
2023/07/25
2050
程序员进阶之算法练习(九十四)
题目链接 题目大意: 有n个整数组成的数组a,现在可以对数组a的元素任意打乱顺序,要求满足: 假设打乱后的数组是b,要满足:𝑏1+𝑏2=𝑏2+𝑏3=…=𝑏𝑛−1+𝑏𝑛=k 也就是相邻两个数字的和相同。
落影
2023/12/23
1130
程序员进阶之算法练习(九十四)
程序员进阶之算法练习(七十四)
题目链接 题目大意: 给出一个整数n,现在可以对整数执行一个操作: 选择整数上两个不同位数的数字交换位置,然后移除整数最右边一位的数字; 重复这个过程,直到整数只剩下1位; 现在想知道这个剩下的数字最小可能为多少。
落影
2023/03/07
2150
程序员进阶之算法练习(八十三)
题目链接 题目大意: 有长度为n的整数数组a,数组元素都由-1和1组成; 现在每次可以选择一个数组位置,翻转位置上元素(-1变成1,1变成-1); 假如想要实现下面的要求,最少需要多少次操作: 𝑎1+𝑎2+…+𝑎𝑛≥0 𝑎1⋅𝑎2⋅…⋅𝑎𝑛=1
落影
2023/08/20
2510
程序员进阶之算法练习(八十一)
题目链接 题目大意: 给出n个整数的数组,现在可以对数组进行以下操作: 选择数组中任意两个不同的整数a[i]和a[j],令a[i]=x,a[j]=y,其中满足x*y = a[i] * a[j];
落影
2023/08/09
3680
程序员进阶之算法练习(八十八)- CF883
题目链接 题目大意: 在地面上有n个点,点都在同一条垂直地面的线上面,每个点的高度为a[i]; 每个点有一条绳子,绳子长度为b[i],一端连着点,一端连着小球(每个点相连的小球是同一个);
落影
2023/10/23
1880
程序员进阶之算法练习(八十八)- CF883
程序员进阶之算法练习(六十七)
题目链接 题目大意: 给出n个整数的数组a和b,现在可以执行任意次下面的操作: 选择索引x,交换数组a和b中的元素a[x]和b[x];
落影
2022/10/04
2570
程序员进阶之算法练习(九十三)
题目链接 题目大意: 有3个字符a/b/c,排成一行; 现在可以选择两个字符,交换对应的位置; 上述操作最多只能执行一次,问能否得到abc的顺序。
落影
2023/12/18
1560
程序员进阶之算法练习(六十八)
题目1 题目链接 题目大意: 有n个球,序号分别是1、2、3、、、、n,每个球上面有一个数字a[1]、a[2]、a[3]、、、a[n],这组数字是不递减的,即是 a[i]≤a[i+1], 1≤i<𝑛; 现在需要给n个球染色,需要满足: 1、每个球只有一个颜色; 2、将某个颜色的球挑选出来,按照序号从小到大放好,上面的数字是严格递增; 问,最少需要几个颜色。 输入: 第一行是𝑡,表示样例数 (1≤𝑡≤100) 每个样例两行,第一行是整数𝑛 (1≤𝑛≤100) 第二行是n个整数 𝑎1,𝑎2,…
落影
2022/10/04
2440
程序员进阶之算法练习(七十五)
题目链接 题目大意: 给出整数n、a、b,询问是否存在由数字1到n组成的排列p和q,满足下面条件: 排列p和q的最长公共前缀长度是a; 排列p和q的最长公共后缀长度是b;
落影
2023/03/12
2320
程序员进阶之算法练习(八十二)
题目链接 题目大意: 给出一个整数n,构造一个长度为n的整数数组a,满足: 1、1≤𝑎𝑖≤1000 对于所有的 1≤𝑖≤𝑛; 2、𝑎𝑖 能整除𝑖,对于所有的 1≤𝑖≤𝑛; 3、𝑎1+𝑎2+…+𝑎𝑛 能够整除 𝑛 .
落影
2023/08/13
2130
程序员进阶之算法练习(八十六)
题目链接 题目大意: 给出n个整数,已知这n个整数是按照下面的规则生成。 1、初始化的时候,数组中有2个整数,每次从数组中选择任意两个整数,计算得到他们差值的绝对值,重新放回数组; 2、重复n-2次操作1,得到n个元素的数组。
落影
2023/09/25
1580
相关推荐
程序员进阶之算法练习(八十七)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验