最惨的一场,基本所有题都挂了,最终得分
给定不降序列
原题 LG-P8590 『JROI-8』这是新历的朝阳,也是旧历的残阳。
贪心策略找到了。。但是式子没推好,最后想了半天只能糊了一个线段树求平方和上去,复杂度
xxxxxxxxxx
1081
2
3
4using namespace std;
5
6typedef long long ll;
7typedef unsigned long long unll;
8typedef unsigned int uint;
9typedef long double ld;
10
11
12
13
14template < typename T = int >
15inline T read(void){
16 T ret(0);
17 short flag(1);
18 char c = getchar();
19 while(!isdigit(c) && c != '-')c = getchar();
20 if(c == '-')flag = -1, c = getchar();
21 while(isdigit(c)){
22 ret *= 10;
23 ret += int(c - '0');
24 c = getchar();
25 }return ret * flag;
26}
27
28int N, K;
29int a[MAXN];
30
31class SegTree{
32private:
33 ll tr[MAXN << 2];
34 ll trsq[MAXN << 2];
35 ll lz[MAXN << 2];
36
37
38
39
40public:
41 void Pushup(int p){
42 tr[p] = (tr[LS] + tr[RS]) % MOD;
43 trsq[p] = (trsq[LS] + trsq[RS]) % MOD;
44 }
45 void Pushdown(int p, int gl, int gr){
46 lz[LS] = (lz[LS] + lz[p]) % MOD, lz[RS] = (lz[RS] + lz[p]) % MOD;
47 trsq[LS] = (trsq[LS] + 2ll * lz[p] % MOD * tr[LS] % MOD + lz[p] * lz[p] % MOD * (MID - gl + 1) % MOD) % MOD;
48 trsq[RS] = (trsq[RS] + 2ll * lz[p] % MOD * tr[RS] % MOD + lz[p] * lz[p] % MOD * (gr - MID - 1 + 1) % MOD) % MOD;
49 tr[LS] = (tr[LS] + lz[p] * (MID - gl + 1) % MOD) % MOD;
50 tr[RS] = (tr[RS] + lz[p]* (gr - MID - 1 + 1) % MOD) % MOD;
51 lz[p] = 0;
52 }
53 void Build(int p = 1, int gl = 1, int gr = N){
54 if(gl == gr)return tr[p] = a[gl], trsq[p] = tr[p] * tr[p] % MOD, void();
55 Build(LS, gl, MID);
56 Build(RS, MID + 1, gr);
57 Pushup(p);
58 }
59 void Modify(int l, int r, ll val, int p = 1, int gl = 1, int gr = N){
60 // printf("l = %d, r = %d, val = %lld, p = %d, gl = %d, gr = %d\n", l, r, val, p, gl, gr);
61 if(l <= gl && gr <= r)
62 return trsq[p] = (trsq[p] + 2ll * val % MOD * tr[p] % MOD + val * val % MOD * SIZ % MOD) % MOD,
63 tr[p] = (tr[p] + val * SIZ % MOD) % MOD,
64 lz[p] = (lz[p] + val) % MOD,
65 void();
66 Pushdown(p, gl, gr);
67 if(l <= MID)Modify(l, r, val, LS, gl, MID);
68 if(MID + 1 <= r)Modify(l, r, val, RS, MID + 1, gr);
69 Pushup(p);
70 }
71 ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
72 if(l <= gl && gr <= r)return trsq[p];
73 Pushdown(p, gl, gr);
74 return
75 ((l <= MID ? Query(l, r, LS, gl, MID) : 0) +
76 (MID + 1 <= r ? Query(l, r, RS, MID + 1, gr) : 0)) % MOD;
77 }
78}st;
79
80int main(){
81 freopen("function.in", "r", stdin);
82 freopen("function.out", "w", stdout);
83
84 N = read(), K = read();
85 for(int i = 1; i <= N; ++i)a[i] = read();
86 st.Build();
87 ll ans(0);
88 for(int i = 1; i <= K; ++i){
89 int sp = -(int)ceil((double)(K + 1) / 2.0);
90 auto ptr = lower_bound(a + 1, a + N + 1, sp);
91 int idx = distance(a + 1, ptr + 1);
92 st.Modify(1, idx - 1, 1);
93 st.Modify(idx, N, i);
94 ans = (ans + st.Query(1, N));
95 st.Modify(1, idx - 1, -1);
96 st.Modify(idx, N, -i);
97 // int mn(1), mx(i);
98 // for(int j = 1; j <= N; ++j){
99 // ll val = max(abs(a[j] + mn), abs(a[j] + mx));
100 // // printf("val: %lld\n", val);
101 // ans = (ans + val * val % MOD) % MOD;
102 // }
103 // // printf("Cur ans : %lld\n", ans);
104 // printf("Curans : %d = %lld\n", i, ans);
105 }printf("%lld\n", ans);
106
107 return 0;
108}
原题 LG-P8564 ρars/ey。
想到了一些性质,考虑到令
原题 LG-P3921 小学数学题。
基本都切了,然后我没想到。。寄了
完全不阳间的题,然后恐怖的水是生命之源在赛时做完调完了,恐怖如斯。。
显然对于一个数最优的要么为
xxxxxxxxxx
791
2
3
4
5
6
7
8
9
10
11using namespace std;
12using namespace __gnu_pbds;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25
26template< typename T = int >
27inline T read(void);
28
29int N, K;
30ll a[1100000];
31ll sum[1100000];
32ll sumsq[1100000];
33ll ans(0);
34
35signed main(){
36 N = read(), K = read();
37 int sp(0);
38 for(int i = 1; i <= N; ++i)
39 a[i] = read(),
40 sum[i] = (sum[i - 1] + a[i] + MOD) % MOD,
41 sumsq[i] = (sumsq[i - 1] + a[i] * a[i] % MOD) % MOD,
42 sp = a[i] < 0 ? i : sp;
43 for(int k = 1; k <= K; ++k){
44 while(sp && abs(a[sp] + 1) < abs(a[sp] + k))--sp;
45 ans = (
46 ans +
47 (sumsq[N] +
48 (
49 2ll * sum[sp] % MOD +
50 (sp +
51 (2 * k % MOD * ((sum[N] - sum[sp] + MOD) % MOD)) % MOD +
52 (N - sp) * k % MOD * k % MOD
53 ) % MOD
54 ) % MOD
55 )
56 ) % MOD;
57 }printf("%lld\n", ans);
58
59 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
60 return 0;
61}
62
63
64
65template < typename T >
66inline T read(void){
67 T ret(0);
68 short flag(1);
69 char c = getchar();
70 while(c != '-' && !isdigit(c))c = getchar();
71 if(c == '-')flag = -1, c = getchar();
72 while(isdigit(c)){
73 ret *= 10;
74 ret += int(c - '0');
75 c = getchar();
76 }
77 ret *= flag;
78 return ret;
79}
咕咕咕。
咕咕咕。
咕咕咕。
update-2022_10_28 初稿