• 2020-11-28 21:27:12

代码:

#include <iostream>
#include <cstring>
using namespace std;
template <class E>
class Stack{
public:
E * data;int len;int capacity;
Stack(int capacity) : capacity(capacity),len(0),data(new E[capacity]) {}
void push(E e){ data[len++] = e; }
E pop(){ return data[--len]; }
E top(){ return data[len-1]; }
bool isEmpty(){ return len == 0; }
int getLen() const { return len; }
};
int len = 0;
char str[50000000];int  A[1600010]; int B[1600010]; Stack<int> S(1600010);
bool validateStackPermutation(int n,int m, char * str){
int x = 0;int y = 0;
for (int i = 0; i < n; ++i){
A[i] = i+1; cin >> B[i];
}
while (x < n){
S.push(A[x++]); strcpy(str+len,"push\n");len+=5;
if (S.getLen() > m) break;
while ((!S.isEmpty()) && (B[y] == S.top())){
S.pop(); y++; strcpy(str+len,"pop\n");len+=4;
}
}
if (S.isEmpty()) return true;
else return false;
}
int main() {
int n =0; int m =0;
cin >> n >> m;
if (validateStackPermutation(n, m, str)){
cout << str;
}else cout << "No\n";
return 0;
}

更多相关内容
• 题目： 列车调度(Train) Description Figure 1 shows the structure of a station for train dispatching. Figure 1 In this station, A is the entrance for each train and B is the exit. S is the transfer end....

## 题目：

列车调度(Train)

Description
Figure 1 shows the structure of a station for train dispatching.

Figure 1
In this station, A is the entrance for each train and B is the exit. S is the transfer end. All single tracks are one-way, which means that the train can enter the station from A to S, and pull out from S to B. Note that the overtaking is not allowed. Because the compartments can reside in S, the order that they pull out at B may differ from that they enter at A. However, because of the limited capacity of S, no more that m compartments can reside at S simultaneously.
Assume that a train consist of n compartments labeled {1, 2, …, n}. A dispatcher wants to know whether these compartments can pull out at B in the order of {a1, a2, …, an} (a sequence). If can, in what order he should operate it?
Input
Two lines:
1st line: two integers n and m;
2nd line: n integers separated by spaces, which is a permutation of {1, 2, …, n}. This is a compartment sequence that is to be judged regarding the feasibility.
Output
If the sequence is feasible, output the sequence. “Push” means one compartment goes from A to S, while “pop” means one compartment goes from S to B. Each operation takes up one line.
If the sequence is infeasible, output a “no”.
Example 1
Input
5 2
1 2 3 5 4
Output
push
pop
push
pop
push
pop
push
push
pop
pop
Example 2
Input
5 5
3 1 2 4 5
Output
No
Restrictions
1 <= n <= 1,600,000
0 <= m <= 1,600,000
Time: 2 sec
Memory: 256 MB
描述
某列车调度站的铁道联接结构如Figure 1所示。
其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。
设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{a1, a2, …, an}的次序，重新排列后从B端驶出。如果可行，应该以怎样
的次序操作?
输入
共两行。
第一行为两个整数n，m。
第二行为以空格分隔的n个整数，保证为{1, 2, …, n}的一个排列，表示待判断可行性的驶出序列{a1，a2，…，an}。
输出
若驶出序列可行，则输出操作序列，其中push表示车厢从A进入S，pop表示车厢从S进入B，每个操作占一行。
若不可行，则输出No。
样例
见英文题面
限制
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000
时间：2 sec
空间：256 MB

## 我的代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAX 1600005
//如果是中国石油大学的同学，请不要抄袭，不然0分处理时很尴尬，请独立完成，有不理解的地方可与我交流
using namespace std;

int A[MAX], S[MAX], B[MAX];
int curA, curS;
bool output[7 * MAX];
int k;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &B[i]);
for (int i = n; i >= 1; i--)
A[n - i + 1] = i;
curA = n;
curS = 0;

for (int i = 1; i <= n; i++)
{
if (S[curS] == B[i])
{
curS--;
output[k++] = false;
}
else if (A[curA] == B[i])
{
--curA;
output[k++] = true;
output[k++] = false;
if (curS + 1 > m)
{
printf("No\n");
return 0;
}
}
else
{
S[++curS] = A[curA--];
output[k++] = true;
i--;
if (!curA || curS > m)
{
printf("No\n");
return 0;
}
}
}

for (int i = 0; i < k; i++)
{
if (output[i])
printf("push\n");
else
printf("pop\n");
}

return 0;
}


