Educational Codeforces Round 125 (Rated for Div. 2) CD题解
C-Bracket Sequence Deletion
题目大意:
当一个括号序列满足以下两个条件之一即为good(长度至少为2):
- 是回文序列
- 左括号和右括号能匹配
每次从左边删除长度最短的good序列,问能够删除几次,最后序列还剩下几个括号。
思路:
用马拉车预处理,然后一边读入括号一边判断当前序列是否为回文或匹配的序列,一旦符合之一就删去。
AC代码:
#include <bits/stdc++.h>
const int N = 1e6 + 10;
using namespace std;
char s[N];
int length, len[N], P, Po; // len[i]保存的是从i到回文右端的长度(i也算在内)
void input()
{
char c;
s[0] = '~';
s[1] = '#';
length = 1;
while ((c = getchar()) != '\n')
{
s[++length] = c;
s[++length] = '#';
}
s[length + 1] = '\0';
}
void manacher()
{
int res = 0;
Po = P = 0;
for (int i = 0; i <= length; i++)
len[i] = 0;
for (int i = 1; i <= length; i++)
{
if (i < P) //如果i在P的左侧,先更新len[i]
{
int j = 2 * Po - i;
len[i] = min(len[j], P - i + 1);
}
while (s[len[i] + i] == s[i - len[i]])
++len[i];
if (len[i] + i - 1 > P) //更新P的位置
{
P = len[i] + i - 1;
Po = i;
}
if (len[i] > res) res = len[i];
}
}
void solve()
{
int n;
scanf("%d", &n);
getchar();
input();
manacher();
int op = 0, cnt = 0, l = 2, flag = 1; // flag记录是否能构成合法序列
for (int i = 2; i < length; i += 2)
{
if (s[i] == '(') //记录左括号比右括号多的数量,等于0说明二者数量相同
cnt++;
else
cnt--;
if (cnt < 0) flag = 0; //一旦右括号比左括号多,那么合法序列就无法构成
if ((i - l) / 2 + 1 < 2) continue; //长度不能小于2
if (flag && cnt == 0) //构成了合法序列
{
op++;
l = i + 2;
}
else if (len[(l + i) / 2] + (l + i) / 2 > i) //构成了回文序列
{
op++;
l = i + 2;
cnt = 0;
flag = 1;
}
}
printf("%d %d\n", op, (length - 1 - l) / 2 + 1);
}
signed main()
{
int T;
scanf("%d", &T);
getchar();
while (T--)
solve();
return 0;
}
D-For Gamers. By Gamers
题目大意:
一共有
m
m
m个怪,每次打一个怪,每次打怪前拥有
C
C
C个金币,怪物有每秒的伤害值和生命值,分别为
D
i
,
H
i
D_i,H_i
Di,Hi,士兵有雇佣费、每秒的伤害值和生命值,分别为
c
i
,
d
i
,
h
i
c_i,d_i,h_i
ci,di,hi。打怪前只能雇佣一种士兵,但是可以雇佣多个。要求在打倒怪物后没有佣兵死亡算通过。怪物每次只能攻击一个士兵。求出每个怪物最小的花费。
C
<
1
0
6
C<10^6
C<106
思路:
要在怪物杀死一个士兵前将其打败,那么要满足
H
d
<
h
D
\frac{H}{d}<\frac{h}{D}
dH<Dh也就是
H
D
<
h
d
HD<hd
HD<hd能不能通过只和伤害值与生命值的乘积有关,所以预处理用
d
h
[
i
]
dh[i]
dh[i]来表示花费
i
i
i所能得到的最大伤害和生命的乘积值。然后对于每次询问,找到一个大于
D
H
DH
DH的最小
d
h
[
i
]
dh[i]
dh[i]值,
i
i
i就是花费了。需要注意的是,当雇佣多个士兵时,相当于将攻击力相加而生命值不变。
AC代码:
#include <bits/stdc++.h>
const long long N = 1e6 + 5;
using namespace std;
long long dh[N], unit[N]; // dh[i]记录花费i时获得的最大dh值
unordered_map<long long, long long> cost; //记录每种伤害值对应的最小花费
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
long long m, n, C, c, d, h;
cin >> n >> C;
for (long long i = 1; i <= n; i++)
{
cin >> c >> d >> h;
unit[c] = max(unit[c], d * h); //当存在多个花费一样的士兵时只保留最大的dh值
}
for (long long i = 1; i <= C; i++)
{
if (unit[i] == 0) continue;
long long ii = i, cnt = unit[i];
while (ii <= C)
{
dh[ii] = max(dh[ii], cnt);
ii += i;
cnt += unit[i];
}
}
for (long long i = 1; i <= C; i++)
{
dh[i] = max(dh[i - 1], dh[i]);
if (cost.count(dh[i])) continue;
cost[dh[i]] = i;
}
cin >> m;
while (m--)
{
cin >> d >> h;
if (d * h >= dh[C])
cout << "-1 ";
else
{
long long ans = *lower_bound(dh + 1, dh + 1 + C, d * h + 1);
cout << cost[ans] << " ";
}
}
return 0;
}