华师一附中OI组

标题: 间隔排列 [打印本页]

---

作者: admin    时间: 2018-9-11 20:22
标题: 间隔排列
题目：有标号为1,2,3,4的小木块各两块，能不能摆成一列，让两个标号为i的木块中间间隔i个位子，比如，下面是两种可行的摆法
2 3 4 2 1 3 1 4
4 1 3 1 2 4 3 2
此题用dfs来做，第一种做法，枚举1234每个数字可以用两次的有重排列，然后判断排列是否满足条件，在pmn的pr里面加上判断。
怎么判断呢？从左往右找1，位置叫l1，从右往左找1，位置叫r1，那么r1-l1==2(为什么不是1) 4个全判断完。

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=10;  ///假设10个
   
4. int a[mn];
   
5. int b[mn];
   
6. int m,n,i;
   
7. void pr()
   
8. {
   
9.         ///判断是否符合条件
   
10.         int i,l1,l2,l3,l4,r1,r2,r3,r4;
    
11.         for (i=1; a[i]!=1; i++);l1=i;  ///从左往右找1
    
12.         for (i=8; a[i]!=1; i--);r1=i; ///从右往左找1
    
13. 
    
14.         for (i=1; a[i]!=2; i++);        l2=i;
    
15.         for (i=8; a[i]!=2; i--);        r2=i;
    
16. 
    
17.         for (i=1; a[i]!=3; i++);        l3=i;
    
18.         for (i=8; a[i]!=3; i--);        r3=i;
    
19. 
    
20.         for (i=1; a[i]!=4; i++);        l4=i;
    
21.         for (i=8; a[i]!=4; i--);        r4=i;
    
22. 
    
23.         bool b=(r1-l1==2);
    
24.         b=b&&  (r2-l2==3);
    
25.         b=b&&  (r3-l3==4);
    
26.         b=b&&  (r4-l4==5);
    
27. 
    
28.         if (b)
    
29.         {
    
30.                 for (int j=1; j<=2*n; j++) cout<<a[j];
    
31.                 cout<<endl;
    
32.         }
    
33. }
    
34. void dfs(int i)   ///  寻找第i的位置上的数
    
35. {
    
36.         if (i>2*n) pr();
    
37.         for (int k=1; k<=n; k++)
    
38.                 if (b[k]>0)
    
39.                 {
    
40.                         a[i]=k; /// 选择
    
41.                         b[k]--; ///标记
    
42.                         dfs(i+1); ///选下一个
    
43.                         b[k]++; ///复位
    
44.                 }
    
45. }
    
46. int main()
    
47. {
    
48.         n=4;   ///4个木块
    
49.         for (int i=1; i<=n; i++) b[i]=2; ///每个2块
    
50.         dfs(1); ///从第一个开始
    
51.         return 0;
    
52. }

复制代码

这个做法答案是对的但是显然是很浪费的，比如第一个数选1，第二个数还是选了1，此后完全没有必要再去选底3,4,5,6,7,8等位置上的数字，所以很大浪费。我们可以在第一位放1的时候，把第3位也放在1，然后再去选第2位上的数字，假设是2，然后不用选第3位上的数字，（前面决定了已经放了1），直接去选第4位上的数字****

---

作者: admin    时间: 2018-9-15 10:49

1. 
   
2. using namespace std;
   
3. const int mm=18;
   
4. bool b[mm];
   
5. int a[mm*2];
   
6. int n=4;
   
7. void dfs(int i)
   
8. {
   
9.     int j,k;
   
10.     if (i>n*2)  ///摆放完毕，输出
    
11.     {
    
12.         for(j=1; j<=n*2; j++) cout<<a[j]<<' ';
    
13.         cout<<endl;
    
14.     }
    
15.     else if (a[i]>0) dfs(i+1);  ///！！！这个格子已经被预先摆放了
    
16.     for (k=1; k<=n; k++)  
    
17.     {
    
18.         int x=i+k+1; ///计算那一个格子的位置
    
19.         bool b1=(x<=2*n); ///不可以超出范围
    
20.         bool b2=(a[x]==0);///不可以被占用
    
21. 
    
22.         bool bb=b[k] && b1 && b2;
    
23.         if (bb)
    
24.         {
    
25.             a[i]=a[x]=k;
    
26.             b[k]=0;
    
27.             dfs(i+1);
    
28.             b[k]=1;
    
29.             a[i]=a[x]=0;
    
30.         }
    
31.     }
    
32. 
    
33. }
    
34. int main()
    
35. {
    
36.     for (int i=1; i<=n; i++) b[i]=1;
    
37.     dfs(1);
    
38. 
    
39.     return 0;
    
40. }
    

复制代码

---

作者: admin    时间: 2020-3-7 20:52
相比那个1-8排成一排，相邻两个差的绝对值<4的题目而言，这个题的约束条件更多。
假设k放在了i位置，那么应该有如下三个条件要被满足：
1、b[k]!=0  这个显然
2、a[i]!=0  也就说这个位置以前没有被强制放数字
3、i+k+1<=8 因为后面要留下空间给第二个k放下去（两个木块）
4、a[i+k+1]!=0 因为第二个k要放在此处
其中第二个条件可以外面去跳过

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2