NC200522. 简单快乐棋
描述
简单快乐棋
自走棋是一个集运气和智慧于一体的游戏。可能有人没有听说过，所以这里有一个简单规则介绍：每局比赛8名玩家，一局比赛中玩家需要不断的用自己现有的英雄牌与其他玩家对战，当一方的所有英雄全部阵亡时，这位玩家的生命值会减少，游戏进行到只有一名玩家存活时结束。能购买的英雄牌均为一星，当目前场中存在3名同样的一星英雄时，这3名英雄会合成为一个对应的二星英雄，同样的，3个二星英雄会合成为三星英雄，英雄在合成时会先将这三个同样英雄从场上移除，再在当前空位中最左边的一个上生成新合成的英雄。
妮蔻之助：一次性道具，对所拥有的英雄使用会直接生成一个同类的一星英雄在特殊区域（即不占用当前的那n个位置），在特殊区域的英雄可以参与合成，但最后还处于特殊区域的英雄不计入最后英雄状态。
为了简化问题：当有一种英雄在场上已经为三星时，再出现在购买区的这种牌会被忽略，购买区的英雄会依次购买，即先出现在购买区并且不拥有三星同类英雄的英雄会直接被买下，并被放在当前空位中最左边的位置，如果当前没有空位这个英雄牌会被跳过，如果已存在2个同类同星英雄那么在出现第三个时不会被放入空位而是直接合成。你手中的妮蔻之助会在购买区全部买完后再使用，并且优先对更容易升星的英雄使用。
Peter666是集训队中的下棋能手，他想看看你反应是否和他一样快。现在已知你手中已有的n个位置上的英雄（#表示空位），并且都是一星，你还有x个妮蔻之助。接下来告诉你m个购买区中的英雄，作为一个玩家，你一定希望高星英雄越多越好，即让三星英雄尽可能多，再让二星英雄尽可能多，所以我们优先对较容易升星的英雄使用妮蔻之助（例如：有2个妮蔻之助，你手中有3个英雄：两个同样的一星英雄，和另外一个不同的一星英雄时，我们选择对已有两个的英雄使用妮蔻之助），再让英雄人口数尽可能多，在此基础上想让整个英雄状态的字典序尽可能小。你告诉他你现在有几个三星英雄以及对应的名称,并且将你现在拥有的最小字典序英雄状态告诉他。
字典序：如果两个字符串s,t满足s[0] = t[0], s[1] = t[1], …, s[i] = t[i], s[i+1] < t[i+1]，则说明s的字典序比t小。
升星示例：ZED ZED ZED -> ZED**
ZED** ZED** ZED** -> ZED***
输入描述
首先输入3个整数n，m，x。（1 <= n <= 1e4, 1<= m <= 3e4，0 <= x <= 3）。
接下来n行，每行一个字符串表示英雄名（#为空位置）。第i行 表示第i个位置的英雄。（输入保证不会出现3个及以上相同英雄）
接下来m行，每行一个字符串表示英雄名，表示购买区的英雄。
英雄名为不超过30个大写英文字符的字符串。
输出描述
第一行输出三星英雄的数量k。
接下来k行，每行一个字符串表示三星英雄的名称。
接下来输出当前字典序最小的英雄状态在同一行，每个位置用一个空格隔开，空位置用#表示。
示例1
输入:
5 1 1 ZED ZED RIVEN RIVEN # ZED
输出:
0 ZED** RIVEN** # # #
示例2
输入:
8 10 3 NINI # ZED # ZED # # YASOU NINI ZED ZED ZED ZED ZED ZED ZED ZED YASOU
输出:
1 ZED NINI** YASOU** ZED*** NINI # # # #
C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 2124K, 提交时间: 2020-01-06 17:50:21
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for (int i = s; i < int(t); ++i)
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lowbit(x) ((x) & -(x))
#define range(o) o.begin(), o.end()
#define const_range(o) o.cbegin(), o.cend()
#define temp_name template<typename
temp_name T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "<" << p.ff << "," << p.ss << ">"; }
#define container_ostream(container) \
temp_name... T> ostream& operator<<(ostream& os, const container<T...>& c) { \
if (c.empty()) return os << "{ }"; \
auto iter = c.cbegin(); \
os << "{ " << *iter; \
while (++iter != c.cend()) os << ", " << *iter; \
return os << " }"; \
}
container_ostream(vector);
container_ostream(set);
container_ostream(map);
void dbg() { cerr << endl; }
temp_name H, typename... T> void dbg(H h, T... t) { cerr << " " << h; dbg(t...); }
#ifdef LOCAL
#define debug(...) cerr << "[ "#__VA_ARGS__" ] :", dbg(__VA_ARGS__)
#else
#define debug(...) 0
#endif // LOCAL
typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<string> wait(n), star(n), ss(m);
set<string> three, heros;
map<string, vi> one, two;
priority_queue<int, vi, greater<int>> pos;
rep(i, 0, n) {
cin >> wait[i];
if (wait[i] == "#") {
pos.push(i);
} else {
one[wait[i]].pb(i);
heros.insert(wait[i]);
}
}
rep(i, 0, m) {
cin >> ss[i];
heros.insert(ss[i]);
}
for (const auto& hero : heros) {
one[hero];
two[hero];
}
rep(ii, 0, m) {
string s = move(ss[ii]);
if (three.find(s) != three.cend()) continue;
auto iter = one.find(s);
if (int(iter->ss.size()) == 2) {
for (int i : iter->ss) {
wait[i] = "#";
star[i].resize(0);
pos.push(i);
}
iter->ss.resize(0);
iter = two.find(s);
if (int(iter->ss.size()) == 2) {
for (int i : iter->ss) {
wait[i] = "#";
star[i].resize(0);
pos.push(i);
}
iter->ss.resize(0);
three.insert(s);
wait[pos.top()] = s;
star[pos.top()] = "***";
pos.pop();
} else {
iter->ss.pb(pos.top());
wait[pos.top()] = s;
star[pos.top()] = "**";
pos.pop();
}
} else if (pos.empty()) {
continue;
} else {
iter->ss.pb(pos.top());
wait[pos.top()] = s;
pos.pop();
}
}
rep(x, 1, 4) {
for (auto& hero : two) {
if (k < x) break;
auto iter = one.find(hero.ff);
if (int(hero.ss.size()) == 2 && int(iter->ss.size()) == 3 - x) {
for (int i : hero.ss) {
wait[i] = "#";
star[i].resize(0);
pos.push(i);
}
hero.ss.resize(0);
for (int i : iter->ss) {
wait[i] = "#";
star[i].resize(0);
pos.push(i);
}
iter->ss.resize(0);
three.insert(hero.ff);
wait[pos.top()] = hero.ff;
star[pos.top()] = "***";
pos.pop();
k -= x;
}
}
}
rep(x, 1, 4) {
for (auto& hero : one) {
if (k < x) break;
if (int(hero.ss.size()) == 3 - x) {
for (int i : hero.ss) {
wait[i] = "#";
star[i].resize(0);
pos.push(i);
}
hero.ss.resize(0);
two[hero.ff].pb(pos.top());
wait[pos.top()] = hero.ff;
star[pos.top()] = "**";
pos.pop();
k -= x;
}
}
}
for (const auto& hero : heros) {
if (!k || pos.empty()) break;
if (three.find(hero) != three.cend()) continue;
wait[pos.top()] = hero;
pos.pop();
--k;
}
cout << three.size() << endl;
for (const auto& hero : three) cout << hero << "\n";
rep(i, 0, n) cout << wait[i] << star[i] << " \n"[i == n - 1];
}
C++11(clang++ 3.9) 解法, 执行用时: 23ms, 内存消耗: 4944K, 提交时间: 2019-12-29 10:51:40
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define pb push_back
typedef long long LL;
using namespace std;
const int maxn = 1E5 + 5;
const int inf = (1 << 30);
int n, m, k;
string id, ans[maxn];
priority_queue<int, vector<int>, greater<int> > rem;
map<string, int> cnt;
map<string, vector<int> > pos;
int now;
set<string> three, two, one, all;
set<string>::iterator it;
void up(int to, int ned){
if(to == 3){
it = two.begin();
while(k >= ned && it != two.end()){
if(cnt[*it + "**"] == 2 && 3 - cnt[*it] == ned){
for(int i = 0; i < pos[*it + "**"].size(); ++i){
ans[pos[*it + "**"][i]] = '#';
rem.push(pos[*it + "**"][i]);
}
for(int i = 0; i < pos[*it].size(); ++i){
ans[pos[*it][i]] = '#';
rem.push(pos[*it][i]);
}
pos[*it + "**"].clear();
pos[*it].clear();
now = rem.top(); rem.pop();
three.insert(*it);
ans[now] = *it + "***";
k -= ned;
}
it++;
}
}
else if(to == 2){
it = one.begin();
while(k >= ned && it != one.end()){
if(3 - cnt[*it] == ned){
for(int i = 0; i < pos[*it].size(); ++i){
ans[pos[*it][i]] = '#';
rem.push(pos[*it][i]);
}
pos[*it].clear();
now = rem.top(); rem.pop();
ans[now] = *it + "**";
k -= ned;
}
it++;
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i){
cin >> id;
ans[i] = id;
if(id[0] == '#') rem.push(i);
else{
cnt[id]++;
one.insert(id);
all.insert(id);
pos[id].pb(i);
}
}
while(m--){
cin >> id;
if(three.count(id)) continue;
if(cnt[id] == 2){
ans[pos[id][0]] = '#';
ans[pos[id][1]] = '#';
rem.push(pos[id][0]);
rem.push(pos[id][1]);
one.erase(id);
cnt[id] -= 2;
pos[id].clear();
id += "**";
cnt[id]++;
if(cnt[id] == 3){
cnt[id] -= 3;
ans[pos[id][0]] = '#';
ans[pos[id][1]] = '#';
rem.push(pos[id][0]);
rem.push(pos[id][1]);
now = rem.top(); rem.pop();
pos[id].clear();
two.erase(id);
id += '*';
ans[now] = id;
three.insert(id.substr(0, id.length() - 3));
}else{
now = rem.top(); rem.pop();
ans[now] = id;
pos[id].pb(now);
two.insert(id.substr(0, id.length() - 2));
}
}else{
if(rem.empty()) continue;
now = rem.top(); rem.pop();
one.insert(id);
all.insert(id);
cnt[id]++;
ans[now] = id;
pos[id].pb(now);
}
}
up(3, 1);
up(3, 2);
up(3, 3);
up(2, 1);
up(2, 2);
up(2, 3);
it = all.begin();
while(k > 0 && it != all.end()){
if(rem.empty()) break;
if(three.count(*it)){
it++;
continue;
}
now = rem.top(); rem.pop();
ans[now] = *it;
it++;
--k;
}
cout << three.size() << endl;
for(it = three.begin(); it != three.end(); it++){
cout << *it << endl;
}
for(int i = 1; i <= n; ++i){
cout << ans[i] << ' ';
}
cout << endl;
return 0;
}