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

正文

1.Alex and a Rhombus

题目链接 题目大意： 给出一个整数n，下面给出当n=1、2、3的图：

计算第n个图，需要多少个方格组成。

输入： 一个整数? (1≤?≤100)

输出： 需要的方格数量。

Examples input 1 output 1 input 2 output 5 input 3 output 13

题目解析： 等差数列，1、3、5、、、2n-1； 两个等差数列，减去一个多余的2n-1,于是有： 一个等差数列和sum: (1+(2n-1)) x n/2 最终得到 ans = 2 x sum - (2n-1) = 2n^2 - 2n + 1。

    int n;
    cin >> n;
    cout << 2 * n * n - 2 * n + 1 << endl;

2.Nick and Array

题目链接 题目大意： 有一个数组?=[?1,?2,…,??] ，可以对任意数进行下面的操作： ??:=−??−1； 每个数可以操作任意次；

要求 最后的乘积（?1⋅?2⋅…??）最大。

输入： 第一行， ? (1≤?≤10^5) 第二行，n个整数； ?1,?2,…,?? (−10^6 ≤ ?? ≤ 10^6)

输出： 一行，使得乘积最大的n个整数（?1,?2,…,??）

Examples input 4 2 2 2 2 output -3 -3 -3 -3 input 1 0 output 0

题目解析： 题目的要求是乘积最大，但是数字有很多，最终的乘积肯定会很大。 再来看看题目的操作，其实就是x= -x-1; 如果操作两次呢？x = -(-x-1) -1 = x + 1 - 1 = x; 操作两次是变回x，那么可以知道对于每个数字只有1个选择：要么不操作，要么操作一次。

回头来看看乘积最大的要求，先不考虑正负的问题，要使得乘积最大，自然是每个数字越大越好。 容易知道，乘积对于负数有一个负负得正的作用，那么要使得乘积最大要满足两个条件： 1、所有的数字里不会出现单数的负数，否则结果一定是负数； 2、每个数字要尽可能的大；

分析这个操作x=-x-1，容易知道对于正数，当x操作一次之后，绝对值是+1；对于负数，当x操作一次之后，绝对值是-1；

综上，我们可以先将所有的数字全部变为负数，这样可以使得绝对值最大。 但是因为可能会出现单数的负数，此时我们需要选择一个负数变为整数，通过推导，我们会选择负数中绝对值最大的那个变为负数。

推导： 先假设有两个正整数x和y，并且x<y。 (x-1)y=xy-y x(y-1)=xy-x 因为x<y,所以有(x-1)y < x(y-1)

    int n;
    cin >> n;
    int index = -1;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] >= 0) {
            a[i] = -a[i] - 1;
        }
        if (index == -1) {
            index = i;
        }
        else if (a[i] < a[index]) {
            index = i;
        }
    }
    if (n % 2) {
        a[index] = -a[index] - 1;
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }

3.Valeriy and Deque

题目链接 题目大意： 有一个数组a，长度为n； 现在有一个操作，从数组最前面（a[0],a[1]）拿出两个数字假设是x，y； 如果x<y，则把x放在数组的最后面，把y放在数组的最前面； 如果x>=y,则把x放在数组的最前面，把y放在数组的最前面；

问这个操作进行若干次之后，拿出来的数字x、y是什么；

输入： 第一行，两个整数? and ? (2≤?≤10^5, 0≤?≤3⋅10^5)，分别表示数组长度和询问次数； 接下来有n个整数，?1, ?2, ..., ??, where ?? (0≤??≤10^9) 接下来有q行，每行一个整数??,(1≤??≤10^18)

输出： 对于q个询问，每个输出一行，一行有两个整数x、y；

Examples input 5 3 1 2 3 4 5 1 2 10 output 1 2 2 3 5 2

样例解释： 原始数组是[1,2,3,4,5]，在每次操作之前，数字的样子：（每次操作都是拿出前两个） [1,2,3,4,5] [2,3,4,5,1] [3,4,5,1,2] [4,5,1,2,3] [5,1,2,3,4] [5,2,3,4,1] [5,3,4,1,2] [5,4,1,2,3] [5,1,2,3,4] [5,2,3,4,1]

