【TFLSnoi李志帅】第十⑥篇文章---难题求解

遇见几道难题，求解！

①.I - 数字组合（课后作业）

现在小瓜有1到n这n个整数，他想知道用这n个整数组成一个长度为n的数字序列的所有方法（每个整数可以重复使用）。你能帮助他吗？

Input

一行一个整数n（1<=n<=6）。

Output

若干行，每行表示用1到n组成一个长度为n的数字序列的一种方法。所有方法按字典序输出。

Sample Input

Sample Output

1 1
1 2
2 1
2 2


————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


我的垃圾骗分代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     long long n;
 6     cin>>n;
 7     if(n==1)cout<<1;
 8     if(n==2){
 9         cout<<"1 1"<<endl;
10         cout<<"1 2"<<endl;
11         cout<<"2 1"<<endl;
12         cout<<"2 2"<<endl;
13     }
14     if(n==3){
15         for(int i=1;i<=3;i++){
16             for(int j=1;j<=3;j++){
17                 for(int k=1;k<=3;k++)
18                 cout<<i<<" "<<j<<" "<<k<<endl;
19             }
20         }
21     }
22     if(n==4){
23         for(int i=1;i<=4;i++){
24             for(int j=1;j<=4;j++){
25                 for(int k=1;k<=4;k++){
26                     for(int a4=1;a4<=4;a4++)cout<<i<<" "<<j<<" "<<k<<" "<<a4<<endl;
27                 }
28                 
29             }
30         }
31     }
32     if(n==5){
33         for(int i=1;i<=5;i++){
34             for(int j=1;j<=5;j++){
35                 for(int k=1;k<=5;k++){
36                     for(int a4=1;a4<=5;a4++){
37                         for(int a5=1;a5<=5;a5++)cout<<i<<" "<<j<<" "<<k<<" "<<a4<<" "<<a5<<endl;
38                     }
39                 }
40                 
41             }
42         }
43     }
44     if(n==6){
45             for(int i=1;i<=6;i++){
46             for(int j=1;j<=6;j++){
47                 for(int k=1;k<=6;k++){
48                     for(int a4=1;a4<=6;a4++){
49                         for(int a5=1;a5<=6;a5++){
50                             for(int a6=1;a6<=6;a6++)cout<<i<<" "<<j<<" "<<k<<" "<<a4<<" "<<a5<<" "<<a6<<endl;
51                         }
52                     }
53                 }
54                 
55             }
56         }
57     }
58     return 0;
59 }

因为数据规模较小，所以侥幸过了

再来看看别人的代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <climits>
 6 #include <cstring>
 7 #include <string>
 8 #include <algorithm>
 9 #include <vector>
10 #include <deque>
11 #include <list>
12 #include <utility>
13 #include <set>
14 #include <map>
15 #include <stack>
16 #include <queue>
17 #include <bitset>
18 #include <iterator>
19 using namespace std;
20 
21 typedef long long ll;
22 const int inf = 0x3f3f3f3f;
23 const ll  INF = 0x3f3f3f3f3f3f3f3f;
24 const double PI = acos(-1.0);
25 const double E = exp(1.0);
26 const int MOD = 1e9+7;
27 const int MAX = 1e5+5;
28 int n;
29 int a[6+5];
30 
31 void dfs(int i)
32 {
33     if(i == n)
34     {
35         for(int j = 0; j < n; j++)
36             cout << a[j] << " ";
37         cout << endl;
38         return;
39     }
40     for(int k = 1; k <= n; k++)
41     {
42         a[i] = k;
43         dfs(i+1);
44     }
45 }
46 
47 int main()
48 {
49     ios::sync_with_stdio(false);
50     cin.tie(0);
51     cout.tie(0);
52 
53     while(cin >> n)
54     {
55         dfs(0);
56     }
57 
58     return 0;
59 }

我发现我看不懂啊！！！

我发现我看不懂啊！！！（重要的事情说三遍

所以。。。求解啊！感谢

——————————————————————————————————————————————————————————————————————————

②.C - 最长回文子串（课后作业）

输入一个字符串Str，输出Str里最长回文子串的长度。

回文串：指aba、abba、cccbccc、aaaa这种左右对称的字符串。

串的子串：一个串的子串指此（字符）串中连续的一部分字符构成的子（字符）串
例如 abc 这个串的子串：空串、a、b、c、ab、bc、abc

Input

输入Str（Str的长度 <= 1000)

Output

输出最长回文子串的长度L。

Sample Input

daabaac

Sample Output

5


——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————-
我真的是写不出来
再看看别人的：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 char str[1000002 + 1200];
 6 int fast(char *p) {
 7     int ans = 1;
 8     for (int i = 1; p[i]; ++i) {
 9         int s = i, e = i, t;
10         while(p[e+1] == p[i]) {
11             ++e;
12         }
13         i = e;
14         while(p[s-1] == p[e+1]) {
15             --s;
16             ++e;
17         }
18         if((t = e-s+1) > ans) {
19             ans = t;
20         }
21     }
22     return ans;
23 }
24 int main() {
25     str[0] = '$';
26     while (cin>>(str+1)) {
27         cout<<fast(str)<<endl;
28     }
29     return 0;
30 }

？？？

有一点看不懂，这是用了指针吗？

