C++ 祖玛 ZUMA
SLT版本 string,queue
/*
* 祖玛 Zuma
*
* hello@shezw.com 2020.06.29
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct opr{
int t;
char c;
opr( int target, char color ){
t = target;
c = color;
}
};
void checkElimination( string & balls, int cursor ){
if( balls.empty() ){ return; }
int i = 1; int l = cursor, r = cursor, len = balls.size();
while( cursor-i > -1 ){
if( balls[cursor-i] != balls[cursor] ) break;
l = cursor - (i++);
}
i = 1;
while( cursor+i < len ){
if( balls[cursor+i] != balls[cursor] ) break;
r = cursor + (i++);
}
if( r - l > 1 ){
balls.erase( l,r-l+1 );
if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时，原右侧必不为空，右侧第一个将取代原L。
}
}
int main()
{
string balls; int count; // 主要变量
int t; char c; // 缓存变量
cin>>balls; // 读取初始化彩球
cin>>count; // 读取初始化数量
queue<opr> oprs; // 操作队列
while( cin >> t ){ // 读取数字
cin >> c; // 读取颜色
oprs.push( opr(t,c) ); // 压入队列
}
while( !oprs.empty() ){
// cout<< oprs.front().t << " " << oprs.front().c << endl;
t = oprs.front().t;
c = oprs.front().c;
balls.insert( t, 1, c );
checkElimination( balls, t );
oprs.pop();
cout << (balls.empty() ? "-" : balls) << endl;
}
// cout << oprs.size() << endl;
// cout<< balls << endl << count << endl << oprs.front().c << endl;
}
由于清华judge是不允许使用SLT的，所以使用自建QUEUE来完成。
非SLT版
/*
* 祖玛 Zuma
*
* hello@shezw.com 2020.06.29
*/
#include <iostream>
#include <string>
using namespace std;
struct opr{
int t;
char c;
opr(){}
opr( int target, char color ){
t = target;
c = color;
}
};
template <typename T>
struct qe{
qe<T>* prev;
qe<T>* next;
T data;
qe(){}
qe( T d, qe<T>* p = NULL, qe<T>* n = NULL ){
data = d; prev = p; next = n;
}
};
template <typename T>
class queue{ // 专为本算法特别定制队列,简化版
private:
int _size = 0;
public:
qe<T>* _head;
qe<T>* _tail;
queue(){
_size = 0;
_head = new qe<T>;
_tail = new qe<T>;
_head->next = _tail; _head->prev = NULL;
_tail->prev = _head; _tail->next = NULL;
}
~queue(){
}
int size(){return _size;}
void push( T data ){
qe<T>* newQe = new qe<T>( data, _tail->prev, _tail );
_tail->prev->next = newQe;
_tail->prev = newQe;
_size++;
}
void pop(){
if( empty() ) return;
_head->next = _head->next->next;
delete _head->next->prev;
_head->next->prev = _head;
_size--;
}
bool empty(){
return _size == 0;
}
const T & front(){
return _head->next->data;
}
};
void checkElimination( string & balls, int cursor ){
if( balls.empty() ){ return; }
int i = 1; int l = cursor, r = cursor, len = balls.size();
while( cursor-i > -1 ){
if( balls[cursor-i] != balls[cursor] ) break;
l = cursor - (i++);
}
i = 1;
while( cursor+i < len ){
if( balls[cursor+i] != balls[cursor] ) break;
r = cursor + (i++);
}
if( r - l > 1 ){
balls.erase( l,r-l+1 );
if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时，原右侧必不为空，右侧第一个将取代原L。
}
}
int main()
{
string balls; int count; // 主要变量
int t; char c; // 缓存变量
cin>>balls; // 读取初始化彩球
cin>>count; // 读取初始化数量
queue<opr> oprs; // 操作队列
while( cin >> t ){ // 读取数字
cin >> c; // 读取颜色
oprs.push( opr(t,c) ); // 压入队列
}
while( !oprs.empty() ){
// cout<< oprs.front().t << " " << oprs.front().c << endl;
t = oprs.front().t;
c = oprs.front().c;
balls.insert( t, 1, c );
checkElimination( balls, t );
oprs.pop();
cout << (balls.empty() ? "-" : balls) << endl;
}
// cout << oprs.size() << endl;
// cout<< balls << endl << count << endl << oprs.front().c << endl;
}
编译结果 95/100 最坏结果 204ms 14388KB。
这样看来还需要进一步优化。 20200629
最近回复