PAT甲级学习笔记（一）
##以下PAT链表数据结构相关题目
1.A1032Sharing。本题要求你写一个程序找出两个链表中第一个相同的结点的位置，先用list存储结点，遍历第一个链表（注意遍历链表的写法）将所有结点标记为true，再遍历第二个链表，当出现第一个true的时候打印此时的结点地址，也就是list的下标，相对简单，注意这道题目中主函数中有两个返回出口
#include <iostream>
#include <vector>
using namespace std;
struct node{
char data;
int next;
bool flag;
} list[100000];
int main(){
int start1, start2, n;
scanf("%d %d %d", &start1, &start2, &n);
for(int i = 0; i < n; i++){
char c;
int a, b;
scanf("%d %c %d",&a, &c, &b);
list[a] = {c, b, false};
}
for(int i = start1; i != -1; i = list[i].next){
list[i].flag = true;
}
for(int i = start2; i != -1; i = list[i].next){
if(list[i].flag == true){
printf("%05d",i);
return 0;
}
}
printf("-1");
return 0;
}
2.A10521052 Linked List Sorting。注意链表元素不在结构中的情况一定要考虑进去，这道题没做出来是因为不会链表的赋值操作，注意柳神代码中的list[a] = {a, b, c, false}的写法。本题的第四个测试点考察如果链表元素为0的时候应该输出0 -1，所以一定要考虑进去
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int address, key, next;
bool flag;
}list[100005];
bool cmp(node a, node b){
return !a.flag || !b.flag ? a.flag > b.flag : a.key < b.key;
}
int main(){
int n, first, a, b, c, sum = 0;
scanf("%d %d", &n, &first);
for(int i = 0; i < n; i++){
scanf("%d %d %d", &a, &b, &c);
list[a] = {a, b, c, false};
}
for(int p = first; p != -1; p = list[p].next ){
sum++;
list[p].flag = true;
}
sort(list, list + 100000, cmp);
if(sum == 0) printf("0 -1");
else{
printf("%d %05d\n", sum, list[0].address);
for(int i = 0; i < sum; i++){
if(i == 0){
printf("%05d %d", list[i].address, list[i].key);
}else{
printf(" %05d\n", list[i].address);
printf("%05d %d",list[i].address, list[i].key);
}
}
printf(" -1");
}
return 0;
}
3.A1097 Deduplication on a Linked List.这道题先输入链表，然后用flag进行标记，已经输出过的地址的flag标记为1，先输出统计没有重复的，然后把重复的赋值给ans，最后再输出。注意题目中的数组大小，避免如果ans数组开小了，会出现段错误
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int data,next;
}list[100005];
struct node1{
int address, data;
}ans[100005];
int flag[10005] = {0};
int main(){
int first, n;
scanf("%d %d", &first, &n);
for(int i = 0; i < n; i++){
int temp;
scanf("%d", &temp);
scanf("%d %d",&list[temp].data, &list[temp].next);
}
int sgn = 0, sum = 0;
for(int p = first; p != -1; p = list[p].next){
if(sgn == 0){
printf("%05d %d ", p, list[p].data);
flag[abs(list[p].data)] = 1;
sgn = 1;
}else{
if(flag[abs(list[p].data)] == 0){
printf("%05d\n", p);
printf("%05d %d ", p, list[p].data);
flag[abs(list[p].data)] = 1;
}
else {
ans[sum].address = p;
ans[sum].data = list[p].data;
sum++;
}
}
}
printf("-1\n");
int sgn1 = 0;
for(int i = 0; i < sum ; i++){
if(sgn1 == 0){
printf("%05d %d", ans[i].address,ans[i].data);
sgn1 = 1;
}else{
printf(" %05d\n", ans[i].address);
printf("%05d %d", ans[i].address, ans[i].data);
}
}
if(sum != 0) printf(" -1");
return 0;
}
柳神的代码使用定义结构体中，增加一个num标记，不需要删除的结点num等于cnt1，需要删除的结点等于cnt2+max，然后按照num大小进行排序，再输出就会得到最后的结果。真的很巧妙。
4.A1074Reversing Linked List。这道题有定义变量的时候，next可能是头文件的关键字，所有如果把next数组定义在main函数外边会出现编译不通过的现象。题目中说的是每k个元素反转一次，认真读题，使用数组的一个好处是可以使用sort函数，更加方便，柳神甲级和乙级的题解不太一样，甲级没有使用sort函数，比较麻烦。
#include <iostream>
#include <algorithm>
using namespace std;
int list[100000], data[100000], ans[100000];
int next0[100000];
int main(){
int first, n, k;
int temp;
scanf("%d %d %d", &first, &n, &k);
for(int i = 0; i < n; i++){
cin >> temp;
cin >> data[temp] >> next0[temp];
}
int sum = 0;
while(first != -1){
list[sum++] = first;
first = next0[first];
}
for(int i = 0; i < sum; i++) ans[i] = list[i];
for(int i = 0; i < (sum - sum % k); i += k){//每k个结点一逆转
reverse(begin(list) + i, begin(list) + i + k );
}
for(int i = 0; i < sum - 1; i++)
printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
printf("%05d %d -1",list[sum - 1], data[list[sum - 1]]);
return 0;
}
##以下是PAT甲级dfs题目
1.A1013 Battle Over Cities.这道题注意理解dfstrave的部分直接放在了main（）函数当中。这是求连通分量的一个模板解法，要记下来
#include <iostream>
#include <algorithm>
using namespace std;
int G[1010][1010];
bool visit[1010];
int n;
void dfs(int u){
visit[u] = true;
for(int i = 1; i <= n; i++){
if(visit[i] == false && G[u][i] == 1)//结点没有被访问，并且结点到下一个结点有路径
dfs(i);
}
}
int main(){
int m, k, a, b;
scanf("%d%d%d",&n, &m, &k);
for(int i = 0; i < m; i++){
scanf("%d%d",&a, &b);
G[a][b] = G[b][a] = 1;
}
for(int i = 0; i < k; i++){
fill(visit, visit + 1010, false);
scanf("%d", &a);
int cnt = 0;
visit[a] = true;
for(int j = 1; j <= n; j++){
if(visit[j] == false){
dfs(j);
cnt++;
}
}
printf("%d\n", cnt - 1);
}
return 0;
}
2.A1021 Deepest Root。这道题注意用vector存储图的情况。连通分量的求法同1013.两次遍历就可以求出来所有最大深度的根
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int n, maxheight = 0;
vector<vector<int> > v;//用来存储图
bool visit[10010];
set<int> s;
vector<int> temp;
void dfs(int node, int height){
if(height > maxheight){
temp.clear();
temp.push_back(node);
maxheight = height;
}else if(height == maxheight){
temp.push_back(node);
}
visit[node] = true;
for(int i = 0; i < v[node].size(); i++){
if(visit[v[node][i]] == false){
dfs(v[node][i], height + 1);
}
}
}
int main(){
scanf("%d", &n);
v.resize(n + 1);//必须要有
int cnt = 0, s1 = 0, a, b;
for(int i = 0; i < n - 1; i++){
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if(visit[i] == false){
dfs(i, 1);
if(i == 1){
if(temp.size() != 0) s1 = temp[0];
for(int j = 0; j < temp.size(); j++)
s.insert(temp[j]);
}
cnt++;
}
}
if(cnt >= 2){
printf("Error: %d components", cnt);
}else{
temp.clear();
maxheight = 0;
fill(visit, visit + 10010, false);
dfs(s1, 1);
for(int i = 0; i < temp.size(); i++)
s.insert(temp[i]);
for(auto it = s.begin(); it != s.end(); it++)
printf("%d\n", *it);
}
return 0;
}
3.A1103Integer Factorization 这道题要注意剪枝
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n, k, p, maxFacSum = -1;
vector<int> v, ans, tempAns;
void init(){
int temp = 0, index = 1;
while(temp <= n){
v.push_back(temp);
temp = pow(index, p);
index++;
}
}
void dfs(int index, int tempSum, int tempK, int facSum){
if(tempK == k){
if(tempSum == n && facSum > maxFacSum){
ans = tempAns;//两个容器直接相等了
maxFacSum = facSum;
}
return;//表明得到了结果直接退出dfs
}
while(index >= 1){
if(tempSum + v[index] <= n){
tempAns[tempK] = index;
dfs(index, tempSum + v[index], tempK + 1, facSum + index);
}
if(index == 1) return;
index--;
}
}
int main(){
scanf("%d%d%d",&n, &k, &p);
init();
tempAns.resize(k);
dfs(v.size() - 1, 0, 0, 0);
if(maxFacSum == -1){
printf("Impossible");
return 0;
}
printf("%d = ", n);
for(int i = 0; i < ans.size(); i++){
if(i != 0) printf(" + ");
printf("%d^%d", ans[i], p);
}
return 0;
}
4.A1131Subway Map 代码都看不懂
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<vector<int> > v(10000);
int visit[10000], minCnt, minTransfer, start, end1;
unordered_map<int, int> line;
vector<int> path, tempPath;
int transferCnt(vector<int> a){
int cnt = -1, preLine = 0;//两个站相邻也需要一次换乘，preLine为0
for(int i = 1; i < a.size(); i++){
if(line[a[i-1]*10000+a[i]] != preLine) cnt++;
preLine = line[a[i-1]*10000+a[i]];
}
return cnt;
}
void dfs(int node, int cnt){
if(node == end1 && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))){
minCnt = cnt;
minTransfer = transferCnt(tempPath);
path = tempPath;
}
if(node == end1) return;//到了最后一个结点，直接退出
for(int i = 0; i < v[node].size(); i++){
if(visit[v[node][i]] == 0){
visit[v[node][i]] = 1;
tempPath.push_back(v[node][i]);
dfs(v[node][i], cnt + 1);
visit[v[node][i]] = 0;
tempPath.pop_back();
}
}
}
int main(){
int n, m, k, pre, temp;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &m, &pre);
for(int j = 1; j < m; j++){
scanf("%d", &temp);
v[pre].push_back(temp);
v[temp].push_back(pre);
line[pre*10000+temp] = line[temp*10000+pre] = i+1;
pre = temp;
}
}
scanf("%d", &k);
for(int i = 0; i < k; i++){
scanf("%d%d", &start, &end1);
minCnt = 99999, minTransfer = 99999;
tempPath.clear();
tempPath.push_back(start);
visit[start] = 1;//设置第一项为已经访问，之后要清空
dfs(start, 0);
visit[start] = 0;
printf("%d\n", minCnt);
int preLine = 0, preTransfer = start;
for(int j = 1; j < path.size(); j++){
if(line[path[j-1]*10000+path[j]] != preLine){
if(preLine != 0){
printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]);
}
preLine = line[path[j-1]*10000+path[j]];
preTransfer = path[j-1];
}
}
printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer,end1);
}
return 0;
}
5.1130 Infix Expression (25分)
#include <iostream>
using namespace std;
struct node {
string data;
int l, r;
}a[100];//任何一个结点都包括一个string数据，和两个int型孩子
string dfs(int root){
if(a[root].l == -1 && a[root].r != -1) return "(" + a[root].data + dfs(a[root].r) + ")";
if(a[root].l != -1 && a[root].r != -1) return "(" + dfs(a[root].l) + a[root].data + dfs(a[root].r) + ")";
if(a[root].l == -1 && a[root].r == -1) return a[root].data;//表示从叶子结点网上返回
}
int main(){
int n, judge[100] = {0}, root = 1;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].data >> a[i].l >> a[i].r;
if(a[i].l != -1) judge[a[i].l] = 1;
if(a[i].r != -1) judge[a[i].r] = 1;
}
while(judge[root] == 1) root++;//用来计算根节点的序号。即所有的孩子结点都没有它
string ans = dfs(root);
if(ans[0] == '(') ans = ans.substr(1, ans.size() - 2);
cout << ans;
return 0;
}
6.A1142 Maximal Clique (25分)
#include <iostream>
#include <vector>
using namespace std;
int e[210][210];
int main(){
int nv, ne, m, ta, tb, k;
scanf("%d%d",&nv, &ne);
for(int i = 0; i < ne; i++){
scanf("%d%d", &ta, &tb);
e[ta][tb] = e[tb][ta] = 1;
}
scanf("%d", &m);
for(int i = 0; i < m; i++){
scanf("%d", &k);
vector<int> v(k);//注意学习这种存储方式,表示大小为k
int hash[210] = {0}, isclique = 1, ismaximal = 1;
for(int j = 0; j < k; j++){
scanf("%d",&v[j]);//不需要设置临时变量，直接读入容器
hash[v[j]] = 1;//相当于vis
}
for(int j = 0; j < k; j++){
if(isclique == 0) break;//再跳出来上一层循环
for(int l = j + 1; l < k; l++){
if(e[v[j]][v[l]] == 0){
isclique = 0;
printf("Not a Clique\n");
break;//只能跳出一层循环
}
}
}
if(isclique == 0) continue;//表示判断结束了，直接下一组数据
for(int j = 1; j <= nv; j++){
if(hash[j] == 0){
for(int l = 0; l < k; l++){
if(e[v[l]][j] == 0) break;
if(l == k - 1) ismaximal = 0;//表明里面的结点都选完了
}
}
if(ismaximal == 0){
printf("Not Maximal\n");
break;
}
}
if(ismaximal == 1) printf("Yes\n");
}
return 0;
}
7.1150 Travelling Salesman Problem (25分)
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int e[210][210], n, m, k, ans = 99999999, ansid;
vector<int> v;
void check(int index){
int sum = 0, cnt, flag = 1;
scanf("%d", &cnt);
set<int> s;
vector <int> v(cnt);
for(int i = 0; i < cnt; i++){
scanf("%d", &v[i]);
s.insert(v[i]);
}
for(int i = 0; i < cnt - 1; i++){
if(e[v[i]][v[i+1]] == 0) flag =0;
sum += e[v[i]][v[i+1]];
}
if(flag == 0){
printf("Path %d: NA (Not a TS cycle)\n", index);
}else if(v[0] != v[cnt-1] || s.size() != n){
printf("Path %d: %d (Not a TS cycle)\n", index, sum);
}else if(cnt != n+1){//真是巧妙
printf("Path %d: %d (TS cycle)\n", index, sum);
if(sum < ans){
ans = sum;
ansid = index;
}
}else{
printf("Path %d: %d (TS simple cycle)\n", index, sum);
if (sum < ans) {
ans = sum;
ansid = index;
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
int t1, t2, t;
scanf("%d%d%d", &t1, &t2, &t);
e[t1][t2] = e[t2][t1] = t;
}
scanf("%d", &k);
for(int i = 1; i<= k; i++) check(i);
printf("Shortest Dist(%d) = %d\n", ansid, ans);
return 0;
}
上面使用set来计算访问结点的个数真是巧妙，要学会；本题明显适应于使用函数的方法来解决问题，要有分段处理的思想；对于是不是旅行图的判断要认真学会。
8.1122 Hamiltonian Cycle (25分)
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int G[210][210] = {0};
vector<int> path;
int main(){
int n, m, ta, tb;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d%d", &ta, &tb);
G[ta][tb] = G[tb][ta] = 1;
}
int k;
scanf("%d", &k);
for(int i = 0; i < k; i++){
int n1, start, t;
path.clear();
set<int> s;
scanf("%d%d", &n1, &start);
path.push_back(start);
for(int j = 0; j < n1-1; j++){
scanf("%d", &t);
path.push_back(t);
s.insert(t);
}
int flag = 1;
for(int j = 0; j < n1 - 1; j++){
if(G[path[j]][path[j+1]] == 0) flag = 0;
}
// cout << flag <<"$$" << endl;
if(flag == 0){
printf("NO\n");
continue;
}
if(start == path[n1-1] && s.size() == n && n == n1-1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
这是第一道自己做出来的图的题。注意使用数组的时候，一定要注意会不会越界，尤其是path[n-2]这样的情况，否则会出现段错误；这道题需要考虑道路走不通的情况；按照柳神的代码，优化的地方有：1.只有计数功能的循环，可以直接使用while(cnt–)这样的形式。2.分析问题的时候可以画出顺序图，这道题，多走，少走，或者成环设置成flag1， 道路走不通设置成flag2，逻辑就十分清晰。