Edu Codeforces Round 141

第一题

介绍一函数： std::rotate

用法：std::rotate( first_element, n_first( will be the first element after ratating ), last_element )

作用：从原容器迭代器为n_first的位置开始依次向后输出每个元素，直到输出到最后一个元素，此时再从容器迭代器为first_element的位置开始向后输出，直到迭代器为n_first为止

举例：

vector<int> v = {1, 2, 3, 4, 5};
rotate(v.begin(), v.begin() + 2, v.end());
for (auto x : v) cout << x << ' ';
则输出结果为：3 4 5 1 2

题意：

给定一个长度为 $nn$ 的数组，将该数组重新排列使得数组内的每一个数都不等于其前面的所有数字之和

分析：

我们从大到小排列此数组的元素，若 $a[1]==a[n]a[1]\; ==\; a[n]$ ，则此数组无法重新排列使得数组内的每一个数都不等于其前面的所有数字之和。若 $a[1]==a[2]a[1]\; ==\; a[2]$ ，则只需把 $a[n]a[n]$ 放在数组的首位即可。

第二题

题意：

构造一个长宽为 $nn$ 的矩阵，要求矩阵内所有的数字是 $[1,n^2][1,\; n^\{2\}]$ 的排列，且要求矩阵内每两个相邻数之间的绝对值之差的种类数量最多，输出该矩阵

分析：

• 可以按一小一大的方式蛇形排列
• 可以按一小一大的方式回形排列

代码：

// 蛇形排列
int l = 1, r = n * n, cnt = 1;
for (int i = 1;i <= n;i ++)
{
    if (i & 1)
        for (int j = 1;j <= n;j ++)
        {
            if (cnt & 1) a[i][j] = l ++;
            else a[i][j] = r --;
            cnt ++;
        }
    else
        for (int j = n;j >= 1;j --)
        {
            if (cnt & 1) a[i][j] = l ++;
            else a[i][j] = r --;
            cnt ++;
        }
}

// 回形排列
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
for (int i = 1, j = 1, d = 0, l = 1, r = n * n, cnt = 0;l <= r;cnt ++)
{
    if (cnt & 1) a[i][j] = r --;
    else a[i][j] = l ++;
            
    int x = i + dx[d], y = j + dy[d];
    if (x > n || x < 1 || y > n || y < 1 || a[x][y])
    {
        d = (d + 1) % 4;
        x = i + dx[d];
        y = j + dy[d];
    }
    i = x;
    j = y;
}

第三题

参考：https://zhuanlan.zhihu.com/p/597599265

第四题

参考：https://zhuanlan.zhihu.com/p/597599265