Educational Codeforces Round 121 (Rated for Div. 2) (A-C)题解
源代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Educational%20Codeforces%20Round%20121%20(Rated%20for%20Div.%202)更好的阅读体验:http://www.abmcar.top/archives/educationalcodeforcesround
源代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Educational%20Codeforces%20Round%20121%20(Rated%20for%20Div.%202)
更好的阅读体验:http://www.abmcar.top/archives/educationalcodeforcesround121ratedfordiv2
A. Equidistant Letters
题目大意:给你一个字符串,让你重排使得其中恰好出现2次的字母距离相同
思路:一个很简单的办法,直接按字典序排列,这样所有出现两次的字母相邻,距离相同
代码:
void work()
{
string oriString;
cin >> oriString;
sort(oriString.begin(),oriString.end());
cout << oriString << endl;
}
B. Minor Reduction
题目大意:给你一个数字,让你选择其中相邻的两位相加后替换这两位,让你求替换后大的数
思路:
有这么几种情况
- 存在两位相加后大于等于10,此时位数不变,但相加必定比之前小,选择最靠后的能>=10的相加
- 不存在两位相加大于等于10,此时位数始终小1,选择让开头两位相加,此时最大
代码:
void work()
{
string s;
cin >> s;
vector<int> nums;
for (char it : s)
nums.push_back(it - '0');
int pos = 0;
for (int i = s.size() - 1; i >= 1; i--)
{
int nowNum = nums[i] + nums[i - 1];
if (nowNum >= 10)
{
pos = i - 1;
break;
}
}
for (int i = 0; i < nums.size(); i++)
{
if (pos == i)
{
cout << nums[i] + nums[i + 1];
i++;
}
else
cout << nums[i];
}
cout << endl;
}
C. Monsters And Spells
题目大意:
有n个怪物,每个怪物在ki秒出现,有hi滴血,你每秒可以选择施法或者不施法,如果不施法,伤害为1,否则伤害为上一秒伤害+1(起手除外),此时伤害多少,消耗多少法力值
思路:
我们可以简单计算出来至少需要在什么时候开始施法来在怪物出现时打到相应的伤害,由此可以得到一个需要施法的时间区间,如果区间存在相连的部分,则相连,最后计算所有合并后的施法区间的消耗法力值即可
代码:
void work()
{
cin >> n;
map<int, int> M;
vector<int> k(n + 1), h(n + 1);
for (int i = 1; i <= n; i++)
cin >> k[i];
for (int i = 1; i <= n; i++)
cin >> h[i];
for (int i = 1; i <= n; i++)
M[k[i] - h[i]] = max(k[i], M[k[i] - h[i]]);
int nowTime = 0;
int cnt = 0;
int ans = 0;
for (auto it : M)
{
if (it.second == 0)
continue;
if (cnt > it.first)
{
cnt = max(cnt, it.second);
continue;
}
int nowLess = cnt - nowTime;
ans += (nowLess + 1) * nowLess / 2LL;
nowTime = it.first;
cnt = it.second;
}
int nowLess = cnt - nowTime;
ans += (nowLess + 1) * nowLess / 2LL;
cout << ans << endl;
}
更多推荐
所有评论(0)