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

前言

这次的题目质量非常高,除了第一道签到题之外都是很不错的想法题,值得学习。

  • 几乎所有的程序员都能做A题;
  • 思维缜密的程序员可以做B题;
  • 数学还没还给老师的能做C题;
  • 接受过算法训练的能过D,E题;

看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。

文集: 程序员进阶之算法练习(一) 程序员进阶之算法练习(二) 程序员进阶之算法练习(三) 程序员进阶之算法练习(四) 代码地址

A

题目链接 题目大意:2个人,投掷n次骰子,大的赢,问谁赢,平局输出"Friendship is magic!^^"。 代码实现

题目解析: 如题,照着写即可。

B

题目链接 题目大意:n个城市,第i和i+1之间有一条边,第n个和第1个有边。n个城市中有k个特殊城市,与n个城市之间都存在边。每个城市有一个权重c[i],边(i, j)的值为c[i] * c[j]。 求所有边的值的和。

代码实现

    long long sum = 0, ans = 0, n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        sum += c[i];
    }
    for (int i = 1; i <= m; ++i) {
        long long k;
        cin >> k;
        flag[k] = 1;
        sum -= c[k];
        ans += c[k] * sum;
    }
    for (int i = 1; i <= n; ++i) {
        int next;
        if (i == n) {
            next = 1;
        }
        else {
            next = i + 1;
        }
        if (!flag[next] && !flag[i]) {
            ans += c[i] * c[next];
        }
    }
    
    cout << ans;

题目解析: 首先n个城市形成一个环,其次每一个特殊城市都会新增若干条边。任意两个城市之间最多只有一条边。

第1个特殊城市a[1],新增n条边,其中2条边和环重叠; 第i个特殊城市a[i],新增n条边,其中2条边和环重叠,i-1条边和之前特殊城市形成的边重叠;

为了便于计算,先不考虑环。 第1个特殊城市a[1],新增n条边; 第i个特殊城市a[i],新增n条边,i-1条边和之前特殊城市形成的边重叠; 先计算出所有特殊城市产生的边; 对于环上的边,如果两点都不是特殊城市,那么是还没计算过的边; 可以求出总和。

C

题目链接 题目大意:n个点形成的多边形,整体以v的速度向x轴负方向移动;点P从(0,0)向(0,w)以最大u的速度前进。问,不撞到多边形的最短到达时间。(相交不算碰撞)

代码实现

    long long sum = 0, ans = 0, n, w, v, u;
    cin >> n >> w >> v >> u;
    double k = u * 1.0 / v, ret = 0, l = w * 1.0 / u, minT = 10E9, maxT = -10E9;
    while (n--) {
        long long x, y;
        cin >> x >> y;
        double t = y - k * x;

        minT = min(minT, -t / k);
        maxT = max(maxT, -t / k);
    }
    if (minT >= 0) {
        ret = l;
    }
    else if (maxT <= 0) {
        ret = l;
    }
    else {
        ret = l + maxT / v;
    }
    printf("%.6lf", ret);

题目解析

为了达到最短时间,并且点与多边形碰撞,可以知道会有如下结果: 1、点直接到(0,w); 2、点在行进过程中等待若干时间,到达(0,w);

核心:变换参考系,假设多边形不动,把v的速度叠加到点P上,那么变成点P以-v的速度在x轴运动。 求出每个点相对点P的速度斜率曲线在X轴上的距离,得到最大和最小的两个值minT和maxT。 如果minT>=0或者MaxT<=0,点P可以直接到达点w;(多边形太远和太近两种情况) 其他情况,点P要在x轴移动maxT的距离,再直线到达点w。(在x轴移动maxT的距离相当于等待maxT/v的时间)

D

题目链接 题目大意:给出有n个数字的数组a, 有m个询问。 (1 ≤ n ≤ 1 000 000)(1 ≤ a[i] ≤ 10e9) (1 ≤ m ≤ 1 000 000) 询问给出两个数字l, r。(1 ≤ l ≤ r ≤ n) 在区间[l, r]中,把出现偶次的数字统计出来。对这些数字求异或,得到询问的值。

代码实现:(树状数组)

int low_bit(int x) {
    return x & (-x);
}

void tree_add(int x, int v) {
    while (x <= n) {
        tree[x] ^= v;
        x += low_bit(x);
    }
}

int tree_sum(int x) {
    int sum = 0;
    while (x) {
        sum ^= tree[x];
        x -= low_bit(x);
    }
    return sum;
}

题目解析: 区间求值,数据量极大,可以猜测是从区间相减来求子区间的值,从这里出发。 [l, r]区间的偶数次的数字的异或和为sumA; [l, r]区间的奇数次的数字的异或和为sumB; sumA ^ sumB的值为什么? [l, r]区间段所有数字的异或和!

其中sumB直接对[l, r]所有的区间求异或和即可;(偶次的会为0) 重点就是[l, r]的不重复的异或和。 用map<int, int> 来维护a[i]上一次出现的位置,如果a[i]已经出现,那么在原来的位置进行异或即可。 于是变成区间[l, r]求和。 这个是树状数组最擅长的事情了。

E

题目链接 题目大意:n个数字,从中选取m个数字,使得乘积S被k整除。如果有多个组合,m最小;还有多个,S最小。(1 ≤ n ≤ 1 000, 1 ≤ k ≤ 10e12). 代码实现

