Asterisk

题意：使用题目要求的符号 “，”“*” “（）”，另数列1~n变成给定的顺序

解法：利用栈相互合并，如果当前相邻两个合并的子序列为顺序，那么在中间用“，”链接；如果是逆序那么用“*”号链接。可以证明总长度不会超过1e5

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int a[10010], n, tot;
char c[10];
struct Node {
string s;
int l, r;
Node *lp, *rp;
Node() {
s = "";
l = 0; r = 0;
lp = NULL; rp = NULL;
}
};
Node *head, *tail;
int main() {
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
cin >> n;
head = NULL;
tail = NULL;
a[0] = -1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
snprintf(c, sizeof(c), "%d", a[i]);
if (a[i] != a[i-1]+1) {
tot++;
Node* temp = new Node;
temp->s = c;
temp->l = temp->r = a[i];
temp->rp = NULL;
if (tot == 1) {
temp->lp = NULL;
head = temp;
tail = temp;
} else {
temp->lp = tail;
tail->rp = temp;
tail = temp;
}
} else {
tail->s = tail->s+","+c;
tail->r = tail->r+1;
}
}
Node* p;
for (p = head; p != NULL; p = p->rp) {
if (tot == 1) break;
while (1) {
bool flag = false;
if (p->lp != NULL) {
if (p->l == p->lp->r+1) {
Node* temp = p->lp;
if (p->lp->lp != NULL) p->lp->lp->rp = p;
if (head == p->lp) head = p;
p->s = p->lp->s+","+p->s;
p->l = p->lp->l;
p->lp = p->lp->lp;
delete temp;
flag = true;
tot--;
} else if (p->r+1 == p->lp->l) {
Node* temp = p->lp;
if (head == p->lp) head = p;
if (p->lp->lp != NULL) p->lp->lp->rp = p;
p->s = "("+p->s+")*("+p->lp->s+")";
p->l = p->l;
p->r = p->lp->r;
p->lp = p->lp->lp;
p->rp = p->rp;
delete temp;
flag = true;
tot--;
}
}
if (p->rp != NULL) {
if (p->r+1 == p->rp->l) {
Node* temp = p->rp;
if (tail == p->rp) tail = p;
if (p->rp->rp != NULL) p->rp->rp->lp = p;
p->s = p->s+","+p->rp->s;
p->l = p->l;
p->r = p->rp->r;
p->lp = p->lp;
p->rp = p->rp->rp;
delete temp;
flag = true;
tot--;
} else if (p->l == p->rp->r+1) {
Node* temp = p->rp;
if (tail == p->rp) tail = p;
if (p->rp->rp != NULL) p->rp->rp->lp = p;
p->s = "("+p->rp->s+")*("+p->s+")";
p->l = p->rp->l;
p->r = p->r;
p->lp = p->lp;
p->rp = p->rp->rp;
delete temp;
flag = true;
tot--;
}
}
if (!flag) break;
if (tot == 1) break;
}
}
if (tot == 1) cout << "(" << head->s << ")" << endl;
else cout << "IMPOSSIBLE" << endl;
}

(最后偷懒没有清空内存，别学我蛤~

最后

以上就是善良西牛为你收集整理的AsteriskAsterisk的全部内容，希望文章能够帮你解决AsteriskAsterisk所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。