C++ 祖玛 ZUMA
2023-03-07 09:13:37 时间
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
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的