220123总结

• 上午写的代码基本都在上一篇里了
• 下午做了点题

下午做的四道题

1. P1706 全排列问题

   题目描述

   按照字典序输出自然数 $1$到 $n$所有不重复的排列，即 $n$的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

   输入格式

   一个整数$n$。

   输出格式

   由 $1 \sim n$ 组成的所有不重复的数字序列，每行一个序列。

   每个数字保留 5个场宽。

   题倒是很简单，

   但是需要注意“保留5个场宽”

   因为忘了保留场宽WA了好几次的痛，谁懂。。。

2. P1157 组合的输出

   这是上午的原题，见上一篇

   然后我又忘留场宽了。。。

3. N皇后问题没找到原题

   就不写八皇后了，写了N皇后直接把N赋值为8就行

首先，规则是：两个皇后不能在同一行、同一列、统一对角线上

而且我们是一行一行放皇后，所以我们可以保证不会存在两个皇后在同一行上（因为一行只放一个）

那么，我们就需要开三个数组，分别记录每一列、左上-右下对角线和右上-左下对角线是否可以放皇后

列数就是N

左上-右下对角线上的点坐标差相等（注意不是差的绝对值！！我因为这一点小问题卡了一天）

右上-左下的对角线上的点坐标和相等

易知$N\times N$的棋盘，有$N$列，$2N-1$条左上-右下对角线与$2N-1$条右上-左下对角线

为了省事就都开$2N$的数组吧（

剩下的思路就简单起来了

核心代码

int R[30];
int A[30];
int B[30];
int C[30];

void Search(int n){
	//从第1列到第N列遍历 
	for(int i = 1;i<=N;i++){
		//如果满足条件就继续 这里C的i-n可能为负数，所以加上了N确保数组下标为正 
		if((!A[i]) && (!B[i+n]) && (!C[i-n+N])){
			//放入皇后 
			A[i] = 1;
			B[i+n] = 1;
			C[i-n+N] = 1;
			//记录答案 
			R[n] = i;
			//满足条件就输出 
			if(n == N-1){
				print();
			}else{
				Search(n+1);
			}
			//回溯 
			A[i] = 0;
			B[i+n] = 0;
			C[i-n+N] = 0;
		}
	}
}

我双忘留场宽了。。。

1. 有重复元素的排列问题

   设$R={r_1,r_2,\cdots,r_n}$是要进行排列的n个元素，其中元素$r_1,r_2,\cdots,r_n$可能相同。试设计一个算法，列出R的所有不同排列。

   【输入格式】

   文件的第一行是元素个数n，$1\leqslant n\leqslant 500$。接下来的1行是待排列的n个元素。

   【输出格式】

   n个元素的所有不同排列。最后一行是排列总数。

   【输入样例】

   4

   aacc

   【输出样例】

   aacc

   acac

   acca

   caac

   caca

   ccaa

   6

   摆烂偷懒写法

   next_permutation永远的神

   #include<bits/stdc++.h>
   using namespace std;
   
   int main(){
   	string s;
   	int n;
   	scanf("%d",&n);
   	cin>>s;
   	int num = 1;
   	cout<<s<<endl;
   	while(next_permutation(s.begin(),s.end())){
   		cout<<s<<endl;
   		num++;		
   	}
   	printf("%d",num);
   }

其他

memset函数按字节对内存块进行初始化，所以不能用它将int数组初始化为0和-1之外的其他值（除非该值高字节和低字节相同）