Title Link: The last dance - topic - Daimayuan Online Judge
Title Description:
The teacher prepared a dance for the graduating students. 2N students will participate in the dance. They will be divided into N pairs of dancers. Each student has a number. If the student with number I and the student with number J are paired, the satisfaction of this pair is Ai, J (i<j). We stipulate that the satisfaction of this dance is the XOR and sum of the satisfaction of each team, that is, when the students are divided into N groups, the satisfaction of the I pair of students is Ai, So the satisfaction of the dance is A1 ⊕ A2 ⊕ AN
Please find out the maximum satisfaction of this dance
Enter Description:
The first line gives a number N, 2N people attend the dance
Next, a matrix is given to express the satisfaction of i and j pairing
A1,2,A1,3,..A1,2N
A2,3,...A2,2N
.. .. ..
A2N−1,2N
Where 1 ≤ N ≤ 8,0 ≤ Ai,j ≤ 2^30
Output Description:
Output the maximum satisfaction of this dance
Example:
Input:
2
4 0 1
5 3
2
Output:
6
It can be seen that the range of n is very small. From the range of N, it is easy to think of using dfs to search. Personally, i think this problem is somewhat similar to the eight queens problem. It is also considered that only one number can be selected for each row and column. Consider searching each pair, one-to-one to match, and this problem is easy to time out if the search is popular, so pruning is required. The basic idea of pruning is to reduce repetition for this problem. Because each number of this problem must be selected, you can search by increasing i in the search. You can directly add to 1, because 1 will certainly be matched, and then find the location that matches 1 (small pruning). Because each number must be matched, in the matching search of each pair, the first unmatched number can be matched, and then the matching positions can be enumerated.
There is also a small note here, because the range of aij is <=2^30, and it will not explode int. you can use int directly. The measured longlong is nearly twice as slow as int
code:
#include <bits/stdc++.h>
using namespace std;
bool vis[20];
int a[20][20];
int ans, n;
void dfs(int step, int res) // step is the currently matched logarithm, and res is the current XOR and
{
if (step == n) //All matching updated answers
{
ans = max(ans, res);
return;
}
int i;
for (i = 2; i <= n + n - 1; i++)
{
if (!vis[i]) //Find the first unmatched number in 1~2n (pruning)
break;
}
for (int j = i + 1; j <= n + n; j++)
{
if (vis[j] == 0) //Not matched
{
vis[i] = 1, vis[j] = 1; //matching
dfs(step + 1, res ^ a[i][j]);
vis[i] = 0, vis[j] = 0; //Unmark
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n + n - 1; i++)
for (int j = i + 1; j <= n + n; j++)
cin >> a[i][j];
vis[1] = 1; // 1 will definitely be matched. Add matching directly (pruning)
for (int i = 2; i <= n + n; i++) //Enumerate locations that match 1
{
vis[i] = 1;
dfs(1, a[1][i]);
vis[i] = 0;
}
cout << ans;
}Eight queens problem
Title Link: Eight queens question - topic - Daimayuan Online Judge
Title Description:
In an n × Put n queens into the chessboard of N. The Queens should not attack each other and output all schemes.
A queen can attack all the squares in the same row, column and diagonal.
Input format:
On the first line, enter an integer n.
Output format:
Output several rows, and each row outputs n integers, representing the column of the queen of rows 1,2,..., N in turn.
Output from small to large in dictionary order.
n queens cannot be in the same row, column or diagonal, that is, there can only be one queen for each row, column and diagonal. Consider enumerating the columns occupied by each row queen.
For a point (x,y), the next position of its main diagonal is (x+1, y+1) and the previous position is (x-1, y-1). If the values of row labels minus column labels are equal, it can be used to mark whether it is on the same main diagonal. Because the array subscript cannot be negative, add n to the value of each row minus column subscript.
Similarly, for a point (x,y), the next position of its sub diagonal is (x+1, y-1) and the previous position is (x-1, y+1). If the values of row and column labels are equal, then whether it is on the same sub diagonal is marked.
code:
#include <bits/stdc++.h>
using namespace std;
int n, dis[13], s[13], dx[30], dy[30]; // s[i] is the queen placed at line I s[j]
// dis marks whether each column is occupied, s stores the position of the queen, dx marks the sub diagonal, dy marks the main diagonal
void dfs(int step) // step is the number of queens currently placed
{
if (step == n) //Put all in output answer
{
for (int i = 1; i <= n; i++)
printf("%d ", s[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++)
{
if (dis[i] == 0 && dx[step + 1 + i] == 0 && dy[step + 1 - i + n] == 0)
{
s[step + 1] = i; //Put the queen in row step+1 and column i
dis[i] = 1; //Mark that column i has been occupied
dx[step + 1 + i] = 1; //Mark sub diagonal
dy[step + 1 - i + n] = 1; //Mark main diagonal
dfs(step + 1);
dis[i] = 0; //Unmark
dx[step + 1 + i] = 0;
dy[step + 1 - i + n] = 0;
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) //The dictionary order is output from small to large, so i enumerates from small to large
{
s[1] = i; //Put the queen in row 1, column i
dis[i] = 1; //Mark that column i has been occupied
dx[1 + i] = 1; //Mark sub diagonal
dy[1 - i + n] = 1; //Mark the main diagonal, because i-j may be a negative number, so +n is used
//(abs cannot be taken! Because abs(1-2)=1 and abs(2-1)=1 and (1,2), (2,1) are not on the same main diagonal
dfs(1);
dis[i] = 0; //Unmark
dx[1 + i] = 0;
dy[1 - i + n] = 0;
}
}ending......
I am not talented. If you have any questions, please correct me! I appreciate it!