int n;
    long long k;
    cin >> n >> k;
    long long t = sqrt(k);
    
    for (long long i = 1; i <= t; ++i) {
        if (k % i == 0) {
            vec.push_back(k / i);
            vec.push_back(i);
        }
    }
    int vecSize = vec.size();
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vecSize; ++i) {
        Hash[vec[i]] = i;
    }
    
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        b[i] = gcd(a[i], k);
    }
    if (k == 1)
    {
        cout << 1 << endl;
        cout << min_element(a + 1, a + 1 + n) - a << endl;
        return 0;
    }
    
    for (int j = 1; j < vecSize; ++j) {
        dp[0][j] = make_pair(n + 1, 0);
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < vecSize; ++j) {
            long long gcdnum = gcd(b[i], vec[j]);
            int pre = Hash[vec[j] / gcdnum];
            
            dp[i][j] = min(dp[i - 1][j], make_pair(dp[i - 1][pre].first + 1, dp[i - 1][pre].second + a[i]));
        }
    }
    
    
    if (dp[n][vecSize - 1].first > n) {
        cout << -1 << endl;
        return 0;
    }
    else {
        cout << dp[n][vecSize - 1].first << endl;
        int pre = vecSize - 1;
        for (int i = n; i > 0; --i) {
            if (dp[i][pre] == dp[i - 1][pre]) {
                continue;
            }
            printf("%d ", i);
            pre = Hash[vec[pre] / gcd(vec[pre], b[i])];
        }
    }

题目解析: 求出k的所有非1因子集合T,那么对于数字a[i],不为T的因子没有用。 那么题目变成: 一堆物品,每个物品都有相应的cost(数量,大小),要把背包背满(可以超过),使得总数量最小,并且总数字和最小。 题目非常明显的是DP。

d[i][j][k] 表示前i个数字,第j个因子有k个的最小总数和最小数字和。 最后在所有 d[n][j][k] 中第j个因子中,k大于题目要求中,寻找最小值即可。

d[i][j][k] 根据第i个数的因子,有: d[i][j][k] = min(d[i - 1][j][k], d[i-1][j-s][k-t]) s、t取决于k的第j个因子的个数。

状态复杂度n*k的因子数K,10^12的因字数不会超过45个,按50个算。那么状态数最大为 50000个。 转移复杂度为O(1)。 那么总得复杂度O(N x K).

这种做法的难点在于,对于一个数字,转移的时候无法通过一个式子来表达。(一个数字有多个参数)

换一种dp的表示方式。 求出K的所有约数,15=1,2,3,5,15。 于是,一个数的状态可以表示成从左到右的移动。 dp[i][j]表示前i个数字,能前进到第j个的最优解。 dp[i][j] = min(dp[i-1][j], dp[i-1][j/gcd(k, x)] + 1); 题目可解。复杂度O(N * K). K为因子个数

卡在某个地方很久: b[i] = gcd(a[i], k); 可以优化,减少gcd的复杂度。

总结

任务和娱乐全在一念之间。 同样的Codeforces,在训练期间是任务,毕业之后却是娱乐。 任务重要是完成,娱乐却是要让自己满意。 如今很愿意花时间在Codeforces上,即使如今的选择比以前更多。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

数学菜鸟的AI学习攻略 | 数学符号轻松入门

50740
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 转向机车

转向机车类继承机车类并增加转向行为。每个行为都被定义成公开函数,在每帧或者一段时间间隔内调用以实现对应的转向力。通常所有转向力在调用之后再调用机车的update...

21670
来自专栏数值分析与有限元编程

定积分的精确定义

定积分与不定积分之间的关系:若定积分存在,则它是一个具体的数值(曲边梯形的面积),而不定积分是一个函数表达式,它们仅仅在数学上有一个计算关系(牛顿-...

74430
来自专栏算法channel

动态规划|相邻约束下的最优解(House Robber II )

01 House Robber II This time, all houses at this place are arranged in a circl...

38240
来自专栏专知

【LeetCode 202】 关关的刷题日记35 – Leetcode 202. Happy Number

关关的刷题日记35 – Leetcode 202. Happy Number 题目 Write an algorithm to determine if a n...

28970
来自专栏Vamei实验室

概率论02 概率公理

概率论早期用于研究赌博中的概率事件。赌徒对于结果的判断基于直觉,但高明的赌徒尝试从理性的角度来理解。然而,赌博中的一些结果似乎有矛盾。比如掷一个骰子,每个数字出...

23290
来自专栏灯塔大数据

每周学点大数据 | No.4算法的分析之时间复杂度

No.4期 算法的分析之时间复杂度 小可:嗯,我觉得评价一个算法的最基本方式就是看它运行得快不快。 Mr. 王:嗯,这是重要的考量标准之一。研究算法运行得快不...

29990
来自专栏码匠的流水账

hyperloglog的java版使用

对于海量数据来说,数据内存占用会变得很高. Probabilistic数据结构牺牲了一下准确率去换取更低内存占用。比如一个HyperLogLog的数据结构只需要...

20010
来自专栏小樱的经验随笔

2017"百度之星"程序设计大赛 - 复赛1003&&HDU 6146 Pokémon GO【数学,递推,dp】

Pokémon GO Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K...

35270
来自专栏专知

关关的刷题日记84 – Leetcode 231. Power of Two

关关的刷题日记84 – Leetcode 231. Power of Two 题目 Given an integer, write a function to ...

32770

扫码关注云+社区

领取腾讯云代金券