牛客练习赛91（并查集+二维偏序+二分）
BC.魔法学院
题意
亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。
目前她已经收集了个不包括空格的可见字符，第个字符为。可是她想要把自己收集的个字符的价值和最大化，因此去请求了戴安娜的帮助。
戴安娜有种魔法，第种魔法可以将区间的一个字符替换为。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。
请问戴安娜使用完若干次魔法后，亚可收集的个字符的最大价值和可以是多少？
数据范围
\(1<=n<=10^7\)
\(1<=m<=10^6\)
多组测试样例
输入
3 3
aaa
1 3 b
2 3 c
3 3 d
输出
297
分析
按照字符 \(c\) 的价值降序排序，后面的字符一定不能覆盖前面的字符。
这样用并查集就可以解决了
代码
const int N = 2e7 + 5;
int n, m, k, _;
struct TMP
{
int l, r;
char opt;
bool operator<(TMP o){
return opt > o.opt;
}
void read(){ sdd(l, r); sc(opt); }
TMP(int l = 0, int r = 0, char ch = 0) : l(l), r(r), opt(ch){}
};
vector v;
char ch[N];
int fa[N];
int Find(int x)
{
if(x == fa[x]) return x;
return fa[x] = Find(fa[x]);
}
signed main()
{
// IOS;
while(~ sdd(n, m)){
ss(ch + 1);
ch[n + 1] = 0;
rep(i, 1, m){
TMP tmp;
tmp.read();
v.pb(tmp);
}
sort(v.begin(), v.end());
for(int i = 1; i <= n + 1; i ++) fa[i] = i;
ll ans = 0;
int sz = v.size(), res = 0;
for(int i = 0; i < sz; i ++){
int x = v[i].l, y = v[i].r;
int now = Find(x);
while(now <= y){
ch[now] = max(v[i].opt, ch[now]);
fa[now] = Find(now + 1);
now = Find(now + 1);
}
}
for(int i = 1; i <= n; i ++) ans += ch[i];
pll(ans);
}
// PAUSE;
return 0;
}
D.监狱逃亡
题意
勇者为救公主杀入魔塔，不料在魔塔三层遭遇魔王偷袭，失去了神圣剑与神圣盾，而自身也被关入监狱。
监狱是一块的区域，每块格子都有一个价值。勇者目前在监狱的左上角处，而他需要逃亡到监狱的右下角处。
勇者每次可以向右或者向下移动一格，请问勇者逃亡到右下角，其路径价值和大于等于0的不同方法数一共有多少种，答案对取模。
数据范围
\(1<=n<=5*10^5\)
\(-10^9<=a_i<=10^9\)
多组测试样例
输入
2
0 -1
-1 -1
-1 3
输出
3
分析
可以发现只会向下走两次，故可以得到
\(s_1[l]+s_2[r]-s_2[l-1]+s_3[n]-s_3[r-1]>=0\)
\(s_1[l]-s_2[l-1]+s_3[n]>=s_3[r-1]-s_2[r]\)
另 \(a[l]=s_1[l]-s_2[l-1]+s_3[n],\ b[r]=s_3[r-1]-s_2[r]\)
然后寻找 $a[i]>=b[j] && j >= i $ 的个数
树状数组+离散化就可以了
代码
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int n, m, k, _;
ll a[N], b[N];
ll sum[5][N];
vector v;
ll c[N];
int getid(ll x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void add(int i, int x)
{
while(i < N){
c[i] += x;
i += lowbit(i);
}
}
int ask(int i)
{
int ans = 0;
while(i){
ans += c[i];
i -= lowbit(i);
}
return ans;
}
ll adp(ll &x)
{
x %= mod;
x += mod;
x %= mod;
return x;
}
signed main()
{
//IOS;
while(~ sd(n)){
for(int k = 1; k <= 3; k ++){
for(int i = 1; i <= n; i ++){
sd(m);
sum[k][i] = m + sum[k][i - 1];
}
}
for(int i = 1; i <= n; i ++){
a[i] = sum[1][i] - sum[2][i - 1] + sum[3][n];
b[i] = sum[3][i - 1] - sum[2][i];
v.pb(a[i]);
v.pb(b[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()),v.end());
rep(i, 1, n){
a[i] = getid(a[i]);
b[i] = getid(b[i]);
}
ll ans = 0;
for(int i = 1; i <= n; i ++){
add(a[i], 1);
ans += (i - ask(b[i] - 1));
adp(ans);
}
pll(ans);
}
// PAUSE;
return 0;
}
E.游戏人生
题意
白正在玩的游戏到了boss阶段，该阶段一共有个回合，对于每个回合，由白先行动，然后boss再进行攻击。
每回合白可以选择下面一种方式进行操作：
1.普通攻击，对boss造成点伤害。
2.狂暴攻击，当自己生命值大于时，可以消耗点生命值对boss造成点伤害。
3.防御，本回合boss对你造成的点伤害变为(向下取整)。
经过攻略查询，现已知boss的初始生命值为，以及每个回合对玩家造成的伤害为。
游戏要求白必须在个回合内战胜boss（即在个回合的某个回合内使boss的生命值降为或者更低），并保证这个过程中白的生命值一直大于。
在保证通关游戏的前提下，请计算白的最少初始生命值。若无法通关游戏，则输出。
数据范围
\(1<=hp, A, B<=10^9\)
\(1<=n<=10^5\)
\(a_i<=10^9\)
多组测试样例
输入
1
5 1 1
3
1 1 1
输出
5
分析
当时看着就像个二分，这个贪心真是绝了
假设 \(x\) 为答案，那么每次都是狂暴攻击，直到 \(x\) 变为 \(0\)， 然后将之前的狂暴攻击转为普通攻击，普通攻击还可以变成防御，这样每次 \(boss\) 都会加 \(A\)，也就是说，此时我需要加最多的血量也就是 \(max(B, \frac{a[i]}{2}向上取整)\)
代码
const int N = 1e5 + 5;
int n, m, k, _;
ll a[N];
ll H, A, B;
bool C(ll x)
{
priority_queue q, maxx;
ll hp = H;
for(int i = 1; i <= n; i ++){
if(hp - A <= 0) return 1;
if(x > B && hp - 2 * A <= 0) return 1;
hp -= 2 * A;
x -= (a[i] + B);
maxx.push(a[i]);
if(x <= 0){
while(x <= 0){
if(q.empty() == 0 && q.top() >= B){
hp += A;
x += q.top();
q.pop();
}
else if(maxx.empty() == 0){
hp += A;
x += B;
q.push((maxx.top() + 1) / 2);
maxx.pop();
}
else if(q.empty() == 0){
hp += A;
x += q.top();
q.pop();
}
else return 0;
}
}
if(hp <= 0 && x > 0) return 1;
}
return (hp <= 0 && x > 0);
}
signed main()
{
//IOS;
rush(){
sll3(H, A, B);
sd(n);
rep(i, 1, n) sll(a[i]);
ll l = 1, r = 1e18, ans = -1;
// dbg(C(5));
while(r >= l){
ll mid = l + r >> 1;
if(C(mid)){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
pll(ans);
}
// PAUSE;
return 0;
}