首页 > 其他分享 >P1155 [NOIP2008 提高组] 双栈排序

P1155 [NOIP2008 提高组] 双栈排序

时间:2024-04-13 15:22:15浏览次数:32  
标签:int 染色 NOIP2008 双栈 st P1155

P1155 [NOIP2008 提高组] 双栈排序

有思维的二分图染色题。

对于“双”类的题目,我们通常分开考虑单个时的性质。对于一个栈,有一个基本的定理:

若出现 \(i< j<k\),有 \(a_k<a_i<a_j\),那么一定不合法,即没有合法的出栈顺序使之有序。

对于两个栈,我们相当于把序列分成两部分,使每部分之间不矛盾。

那么我们就可以预处理出 \(f_i=\min\limits_{j=i}^ja_j\),枚举 \(i\),\(j\),若有 \(f_{j+1}<a_i<a_j\),则 \(i\) 与 \(j\) 就不能出现在一个栈中。

这种形式就是我们熟悉的二分图染色问题,两两连边的两点不能染成同一颜色。所以可以解决无解情况:无法染色即无解。

染色完之后,接下来就要考虑如何使操作序列字典序最小。

对于每一次入栈,我们都必须保证当前栈的单调性,即从栈底到栈顶递减,否则无法有序。所以在入栈前,我们先把该弹出的弹出,维护单调性。

而如果要入第二个栈,我们要先检查第一个栈是否能弹出,让字典序最小。

总结:对于模型的理解和熟悉,能够第一时间反应;贪心的完整,思路清晰。

#include <bits/stdc++.h>
typedef long long ll;
int read() {
	int x = 0, f = 1;
	char c = getchar();
	while(!isdigit(c)) {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(isdigit(c)) {
		x = (x << 3) + (x << 1) + (c - '0');
		c = getchar();
	} 
	return x * f;
}
int n, cnt, pos = 1;
int col[1010], h[1010], f[1010];
int a[1010];
struct node {
	int to, nxt;
} e[2000010];
void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = h[u];
	h[u] = cnt;
}
bool dfs(int u, int fa, int co) {
	col[u] = co;
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa) continue;
		if(col[v] == -1) {
			if(!dfs(v, u, co ^ 1)) return 0;
		}
		else if(col[u] == col[v]) return 0;
	}
	return 1;
}
std::stack<int> st[2];
bool pop(int c) {
	if(!st[c].empty() && st[c].top() == pos) {
		pos++;
		st[c].pop();
		if(c == 0) std::cout << "b ";
		else std::cout << "d ";
		return 1;
	}
	return 0;
}
void Solve() {
	n = read();
	for(int i = 1; i <= n; i++) {
		a[i] = read();
	}
	f[n + 1] = 0x3f3f3f3f;
	for(int i = n; i >= 1; i--) {
		f[i] = std::min(f[i + 1], a[i]);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(f[j + 1] < a[i] && a[i] < a[j]) {
				add(i, j), add(j, i), col[i] = col[j] = -1;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(col[i] == -1) {
			if(!dfs(i, 0, 0)) {
				std::cout << "0\n";
				return;
			}
		}
	}
	// for(int i = 1; i <= n; i++) {
	// 	std::cout << col[i] << "\n";
	// }
	for(int i = 1; i <= n; i++) {
		if(col[i] == 1) {
			while(pop(0));
		}
		while(!st[col[i]].empty() && st[col[i]].top() < a[i]) {
			if(!pop(col[i])) pop(col[i] ^ 1);
		}
		if(col[i] == 1) {
			while(pop(0));
		}
		st[col[i]].push(a[i]);
		if(col[i] == 0) std::cout << "a ";
		else std::cout << "c ";
	}
	while(pop(0) || pop(1)) {
		if(!pop(0)) pop(1);
	}
	return;
}

int main() {
	
	Solve();

	return 0;
}

标签:int,染色,NOIP2008,双栈,st,P1155
From: https://www.cnblogs.com/FireRaku/p/18092164

相关文章

  • P1149 [NOIP2008 提高组] 火柴棒等式
    P1149[NOIP2008提高组]火柴棒等式题目给你\(n\)根火柴棍,你可以拼出多少个形如\(A+B=C\)的等式?等式中的\(A\)、\(B\)、\(C\)是用火柴棍拼出的整数(若该数非零,则最高位不能是\(0\))。用火柴棍拼数字\(0\sim9\)的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    目描述给你 n 根火柴棍,你可以拼出多少个形如A+B=C 的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 00)。用火柴棍拼数字 0∼90∼9 的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果A=B,则+B=C 与B+A=C 视为不同的等式(≥0A,B,C≥......
  • 洛谷 P1006 [NOIP2008 提高组] 传纸条
    题意:传纸条,跟方格取数一样,但是两条路径不能有重复的。思路:还是一样的走,但是x1跟x2不能相等,包括现在跟上一个状态。总结:看了题解,发现题解大多数都是逻辑不正确的,更有离谱的是数组范围都不加特判,数组访问越界但是可以ac的情况,数据太烂了,放个自以为正确的思路吧,发现之前自己提交的......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    题目链接:本题比较重要的点在于判断加数的范围,即枚举的范围大小。由于题目已知\(n\leqslant24\),且用数字\(1\)拼成的数尽可能大。由于\(1111+1=1112\)已经用了\(25\)根小棒,已经超过了题目\(24\)根小棒的数据范围,所以上界为\(1111\)。#include<cstdio>inta[10]=......
  • 【洛谷】 P1006 [NOIP2008提高组]传纸条
    题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,......
  • C++ [NOIP2008 普及组] ISBN 号码
    文章目录一、题目描述[NOIP2008普及组]ISBN号码题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示二、参考代码一、题目描述[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,IS......
  • P1055 [NOIP2008 普及组] ISBN 号码
    P1055[NOIP2008普及组]ISBN号码[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括\(9\)位数字、\(1\)位识别码和\(3\)位分隔符,其规定格式如x-xxx-xxxxx-x,其中符号-就是分隔符(键盘上的减号),最后一位是识别码,例如0-6......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    [NOIP2008提高组]火柴棒等式题目描述给你\(n\)根火柴棍,你可以拼出多少个形如\(A+B=C\)的等式?等式中的\(A\)、\(B\)、\(C\)是用火柴棍拼出的整数(若该数非零,则最高位不能是\(0\))。用火柴棍拼数字\(0\sim9\)的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果\(......
  • [NOIP2008 提高组] 笨小猴
    [NOIP2008提高组]笨小猴来自洛谷:[https://www.luogu.com.cn/problem/P1125]Openjudge:[http://noi.openjudge.cn/ch0109/06/]普及难度,其实不难。我们先审题.设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数第一行输入字符串,......
  • 洛谷题单指南-暴力枚举-P1149 [NOIP2008 提高组] 火柴棒等式
    原题链接:https://www.luogu.com.cn/problem/P1149题意解读:计算符合A+B=C时,火柴棍数量正好等于n,可以采用枚举A、B,然后计算出C,根据A、B、C计算出所有火柴棍数量,再加上4根加号、等号的,如果与n相等,即为一种合法等式。解题思路:题目的关键在于枚举A、B时,最大值的设定,不能超时。分析......