2022.10.28 模拟赛小结
目录最惨的一场，基本所有题都挂了，最终得分 $ 20\texttt{pts} $。
更好的阅读体验戳此进入
赛时思路
T1
给定不降序列 $ a_n $，对于 $ \forall m \le k $，将序列分为可空的 $ m $ 段，对于第 $ i $ 段的数加 $ i $，对于每一个 $ m $ 令 $ q_m $ 为增加后的 $ \sum_{j = 1}na_j2 $，使 $ q_m $ 最大，给定 $ k $，求最大的 $ \sum q_m $。
原题 LG-P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳。
贪心策略找到了。。但是式子没推好，最后想了半天只能糊了一个线段树求平方和上去，复杂度 $ O(n + k \log n) $，理论上能过 $ 60% $ 左右，但是大概是写挂了，花花绿绿的，有 WA 也有 RE，直接爆零。
Code
#define USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long unll;
typedef unsigned int uint;
typedef long double ld;
#define MAXN (1100000)
#define MOD (998244353)
template < typename T = int >
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}return ret * flag;
}
int N, K;
int a[MAXN];
class SegTree{
private:
ll tr[MAXN << 2];
ll trsq[MAXN << 2];
ll lz[MAXN << 2];
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((gl + gr) >> 1)
#define SIZ (gr - gl + 1)
public:
void Pushup(int p){
tr[p] = (tr[LS] + tr[RS]) % MOD;
trsq[p] = (trsq[LS] + trsq[RS]) % MOD;
}
void Pushdown(int p, int gl, int gr){
lz[LS] = (lz[LS] + lz[p]) % MOD, lz[RS] = (lz[RS] + lz[p]) % MOD;
trsq[LS] = (trsq[LS] + 2ll * lz[p] % MOD * tr[LS] % MOD + lz[p] * lz[p] % MOD * (MID - gl + 1) % MOD) % MOD;
trsq[RS] = (trsq[RS] + 2ll * lz[p] % MOD * tr[RS] % MOD + lz[p] * lz[p] % MOD * (gr - MID - 1 + 1) % MOD) % MOD;
tr[LS] = (tr[LS] + lz[p] * (MID - gl + 1) % MOD) % MOD;
tr[RS] = (tr[RS] + lz[p]* (gr - MID - 1 + 1) % MOD) % MOD;
lz[p] = 0;
}
void Build(int p = 1, int gl = 1, int gr = N){
if(gl == gr)return tr[p] = a[gl], trsq[p] = tr[p] * tr[p] % MOD, void();
Build(LS, gl, MID);
Build(RS, MID + 1, gr);
Pushup(p);
}
void Modify(int l, int r, ll val, int p = 1, int gl = 1, int gr = N){
// printf("l = %d, r = %d, val = %lld, p = %d, gl = %d, gr = %d\n", l, r, val, p, gl, gr);
if(l <= gl && gr <= r)
return trsq[p] = (trsq[p] + 2ll * val % MOD * tr[p] % MOD + val * val % MOD * SIZ % MOD) % MOD,
tr[p] = (tr[p] + val * SIZ % MOD) % MOD,
lz[p] = (lz[p] + val) % MOD,
void();
Pushdown(p, gl, gr);
if(l <= MID)Modify(l, r, val, LS, gl, MID);
if(MID + 1 <= r)Modify(l, r, val, RS, MID + 1, gr);
Pushup(p);
}
ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
if(l <= gl && gr <= r)return trsq[p];
Pushdown(p, gl, gr);
return
((l <= MID ? Query(l, r, LS, gl, MID) : 0) +
(MID + 1 <= r ? Query(l, r, RS, MID + 1, gr) : 0)) % MOD;
}
}st;
int main(){
freopen("function.in", "r", stdin);
freopen("function.out", "w", stdout);
N = read(), K = read();
for(int i = 1; i <= N; ++i)a[i] = read();
st.Build();
ll ans(0);
for(int i = 1; i <= K; ++i){
int sp = -(int)ceil((double)(K + 1) / 2.0);
auto ptr = lower_bound(a + 1, a + N + 1, sp);
int idx = distance(a + 1, ptr + 1);
st.Modify(1, idx - 1, 1);
st.Modify(idx, N, i);
ans = (ans + st.Query(1, N));
st.Modify(1, idx - 1, -1);
st.Modify(idx, N, -i);
// int mn(1), mx(i);
// for(int j = 1; j <= N; ++j){
// ll val = max(abs(a[j] + mn), abs(a[j] + mx));
// // printf("val: %lld\n", val);
// ans = (ans + val * val % MOD) % MOD;
// }
// // printf("Cur ans : %lld\n", ans);
// printf("Curans : %d = %lld\n", i, ans);
}printf("%lld\n", ans);
return 0;
}
T2
原题 LG-P8564 ρars/ey。
想到了一些性质，考虑到令 $ dp(i)(0/1) $ 设状态然后转移不了假掉了，然后想不到了，然后寄了，虽然这题因为数据随机生成直接输出 $ f(n) $ 也能获得 $ 40\texttt{pts} $，当然原题没这么良心。
T3
原题 LG-P3921 小学数学题。
基本都切了，然后我没想到。。寄了
T4
完全不阳间的题，然后恐怖的水是生命之源在赛时做完调完了，恐怖如斯。。
正解
T1
显然对于一个数最优的要么为 $ +1 $ 要么为 $ +m $，并且由于序列的单调性一定存在一个分界点 $ sp $，让前面的数均 $ +1 $ 后面的数均 $ +m $ 为最优，且当 $ m $ 增加时显然 $ sp $ 单调递减，于是枚举 $ m $，延续之前的 $ sp $ 找新的，显然第一个不满足 $ (a_{sp} + 1)^2 \le (a_{sp} + m)^2 $ 的即为分界点，于是此时答案为 $ \sum_{i = 1}^{sp}(a_i + 1)^2 + \sum_{i = sp + 1}^{n}(a_i + m)^2 \(，化简一下，\) a_i $ 前缀和为 $ sum_i \(，\) a_i^2 $ 前缀和为 $ sumsq_i $，则为 $ sumsq_n + 2 \times sum_{sp} + sp + 2 \times m \times (sum_n - sum_{sp}) + (n - sp) \times m^2 $。然后需要注意如果比较为 $ \le $ 那么 $ m = 1 $ 的时候会让 $ sp $ 直接变为 $ 0 $，所以选择 $ \lt $。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD 998244353
#define int ll
template< typename T = int >
inline T read(void);
int N, K;
ll a[1100000];
ll sum[1100000];
ll sumsq[1100000];
ll ans(0);
signed main(){
N = read(), K = read();
int sp(0);
for(int i = 1; i <= N; ++i)
a[i] = read(),
sum[i] = (sum[i - 1] + a[i] + MOD) % MOD,
sumsq[i] = (sumsq[i - 1] + a[i] * a[i] % MOD) % MOD,
sp = a[i] < 0 ? i : sp;
for(int k = 1; k <= K; ++k){
while(sp && abs(a[sp] + 1) < abs(a[sp] + k))--sp;
ans = (
ans +
(sumsq[N] +
(
2ll * sum[sp] % MOD +
(sp +
(2 * k % MOD * ((sum[N] - sum[sp] + MOD) % MOD)) % MOD +
(N - sp) * k % MOD * k % MOD
) % MOD
) % MOD
)
) % MOD;
}printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2
咕咕咕。
T3
咕咕咕。
T4
咕咕咕。
UPD
update-2022_10_28 初稿
标签：sp,int,lz,小结,28,tr,gl,2022.10,MOD From： https://www.cnblogs.com/tsawke/p/16945542.html