abc 跳了

[ABC257D] Jumping Takahashi 2

题面

$n$ $i$ $(x_i, y_i)$ $p_i$ $S$ $i$ $j$ $p_i \times S \ge \lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert$ $S$ ，输出最小值。

Solution

$S \ge \dfrac{\lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert}{p_i}$ $S$ $S = \left\lceil \dfrac{\lvert x_i - x_j \rvert + \lvert y_i - y_j \rvert}{p_i} \right\rceil$ $i \rightarrow j$ $O(n^3)$ $O(n^2 \log n)$ 的，不过意义不大。

Code


xxxxxxxxxx
66
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
struct Node{ll x, y, p;}nod[300];
27
ll dis[300][300];
28
ll ans(LONG_LONG_MAX);
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= N; ++i)nod[i].x = read(), nod[i].y = read(), nod[i].p = read();
33
    for(int i = 1; i <= N; ++i)
34
        for(int j = 1; j <= N; ++j)
35
            if(i == j)dis[i][j] = 0;
36
            else
37
                dis[i][j] = (ll)ceil((ld)(abs(nod[i].x - nod[j].x) + abs(nod[i].y - nod[j].y)) / (ld)nod[i].p),
38
                dis[j][i] = (ll)ceil((ld)(abs(nod[i].x - nod[j].x) + abs(nod[i].y - nod[j].y)) / (ld)nod[j].p);
39
    for(int k = 1; k <= N; ++k)
40
        for(int i = 1; i <= N; ++i)
41
            for(int j = 1; j <= N; ++j)
42
                dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));
43
    for(int s = 1; s <= N; ++s){
44
        ll mx(-1);
45
        for(int t = 1; t <= N; ++t)mx = max(mx, dis[s][t]);
46
        ans = min(ans, mx);
47
    }printf("%lld\n", ans);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

52
template < typename T >
53
inline T read(void){
54
    T ret(0);
55
    int flag(1);
56
    char c = getchar();
57
    while(c != '-' && !isdigit(c))c = getchar();
58
    if(c == '-')flag = -1, c = getchar();
59
    while(isdigit(c)){
60
        ret *= 10;
61
        ret += int(c - '0');
62
        c = getchar();
63
    }
64
    ret *= flag;
65
    return ret;
66
}

[ABC257E] Addition and Multiplication 2

题面

$x$ $x=0$ 。

高桥君可以无限执行以下操作：

$i$ $1 \leq i \leq 9$ $C_i$ $x$ $10x+i$ 。

$N$ $x$ 最大是多少？

Solution

在保证长度最长的前提下尽量在更高位选择更大的数即可。

Code


xxxxxxxxxx
62
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int C[20];
27
int mn(INT_MAX), mnp(-1);
28
basic_string < int > ans;
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= 9; ++i){
33
        C[i] = read();
34
        if(C[i] < mn)mn = C[i], mnp = i;
35
    }
36
    ll mxLen = N / mn;
37
    for(int i = 1; i <= mxLen; ++i)
38
        for(int j = 9; j >= mnp; --j)
39
            if(N - C[j] >= (mxLen - i) * mn){
40
                N -= C[j], ans += j; break;
41
            }
42
    for(auto d : ans)printf("%d", d);
43
    printf("\n");
44
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45
    return 0;
46
}
47

48
template < typename T >
49
inline T read(void){
50
    T ret(0);
51
    int flag(1);
52
    char c = getchar();
53
    while(c != '-' && !isdigit(c))c = getchar();
54
    if(c == '-')flag = -1, c = getchar();
55
    while(isdigit(c)){
56
        ret *= 10;
57
        ret += int(c - '0');
58
        c = getchar();
59
    }
60
    ret *= flag;
61
    return ret;
62
}

[ABC257F] Teleporter Setting

题面

$n$ $m$ $i$ $u_i, v_i$ $1$ $u_i = 0$ $n$ $i = 1, 2, \cdots, n$ $u_i$ $i$ $1$ $n$ $-1$ 。

Solution

$u_i = 0$ $S$ $S = 0$ $S \rightarrow i$ $1 \rightarrow n$ $1 \rightarrow n$ $1 \rightarrow S \rightarrow i \rightarrow n$ $1 \rightarrow i \rightarrow S \rightarrow n$ $1$ $n$ $\min$ 即可，记得判一下无解。

