刘伟杰李香来程序大楼

admin

刘伟杰 发表于 2018-10-17 19:17
其实应该用搜索的，我错了

这个很有用，也需要掌握！

刘伟杰

luogu P1036 选数

一个质数判断加一个裸dfs即可

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. int n;
   
5. int s[10000];
   
6. int k;
   
7. int ans;
   
8. 
   
9. bool judge(int x)
   
10. {
    
11.     if(x == 1 || x == 0) return false;
    
12.     if(x == 2) return true;
    
13. 
    
14.     for(int i = 2;i <= x/2;i++)
    
15.     {
    
16.         if(x % i == 0) return false;
    
17.     }
    
18.     return true;
    
19. }
    
20. 
    
21. void dfs(int step,int cnt,int sum)
    
22. {
    
23.     if(step == n+1 || cnt == k)
    
24.     {
    
25.         if(cnt == k && judge(sum)) ans++;
    
26.         return;
    
27.     }
    
28.     dfs(step+1,cnt+1,sum+s[step]);
    
29.     dfs(step+1,cnt,sum);
    
30.     return;
    
31. }
    
32. 
    
33. 
    
34. int main()
    
35. {
    
36.     scanf("%d%d",&n,&k);
    
37.     for(int i = 1;i <= n;i++) scanf("%d",&s[i]);
    
38.     dfs(1,0,0);
    
39.     printf("%d",ans);
    
40.     return 0;
    
41. }
    

复制代码

刘伟杰

luogu P1123

取数游戏（差点做成网络流24。。）

因为周围8个不能取，所以从第一排第一列开始搜，剪枝只用判断左边和上边就ok，也是裸搜加一点点技巧

不知为何输出卡了半天。。

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n,m,t;
   
6. int maps[1000][1000];
   
7. int book[1000][1000];
   
8. int s[1000];
   
9. int ans = 0;
   
10. 
    
11. void dfs(int sum,int x,int y)
    
12. {
    
13.     if(x > n)
    
14.     {
    
15.        ans = max(ans,sum);
    
16.        return;
    
17.     }
    
18.     int tx = x;
    
19.     int ty = y+1;
    
20.     if(ty > m)
    
21.     {
    
22.         tx++;
    
23.         ty = 1;
    
24.     }
    
25.     if(!book[x-1][y+1] && !book[x-1][y-1] && !book[x][y-1] && !book[x-1][y])
    
26.     {
    
27.         book[x][y] = 1;
    
28.         dfs(sum+maps[x][y],tx,ty);
    
29.         book[x][y] = 0;
    
30.     }
    
31.     dfs(sum,tx,ty);
    
32. 
    
33. }
    
34. 
    
35. 
    
36. int main()
    
37. {
    
38.     scanf("%d",&t);
    
39.     while(t--)
    
40.     {
    
41.         ans = 0;
    
42.         scanf("%d%d",&n,&m);
    
43.         for(int i = 1;i <= n;i++)
    
44.         {
    
45.             for(int j = 1;j <= m;j++)
    
46.             {
    
47.                 scanf("%d",&maps[i][j]);
    
48.             }
    
49.         }
    
50.         dfs(0,1,0);
    
51.         printf("%d\n",ans);
    
52.     }
    
53.     return 0;
    
54. }
    

复制代码

刘伟杰

luogu P1443 马的遍历

普及广搜

其实这题广搜确实比深搜简单，于是就广搜做了。。

把马八个方向先预处理一下，然后就是基本的广搜了。。弄一个变量更新最小值，跟走迷宫其实区别不大

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. struct note{
   
6. int x;
   
7. int y;
   
8. 
   
9. };
   
10. 
    
11. int maps[401][401];
    
12. int k;
    
13. int n,m,startx,starty;
    
14. int s;
    
15. int tx,ty;
    
16. int i,j;
    
