Letter Exchange
算法本质
模拟、思维
题目大意
有m个人，每个人随机得到3个字符，保证这3m个字符中有m个a、m个b、m个c。
现在若某个人有3个不同字符则会开心。
定义交换操作：
- 选择某两个人，每个人给出一个字符、收到对方给的字符
输出全部人开心的最少次数、操作信息。
思路推演
恶心的模拟题
朴素的想法就是，可以将人分成10类，然后讨论他们的关系即可。
稍加模拟可以发现，其实只与他们的需求有关，比如aab可以视作存在一个需求：出a收b。
稍加推理可以发现，每次交换最好的结果是满足2个需求，至少是满足一个需求、转换另一个需求。
一共有6种需求，可以分成3组需求，每组内部先相互交换。
随即会发现，每组需求剩余的数目一致，且一定构成环，类似于样例2的例子。
模仿样例2的做法处理即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
string xxx="inw";
map<pair<char,char>, vector<int>> mp; // {c1, c2}，出c1收c2
for (int i=1; i<=n; i++)
{
string s;
cin>>s;
map<char, int> cod;
for (auto c:s)
cod[c]++;
char topc; // 找到需要出的字符
for (auto c:xxx)
if (cod[c]>1)
topc = c;
for (auto c:xxx)
if (cod[c]==0)
mp[{topc, c}].push_back(i);
}
vector<pair<int,int>>id; // 记录每次操作的id
vector<pair<char,char>>zifu; // 记录每次操作的字符
for (int i=0; i<3; i++)
{
for (int j=i+1; j<3; j++)
{
char c1=xxx[i], c2=xxx[j];
while (mp[{c1, c2}].size() && mp[{c2, c1}].size())
{
vector<int> &v1=mp[{c1, c2}], &v2=mp[{c2, c1}];
id.push_back({v1.back(), v2.back()});
zifu.push_back({c1, c2});
v1.pop_back();
v2.pop_back();
}
}
}
vector<int> v1, v2, v3;
char c1, c2, c3;
if (mp[{'i', 'n'}].size())
c1='i', c2='n', c3='w';
else
c1='n', c2='i', c3='w';
v1 = mp[{c1, c2}];
v2 = mp[{c2, c3}];
v3 = mp[{c3, c1}];
m = v1.size();
while (m--)
{
int d1=v1.back(), d2=v2.back(), d3=v3.back();
id.push_back({d1, d2});
zifu.push_back({c1, c2});
id.push_back({d2, d3});
zifu.push_back({c1, c3});
v1.pop_back();
v2.pop_back();
v3.pop_back();
}
cout<<id.size()<<endl;
for (int i=0; i<id.size(); i++)
cout<<id[i].first<<" "<<zifu[i].first<<" "<<id[i].second<<" "<<zifu[i].second<<endl;
return;
}Monsters (hard version)
算法本质
思维、数据结构
题目大意
给定长度n的数组a[]，表示第i只怪物的血量。
现在玩家有2个技能：
- 基础技能：消耗一点能量，使得某个怪物生命值-1
- 必杀技：仅能主动释放一次，不消耗能量，使得所有怪物生命值-1，若杀死某个怪物则会被动再释放一次（可无限叠加）
easy版本：干掉所有怪物，输出玩家最小化的能量消耗。
hard版本：遍历r ~ [1~n]，仅存在1~r的怪物，输出玩家最小化的能量消耗。
思路推演
这里只推理hard版本
思路是希望必杀技消耗的生命值最大，显然把必杀技留在最后时刻用收益最大。
比如[2, 3, 5, 5, 9]就应该先处理成[1, 2, 3, 4, 5]。
朴素的想法是，要构建一个结构，使得每次加入新的怪物，可以log级别处理。
初始的想法是链接，记录变成1的元素原来的值、变成2的元素原来的值等等，这里大概思考了10来分钟，一直没有想到可以log级别维护的做法。
在上面思考的过程也发现了一个事，新增值是否变化后数组的最大值，这个指标比较关键。
稍加研究可以发现，比如[1, 4, 4, 4, 4]这个数组，理想情况其最好变成[1,2,3,4,5]，但<=4的元素个数为5，这说明其中<=4的元素必然有某个值重复了。
同时检查<=1 <=2 <=3的元素个数，可以确定这个重复的值为4，最后一定会变成[1,2,3,4,4]。
这给了启发，可以称某个4值为多余的数。
如果能排除多余数的干扰，则最后必然剩下一个有规律的数组，计算会十分方便。
当加入一个新元素，如何判断是否迫使某个元素多余且找到这个元素。
据上面可知，判断多余元素通过前缀个数 > 当前值判断的。
这里我们可以建立一个线段树Bit[x]=t表示x - 当前初始数组中<=x的元素个数。
这样当Bit[x]值为负的时候，就表明出现了多余的数。
（注：同时出现多个负值，多余的数应该是x值最小的那个）
多余的数我们特定处理即可。
ac核心代码
线段树要求：
- 区间加减
- 找最小值的id（同样最小找最左端的）
因为不会写这个线段树，让焦写的，用他账号提交的，过了。
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)