Code


xxxxxxxxxx
88
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    OPNEW;
29
}ed[610000];
30
ROPNEW(ed);
31
Edge* head[310000];
32

33
int N, M;
34
int dis1[310000], disn[310000];
35

36
void bfs1(void){
37
    memset(dis1, 0x3f, sizeof dis1);
38
    bitset < 310000 > vis; vis.reset();
39
    queue < int > cur; cur.push(1), vis[1] = true, dis1[1] = 0;
40
    while(!cur.empty()){
41
        int p = cur.front(); cur.pop();
42
        for(auto i = head[p]; i; i = i->nxt)
43
            if(!vis[SON])
44
                vis[SON] = true, dis1[SON] = dis1[p] + 1, cur.push(SON);
45
    }
46
}
47
void bfsn(void){
48
    memset(disn, 0x3f, sizeof disn);
49
    bitset < 310000 > vis; vis.reset();
50
    queue < int > cur; cur.push(N), vis[N] = true, disn[N] = 0;
51
    while(!cur.empty()){
52
        int p = cur.front(); cur.pop();
53
        for(auto i = head[p]; i; i = i->nxt)
54
            if(!vis[SON])
55
                vis[SON] = true, disn[SON] = disn[p] + 1, cur.push(SON);
56
    }
57
}
58