展开全文
• 范围查询题目：我的代码： 题目： 范围查询(Range) Descriptioin Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside. ...

## 题目：

范围查询(Range)

Descriptioin
Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside.
Input
The first line contains two integers: n (size of S) and m (the number of queries).
The second line enumerates all the n points in S.
Each of the following m lines consists of two integers a and b and defines an query interval [a, b].
Output
The number of points in S lying inside each of the m query intervals.
Example
Input
5 2
1 3 7 9 11
4 6
7 12
Output
0
3
Restrictions
0 <= n, m <= 5 * 10^5
For each query interval [a, b], it is guaranteed that a <= b.
Points in S are distinct from each other.
Coordinates of each point as well as the query interval boundaries a and b are non-negative integers not greater than 10^7.
Time: 2 sec
Memory: 256 MB
描述
数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。
输入
第一行包括两个整数：点的总数n，查询的次数m。
第二行包含n个数，为各个点的坐标。
以下m行，各包含两个整数：查询区间的左、右边界a和b。
输出
对每次查询，输出落在闭区间[a, b]内点的个数。
样例
见英文题面
限制
0 ≤ n, m ≤ 5×105
对于每次查询的区间[a, b]，都有a ≤ b
各点的坐标互异
各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数
时间：2 sec
内存：256 MB

## 我的代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
template <class T>
//如果是中国石油大学的同学，请不要抄袭，不然0分处理时很尴尬，请独立完成，有不理解的地方可与我交流
//传入数组，待查找的值，和区间左右下标
int Binary_Search(T a[], const T&x, int len){
int left = 0;
int right = len;
while(left < right){
int mid = left + ((right - left)>>1);
if(x < a[mid]){
right = mid;
}else{
left = mid + 1;
}
}
return --left;
}

template <class T>
void swap(T *a,int x, int y){
T temp = a[x];
a[x] = a[y];
a[y] = temp;
}

template <class T>
int partition2(T *a, int left, int right){
T key = a[left];
int l =left + 1;
int r = right;
while(l <= r){
//当内循环会影响外循环的循环变量时，在内循环的循环条件里一定要加上外循环的循环条件限制！！！
while(l <= r && a[l] <= key){
l++;
}
while(l <= r && a[r] > key){
r--;
}
if(l<r)  //等于的时候交换是没有意义的，所以直接l<r即可
swap(a,l,r);
}
swap(a,left,r);
return r;
}

template <class T>
void quick_sort2(T *a, int left, int right){
if(left < right){
int q = partition2(a,left,right);
quick_sort2(a,left,q-1);
quick_sort2(a,q+1,right);
}
}

struct P{
int x;
int y;
};
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int a[n];
P p[m];
for(int i=0; i<n; ++i){
scanf("%d",&a[i]);
}
quick_sort2(a,0,n-1);
for(int i=0; i<m; i++){
scanf("%d %d",&p[i].x,&p[i].y);
int l = Binary_Search(a,p[i].x-1,n);
int r = Binary_Search(a,p[i].y,n);
int ans = r - l;
printf("%d\n",ans);
}
return 0;
}


展开全文
• @TOC 题目 Description Let’s play the game Zuma! There are a sequence of beads on a track at the right beginning. All the beads are colored but no three adjacent ones are allowed to be with a same ...

## 题目

Description
Let’s play the game Zuma!
There are a sequence of beads on a track at the right beginning. All the beads are colored but no three adjacent ones are allowed to be with a same color. You can then insert beads one by one into the sequence. Once three (or more) beads with a same color become adjacent due to an insertion, they will vanish immediately.

Note that it is possible for such a case to happen for more than once for a single insertion. You can’t insert the next bead until all the eliminations have been done.
Given both the initial sequence and the insertion series, you are now asked by the fans to provide a playback tool for replaying their games. In other words, the sequence of beads after all possible eliminations as a result of each insertion should be calculated.
Input
The first line gives the initial bead sequence. Namely, it is a string of capital letters from ‘A’ to ‘Z’, where different letters correspond to beads with different colors.
The second line just consists of a single interger n, i.e., the number of insertions.
The following n lines tell all the insertions in turn. Each contains an integer k and a capital letter Σ, giving the rank and the color of the next bead to be inserted respectively. Specifically, k ranges from 0 to m when there are currently m beads on the track.
Output
n lines of capital letters, i.e., the evolutionary history of the bead sequence.
Specially, “-” stands for an empty sequence.
Example

Input

ACCBA

5

1 B

0 A

2 B

4 C

0 A

Output

ABCCBA

AABCCBA

