【2月3日PATブラシノート】——データ構造特集(1)キュー、スタック、チェーンテーブル

1032 Sharing(25分)(チェーンテーブルの遍歴)
1052 Linked List Sorting(25分)(チェーンテーブルの並べ替えと遍歴)
1097 Deduplication on a Linked List(25分)(チェーンテーブルの遍歴、mapの使用)
1074 Reversing Linked List(25点)(チェーンテーブルの遍歴)
1051 Pop Sequence(25分)(スタックの応用)
1056 Mice and Rice(25点)(キューのアプリケーション)
テーマの整理
1.チェーンテーブル操作
1032 Sharing(25分)(チェーンテーブルの遍歴)
タイトル:2本のチェーンテーブルを与えて、彼らは中間のどこかから最後まで重なり合う可能性があって、重なり合うことを始めるこの点の住所を求めます
ヘッダー1でこのチェーンテーブルを1回巡り、遍歴したノードをtrueとし、さらにヘッダー2からこのチェーンテーブルを遍歴し、trueに遍歴すると、この点が2つのチェーンテーブルの重複点の始まりであることを証明します

#include
using namespace std;
struct node {
	int address;
	char w;
	int nx;
	bool flag;
} nodes[100005];
int n;
int main() {
	int a1,a2;
	int A,C;
	char B[2];
	cin>>a1>>a2>>n;
	for(int i=0; i>A>>B>>C;
		nodes[A].address=A;
		nodes[A].w=B[0];
		nodes[A].nx=C;
		nodes[A].flag=0;
	}
	for(;a1!=-1;a1=nodes[a1].nx){
		nodes[a1].flag=1;
	}
	int ans=-1;
	for(;a2!=-1;a2=nodes[a2].nx){
		if(nodes[a2].flag==1){
			ans=nodes[a2].address;
			break;
		}
	}
	if(ans==-1) printf("-1
");
	else printf("%05d
",ans);
	return 0;
}

1052 Linked List Sorting(25分)(チェーンテーブルの並べ替えと遍歴)
題意:チェーンテーブルを提供し、彼を並べ替えて出力する
!!!まずチェーンテーブルを繰り返します.与えられたノードがチェーンテーブルにない可能性があるからです.

#include
using namespace std;
struct node {
	int data;
	int address;
	int nx;
	bool flag;
} nodes[100005];
bool cmp(node a,node b) {
	if(!a.flag||!b.flag) return a.flag>b.flag;
	else return a.data>n>>ad;
	for(int i=0; i>a>>b>>c;
		nodes[a].address=a;
		nodes[a].data=b;
		nodes[a].nx=c;
		nodes[a].flag=false;
	}
	int cnt=0;
	vectorres;
	for(; ad!=-1; ad=nodes[ad].nx) {
		nodes[ad].flag=true;
		cnt++;
	}
	sort(nodes,nodes+100005,cmp);
	if(!cnt){
		printf("0 -1
");
		return 0;
	}
	printf("%d %05d
",cnt,nodes[0].address);
	for(int i=0; i

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
不合理な要素が存在する配列をソートする方法

bool cmp(node a,node b){
	if(!a.flag||!b.flag) return a.flag>b.flag;
	else return a.data

1097 Deduplication on a Linked List(25分)(チェーンテーブルの遍歴、mapの使用)
問題:存在する重複絶対値のノードを除去して出力するチェーンテーブルを与える
mapで絶対値が重複しているかどうかを覚えればいい

#include
using namespace std;
const int maxn=1e6+100;
struct node {
	int data;
	int address;
	int next;
};
node a[maxn];
mapmp;
int main() {
	vectorans1,ans2;
	int n,add,ad,da,nx;
	cin>>add>>n;
	for(int i=0; i>ad>>da>>nx;
		a[ad].address=ad;
		a[ad].data=da;
		a[ad].next=nx;
	}
	for(; add!=-1; add=a[add].next) {
		if(mp[abs(a[add].data)]) {
			ans2.push_back(a[add]);
		} else {
			mp[abs(a[add].data)]=1;
			ans1.push_back(a[add]);
		}
	}
	for(int i=0; i

1074 Reversing Linked List(25点)(チェーンテーブルの遍歴)
題意:チェーンテーブルを与え、その中の要素をk個反転するごとに出力する
問題:k個を反転するごとに、前のk個だけを反転するのではない

#include
using namespace std;
struct node {
	int data;
	int address;
	int nx;
} nodes[100005];
int main() {
	int ad,n,k;
	int a,b,c;
	cin>>ad>>n>>k;
	for(int i=0; i>a>>b>>c;
		nodes[a].address=a;
		nodes[a].data=b;
		nodes[a].nx=c;
	}
//	cout<ans,res;
	int cnt=0;
	for(; ad!=-1; ad=nodes[ad].nx) {
		ans.push_back(nodes[ad]);
		cnt++;
		if(cnt%k==0) reverse(ans.begin()+cnt-k,ans.end());
	}
	for(int i=0;i

まとめ:
PATのチェーンテーブルに関する問題の多くは、チェーンテーブルの遍歴について他の簡単な内容を加えて、問題の説明が頭に入らないかもしれません.遍歴さえ分かれば、チェーン時計の問題は大丈夫です.
2.スタックとその操作
1051 Pop Sequence(25分)(スタックの応用)
标题:列車は1~nの順番で駅に入って、1つのシーケンスを与えて、このシーケンスに従って駅を出ることができるかどうかを聞きます
スタックの古典的な入門テーマ

#include
using namespace std;
int nums[1005];
int main() {
	int n,m,k;
	cin>>m>>n>>k;

	while(k--) {
		bool flag=true;
		stackstk;
		for(int i=0; i>nums[i];
		}
		int pointers=0;
		for(int i=1;i<=n;i++){
			stk.push(i);
			if(stk.size()>m){
				flag=false;
				break;
			}
			while(!stk.empty()&&stk.top()==nums[pointers]) {
				stk.pop();
				pointers++;
			}
		}
		if(stk.empty()&&flag) printf("YES
");
		else printf("NO
");
	}

	return 0;
}

まとめ
宿のテーマはまだ試験が少ないので、FILOの性質に注意してください.
3.キューの適用
1056 Mice and Rice(25点)(キューのアプリケーション)
标题:n匹のネズミに、mごとに1組だけ分けて、各グループの最大の昇格、最後に各ネズミの順位を出力します
!!!現在のマウスをグループに分けることができるとすると、この昇格していないマウスの順位はグループ+1になります.

#include
using namespace std;
struct node {
	int weight;
	int ID;
} mouse[1005];
int n,m;
int number[1005],ran[1005];
int main() {
	int group;
	cin>>n>>m;
	for(int i=0; i>mouse[i].weight;
	}
	for(int i=0; i>number[i],mouse[i].ID=number[i];
	queueque;
	for(int i=0; imaxn.weight) {
				maxn=que.front();
			}
			ran[que.front().ID]=group+1;
			que.pop();
			cnt++;
			if(cnt==m||i==size-1) cnt=0,que.push(maxn),maxn.weight=-1;
		}
	}
	for(int i=0; i