Nene’s Magical Matrix

题面翻译

有一个 $n\times n$ 的数组，初始时所有位置均为 $0$ ，现在要对其进行若干次操作，操作有两种：

• 选择一个正整数 $i~(1\le i \le n)$ 和一个 $1$ ~ $n$ 的排列 $p_1,p_2,\cdots,p_n$，将每个 $a_{i,j}~(1\le j \le n)$ 同时赋值为 $p_j$。
• 选择一个正整数 $i~(1 \le i \le n)$ 和一个 $1$ ~ $n$ 的排列 $p_1,p_2,\cdots,p_n$，将每个 $a_{j,i}~(1\le j \le n)$ 同时赋值为 $p_j$。

需要进行不多于 $2\times n$ 次操作，使得数组中元素的和最大。输出最终数组中元素的和、操作次数和操作顺序。

一共 $t~ (1\le t \le 500)$ 组数据，每组数据中 $1\le n\le 500$ ，$1\le \sum n^2 \le 5\times 10^5$。

题目描述

The magical girl Nene has an $ n\times n $ matrix $ a $ filled with zeroes. The $ j $ -th element of the $ i $ -th row of matrix $ a $ is denoted as $ a_{i, j} $ .

She can perform operations of the following two types with this matrix:

• Type $ 1 $ operation: choose an integer $ i $ between $ 1 $ and $ n $ and a permutation $ p_1, p_2, \ldots, p_n $ of integers from $ 1 $ to $ n $ . Assign $ a_{i, j}:=p_j $ for all $ 1 \le j \le n $ simultaneously.
• Type $ 2 $ operation: choose an integer $ i $ between $ 1 $ and $ n $ and a permutation $ p_1, p_2, \ldots, p_n $ of integers from $ 1 $ to $ n $ . Assign $ a_{j, i}:=p_j $ for all $ 1 \le j \le n $ simultaneously.

Nene wants to maximize the sum of all the numbers in the matrix $ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j} $ . She asks you to find the way to perform the operations so that this sum is maximized. As she doesn’t want to make too many operations, you should provide a solution with no more than $ 2n $ operations.

A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of test cases follows.

The only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 500 $ ) — the size of the matrix $ a $ .

It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

输出格式

For each test case, in the first line output two integers $ s $ and $ m $ ( $ 0\leq m\leq 2n $ ) — the maximum sum of the numbers in the matrix and the number of operations in your solution.

In the $ k $ -th of the next $ m $ lines output the description of the $ k $ -th operation:

• an integer $ c $ ( $ c \in \{1, 2\} $ ) — the type of the $ k $ -th operation;
• an integer $ i $ ( $ 1 \le i \le n $ ) — the row or the column the $ k $ -th operation is applied to;
• a permutation $ p_1, p_2, \ldots, p_n $ of integers from $ 1 $ to $ n $ — the permutation used in the $ k $ -th operation.

Note that you don’t need to minimize the number of operations used, you only should use no more than $ 2n $ operations. It can be shown that the maximum possible sum can always be obtained in no more than $ 2n $ operations.

样例 #1

样例输入 #1

2
1
2

样例输出 #1

1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

提示

In the first test case, the maximum sum $ s=1 $ can be obtained in $ 1 $ operation by setting $ a_{1, 1}:=1 $ .

In the second test case, the maximum sum $ s=7 $ can be obtained in $ 3 $ operations as follows:

It can be shown that it is impossible to make the sum of the numbers in the matrix larger than $ 7 $ .

最优

1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4

 const int N = 2e5 + 10;
int a[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + i;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += i * i + a[n] - a[i];
    }
    cout << ans << " " << 2 * n << '\n';
    for (int i = 1, j = n; i <= n, j >= 1; i++, j--)
    {
        cout << "1" << " " << i << " ";
        for (int k = 1; k <= n; k++) cout << k << " ";
        cout << '\n';
        cout << "2" << " " << j << " ";
        for (int k = n; k >= 1; k--) cout << k << " ";
        cout << '\n';
    }

}