题目解析： 题目的样例已经很明显阐述了一个规律： 若干次之后，数组中最大值会始终占据第一位。 根据题目的其他描述，每次拿出来的A、B两个数字，在数组最大值放置在第一位之后，剩余的1~n-1的位置会不断轮换。

为了实现简单，我们不去记录他最大值是什么。 直接按照题目要求操作n次，记录其中每次操作的值；此时数组的最大值就会在最左边，接下来的操作会使得1~n-1数组开始循环。

对于q次询问，每次先看询问值mj是否小于n， 是的话可以直接用原来存储的值； 否则就直接取余，再从1~n-1找到下一个值。

为了实现方便，这里n次的模拟可以使用双端队列deque来辅助实现。

    lld n, t;
    cin >> n >> t;
    deque<int> q;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        q.push_back(k);
    }
    
    for (int i = 1; i < n; ++i) {
        int a = q.front();
        q.pop_front();
        int b = q.front();
        q.pop_front();
        ans[i] = make_pair(a, b);
        if (a > b) {
            q.push_front(a);
            q.push_back(b);
        }
        else {
            q.push_front(b);
            q.push_back(a);
        }
    }
    
    for (int i = 0; i < n; ++i) {
        r[i] = q.front();
        q.pop_front();
    }
    

    while (t--) {
        lld k;
        cin >> k;
        if (k < n) {
            cout << ans[k].first << " " << ans[k].second << endl;
        }
        else {
            --k;
            k = k % (n-1);
            cout << r[0] << " " << r[k + 1] << endl;
        }
    }

4.Tolik and His Uncle

题目链接 题目大意： 有 n x m 的网格，小明站在第一个格子(1,1）； 小明可以跳到一个还未访问过格子，每次会产生一个向量(dx, dy)。 当小明访问完所有的格子时，希望所有的向量都是不重复的。

输入： 一行，?,? (1≤?⋅?≤10^6)

输出： 如果无解，输出 -1. 如果有解，按照小明的访问顺序输出每个格子的坐标，一共n x m行，每行两个数字??,?? (1≤??≤?,1≤??≤?)

题目解析： 这是一道典型的构造类题目，需要我们去构造一个走法。 按照题目的要求，每次访问格子的向量不重复，那么产生越大的向量越好，因为越大越不会重复。 基于思路，我们可以知道，(1, 1)往(n, m)跳是最优的； 其次，(n, m)往(1, 2)跳也是OK的； 再接着，（1，2）可以往(n, m-1)跳； 循环往返，就可以得到一个序列。

以4x4的格子为例，走完第一行和最后一行之后，可以得到以下的向量： (3, 3) (-2, -3) (1, 3) (0, -3) (-1, 3) (2, -3) 可以看出来，这些向量都没有重复。 那么同理，对于第二行和倒数第二行，向量也不会重复。

综上，可以知道这个走法是合理的。 题目也不存在无解的情况。

    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        vector<int> t(m);
        a.push_back(t);
    }
    
    topX = topY = 0;
    bottomX = n - 1, bottomY = m - 1;
    topDir = 1;
    bottomDir = -1;
    bool isBottom = 0;
    while (ans.size() < n * m) {
        if (isBottom) { // jump bottom
            ans.push_back(make_pair(bottomX, bottomY));
            
            bottomY += bottomDir;
            if (bottomY < 0) {
                bottomY = 0;
                bottomX--;
                bottomDir = -bottomDir;
            }
            else if (bottomY >= m) {
                bottomY = m - 1;
                bottomX--;
                bottomDir = -bottomDir;
            }
        }
        else {
            ans.push_back(make_pair(topX, topY));
            
            topY += topDir;
            if (topY < 0) {
                topY = 0;
                topX++;
                topDir = -topDir;
            }
            else if (topY >= m) {
                topY = m - 1;
                topX++;
                topDir = -topDir;
            }
        }
        isBottom = !isBottom;
    }
    
    for (int i = 0; i < n * m; ++i) {
        printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
    }

总结

题目1意思很清晰，就是找规律； 题目2看着很复杂，实际上通过分析可以得到很简单做法； 题目3数字的取值范围很大，但实际上后面都是重复循环，同时样例也很好展示了循环当前情况； 题目4属于脑洞题，一时间能想到就简单，想不到的时候就很头疼；