A – Similar String (abc303 a)
题目大意
给定两个字符串,问这两个字符串是否相似。
两个字符串相似,需要每个字母,要么完全相同,要么一个是1
一个是l
,要么一个是0
一个是o
解题思路
按照题意模拟即可。
可以将全部1
换成l
,全部0
换成o
,再判断相等。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s, t;
cin >> n >> s >> t;
replace(s.begin(), s.end(), '1', 'l');
replace(s.begin(), s.end(), '0', 'o');
replace(t.begin(), t.end(), '1', 'l');
replace(t.begin(), t.end(), '0', 'o');
if (s == t)
cout
B – Discord (abc303 b)
题目大意
给定m
个n
的排列,问有多少对((i, j),i 没在这(m)个排列里作为相邻元素出现。
解题思路
拿set
记录每个相邻对(小的在左),然后总数减去相邻对就是答案。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
set> qwq;
auto add = [&](int x, int y){
int l = min(x, y), r = max(x, y);
qwq.insert({l, r});
};
for(int i = 0; i > x;
if (j)
add(la, x);
la = x;
}
}
cout
C – Dash (abc303 c)
题目大意
二维迷宫,当前((0,0)),生命值h
。给定关于 (LRUD)的操作序列, 一次移动消耗一生命值。生命值为负则失败。给定(m)个生命值恢复物品坐标,当生命值小于 (k)时可以消耗该物品,恢复生命值至(k)。
问能否执行完给定的操作序列。
解题思路
按照题意模拟即可,可以用set
储存物品下标。
注意物品只能用一次,所以使用的话记得erase
。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, h, k;
string s;
cin >> n >> m >> h >> k >> s;
set> item;
for(int i = 0; i > x >> y;
item.insert({x, y});
}
auto ok = [&](){
int x = 0, y = 0;
for(auto &i : s){
if (i == 'L')
x --;
else if (i == 'R')
x ++;
else if (i == 'U')
y ++;
else if (i == 'D')
y --;
else {
assert(0);
}
-- h;
auto good = item.find({x, y});
if (h
D – Shift vs. CapsLock (abc303 d)
题目大意
在键盘上输入aA
串。三个操作,一个是按键a
,一个是按键Shift+a
,一个是按键caplock
,效果同正常输入一样,分别耗时(x,y,z)。
问输入给定aA
串所花费的最小时间。
解题思路
设(dp[i][0/1])表示输入完前 (i) 个字符,当前caplock
灯不亮(亮)的最小花费时间。
然后枚举上一次灯是否亮转移即可。注意一些特别情况,比如当前caplock
灯亮的,输入a
,可以是shift+a
,也可以是caplock+a+caplock
。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL x, y, z;
string s;
cin >> x >> y >> z >> s;
array dp{0, z};
for(auto &i : s){
array dp2{0, 0};
if (i == 'a'){
dp2[0] = min(dp[0] + min(z + y + z, x), dp[1] + min(x, y) + z);
dp2[1] = min(dp[0] + min(x, y) + z, dp[1] + min(z + x + z, y));
}else{
dp2[0] = min(dp[0] + min(z + x + z, y), dp[1] + min(x, y) + z);
dp2[1] = min(dp[0] + min(x, y) + z, dp[1] + min(z + y + z, x));
}
dp.swap(dp2);
}
cout
E – A Gift From the Stars (abc303 e)
题目大意
一开始有一些菊花图,然后随便选了两个度数为(1)的不相连通的点,连了一条边。最终得到了一棵树。
现给定这棵树,还原出原来的菊花图,以升序告诉每个菊花图的边数。
解题思路
考虑最边缘(度数为一)的点,其相邻点必定是菊花图的中心。
然后该中心旁边的旁边的点又是另外一个中心的旁边点。即另一个中心与该中心的距离为3。
即我们先去掉所有度数为(1)的点, 然后度数变成(1)的点就是一个菊花图的中心。
再去除度数为 (1)的点,剩下的度数为 1
的点就是上述中心的相邻点。
再去除度数为 (1)的点,就相当于把最外围的菊花图去掉了,局面变成了一开始的样子,即此时再去除度数为(1)的点,然后度数变成 (1)的点就是另一个菊花图的中心。
因此对这棵树作一遍拓扑排序,与最外围(叶子)的距离 对 (3)取模为 (1)的点都是菊花图的中心,其边数就是该中心原来的度数。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector> edges(n);
vector du(n, 0);
for(int i = 0; i > u >> v;
-- u, -- v;
edges[u].push_back(v);
edges[v].push_back(u);
du[u] ++;
du[v] ++;
}
queue team;
vector dis(n, -1);
for(int i = 0; i ans;
while(!team.empty()){
auto u = team.front();
team.pop();
if (dis[u] % 3 == 1){
ans.push_back(edges[u].size());
}
for(auto &v : edges[u]){
if (dis[v] != -1)
continue;
du[v] --;
if (du[v] == 1){
dis[v] = dis[u] + 1;
team.push(v);
}
}
}
sort(ans.begin(), ans.end());
for(auto &i : ans)
cout
F – Damage over Time (abc303 f)
题目大意
一个怪物(h)血。你有 (n)个技能,每回合仅选择一个释放。第 (i)个技能可以对怪物造成持续(t_i)回合的伤害,每回合伤害 (d_i)。
问将怪物血量变为 (0)或以下,最少需要的回合数。
解题思路
初看此题,对于怎么选择技能感觉比较棘手,原因在于技能是持续伤害而不是一次性的。比如一个技能持续伤害10回,但可能5回合后怪物就死了,这样该技能实际伤害量只有一半。因此在考虑选择技能的时候不能仅考虑(t_i times d_i)的值。尽管如此,对于如何选取技能仍没有头绪。
细想上述的棘手点,因为持续回合不确定,导致选择的技能实际造成的伤害是不确定的。如果我们确定了一个持续回合,比如我就打 (x)回合,然后看怪物的血量是否变为(0)或以下,那么,假设当前是第(i)轮的话, 我用什么技能,其实际造成的伤害是确定的,此时那我肯定是贪心地选择造成伤害最大的一个技能。
因此可以枚举持续的回合数(x),然后从第一回合考虑依次使用什么技能。但因为回合数最多高达(10^{18}),因此不能枚举。但注意到回合数与怪物剩余血量之间存在单调性,因此我们可以二分这个回合数,然后计算一下怪物的血量能否变为 (0)或以下。
假设枚举的回合数为 (x),当前处在第 (i)回合,也就是说接下来使用的技能伤害最多持续(t = x – i + 1)回合。我们考虑使用什么技能。
根据技能生效的回合数(t_i)与 (d)的关系,可以将技能分成两类:
- 剩余回合能完整造成伤害的,即造成伤害数为(t_i times d_i)(即 (t_i leq t))
- 剩余回合不能完整造成伤害的,即造成伤害数为(t times d_i)(即 (t_i > t))
将技能按照(t_i)升序排序,前一类是(t_i leq t) ,我们预处理一个关于(t_i times d_i)的前缀最大值。后一类因为 (t)是固定的,因此就要找一个满足(t_i > t)最大的(d_i),因此再处理一个关于(d_i)的后缀最大值。
对于当前回合使用的技能,就取这两类技能中造成伤害值较大的那个。
由于回合数高达(10^{18}),一回合一回合考虑会超时,因此考虑能否多回合地考虑。
如果此时伤害值较大的第一类技能,那么包括这回合之后的回合,我们肯定是一直使用这个技能(因为它始终是第一类技能(能完整造成伤害)中伤害最大的,而第二类技能的伤害会随着(t)减少而更少,不会比第一类伤害值大),直到剩下的回合数不足以该技能完整造成伤害,再重新考虑,即持续使用(cnt = t – t_i + 1)次,造成(cnt times t_i times d_i)的伤害。之后该技能变成了第二类。
而如果伤害值较大的是第二类技能,那么包括这回合之后的回合,我们还是一直使用这个技能(因为它始终是第二类技能(不能完整造成伤害)中伤害最大的),但由于随着不断的使用,其造成的伤害会越来越少(剩余回合(t)不断变小),因此直到其伤害值小于第一类技能的最大值,再重新考虑,即持续使用(cnt = t – lfloor frac{max_1}{d_i} rfloor)次,造成(d_{max} times (t + t – 1 + t – 2 + cdots + t – cnt + 1) = d_{max} times frac{(t + t – cnt + 1)cnt}{2})伤害。其中(max_1)是第一类技能造成伤害的最大值。
这样每个技能最多考虑两次(一次第一类,一次第二类),因此验证的复杂度为(O(n))。
总的时间复杂度就是 (O(nlog n))
由于回合数有(O(10^{18})),技能总伤害也有(O(10^{18})),验证时可能会超 long long
范围,因此得开__int128
。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
LL h;
cin >> n >> h;
vector> spell(n); // t * d, t, d
for(auto &i : spell){
cin >> i[1] >> i[2];
i[0] = i[1] * i[2];
i[1] = -i[1];
}
sort(spell.begin(), spell.end(), [](const auto& a, const auto&b){
return a[1] > b[1]; // t, small first
});
vector> premax(n);
premax[0] = spell[0];
for(int i = 1; i 0 && x > 0){
while(pos >= 0 && -premax[pos][1] > x){
sufmax = max(sufmax, spell[pos][2]);
-- pos;
}
if (pos = 0)
down = premax[pos][0] / sufmax;
__int128 cnt = x - down;
__int128 sum = cnt * (x - cnt + 1 + x) / 2 * sufmax;
cur -= sum;
x -= cnt;
}else{
__int128 cnt = x - -premax[pos][1] + 1;
cur -= cnt * premax[pos][0];
x -= cnt;
}
}
return cur > 1;
if (check(mid))
r = mid;
else
l = mid;
}
cout
G – Bags Game (abc303 g)
题目大意
解题思路
神奇的代码
Ex – Constrained Tree Degree (abc303 h)
题目大意
给定一个集合,其元素范围在(1 sim n – 1)内。
问有多少棵(n)个节点的数,其每个节点的度数都属于该集合里。
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net