59
int main(){
60
    N = read(), M = read();
61
    for(int i = 1; i <= M; ++i){
62
        int s = read(), t = read();
63
        head[s] = new Edge{head[s], t};
64
        head[t] = new Edge{head[t], s};
65
    }bfs1(), bfsn();
66
    for(int i = 1; i <= N; ++i){
67
        int ans = min({dis1[N], dis1[0] + disn[i], dis1[i] + disn[0]});
68
        printf("%d%c", ans >= 0x3f3f3f3f ? -1 : ans, i == N ? '\n' : ' ');
69
    }
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

74
template < typename T >
75
inline T read(void){
76
    T ret(0);
77
    int flag(1);
78
    char c = getchar();
79
    while(c != '-' && !isdigit(c))c = getchar();
80
    if(c == '-')flag = -1, c = getchar();
81
    while(isdigit(c)){
82
        ret *= 10;
83
        ret += int(c - '0');
84
        c = getchar();
85
    }
86
    ret *= flag;
87
    return ret;
88
}

[ABC257G] Prefix Concatenation

题面

$S, T$ $T$ $k$ $S$ $S$ $T$ $k$ $k$ 不存在输出 -1。

Solution

$O(n^2)$ $S(i, j), T(i, j)$ $[i, j]$ $dp(i)$ $T(1, i)$ $k$ 。易得转移：

d p (i) = min_{j < i \land S (1, i - j) = T (j + 1, i)} d p (j) + 1

$\texttt{1D1D}$ $O(n^2)$ 的无法通过，考虑优化。

$dp(i)$ $dp(i) \gt dp(i + 1)$ $dp(i + 1)$ $i + 1$ $dp(i)$ $k$ 不劣，得证。

$j$ 转移即可，可以通过 KMP 中的 next 数组维护。

$S$ $T$ P = S + '#' + T $P$ $i$ $j$ $i - nxt(len_S + 1 + i)$ $+1$ 即为我们添加的占位符 #。

$\texttt{1D0D}$ $O(n)$ ，可以通过。

同时还有一种方法，发现修改状态为后缀可以支持逆序转移，于是转移变为：

d p (i) = min_{j > i \land S (1, j - i) = T (i, j - 1)} d p (j) + 1

$j$ $S$ $T(i, len_T)$ $O(n \log n)$ ，劣于正向转移但也可以通过，且思路更直观，仅代码实现略长。

Code


xxxxxxxxxx
61
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
string S, T;
26
char s[1100000];
27
int dp[1100000];
28
int nxt[1100000];
29

30
int main(){
31
    memset(dp, 0x3f, sizeof dp);
32
    cin >> S >> T;
33
    sprintf(s + 1, "%s#%s", S.c_str(), T.c_str());
34
    int lenS = S.length(), lenT = T.length();
35
    dp[lenS + 1] = 0;
36
    int cur(0);
37
    for(int i = 2; i <= lenS + lenT + 1; ++i){
38
        while(cur && s[cur + 1] != s[i])cur = nxt[cur];
39
        if(s[cur + 1] == s[i])++cur;
40
        if(i > lenS + 1)dp[i] = dp[i - cur] + 1;
41
        nxt[i] = cur;
42
    }printf("%d\n", dp[lenS + lenT + 1] < 0x3f3f3f3f ? dp[lenS + lenT + 1] : -1);
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47
template < typename T >
48
inline T read(void){
49
    T ret(0);
50
    int flag(1);
51
    char c = getchar();
52
    while(c != '-' && !isdigit(c))c = getchar();
53
    if(c == '-')flag = -1, c = getchar();
54
    while(isdigit(c)){
55
        ret *= 10;
56
        ret += int(c - '0');
57
        c = getchar();
58
    }
59
    ret *= flag;
60
    return ret;
61
}

[ABC257Ex] Dice Sum 2

题面

$n$ $i$ $A_{i, 1}, A_{i, 2}, \cdots, A_{i, 6}$ $i$ $C_i$ $k$ $k$ $k$ $998244353$ 意义下的收益期望最大值。

Solution

果然难题的尽头是推式子。

$k$ $A_1, A_2, \cdots, A_k$ ，不难根据期望定义列出式子：

E = \sum_{x_{1} = 1}^{6} \sum_{x_{2} = 1}^{6} \dots \sum_{x_{k} = 1}^{6} \frac{1}{6^{k}} \sum_{i = 1}^{k} A_{i, x_{i}} - \sum_{i = 1}^{k} C_{i}

$\sum_{i = 1}^kA_{i, x_i}$ $A$ $k - 1$ $6^{k - 1}$ $6^{k - 2}$ ），即：

E = \frac{1}{6^{k}} (\sum_{i = 1}^{k} \sum_{x_{i} = 1}^{6} 6^{k - 1} A_{i, x_{i}}^{2} + \sum_{i = 1}^{k} \sum_{j = 1}^{k} \sum_{x_{i} = 1}^{6} \sum_{x_{j} = 1}^{6} 6^{k - 2} A_{i, x_{i}} A_{j, x_{j}} \times [i \neq j]) - \sum_{i = 1}^{k} C_{i}

然后将前面的分式带进去并进一步化简：

E = \frac{1}{6} \sum_{i = 1}^{k} \sum_{x_{i} = 1}^{6} A_{i, x_{i}}^{2} + \frac{1}{36} \sum_{i = 1}^{k} \sum_{j = 1}^{k} \sum_{x_{i} = 1}^{6} \sum_{x_{j} = 1}^{6} A_{i, x_{i}} A_{j, x_{j}} \times [i \neq j] - \sum_{i = 1}^{k} C_{i}

$i \neq j$ $i = j$ 的部分，化简为：

E = \frac{1}{6} \sum_{i = 1}^{k} \sum_{x_{i} = 1}^{6} A_{i, x_{i}}^{2} + \frac{1}{36} (\sum_{i = 1}^{k} \sum_{x_{i} = 1}^{6} A_{i, x_{i}})^{2} - \frac{1}{36} \sum_{i = 1}^{k} (\sum_{x_{i} = 1}^{6} A_{i, x_{i}})^{2} - \sum_{i = 1}^{k} C_{i}

$\sum_{x_i = 1}^6A_{i, x_i}$ ，考虑令：

X_{i} = \frac{1}{6} \sum_{x_{i} = 1}^{6} A_{i, x_{i}}

然后发现第二项可以转化为：

\frac{1}{36} (\sum_{i = 1}^{k} \sum_{x_{i} = 1}^{6} A_{i, x_{i}})^{2} = (\sum_{i = 1}^{k} X_{i})^{2}

$X_i$ 转化：

\begin{aligned} \frac{1}{6} \sum_{i = 1}^{k} \sum_{x_{i} = 1}^{6} A_{i, x_{i}}^{2} - \frac{1}{36} \sum_{i = 1}^{k} (\sum_{x_{i} = 1}^{6} A_{i, x_{i}})^{2} - \sum_{i = 1}^{k} C_{i} \\ = & \sum_{i = 1}^{k} (\frac{1}{6} \sum_{x_{i} = 1}^{6} A_{i, x_{i}}^{2} - X_{i}^{2} - C_{i}) \end{aligned}

此时若我们令：

Y_{i} = \frac{1}{6} \sum_{x_{i} = 1}^{6} A_{i, x_{i}}^{2} - X_{i}^{2} - C_{i}

则原式转化为：

(\sum_{i = 1}^{k} X_{i})^{2} + \sum_{i = 1}^{k} Y_{i}

写的更明显一点，我们就是要求：

max {{(\sum X)}^{2} + \sum Y}

$n \choose k$ $(\sum X, \sum Y)$ $(x, y)$ $x^2 + y$ 。

$\lvert x \rvert$ $y$ $-kx + y$ $-k$ $kx + y$ $k$ $k \sum X + \sum Y$ $kX + Y$ $k$ $k$ $k$ $k$ 个骰子）求和即可。

$k \rightarrow k'$ $i, j$ 之间顺序变化时显然有以下式子（举个例子，大小关系相反亦可）：

\begin{array}{r} k X_{i} + Y_{i} < k X_{j} + Y_{j} \\ k^{'} X_{i} + Y_{i} > k^{'} X_{j} + Y_{j} \end{array}

显然对于这两种情况的转折点存在于：

k = \frac{Y_{j} - Y_{i}}{X_{i} - X_{j}}

$i, j$ 之间的大小关系会改变。

$O(n^2)$ $k$ $O(1)$ $O(n^2 \log n^2)$ ，可以通过。

$X, Y$ long long $(36X, 36Y)$ $36$ 的逆元即可。

Tips：还有一个我调了很久的细节，就是过程中不能取模，否则大小关系会变化，导致答案错误。

然后按照这个思路实现之后大概是这样：


xxxxxxxxxx
94
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
ll inv36;
28
int N, K;
29
ll C[1100];
30
ll A[1100][10];
31
ll X[1100], Y[1100];
32
struct MyPair{int first, second;};
33
map < ld, basic_string < MyPair > > mp;
34
bitset < 1100 > inAns;
35
ll ansX(0), ansY(0);
36
ll ans(LONG_LONG_MIN);
37
int idx[1100];
38

39
ll qpow(ll a, ll b){
40
    ll ret(1), mul(a);
41
    while(b){
42
        if(b & 1)ret = ret * mul % MOD;
43
        b >>= 1;
44
        mul = mul * mul % MOD;
45
    }return ret;
46
}
47

48
int main(){
49
    inv36 = qpow(36ll, MOD - 2);
50
    N = read(), K = read();
51
    for(int i = 1; i <= N; ++i)C[i] = read(), idx[i] = i;
52
    for(int i = 1; i <= N; ++i){
53
        for(int j = 1; j <= 6; ++j)
54
            A[i][j] = read(),
55
            X[i] += A[i][j], //6Xi
56
            Y[i] += 6 * A[i][j] * A[i][j]; //36Yi
57
        Y[i] -= X[i] * X[i] + 36 * C[i];
58
    }
59
    for(int i = 1; i <= N; ++i)for(int j = i + 1; j <= N; ++j)
60
        mp[(ld)(Y[j] - Y[i]) / (ld)(X[i] - X[j])] += MyPair{i, j};
61
    ld k = mp.begin()->first - 0.1;
62
    sort(idx + 1, idx + N + 1, [=](const int &a, const int &b)->bool{return k * (ld)X[a] + (ld)Y[a] > k * (ld)X[b] + (ld)Y[b];});
63
    for(int i = 1; i <= K; ++i)
64
        ansX += X[idx[i]], ansY += Y[idx[i]], inAns[idx[i]] = true;
65
    ans = max(ans, ansX * ansX + ansY);
66
    for(auto mdf : mp){
67
        for(auto Pair : mdf.second){
68
            int l = Pair.first, r = Pair.second;
69
            if(inAns[l] ^ inAns[r]){
70
                if(!inAns[l] && inAns[r])swap(l, r);
71
                inAns[l] = false, inAns[r] = true;
72
                ansX += -X[l] + X[r], ansY += -Y[l] + Y[r];
73
            }
74
        }ans = max(ans, ansX * ansX + ansY);
75
    }printf("%lld\n", (ans % MOD * inv36 % MOD + MOD) % MOD);
76
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77
    return 0;
78
}
79

80
template < typename T >
81
inline T read(void){
82
    T ret(0);
83
    int flag(1);
84
    char c = getchar();
85
    while(c != '-' && !isdigit(c))c = getchar();
86
    if(c == '-')flag = -1, c = getchar();
87
    while(isdigit(c)){
88
        ret *= 10;
89
        ret += int(c - '0');
90
        c = getchar();
91
    }
92
    ret *= flag;
93
    return ret;
94
}

看起来没什么问题，但是交上去就会发现错了很多点，感觉可能是精度之类的问题，于是我们考虑去掉所有浮点数相关运算。

$k$ $k = -\infty$ $Y$ $X$ 即可。

$X$ $k$ 是单调的，当然这个点我也没有完全弄明白，如果有大佬知道的话欢迎解惑。

Code


xxxxxxxxxx
96
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
ll inv36;
28
int N, K;
29
ll C[1100];
30
ll A[1100][10];
31
ll X[1100], Y[1100];
32
struct Node{
33
    int l, r;
34
    friend const bool operator < (const Node &a, const Node &b){
35
        return (Y[a.r] - Y[a.l]) * (X[b.l] - X[b.r]) < (Y[b.r] - Y[b.l]) * (X[a.l] - X[a.r]);
36
    }
37
};
38
basic_string < Node > mdfs;
39
multimap < ld, pair < int, int > > mp;
40
bitset < 1100 > inAns;
41
ll ansX(0), ansY(0);
42
ll ans(LONG_LONG_MIN);
43
int idx[1100];
44

45
ll qpow(ll a, ll b){
46
    ll ret(1), mul(a);
47
    while(b){
48
        if(b & 1)ret = ret * mul % MOD;
49
        b >>= 1;
50
        mul = mul * mul % MOD;
51
    }return ret;
52
}
53

54
int main(){
55
    // freopen("in.txt", "r", stdin);
56
    inv36 = qpow(36ll, MOD - 2);
57
    N = read(), K = read();
58
    for(int i = 1; i <= N; ++i)C[i] = read(), idx[i] = i;
59
    for(int i = 1; i <= N; ++i){
60
        for(int j = 1; j <= 6; ++j)
61
            A[i][j] = read(),
62
            X[i] += A[i][j], //6Xi
63
            Y[i] += 6 * A[i][j] * A[i][j]; //36Yi
64
        Y[i] -= X[i] * X[i] + 36 * C[i];
65
    }
66
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)if(X[i] < X[j])mdfs += Node{i, j};
67
    sort(mdfs.begin(), mdfs.end());
68
    sort(idx + 1, idx + N + 1, [](const int &a, const int &b)->bool{return X[a] < X[b];});
69
    for(int i = 1; i <= K; ++i)
70
        ansX += X[idx[i]], ansY += Y[idx[i]], inAns[idx[i]] = true;
71
    ans = max(ans, ansX * ansX + ansY);
72
    for(auto mdf : mdfs)
73
        if(inAns[mdf.l] && !inAns[mdf.r])
74
            inAns[mdf.l] = false, inAns[mdf.r] = true,
75
            ansX += -X[mdf.l] + X[mdf.r], ansY += -Y[mdf.l] + Y[mdf.r],
76
            ans = max(ans, ansX * ansX + ansY);
77
    printf("%lld\n", (ans % MOD * inv36 % MOD + MOD) % MOD);
78
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
79
    return 0;
80
}
81

82
template < typename T >
83
inline T read(void){
84
    T ret(0);
85
    int flag(1);
86
    char c = getchar();
87
    while(c != '-' && !isdigit(c))c = getchar();
88
    if(c == '-')flag = -1, c = getchar();
89
    while(isdigit(c)){
90
        ret *= 10;
91
        ret += int(c - '0');
92
        c = getchar();
93
    }
94
    ret *= flag;
95
    return ret;
96
}

UPD

update-2022_12_19 初稿

AtCoder Beginner Contest 257 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

abc 跳了

[ABC257D] Jumping Takahashi 2

题面

Solution

Code

[ABC257E] Addition and Multiplication 2

题面

Solution

Code

[ABC257F] Teleporter Setting

题面

Solution

Code

[ABC257G] Prefix Concatenation

题面

Solution

Code

[ABC257Ex] Dice Sum 2

题面

Solution

Code

UPD