题目链接：https://codeforces.com/gym/102028
B. Ultraman vs. Aodzilla and Bodzilla
题意：
两只怪兽，它们的生命和攻击分别为hpA,hpB,attA,attB，现在你要打败它们，第i回合你的攻击为i。问在承受伤害最少的前提下，攻击序列字典序最小是怎样的。攻击A就是A，攻击B就是B。最后输出承受的最小伤害和攻击序列。
题解：
最后的答案肯定是总回合最小时产生的，但是先打死谁不一定，答案就是两种情况的最小值。之后考虑贪心地构造攻击序列。
这里用了种很巧妙地方法吧，定义溢出伤害为最后一击多余出来的伤害。
我们先考虑先将A打死，然后打B的情况。这种字典序已经尽可能小的，只要保证回合数最小就行了。怎么判断回合数最小呢，设Ra为击败A时的溢出伤害，Rtot为最后一击时的溢出伤害（包含了A溢出的伤害），这里Rtot的计算方法参考代码，如果现在Ra > Rtot，说明如果不要A的溢出伤害，可能会多打一回合，那么这时就应该在某一回合打B，这里的位置我们选择尽可能后面的就是Ra（细节考虑一下）。
另外一种情况，我们就先尽可能地将前面的换成A，最后再来判断Rb和Rtot的关系，如果有Rb > Rtot（注意这里Rb会不断减小，因为我们换了一些操作），那么此时如果没有Rb就要多打一回合，设最后一次操作在第i回合，显然现在Rb < i + 1，直接攻击是攻击不了的。我们此时将最后一次操作撤销，将第i + Rb - Rtot次攻击置为A即可，这样也满足最优（A尽可能靠前并且回合数最小）。
细节可以琢磨一下。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + ;
int T;
ll ha, hb, atta, attb;
ll Get_sum(ll x) {
return 1ll * x * (x + ) / ;
}
ll Get_round(ll x) {
ll ans = ;
while(Get_sum(ans) < x) ans++;
return ans ;
}
int main() {
ios::sync_with_stdio(false) ;cin.tie() ;
cin >> T;
while(T--) {
cin >> ha >> hb >> atta >> attb;
ll ra = Get_round(ha), rb = Get_round(hb), rtot = Get_round(ha + hb);
string res(rtot,'B') ;
ll ans = min(atta * ra + attb * rtot , attb * rb + atta * rtot) ;
if(atta * ra + attb * rtot == ans) {
string cur(rtot,'A') ;
for(int i = ra ; i < rtot ; i++) cur[i] = 'B' ;
ll remain_a = Get_sum(ra) - ha , remain_tot = Get_sum(rtot) - ha - hb ;
if(remain_a > remain_tot) {
cur[remain_a - ] = 'B' ;
}
res = min(res ,cur) ;
}
int last;
if(attb * rb + atta * rtot == ans) {
string cur(rtot,'B') ;
for(int i = rb ; i < rtot; i++) cur[i] = 'A' ;
ll remain_b = Get_sum(rb) - hb;
ll remain = remain_b - Get_sum(rtot) + ha + hb;
for(int i = ; i < ra ; i++) {
if(remain_b >= i + ) {
cur[i] = 'A' ;
remain_b -= i + ;
remain -= i + ;
last = i ;
}
}
if(remain > ) {
cur[last] = 'B';
cur[last + remain] = 'A' ;
}
res = min(res, cur) ;
}
cout << ans << ' ' << res << '\n' ;
}
return ;
}
C. Supreme Command
题意：
有一个n*n的棋盘，现在每一行每一列有一个棋子，位置给出。然后有m次操作，操作包含：
1.L/R/U/D k，将所有的棋子向左/右/上/下全部移动k格；2. ? k，询问第k个棋子现在的坐标； 3. !，询问有多少对棋子在同一个格子上面。
题解：
当有棋子接触边界或者重叠在一起时就永远不会分开了，所以我们可以利用这个信息，如果直接考虑移动棋子，那么很麻烦。所以我们就直接考虑移动上下左右的边界线。
这个题横纵二维可以分开考虑，我们主要考虑水平方向就行。用一个区间[L,R]表示所有的棋子在不超过R-L+1的这个范围中，注意这里的L,R和棋盘上的有所不同，同时维护一个偏移量d就行了。这样我们就可以根据这个偏移量和L,R确定出一个棋子的位置。细节见代码吧。
因为每行每列一开始只有一个棋子，所以如果棋子有重叠，那么最终一定位于[L,R]边界处，每次移动边界时考虑一下当前位置的棋子是否在边界上就行了。最终的询问，分几种情况考虑一下就好了，因为最终的格子可能只有一个，或者一列，一横行，这些答案都是不一样的。
具体细节见代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + ;
int T;
int n, m;
ll LL, LR, RL, RR;
ll C[N] ;
bool vis[N] ;
void cal(int i);
struct sol{
int pos[N], id[N];
ll l, r, d;
void init() {
l = , r = n, d = ;
}
void init_cal() {
cal(id[]), cal(id[n]) ;
}
void setpos(int p, int i) {
pos[i] = p;
id[p] = i;
}
void left(int k) {
while(l < r && l + d - k < ) cal(id[++l]);
if(l + d - k >= ) d -= k;
else d = - l ;
}
void right(int k) {
while(r > l && r + d + k > n) cal(id[--r]);
if(r + d + k <= n) d += k;
else d = n - r;
}
int query(int p) {
if(pos[p] <= l) return l + d;
if(pos[p] >= r) return r + d;
return pos[p] + d;
}
}A, B;
void cal(int i) {
if(vis[i]) return ;
else if(A.pos[i] <= A.l && B.pos[i] <= B.l) vis[i] = , LL++;
else if(A.pos[i] <= A.l && B.pos[i] >= B.r) vis[i] = , LR++;
else if(A.pos[i] >= A.r && B.pos[i] <= B.l) vis[i] = , RL++;
else if(A.pos[i] >= A.r && B.pos[i] >= B.r) vis[i] = , RR++;
}
ll Query() {
if(A.r - A.l > && B.r - B.l > ) return C[LL] + C[RR] + C[LR] + C[RL] ;
if(A.r - A.l == && B.r - B.l > ) return C[LL + RL] + C[LR + RR] ;
if(B.r - B.l == && A.r - A.l > ) return C[LL + LR] + C[RR + RL] ;
return C[LL + LR + RR + RL] ;
}
int main() {
scanf("%d", &T) ;
for(int i = ; i < N ; i++)
C[i] = (ll)(i - ) * i / ;
while(T--) {
scanf("%d%d", &n, &m) ;
for(int i = ; i <= n ; i++) {
int x, y ;
scanf("%d%d", &x, &y) ;
B.setpos(x, i);
A.setpos(y, i);
}
LL = LR = RR = RL = ;
A.init() ; B.init() ;
A.init_cal() ; B.init_cal() ;
int k;
char s[] ;
for(int i = ; i <= m ; i++) {
scanf("%s",s);
if(s[] == '!') cout << Query() << '\n';
else {
scanf("%d", &k) ;
if(s[] == 'L') A.left(k) ;
else if(s[] == 'R') A.right(k) ;
else if(s[] == 'U') B.left(k) ;
else if(s[] == 'D') B.right(k) ;
else cout << B.query(k) << ' ' << A.query(k) << '\n' ;
}
//cout << LL << ' ' << LR << ' ' << RR << ' ' << RL << '\n' ;
}
for(int i = ; i <= n; i++) vis[i] = false;
}
return ;
}
H. Can You Solve the Harder Problem?
题意:
给出n个数，求出所有区间中最大值的和，注意相同序列的区间不重复考虑。
题解:
先不考虑去重的情况，我们可以单独考虑每一个值作为区间最大值时的贡献。这个可以直接用单调栈来维护，但是用单调栈的话不便于去重，所以我们可以考虑线段树。
线段树的做法就是从后往前，依次将每个数插到线段树中，并且做一次区间set，将[i，Ri - 1]这个范围中的数置为ai，然后每次将所有的值累加起来即可。这样位于i位置时考虑了当前数对右边的贡献，对左边的贡献在之后会考虑到：如果在他之前的数比他小的话，那么每次求和也会算上ai对左边区间的贡献。
之后就是去重的问题了，去重我们可以考虑利用height数组，每次减去重复的那段即可。这样可行的原因在于，比如当前这个数height[i] = 4，那么说明他后面的几个数height依次为3,2,1，我们会依次减去，最终当前这个长度为4的序列的贡献我们就不会考虑了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + ;
int tt ;
int n;
int a[N], b[N], d[N], s[N], tmp[N];
int x[N], y[N], sa[N], c[N], height[N], Rank[N], Right[N] ;
void Get_sa(int m) {
n++;
for(int i = ; i < m ; i++) c[i] = ;
for(int i = ; i < n ; i++) c[x[i] = d[i]]++;
for(int i = ; i < m ; i++) c[i] += c[i - ] ;
for(int i = n - ; i >= ; i--) sa[--c[x[i]]] = i;
for(int k = ; k <= n ; k <<= ) {
int p = ;
for(int i = n - k; i < n ; i++) y[p++] = i ;
for(int i = ; i < n ; i++) if(sa[i] >= k) y[p++] =sa[i] - k;
for(int i = ; i < m ; i++) c[i] = ;
for(int i = ; i < n ; i++) c[x[y[i]]]++;
for(int i = ; i < m ; i++) c[i] += c[i - ];
for(int i = n - ; i >= ; i--) sa[--c[x[y[i]]]] = y[i] ;
swap(x , y);p = ;x[sa[]] = ;
for(int i = ; i < n ; i++)
x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;
if(p >= n) break ;
m = p;
}
n--;
}
void Get_height() {
int k = ;
for(int i = ; i <= n ; i++) Rank[sa[i]] = i ;
for(int i = ; i < n ; i++) {
if(k) k--;
int j = sa[Rank[i] - ];
while(d[i + k] == d[j + k]) k++;
height[Rank[i]] = k ;
}
}
ll T[N << ] , setv[N << ] ;
void build(int o , int l , int r) {
if(l == r) {
T[o] = ;
setv[o] = ;
return ;
}
int mid = (l + r) >> ;
build(o << , l, mid) ;
build(o << | , mid + , r) ;
T[o] = setv[o] = ;
}
void Get_limt() {
int cnt = ;
for(int i = ; i <= n ; i++) {
if(cnt == || d[i] < d[s[cnt]]) {
s[++cnt] = i ;
} else {
while(cnt > && d[i] >= d[s[cnt]])
Right[s[cnt--]] = i;
s[++cnt] = i;
}
}
}
void push_down(int o,int L,int R) {
if(setv[o]) {
T[o] = (R - L + ) * setv[o] ;
setv[o << ] = setv[o << | ] = setv[o] ;
setv[o] = ;
}
}
void push_up(int o, int L, int R) {
int mid = (L + R) >> ;
T[o] = setv[o << ] ? 1ll * setv[o << ] * (mid - L + ) : T[o << ] ;
T[o] += setv[o << | ] ? 1ll * setv[o << | ] * (R - mid) : T[o << |] ;
}
void Set(int o, int L ,int R, int l, int r, int v) {
if(l <= L && R <= r) {
setv[o] = v;
return ;
}
push_down(o, L, R);
int mid = (L + R) >> ;
if(l <= mid) Set(o << , L, mid, l , r, v) ;
if(r > mid) Set(o << | , mid + , R ,l, r ,v) ;
push_up(o, L, R ) ;
}
ll query(int o , int L, int R, int l , int r) {
if(l <= L && R <= r) {
return setv[o] ? setv[o] * (R - L + ) : T[o] ;
}
push_down(o, L, R);
int mid = (L + R) >> ;
ll ans = ;
if(l <= mid) ans += query(o << , L , mid ,l , r) ;
if(r > mid) ans += query(o << | , mid + , R , l , r) ;
return ans ;
}
int main() {
ios::sync_with_stdio(false); cin.tie() ;
cin >> tt;
while(tt--) {
cin >> n ;
for(int i = ; i < n ; i++) cin >> a[i] , b[i] = d[i] = a[i];
sort(b, b + n) ;
int k = unique(b, b + n) - b;
for(int i = ; i < n ; i++) d[i] = lower_bound(b, b + k, d[i]) - b + ;
d[n] = ;
Get_sa(n + ) ;
Get_height() ;
d[n] = n + ;
Get_limt() ;
build(, , n - );
ll res = ;
for(int i = ; i <= n ; i++)
tmp[sa[i]] = height[i] ;
for(int i = n - ; i >= ; i--) {
Set(, , n - , i, Right[i] - , a[i]) ;
res += setv[] ? (n - i) * setv[] : T[] ;
if(tmp[i] > ) res -= query(, , n - , i, i + tmp[i] - ) ;
}
cout << res << '\n' ;
}
return ;
}