本期题目包括：
1074：https://pintia.cn/problem-sets/994805342720868352/problems/994805394512134144
1052：https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464
1032：https://pintia.cn/problem-sets/994805342720868352/problems/994805460652113920
1097：https://pintia.cn/problem-sets/994805342720868352/problems/994805375457411072
1103：https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224
1091：https://pintia.cn/problem-sets/994805342720868352/problems/994805375457411072
1074：
题目大意：给定一长度为n的链表，要求每k次反转一次，例如链表为1-2-3-4-5-6,当k=3时，反转结果为3-2-1--6-5-4，当k等于4的时，反转结果为4-3-2-1-5-6；
解题思路：讲链表地址存入顺序表中转置最后输出，这样相比与链表反转算法会少操作狠多
假定长度为10，我们有一个1，2，3，4，5，6，7，8，9，10的链表，且假设k=4，所以说有1-4，5-8被反转，那设他们的下标为i，在满足i+4<=n的条件下是可以被转置的，
例如：i，i+1,i+2,i+3,i+4.......i+k-1；
我们要将反转两数的下标和为2*i+k-1；
两两操作要执行k/2次；
最好转置完后输出即可
参考代码：
1 #include<bits/stdc++.h>//1074
2 using namespace std;
3 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
4 #define int long long
5 int n,k,st;
6 int cnt;
7 const int N=1e5+10;
8 struct node
9 {
10 int key;//键值
11 int ne;//下一个节点的首地址
12 }L[N];
13 vector<int>q;//存放结果
14 signed main()
15 {
16 IOS;
17 cin>>st>>n>>k;
18 for(int i=0;i<n;i++)
19 {
20 int a,b,c;
21 cin>>a>>b>>c;
22 L[a].key=b;
23 //L[c].ne=c;
24 L[a].ne=c;
25 }
26 for(int i=st;~i;i=L[i].ne)//存入地址
27 {
28 q.push_back(i);
29 }
30 for(int i=0;i+k<=q.size();i+=k)//满足每k个转置
31 {
32 //i+0,i+1,i+2.....i+k-1;
33 for(int j=0;j<k/2;j++)//操作k/2轮
34 {
35 int tmp=q[i+j];
36 q[i+j]=q[i+k-j-1];
37 q[i+k-j-1]=tmp;
38 }
39 }
40 for(int i=0;i<q.size();i++)
41 {
42 if(i<q.size()-1)
43 {
44 printf("%05lld %lld %05lld\n",q[i],L[q[i]].key,q[i+1]);
45 }
46 else
47 printf("%05lld %lld -1",q[i],L[q[i]].key);
48 }
49 // for(int i=0;i<q.size();i++)
50 //printf("%05lld ",q[i]);
51 return 0;
52 }
1052：
题目大意：给定一个链表要求给其键值排序后输出
题目思路：
题目给出的数据有可能是不存在于链表上的节点即无效节点，我们因此可以设一个flag值表示这个节点是否有效；
首先我们在开始的时候肯定是要把所有的节点初始化为无效，在输入完地址，键值和下一个邻接点的地址之后，我们枚举按照节点连接顺序每个节点地址，并且置该地址的节点为有效值并统计节点有效数目，如果节点的有效数目是0，就输出0和-1就好了
如果不是的话
我们首先要按照题目要求设计排序，这里排序可以这样设计：
我们可以把所有的有效节点放在较为靠前的部分，无效的放在后面，所以说当出现无效节点的时候，可以return a.flag>b.flag，即按照节点的有效性进行排序，如果曼纳祖有效性了，就要按照节点的大小顺序进行排序了，这里可以return a.key<b.key；
然后有多少个有效节点就按照题目要求进行输出即可
1 #include<bits/stdc++.h>//1052
2 using namespace std;
3 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
4 #define int long long
5 int cnt;
6 const int N=1e5+10;
7 struct node
8 {
9 int address;
10 int key;
11 int ne;
12 bool flag;
13 }L[N];
14 bool cmp(node a,node b)
15 {
16 if(!a.flag||!b.flag)//将有效节点放在前面
17 {
18 return a.flag>b.flag;
19 }
20 else
21 return a.key<b.key;//按大小顺序进行排序
22 }
23 signed main()
24 {
25 IOS;
26 for(int i=0;i<N;i++)//init()
27 L[i].flag=false;
28 int n,st;
29 cin>>n>>st;
30 for(int i=0;i<n;i++)
31 {
32 int a,d,e;
33 cin>>a>>d>>e;
34 L[a].address=a;
35 L[a].key=d;
36 L[a].ne=e;
37 }
38 int s=st;//存放首地址
39 while(s!=-1)//没有到末地址
40 {
41 L[s].flag=true;
42 cnt++;//统计有效节点个数
43 s=L[s].ne;
44 }
45 if(!cnt)
46 cout<<0<<" "<<-1<<endl;
47 else
48 {
49 sort(L,L+N,cmp);
50 printf("%lld %05lld\n",cnt,L[0].address);
51 for(int i=0;i<cnt;i++)
52 {
53 if(i<cnt-1)
54 printf("%05lld %lld %05lld\n",L[i].address,L[i].key,L[i+1].address);
55 else
56 printf("%05lld %lld -1",L[i].address,L[i].key);
57 }
58 }
59 return 0;
60 }
1032：
题目大意:给定两个word，word中每个letter代表一个节点，这个节点有prior,key,next，题目要求找出两个word的相同部分并且输出相同部分第一个letter的site；
解题思路：正常输入后将待检验的word的节点的地址标为已经标记过，在检验数组中如果碰到已经被标为true的标记数组就break,然后输出即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
4 #define int long long
5 const int N=1e5+10;
6 struct node
7 {
8 char data;
9 int ne;
10 bool flag;
11 }le[N];
12 signed main()
13 {
14 IOS;
15 for(int i=0;i<N;i++)
16 le[i].flag=false;
17 int st1,st2,n;
18 cin>>st1>>st2>>n;
19 for(int i=0;i<n;i++)
20 {
21 int a,e;
22 char d;
23 cin>>a>>d>>e;
24 le[a].data=d;
25 le[a].ne=e;
26 }
27 int s;
28 for(s=st1;~s;s=le[s].ne)
29 {
30 le[s].flag=true;
31 }
32 for(s=st2;~s;s=le[s].ne)
33 {
34 if(le[s].flag)
35 break;
36 }
37 if(s!=-1)
38 printf("%05lld",s);
39 else
40 printf("%lld",-1);
41 return 0;
42 }
1097：其实这个题以前做过，是天梯赛l2的第一题；
题目大意：其实就是题面意思，给定一链表，要求删除绝对值重复的元素，保留的是开始是没有绝对值与其相等的节点。
题目思路：用两个数组来存储删除和保留的节点，并且设置一个标记数组，如果这个标记数组被标记过了，就是重复的元素将其放入b数组，其余的放入a数组并且标记
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 int st,n;
6 const int N=1e5+10;
7 struct node
8 {
9 int key;
10 int ne;
11 }L[N];
12 bool vis[N];
13 vector<int>a,b;//a,存储保留的，b存储删除的
14 signed main()
15 {
16 IOS;
17 cin>>st>>n;
18 for(int i=0;i<n;i++)
19 {
20 int add,data,next;
21 cin>>add>>data>>next;
22 L[add].key=data;
23 L[add].ne=next;
24 }
25 for(int i=st;~i;i=L[i].ne)
26 {
27
28 if(!vis[abs(L[i].key)])//下标是绝对值
29 {
30 vis[abs(L[i].key)]=true;//标记
31 a.push_back(i);
32 }
33 else{
34 b.push_back(i);
35 }
36 }
37 for(int i=0;i<a.size();i++)
38 {
39 if(i<a.size()-1)
40 {
41 printf("%05lld %lld %05lld\n",a[i],L[a[i]].key,a[i+1]);
42 }
43 else
44 printf("%05lld %lld -1\n",a[i],L[a[i]].key);
45 }
46 for(int i=0;i<b.size();i++)
47 {
48 if(i<b.size()-1)
49 {
50 printf("%05lld %lld %05lld\n",b[i],L[b[i]].key,b[i+1]);
51 }
52 else
53 printf("%05lld %lld -1",b[i],L[b[i]].key);
54 }
55 return 0;
56 }
总结一下关于链表操作的做法：
首先肯定是要写链表的结构，包括他的地址，键值和下一个邻接点的地址，并且根据题目，我们可以设一个链表节点的性质，比如这个链表是不是有效的，是不拴被访问过的等等；
并且我们在输入的时候一般会采用hash输入，即是用节点的前驱地址来表示这个节点的下标，并且，这个做可能会导致链表不连续，这时候根据题目要求就可以进行对有效性的排序，将有效的节点放在前面将无效的节点放在后面，例如上面的1052
1 struct node
2 {
3 int address;
4 int key;
5 int ne;
6 bool flag;
7 }L[N];
然后是要对链表初始化，将他的性质全部置为true或者false;
1 for(int i=0;i<N;i++)
2 L[i].flag=false;
第三点是对链表进行地址顺序的遍历，这时候我们就可以对他的性质进行赋值，并且如果有题目要求按照第几个节点输出或者是有统计多少个连续节点的要求就可以统计有效节点的顺序
1 while(s!=-1)
2 {
3 L[s].flag=true;
4 cnt++;
5 s=L[s].ne;
6 }
7
8
9
10 或者是
11
12
13 for(s=st1;~s;s=le[s].ne)
14 {
15 le[s].flag=true;
16 cnt++;
17 }
第四点就是题目的具体要求了，按照题目要求在进行操作就可以了
1103：
题目大意：给定三个数n,k,p；表示用k个数的p次方之和为n，并且，要求输出这k个数的字典序是最大的，例如
当n=169时，有12^2+4^2+2^2+2^2+1^2,11^2+6^2+2^2+2^2+2^2, 6^2 + 6^2 + 6^2 + 6^2 + 5^2;
其中第三个序列的所有底数之和最大，也就是字典序最大，题目要求输出这个最大的序列
题目思路：
dfs
可以先打表，按照下标表示第i个数的k次方，当然是满足这第i个数的k次方要小于等于n；
然后要设置两个数组来表示最优结果序列和当前选择序列；
如果满足条件的情况下并且他的当前序列和是最大的，我们更新最大值并且更新最优序列
另外在设计分支的时候，为保证字典序最大我们可以从打完的表的最大位开始从后往前
选择的话存在选多次，所以如果选择的话下标可以不变，
如果不选的话下标就要减1了因为是从后往前遍历的
所以dfs的主体框架可以这么写：
void dfs(int index,int sum,int cnt,int tsum)
{ if(sum>n||cnt>k)
return ;
if(sum==n&&cnt==k)
{ }
if(index>0)
{ }
}
其中tsum表示的是当前底数序列的和，sum表示的是前a[i]^k之和
参考代码：
1 #include<bits/stdc++.h>//1103
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 vector<int>ans,tmp,num;//最优序列，当前序列，表
6 int n,k,p;
7 int maxnsum=-1;
8 int caluate(int u)//计算k次方
9 {
10 int a=1;
11 for(int i=1;i<=p;i++)
12 {
13 a=a*u;
14 }
15 return a;
16 }
17 void init()//打表
18 {
19 int i=0;
20 int digit=0;
21 while(digit<=n)
22 {
23 num.push_back(digit);
24 i++;
25 digit=caluate(i);
26 }
27
28 }
29 void dfs(int index,int sum,int cnt,int tsum)
30 {
31
32 if(sum>n||cnt>k)//大于了就不满足了
33 return ;
34 if(sum==n&&cnt==k)
35 {
36 if(tsum>maxnsum)//更新最大值
37 {
38 maxnsum=tsum;
39 ans=tmp;//更新最优序列
40 }
41 }
42 if(index>0)
43 {
44 //选
45 tmp.push_back(index);//将当前底数存入
46 dfs(index,sum+num[index],cnt+1,tsum+index);
47 //不选
48 tmp.pop_back();
49 dfs(index-1,sum,cnt,tsum);
50 }
51 }
52 signed main()
53 {
54 IOS;
55 //init();
56 cin>>n>>k>>p;
57 init();
58 dfs(num.size()-1,0,0,0);//倒着来选出字典序最大的序列
59 if(maxnsum<0)
60 {
61 printf("Impossible");
62 }
63 else
64 {
65 printf("%d = ",n);
66 for(int i=0;i<ans.size();i++)
67 {
68 if(i<ans.size()-1)
69 {
70 printf("%d^%d + ",ans[i],p);
71 }
72 else
73 printf("%d^%d",ans[i],p);
74 }
75 }
76 return 0;
77 }
1091：
题目大意：
题目背景是基于脑中风，要求卒中区域的最大体积
题目给定了n张脑中风切片，并且每张脑中风切片是一个m*n的矩阵，脑卒区域是1，正常取余是2
并且卒中区域是一个多个相邻脑卒区域构成的，这里的相邻就是前后上下左右相邻，只要相邻的多余t个，就构成卒中区域，否则就不算
题目要求的是卒中的最大面积
题目思路：
其实已经很明朗了，经典三维bfs了，和杭电那道题已经算是高度相似了：https://www.cnblogs.com/LQS-blog/p/16265466.html
需要注意的依旧是那几点：
注意标记，注意统计，注意判断函数怎么写
参考代码：
1 #include<bits/stdc++.h>//1091
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);;cin.tie(0);cout.tie(0);
5 int m,n,l,t;
6 int mapp[1300][140][100];
7 struct node
8 {
9 int x,y,z;
10 };
11 queue<node>q;
12 bool vis[1300][140][100];
13 int X[6] = {1, 0, 0, -1, 0, 0};
14 int Y[6] = {0, 1, 0, 0, -1, 0};
15 int Z[6] = {0, 0, 1, 0, 0, -1};
16 bool check(int nx, int ny, int nz) {
17 if (nx >= m || nx < 0|| ny < 0|| ny >=n||nz<0 || nz >=l )
18 return false;
19 if (mapp[nx][ny][nz] == 0 || vis[nx][ny][nz] == true)
20 return false;
21 return true;
22 }
23 int bfs(int dx,int dy,int dz)
24 {
25 int cnt=1;//起点也包括在内
26 vis[dx][dy][dz]=true;//标记被访问过
27 queue<node>q;
28 node start,next;
29 start.x=dx;
30 start.y=dy;
31 start.z=dz;
32 q.push(start);
33 while(!q.empty())
34 {
35 start=q.front();
36 q.pop();
37 for(int i=0;i<6;i++)
38 {
39 next.x=start.x+X[i];
40 next.y=start.y+Y[i];
41 next.z=start.z+Z[i];
42 if(check(next.x,next.y,next.z))
43 {
44 vis[next.x][next.y][next.z]=true;
45 cnt++;
46 q.push(next);
47 }
48 }
49 }
50 if(cnt>=t)//构成卒中区域
51 return cnt;
52 else
53 return 0;
54 }
55 signed main()
56 {
57 IOS;
58 cin>>m>>n>>l>>t;
59 for(int k=0;k<l;k++)
60 {
61 for(int i=0;i<m;i++)
62 {
63 for(int j=0;j<n;j++)
64 {
65 cin>>mapp[i][j][k];
66 }
67 }
68 }
69 int ans=0;
70 for(int k=0;k<l;k++)
71 {
72 for(int i=0;i<m;i++)
73 {
74 for(int j=0;j<n;j++)
75 {
76 if(mapp[i][j][k]==1&&!vis[i][j][k])//没有被访问过并且是脑卒区域
77 {
78 ans+=bfs(i,j,k);
79 }
80 }
81 }
82 }
83 cout<<ans;
84 return 0;
85 }
pat链表专题训练+搜索专题的更多相关文章
- 算法专题训练 搜索a-T3 Ni骑士(ni)
搞了半天八数码弄不出来就只好来打题解 这道题是在搜索a碰到的(链接: http://pan.baidu.com/s/1jG9rQsQ ) 感觉题目最大亮点就是这英文简写"ni", ...
- HDU（搜索专题） 1000 N皇后问题（深度优先搜索DFS)解题报告
前几天一直在忙一些事情,所以一直没来得及开始这个搜索专题的训练,今天做了下这个专题的第一题,皇后问题在我没有开始接受Axie的算法低强度训练前,就早有耳闻了,但一直不知道是什么类型的题目,今天一看,原 ...
- dp专题训练
****************************************************************************************** 动态规划 专题训练 ...
- DP专题训练之HDU 2955 Robberies
打算专题训练下DP,做一道帖一道吧~~现在的代码风格完全变了~~大概是懒了.所以.将就着看吧~哈哈 Description The aspiring Roy the Robber has seen a ...
- 【算法系列学习三】[kuangbin带你飞]专题二 搜索进阶 之 A-Eight 反向bfs打表和康拓展开
[kuangbin带你飞]专题二 搜索进阶 之 A-Eight 这是一道经典的八数码问题.首先,简单介绍一下八数码问题: 八数码问题也称为九宫问题.在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的 ...
- NOIP2018提高组金牌训练营——搜索专题
NOIP2018提高组金牌训练营——搜索专题 1416 两点 福克斯在玩一款手机解迷游戏,这个游戏叫做”两点”.基础级别的时候是在一个n×m单元上玩的.像这样: 每一个单元有包含一个有色点.我们将用不 ...
- Leetcode之二分法专题-240. 搜索二维矩阵 II（Search a 2D Matrix II）
Leetcode之二分法专题-240. 搜索二维矩阵 II(Search a 2D Matrix II) 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target.该矩阵 ...
- Leetcode之二分法专题-35. 搜索插入位置（Search Insert Position）
Leetcode之二分法专题-35. 搜索插入位置(Search Insert Position) 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引.如果目标值不存在于数组中,返回它将会 ...
- 搜索专题:Balloons
搜索专题:Balloons 这道题一看与时间有关,第一想到的就是BFS,定义一个状态,包含每一个状态的剩余气球数,已经进行的时间和每一个志愿者上一次吹气球的时间: 每一次状态转换时,检查是否有没有使用 ...
- Leedcode算法专题训练（链表）
1.发现两个链表的交点 160.两个链表的交集(容易) Leetcode /力扣 public class Solution { public ListNode getIntersectionNode ...
随机推荐
- string stack操作要注重细节问题
A string S consisting of N characters is considered to be properly nested if any of the following co ...
- 操作系统开发系列—1.HelloWorld ●
org 07c00h ;伪指令,告诉编译器程序会被加载到7c00处 mov ax, cs mov ds, ax mov es, ax call DispStr ;调用显示字符串例程 jmp $ ;无限 ...
- Android addHeaderView和setAdapter的调用顺序后报错
在4.4之前的系统,setAdapter后再设置addHeaderView会爆 ListView想要添加headerview的话,就要通过addHeaderView这个方法,然后想要为ListView ...
- knockout 学习实例7 foreach
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title> ...
- 概率 Gym 100502D Dice Game
题目传送门 /* 题意:两个人各掷两个骰子,给出每个骰子的最小值和最大值,其余值连续分布 问两人投掷,胜利的概率谁大 数据小,用4个for 把所有的可能性都枚举一遍,统计每一次是谁胜利 还有更简单的做 ...
- Redis系列-存储篇list主要操作函数小结
在总结list之前,先要弄明白几个跟list相关的概念: 列表:一个从左到右的队列,个人理解更类似于一个栈,常规模式下,先进列表的元素,后出. 表头元素:列表最左端第一个元素. 表尾元素:列表最右端的 ...
- Facade模式
Facade模式要求一个子系统的外部与其内部的通信必须通过一个统一的Facade对象进行.Facade模式提供一个高层次的接口,使得子系统更易于使用. 就如同医院的接待员一样,Facade模式的Fa ...
- JavaScript（一）---- 概述
JavaScript一种直译式脚本语言,是一种动态类型.弱类型.基于原型的语言,内置支持类型.它的解释器被称为JavaScript引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在HTML(标 ...
- Vue 爬坑之路（十一）—— 基于 Nuxt.js 实现服务端渲染（SSR）
直接使用 Vue 构建前端单页面应用,页面源码时只有简单的几行 html,这并不利于网站的 SEO,这时候就需要服务端渲染 2016 年 10 月 25 日,zeit.co 背后的团队对外发布了一个 ...
- Java Date类的使用总结
Date类表示特定的瞬间,精确到毫秒. 有2种方法可以创建Date对象(这里不考虑已过时的构造函数) 1.public Date()——分配 Date 对象并初始化此对象,以表示分配它的时间(精确到毫 ...
![[免费专栏] Android安全之Android奇淫run-as命令](/img/d5/771802eb57f24c1cf88657f5c5a724.png)
![[免费专栏] Android安全之ZIP文件目录遍历漏洞](/img/11/c9116562b0ce57205e73fc442874d3.png)