还有这一篇

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int main() {
 5     char s[1005], t[2010];
 6     memset(t, 0, sizeof(t));
 7     cin>>s;
 8     int length = strlen(s);
 9     int k = 0;
10     t[0] = '#';
11     for(int i = 1; i <= 2*length - 1; i+=2) {
12         t[i] = s[k++];
13         t[i+1] = '#';
14     }
15     int l, r, temp, max = 0;
16     for(int i = 0; i <= 2*length; i++) {
17         l = r = i;
18         if(l==0 || r==2*length) {
19             temp = 1;
20         } else {
21             while(t[l]==t[r]) {
22                 l--;
23                 r++;
24             }
25             temp = r-l;
26         }
27         if(temp > max) {
28             max = temp;
29         }
30     }
31     cout<<(max-1)/2<<endl;
32     return 0;
33 }

看倒是能看懂了，但是我不明白它的算法思想啊QAQ

————————————————————————————————————————————————————————————————————————

③.H - 全排列（课后作业）

输入一个整数n（n <= 9），输出1、2、3、······、n这n个数的全排列（按照字典序输出）。

Input

一个整数n

Output

多行，每行表示一种排列，行内使用空格分隔相邻两数。

Sample Input

Sample Output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1




——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————-
本来我试图列表骗分，但是发现太长了，手要断了还没列出了。。。
所以，还是看看别人的代码叭：

 1 #include<iostream>
 2 using namespace std;
 3 int a[10];
 4 bool vis[10]={0};
 5 void dfs(int x, const int& m)//x计数以搜索的数的个数 
 6 {
 7     if(x>m)//搜索数目足够是输出所有的数 
 8     {
 9         for(int i=1;i<=m;i++)
10             cout<<a[i]<<' ';
11         cout<<endl;
12         return;
13     }
14     for(int i=1;i<=m;i++)
15         if(!vis[i])//判断数i是否已经被载入数组 
16         {
17             a[x]=i;
18             vis[i]=1;
19             dfs(x+1,m);
20             vis[i]=0;
21         }
22 }
23 
24 int main()
25 {
26     int n;
27     cin>>n; 
28     dfs(1,n); 
29     return 0;
30  }

哦，还有他的分析：

分析过程

初步涉及算法，描述错误，还请担待。
首先，这是使用的是dfs算法，向着一种情况不断的深入直至找到答案再到下一种情况不断延伸。这里的思路是用dfs分别找到每一位应该放的数。

这仅作本人笔记使用，有什么不足的地方还请指出，谢谢！

？？？

感觉这几道题好针对萌新啊

没办法，继续求解

————————————————————————————————————————————

最后一道：

④.J - 选数字（进阶习题）

从1-n中选出m个数，要求同样的数字不能重复选择，按照字典序正序输出所有方案。

例如：从1到4中选出2个数，共有6种方法，按照字典序输出，依次为：

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

Input

输入共2个数m, n，中间用空格分隔。（1 <= m <= n <= 20）

Output

按照字典序正序输出所有方案。

Sample Input

4 2

Sample Output

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


————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
写不出来，搜到一个，结果发现是Java版的。。。

又发现个c++版的，结果咋又用上指针了？QAQ

 1 void SelectK_01(int n,int k)
 2 {
 3     //true is selected
 4     bool *nselect = (bool *)malloc(n*sizeof(bool));
 5     
 6     int i = 0;
 7     
 8     //初始化第一个组合，即选择前k个数 
 9     while(i<n)
10     {
11         if(i<k)
12          nselect[i] = true;
13         else
14          nselect[i] = false;
15         i++;
16     }
17     
18     i = 0;
19     while(i<n){
20         if(nselect[i]) printf(" %d ",i+1);
21         i++;
22     }
23     printf("
");
24     
25     i=0;
26     while(i<n-1)
27     {
28         //找到第一个10组合，并交换10的位置 
29         if(nselect[i] && !nselect[i+1])
30         {
31             int temp = nselect[i];
32             int x=0,y=0;
33             nselect[i] = nselect[i+1];
34             nselect[i+1] = temp;
35             //将该组合左边所有的1移至数组最左边 
36             while(y<i)
37             {
38                 if(nselect[y])
39                 {
40                     temp = nselect[y];
41                     nselect[y] = nselect[x];
42                     nselect[x] = temp;
43                     x++;
44                 }
45                 y++;
46             }
47             
48             i = 0;
49             while(i<n){
50                 if(nselect[i]) printf(" %d ",i+1);
51                 i++;
52             }
53             printf("
");
54             
55             i = (x==0?0:x-1);
56         }
57         else i++; 
58     }
59     free(nselect);
60 }
61

还有那个free。。。？

好不容易找见个c++递归版的，结果。。。

 1 //d存储选择的数，NUM指示选择多少个数，即初始k的大小
 2 void Recursive_SelectK(int n,int k,int d[],const int NUM)
 3 {
 4     int i = n;
 5     if(k > n) return;
 6     while(i>=k)
 7     {
 8         d[NUM-k] = i;
 9         if(k>1) Recursive_SelectK(i-1,k-1,d,NUM);
10         else
11         {
12             int j = 0;
13             while(j<NUM)
14             {
15                 printf("%d ",d[j]);
16                 j++;
17             }
18             printf("
");
19         }
20         i--;
21     }
22 }

有点没法理解QAQ

强制性微笑………^V^

求解啊！！！