17. int next[8][2] = {{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
    
18. int main()
    
19. {
    
20.     struct note que[40001];
    
21.     memset(maps,-1,sizeof(maps));
    
22.     int head = 1;
    
23.     int tail = 1;
    
24.     scanf("%d%d%d%d",&n,&m,&startx,&starty);
    
25.     tail++;
    
26.     que[tail].x = startx;
    
27.     que[tail].y = starty;
    
28.     maps[que[tail].x][que[tail].y] = 0;
    
29.     while(head < tail)
    
30.     {
    
31.         head++;
    
32.         s = maps[que[head].x][que[head].y] + 1;
    
33.         for(k = 0;k < 8;k++)
    
34.         {
    
35.            tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1];
    
36.            if(maps[tx][ty] == -1 && tx >= 1 && tx <= n && ty >= 1 && ty <= m)
    
37.            {
    
38.                tail++;
    
39.                que[tail].x = tx;
    
40.                que[tail].y = ty;
    
41.                maps[tx][ty] = s;
    
42.            }
    
43.         }
    
44. 
    
45.     }
    
46.     for(i = 1;i <= n;i++)
    
47.     {
    
48.         for(j = 1;j <= m;j++)
    
49.         {
    
50.             printf("%-5d",maps[i][j]);
    
51.         }
    
52.         printf("\n");
    
53.     }
    
54. 
    
55. return 0;
    
56. }
    

复制代码

刘伟杰

luogu P2404 自然数的拆分问题

这题以前做过一个类似的。。。但到现在都有点没搞懂。。。

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int s[1000] = {1};
   
6. int n;
   
7. int k;
   
8. void print(int x)
   
9. {
   
10.     for(int i = 1;i < x;i++)
    
11.     {
    
12.         printf("%d+",s[i]);
    
13.     }
    
14.     printf("%d",s[x]);
    
15.     printf("\n");
    
16. }
    
17. void dfs(int x)
    
18. {
    
19.     for(int i = s[x-1];i <= k;i++)
    
20.     {
    
21.         if(i == n) continue;
    
22.         s[x] = i;
    
23.         k -= i;
    
24.         if(k == 0) print(x);
    
25.         else dfs(x+1);
    
26. 
    
27.         k+=i;
    
28.     }
    
29. }
    
30. 
    
31. int main()
    
32. {
    
33.     scanf("%d",&n);
    
34.     k = n;
    
35.     dfs(1);
    
36.     return 0;
    
37. }
    

复制代码

刘伟杰

luogu P1238 走迷宫

3次才AC 第一次 50 第二次 80 第三次 100

分析原因：

1、上下左右看错？？？？

2、初始位置要标记。。。

3、这其实就是一道水题。。。。

迷宫类型问题的基本套路，记得剪枝，不然要tle的。。

AC代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int maps[1000][1000];
   
6. int book[1000][1000];
   
7. int a[1000][3];
   
8. int next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
   
9. int n,m;
   
10. int flag;
    
11. int p,q,sx,sy;
    
12. void print(int x)
    
13. {
    
14.     for(int i = 1;i < x;i++)
    
15.     {
    
16.         printf("(%d,%d)->",a[i][1],a[i][2]);
    
17.     }
    
18.     printf("(%d,%d)",a[x][1],a[x][2]);
    
19.     printf("\n");
    
20. }
    
21. void dfs(int x,int y,int step)
    
22. {
    
23.     int tx,ty;
    
24.     if(x == p && y == q)
    
25.     {
    
26.         flag = 1;
    
27.         print(step);
    
28.         return;
    
29.     }
    
30.     for(int k = 0;k <= 3;k++)
    
31.     {
    
32.         tx = x + next[k][0];
    
33.         ty = y + next[k][1];
    
34. 
    
35.         if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
    
36. 
    
37.         if(book[tx][ty] == 0 && maps[tx][ty] == 1)
    
38.         {
    
39.             book[tx][ty] = 1;
    
40.             a[step+1][1] = tx;
    
41.             a[step+1][2] = ty;
    
42.             dfs(tx,ty,step+1);
    
43.             book[tx][ty] = 0;
    
44.         }
    
45.     }
    
46. }
    
47. int main()
    
48. {
    
49.     int i,j;
    
50.     scanf("%d%d",&n,&m);
    
51.     for(i = 1;i <= n;i++)
    
52.     {
    
53.         for(j = 1;j <= m;j++)
    
54.         {
    
55.             scanf("%d",&maps[i][j]);
    
56.         }
    
57.     }
    
58.     scanf("%d%d",&sx,&sy);
    
59.     scanf("%d%d",&p,&q);
    
60.     a[1][1] = sx;
    
61.     a[1][2] = sy;
    
62.     book[sx][sy] = 1;
    
63.     dfs(sx,sy,1);
    
64.     if(flag == 0)
    
65.     {
    
66.         printf("-1");
    
67.     }
    
68.     return 0;
    
69. }
    

复制代码

刘伟杰

luogu P1233 木棍加工

先排序，再寻找最大不上升序列

贪心思想。。。没用dp。

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. struct Mugun{
   
6.     int l;
   
7.     int w;
   
8.     int book;
   
9. }m[100000];
   
10. 
    
11. int n;
    
12. int ans = 0;
    
13. 
    
14. int cmp(struct Mugun a,struct Mugun b)
    
15. {
    
16.     return a.l > b.l;
    
17.     if(a.l == b.l)
    
18.         return a.w > b.w;
    
19. }
    
20. int temp;
    
21. int main()
    
22. {
    
23.     scanf("%d",&n);
    
24.     for(int i = 1;i <= n;i++)
    
25.     {
    
26.         scanf("%d%d",&m[i].l,&m[i].w);
    
27.         m[i].book = 0;
    
28.     }
    
29.     sort(m+1,m+1+n,cmp);
    
30.     for(int i = 1;i <= n;i++)
    
31.     {
    
32.         if(m[i].book == 0)
    
33.         {
    
34.             temp = m[i].w;
    
35.             for(int j = i+1;j <= n;j++)
    
36.             {
    
37.                 if(m[j].w<=temp&&m[j].book == 0)
    
38.                 {
    
39.                     m[j].book = 1;
    
40.                     temp = m[j].w;
    
41.                 }
    
42.             }
    
43.         }
    
44.     }
    
45.     for(int i = 1;i <= n;i++)
    
46.     {
    
47.         if(m[i].book == 0)
    
48.         {
    
49.             ans++;
    
50.         }
    
51.     }
    
52.     printf("%d",ans);
    
53. 
    
54. 
    
55. 
    
56. 
    
57.     return 0;
    
58. }
    

复制代码

刘伟杰

luogu P1216 数字三角形

DP。。。吧

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n,a[1002],i,j,ans,p;
   
6. 
   
7. int main()
   
8. {
   
9.     scanf("%d",&n);
   
10.         for(i=n;i;i--)
    
11.                 for(j=i;j<=n;j++)
    
12.                         scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;
    
13.         for(i=1;i<=n;i++)
    
14.         ans=max(ans,a[i]);
    
15.         printf("%d",ans);
    
16.         return 0;
    
17. }
    

复制代码