算法算法文集程序员

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

2016-08-28  本文已影响270人  落影loyinglin

前言

这次只有四个题目,E题是个奇奇怪怪的数学题,就不去啃这个硬骨头了,我们来分析下A/B/C/D:

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

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

A

题目链接
题目大意:输入n,输出一个字符串。
n = 1:I hate it
n = 2:I hate that I love it
n = 3:I hate that I love that I hate it

代码实现

    int n;
    cin >> n;
    
    string ret = "I hate ";
    for (int i = 0; i < n - 1; ++i) {
        if (i % 2 == 0) {
            ret += "that I love ";
        }
        else {
            ret += "that I hate ";
        }
    }
    ret += "it";
    cout << ret << endl;

题目解析
找规律。
把字符串分割成三部分"I hate " + ... + "it",再根据n构建中间的字符串。

B

题目链接
题目大意:有一个数字游戏:给出一堆整数,轮流进行操作,不能操作者输;
操作是把一个正整数x拆成两个正整数i,j并且i + j = x。
现在有n个整数a[i],小明希望知道当只有前i个(i=1~n)数字的时候,游戏的胜率情况。

输入:
第一行 n (1 ≤ n ≤ 100 000)
第二行 n个数字,a1, a2, ..., an (1 ≤ a[i] ≤ 1e9),

输出:
n行数据,第i输出假如只有前i个数字的时候,游戏的胜负情况;
如果先手者赢则输出1,如果后手者赢则输出2;

Examples
input
3
1 2 3
output
2
1
1

代码实现

    int n, t = 1; // 1表示先手必败 0表示先手必胜
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        if (k != 1) {
            t = 1 -( t ^ (k % 2));
        }
        cout << t + 1 << endl;
    }

题目解析
假设,先手必胜为0, 先手必败为1.
那么有
0 + 1 = 0
1 + 0 = 0
0 + 0 = 1
1 + 1 = 1
异或操作符嘛。
具体理解思路就是:
1、当你对一个数x进行拆分时,其实就是拆分必胜和必败的状态;
2、必胜一步可以转为必败,必败一步可以转成必胜;
所以实际上根据奇偶数就可以判断必败或者必胜。
比如说:1是必败,那么2就是必胜,3就是必败,4就是必胜。

C

题目链接
题目大意
这是一个手机系统本地推送的模拟。
先输入n、q, n为应用数量,q为操作数量。(1 ≤ n, q ≤ 300 000)
接下来q行,每行有两个数字x、y:

问每次输入后,剩余的未读数量。

Examples
input
3 4
1 3
1 1
1 2
2 3
output
1
2
3
2

代码实现

int n, m, ls = 1, k = 0, sum = 0;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        lld x, y;
        cin >> x >> y;
        if (x == 1) {
            a[++k] = y;
            ++num[y];
            ++sum;
        } else if (x == 2) {
            sum -= num[y];
            num[y] = 0;
            flag[y] = k;
        }
        else if (x == 3) {
            for (; ls <= y; ++ls) {
                if (ls > flag[a[ls]]) {
                    flag[a[ls]] = ls;
                    --num[a[ls]];
                    --sum;
                }
            }
        }
        cout << sum << endl;
    }

题目解析
题目的难点在于操作2会更新应用所有的通知 以及 操作3读取前y个notify的去重。
观察题目,发现只关注未读的数量,而未读的数量只有操作1能产生。

把操作1形成的数字看成一串数列,num[i]记录id为i的应用目前的未读数量;
对于操作2,只需把num[y]清空,添加flag[y]=k的标志,表示应用y在第k个以前全部已读;
对于操作3,只需向右遍历数字,直到个数大于等于y。

PS:因为没看清题目的操作3,导致误认为是最新的前y个,实际是最初产生的y个,这样导致的难度相差比较多。

D

题目链接
题目大意
有n只椅子排成一行(从左到右序号1到n),蚁人Scott站在第s只椅子;
蚁人可以从某只椅子跳到其他任何椅子,现在他想经过每一只椅子,最终停在第e只椅子上;(每只椅子只经过一次)
众所周知,蚁人能变大变小;在这里,蚁人只能在椅子上进行变化,且只有两种状态:巨人和小人;
蚁人往椅子左边跳的时候,只能是小人状态;
蚁人往椅子右边跳的时候,只能是巨人状态;

从椅子i跳到椅子j,花费的时间分为三个:

问Scott从椅子s到椅子e的最短时间是多少。

数学语言:
n个点,每个点有权值x[i],a[i], b[i], c[i], d[i]。
每个点都存在一条边到其他点,对于点i到点j边的代价为:
|x[i] - x[j]| + c[i] + b[j] seconds if j < i.
|x[i] - x[j]| + d[i] + a[j] seconds otherwise (j > i).
求从点s到点e,遍历所有点的最短路径。(每个点只走一次)

输入:
第一行 n, s and e (2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e)
第二行 x1, x2, ..., xn (1 ≤ x[1] < x[2] < ... < x[n] ≤ 1e9).
第三行 a1, a2, ..., an (1 ≤ a1, a2, ..., an ≤ 1e9)
第四行 b1, b2, ..., bn (1 ≤ b1, b2, ..., bn ≤ 1e9)
第五行 c1, c2, ..., cn (1 ≤ c1, c2, ..., cn ≤ 1e9)
第六行 d1, d2, ..., dn (1 ≤ d1, d2, ..., dn ≤ 19)

Example
input
7 4 3
8 11 12 16 17 18 20
17 16 20 2 20 5 13
17 8 8 16 12 15 13
12 4 16 4 15 7 6
8 14 2 11 17 12 8
output
139

样例解释:
路径:4 -> 2 -> 1 -> 6 -> 5 -> 7 -> 3
时间:17 + 24 + 23 + 20 + 33 + 22 = 139.

代码实现

    lld ans = cost(src, dest);
    
    NEXT[src] = dest;
    for (lld i = 1; i <= n; ++i) {
        if (i == src || i == dest) {
            continue;
        }
        lld MAX = inf, key = 0;
        for (lld j = src; j != dest; j = NEXT[j]) {
            if (cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]) < MAX) {
                MAX = cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]);
                key = j;
            }
        }
        ans = ans + MAX;
        NEXT[i] = NEXT[key];
        NEXT[key] = i;
    }
    
    
    cout << ans << endl;

题目解析
每个点都要走到,且每个点只能走一次,那么把点的遍历路径展开最终路径是一条s到t的直线。
归纳法:
n = 2的时候,直接s到t的路径得到最优解;
n = 3的时候,枚举能插入的位置,可以得到最优解;
...
n = k的时候,在n=k-1形成的s到t链上,枚举能插入的位置,得到最优解。

假设插入的位置是i,那么n=k-1的链会分解成几段:s到i,NEXT[i]到t,i到k,k到NEXT[i],其中 s到i 、 NEXT[i]到t 的距离不变。
那么当 cost(i, k) + cost(k, NEXT[i]) - cost(i, NEXT[i]) 最小时,i就是插入的最优解。

证明的关键点:当n=k插入的时候,点k不会对s到i、NEXT[i]到t 的路径造成影响。

证明实际存在缺陷,目前还未完善证明,这个做法实则是贪心。

上一篇下一篇

猜你喜欢

热点阅读