AABBCCBA
这里是 - （和CSDN输入冲突所以加上了描述）

A

Restrictions
0 <= n <= 10^4
0 <= length of the initial sequence <= 10^4
Time: 2 sec
Memory: 256 MB
描述
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
输入
第一行是一个由大写字母’A’~'Z’组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示整个回放过程共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。
输出
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
样例
见英文题面
限制
0 ≤ n ≤ 10^4
0 ≤ 初始珠子数量 ≤ 10^4
时间：2 sec
内存：256 MB

## 解析：

1.首先输入的时候要注意使用cin.getline(),因为初始珠子数量可能为0，所以可能读入"/n"
注意：使用fgets()函数会错误
2.定义数组时要开双倍大小20000，否则a[i]=a[i+sub](sub可能等于10000）会越界
3.然后写一个函数按题目的要求模拟即可。从头对字符串扫描，插入字符，消除字符
（若成功消除，则从头扫描），返回操作后的字符串长度，作为是否输出’-'的依据

注意可能不止三个连在一起

## 我的代码：

#include <iostream>
#include <cstring>
#include <cstdio>
//如果是中国石油大学的同学，请不要抄袭，不然0分处理时很尴尬，请独立完成，有不理解的地方可与我交流
using namespace std;
char s[20030];
int solve(int pos,char c, int len)
{
for(int i=len; i>pos; i--)
s[i] = s[i-1];
s[pos] = c;
len++;
for(int i=0; i<len-2; i++)
{
if(s[i]==s[i+1] && s[i+1]==s[i+2])
{
int r,sub;
for(r = i+2; r<len && s[r]==s[i]; r++);
sub = r-i;
for(int j = i; j<len; j++)
{
s[j] = s[j+sub];
}
len-=sub;
i = -1;  //i=-1返回后i++就又从零开始了
}
}
return len;
}

int main()
{
cin.getline(s,10005);
int len = strlen(s);
int m; cin>>m;
while(m--){
int pos;
char c;
scanf("%d %c",&pos, &c);
len = solve(pos,c,len);
if(len)
printf("%s\n",s);
else
printf("-\n");
}
return 0;
}


展开全文
• 清华 oj 大数据
• 题目 旅行商(TSP) Description Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such ...
• 灯塔题目分析我的代码： 题目 Description As shown in the following figure, If another lighthouse is in gray area, they can beacon each other. For example, in following figure, (B, R) is a pair of ...
• 代码： #include <iostream> using namespace std; //@return 返回有序序列中第一个大于等于query的下标，若无返回-1 int binarySearchBAE(int * seq, int n, int query){ int low = 0; int high = n - 1;...
• #ifndef _OJ_ freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif //data input gets(s); int len=strlen(s); int n; //insert的操作次数 scanf("%d",&n); //printf("%d ...
• 祖玛
• 题目：https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1147 分析： 题目提示使用拓扑排序，那么算法一定是基于拓扑排序的框架再加一些额外的操作，于是有两个关键点，写对了，就能满分： 1.拓扑排序： ...
• 题目： https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1145 思路： 使用一维数组和int类型的指针模拟栈的基本操作，再设另一变量i作为入栈序列1,2,...n中的任意一个并不断自增，若i不大于出栈序列out中的...
• 题目：https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1146 分析： 根据真二叉树的特性，前序中第1个节点为当前的树根，第2个节点为当前树的第1个左子树根，可在后序中找到相应的节点，则对应节点在后序中...
• 清华oj 每天一题 通话时长
• 题目 给定n和k，输出用SJT算法生成的第k个排列。其中，第一个排列为1，2，3，…，n。 输入：一行两个整数n,k。 输出：一行用空格隔开的n个数，是SJT算法生成的第k个排列。...数据规模与约定：①保证存在第k个排列；...
• 清华oj 数据结构课堂观察思路 真二叉树重构(Proper Rebuild) 描述 一般来说，给定二叉树的先序遍历序列和后序遍历序列，并不能确定唯一确定该二叉树。 （图一） 比如图一中的两棵二叉树，虽然它们是不同二叉树，...
• 清华oj--每天一题-字母统计字母统计(Count) 字母统计(Count) // An highlighted block #include <stdio.h> #define str_len 4096 int main() { char text[str_len + 1]; int i; gets(text); int count...
• 清华 oj2
• 题目：https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1144 分析前言： 网上有很多解决此题的代码，但几乎无一例外都是用快速排序+归并排序解决，但我认为这是“敷衍”的做法，为什么？因为根据此题所对应的...
• 清华oj a+b
• 清华 oj 3

...