首页 > 其他分享 >AtCoder Beginner Contest 257 题解

AtCoder Beginner Contest 257 题解

时间：2023-01-07 15:58:52浏览次数：70  
标签：AtCoder return int 题解 sum ret void 257 define

AtCoder Beginner Contest 257 Solution

目录

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

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 $ 的边权即为这个，然后跑一遍 FLoyd，维护每个源点的最大值，最后取个最小值即可，复杂度 $ O(n^3) $。当然不用 Floyd，或者改用 bfs + 二分答案，都是可以做到 $ O(n^2 \log n) $ 的，不过意义不大。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.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;

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;

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

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

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)nod[i].x = read(), nod[i].y = read(), nod[i].p = read();
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(i == j)dis[i][j] = 0;
            else
                dis[i][j] = (ll)ceil((ld)(abs(nod[i].x - nod[j].x) + abs(nod[i].y - nod[j].y)) / (ld)nod[i].p),
                dis[j][i] = (ll)ceil((ld)(abs(nod[i].x - nod[j].x) + abs(nod[i].y - nod[j].y)) / (ld)nod[j].p);
    for(int k = 1; k <= N; ++k)
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j]));
    for(int s = 1; s <= N; ++s){
        ll mx(-1);
        for(int t = 1; t <= N; ++t)mx = max(mx, dis[s][t]);
        ans = min(ans, mx);
    }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);
    int 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;
}

[ABC257E] Addition and Multiplication 2

题面

高桥君有一个整数 \(x\) 。一开始的时候， \(x=0\) 。

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

  • 选择一个整数 \(i\) （ \(1 \leq i \leq 9\) ）。支付 \(C_i\) 日元，把 \(x\) 变为 \(10x+i\) 。

高桥君有 \(N\) 日元，问 \(x\) 最大是多少？

Solution

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.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;

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;

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

int N;
int C[20];
int mn(INT_MAX), mnp(-1);
basic_string < int > ans;

int main(){
    N = read();
    for(int i = 1; i <= 9; ++i){
        C[i] = read();
        if(C[i] < mn)mn = C[i], mnp = i;
    }
    ll mxLen = N / mn;
    for(int i = 1; i <= mxLen; ++i)
        for(int j = 9; j >= mnp; --j)
            if(N - C[j] >= (mxLen - i) * mn){
                N -= C[j], ans += j; break;
            }
    for(auto d : ans)printf("%d", d);
    printf("\n");
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int 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;
}

[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

#define _USE_MATH_DEFINES
#include <bits/stdc++.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;

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;

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

struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[610000];
ROPNEW(ed);
Edge* head[310000];

int N, M;
int dis1[310000], disn[310000];

void bfs1(void){
    memset(dis1, 0x3f, sizeof dis1);
    bitset < 310000 > vis; vis.reset();
    queue < int > cur; cur.push(1), vis[1] = true, dis1[1] = 0;
    while(!cur.empty()){
        int p = cur.front(); cur.pop();
        for(auto i = head[p]; i; i = i->nxt)
            if(!vis[SON])
                vis[SON] = true, dis1[SON] = dis1[p] + 1, cur.push(SON);
    }
}
void bfsn(void){
    memset(disn, 0x3f, sizeof disn);
    bitset < 310000 > vis; vis.reset();
    queue < int > cur; cur.push(N), vis[N] = true, disn[N] = 0;
    while(!cur.empty()){
        int p = cur.front(); cur.pop();
        for(auto i = head[p]; i; i = i->nxt)
            if(!vis[SON])
                vis[SON] = true, disn[SON] = disn[p] + 1, cur.push(SON);
    }
}

int main(){
    N = read(), M = read();
    for(int i = 1; i <= M; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t};
        head[t] = new Edge{head[t], s};
    }bfs1(), bfsn();
    for(int i = 1; i <= N; ++i){
        int ans = min({dis1[N], dis1[0] + disn[i], dis1[i] + disn[0]});
        printf("%d%c", ans >= 0x3f3f3f3f ? -1 : ans, i == N ? '\n' : ' ');
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int 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;
}

[ABC257G] Prefix Concatenation

题面

给定仅存在小写英文字母的字符串 $ S, T $。你需要将 $ T $ 分割成 $ k $ 个 $ S $ 的前缀（或着说用 $ S $ 的若干个前缀组成 $ T $），最小化 $ k $，输出最小值。若 $ k $ 不存在输出 -1。

Solution

首先 $ O(n^2) $ 的 DP 显然，我们记 $ S(i, j), T(i, j) $ 为对应字符串 $ [i, j] $ 的子串，令 $ dp(i) $ 表示考虑 $ T(1, i) $ 的最小 $ k $。易得转移：

\[dp(i) = \min_{j \lt i \land S(1, i - j) = T(j + 1, i)}dp(j) + 1 \]

不难发现这个 $ \texttt{1D1D} $ 的 DP 是 $ O(n^2) $ 的无法通过，考虑优化。

首先有一个思路，已知 $ dp(i) $ 单调不降，证明显然，考虑若 $ dp(i) \gt dp(i + 1) $，那么在 $ dp(i + 1) $ 的方案中将最后一部分去掉第 $ i + 1 $ 个一定可以变为 $ dp(i) $ 且 $ k $ 不劣，得证。

然后根据这个思路我们每次转移只需要找到最小的合法 $ j $ 转移即可，可以通过 KMP 中的 next 数组维护。

具体地，不难发现我们这个东西求的可以转化为求 border，具体地，我们将 $ S $ 后追加一个占位符，然后再连接上 $ T $，记 P = S + '#' + T，这样我们对 $ P $ 跑一遍 KMP 的建立 next 数组过程，不难发现对于转移 $ i $ 时需要的 $ j $，即为 $ i - nxt(len_S + 1 + i) $，这里的 $ +1 $ 即为我们添加的占位符 #。

最终 DP 优化为 $ \texttt{1D0D} $，复杂度 $ O(n) $，可以通过。

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

\[dp(i) = \min_{j \gt i \land S(1, j - i) = T(i, j - 1)}dp(j) + 1 \]

此时发现每次可以转移的 $ j $ 是连续的，对应 $ S $ 和 $ T(i, len_T) $ 的 LCP，于是可以通过哈希 + 二分处理每次转移的 LCP 长度，然后线段树优化 DP 即可，最终复杂度 $ O(n \log n) $，劣于正向转移但也可以通过，且思路更直观，仅代码实现略长。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.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;

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;

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

string S, T;
char s[1100000];
int dp[1100000];
int nxt[1100000];

int main(){
    memset(dp, 0x3f, sizeof dp);
    cin >> S >> T;
    sprintf(s + 1, "%s#%s", S.c_str(), T.c_str());
    int lenS = S.length(), lenT = T.length();
    dp[lenS + 1] = 0;
    int cur(0);
    for(int i = 2; i <= lenS + lenT + 1; ++i){
        while(cur && s[cur + 1] != s[i])cur = nxt[cur];
        if(s[cur + 1] == s[i])++cur;
        if(i > lenS + 1)dp[i] = dp[i - cur] + 1;
        nxt[i] = cur;
    }printf("%d\n", dp[lenS + lenT + 1] < 0x3f3f3f3f ? dp[lenS + lenT + 1] : -1);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int 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;
}

[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\cdots\sum_{x_k = 1}^6 \dfrac{1}{6^k}\sum_{i = 1}^kA_{i, x_i} - \sum_{i = 1}^kC_i \]

然后考虑将中间的 $ \sum_{i = 1}^kA_{i, x_i} $ 转化一下，并去掉外面的一堆求和（关于这步，可以考虑钦定一个骰子为 $ A $ 时，剩下 $ k - 1 $ 个骰子可以任选，即 $ 6^{k - 1} $，而钦定两个骰子并钦定顺序之后则为 $ 6^{k - 2} $），即：

\[E = \dfrac{1}{6^k}(\sum_{i = 1}^k\sum_{x_i = 1}^66^{k - 1}A_{i, x_i}^2 + \sum_{i = 1}^k\sum_{j = 1}^k\sum_{x_i = 1}^6\sum_{x_j = 1}^66^{k - 2}A_{i, x_i}A_{j, x_j} \times [i \neq j]) - \sum_{i = 1}^kC_i \]

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

\[E = \dfrac{1}{6}\sum_{i = 1}^k\sum_{x_i = 1}^6A_{i, x_i}^2 + \dfrac{1}{36}\sum_{i = 1}^k\sum_{j = 1}^k\sum_{x_i = 1}^6\sum_{x_j = 1}^6A_{i, x_i}A_{j, x_j} \times [i \neq j] - \sum_{i = 1}^kC_i \]

发现 $ i \neq j $ 难以处理，尝试通过类似容斥的思想，从平方中去除 $ i = j $ 的部分，化简为：

\[E = \dfrac{1}{6}\sum_{i = 1}^k\sum_{x_i = 1}^6A_{i, x_i}^2 + \dfrac{1}{36}(\sum_{i = 1}^k\sum_{x_i = 1}^6A_{i, x_i})^2 - \dfrac{1}{36}\sum_{i = 1}^k(\sum_{x_i = 1}^6A_{i, x_i})^2 - \sum_{i = 1}^kC_i \]

发现式子中出现了大量的 $ \sum_{x_i = 1}^6A_{i, x_i} $，考虑令：

\[X_i = \dfrac{1}{6}\sum_{x_i = 1}^6A_{i, x_i} \]

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

\[\dfrac{1}{36}(\sum_{i = 1}^k\sum_{x_i = 1}^6A_{i, x_i})^2 = (\sum_{i = 1}^kX_i)^2 \]

然后考虑一三项，同样尽量用 $ X_i $ 转化：

\[\begin{aligned} & \dfrac{1}{6}\sum_{i = 1}^k\sum_{x_i = 1}^6A_{i, x_i}^2 - \dfrac{1}{36}\sum_{i = 1}^k(\sum_{x_i = 1}^6A_{i, x_i})^2 - \sum_{i = 1}^kC_i \\ =& \sum_{i = 1}^k(\dfrac{1}{6}\sum_{x_i = 1}^6A_{i, x_i}^2 - X_i^2 - C_i) \end{aligned} \]

此时若我们令：

\[Y_i = \dfrac{1}{6}\sum_{x_i = 1}^6A_{i, x_i}^2 - X_i^2 - C_i \]

则原式转化为：

\[(\sum_{i = 1}^kX_i)^2 + \sum_{i = 1}^kY_i \]

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

\[\max\left\{ \left(\sum X\right)^2 + \sum Y \right\} \]

显然购买方案一共有 $ 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{aligned} kX_i + Y_i \lt kX_j + Y_j \\ k'X_i + Y_i \gt k'X_j + Y_j \end{aligned} \]

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

\[k = \dfrac{Y_j - Y_i}{X_i - X_j} \]

并且此时仅有 $ i, j $ 之间的大小关系会改变。

所以我们 $ O(n^2) $ 枚举并预处理，然后遍历一下 $ k $，第一次排个序，后面的 $ O(1) $ 修改即可，最终复杂度卡在排序上，为 $ O(n^2 \log n^2) $，可以通过。

Tips：实现时为了便于排序，且 $ X, Y $ 远小于 long long 的范围，我们可以考虑按照 $ (36X, 36Y) $ 排序，这样就不可能有分数了，然后最后乘一个 $ 36 $ 的逆元即可。

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

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

#define _USE_MATH_DEFINES
#include <bits/stdc++.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;

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 (998244353ll)

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

ll inv36;
int N, K;
ll C[1100];
ll A[1100][10];
ll X[1100], Y[1100];
struct MyPair{int first, second;};
map < ld, basic_string < MyPair > > mp;
bitset < 1100 > inAns;
ll ansX(0), ansY(0);
ll ans(LONG_LONG_MIN);
int idx[1100];

ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}

int main(){
    inv36 = qpow(36ll, MOD - 2);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i)C[i] = read(), idx[i] = i;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= 6; ++j)
            A[i][j] = read(),
            X[i] += A[i][j], //6Xi
            Y[i] += 6 * A[i][j] * A[i][j]; //36Yi
        Y[i] -= X[i] * X[i] + 36 * C[i];
    }
    for(int i = 1; i <= N; ++i)for(int j = i + 1; j <= N; ++j)
        mp[(ld)(Y[j] - Y[i]) / (ld)(X[i] - X[j])] += MyPair{i, j};
    ld k = mp.begin()->first - 0.1;
    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];});
    for(int i = 1; i <= K; ++i)
        ansX += X[idx[i]], ansY += Y[idx[i]], inAns[idx[i]] = true;
    ans = max(ans, ansX * ansX + ansY);
    for(auto mdf : mp){
        for(auto Pair : mdf.second){
            int l = Pair.first, r = Pair.second;
            if(inAns[l] ^ inAns[r]){
                if(!inAns[l] && inAns[r])swap(l, r);
                inAns[l] = false, inAns[r] = true;
                ansX += -X[l] + X[r], ansY += -Y[l] + Y[r];
            }
        }ans = max(ans, ansX * ansX + ansY);
    }printf("%lld\n", (ans % MOD * inv36 % MOD + MOD) % MOD);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int 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;
}

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

首先对于初始的排序，不难想到若将 $ k $ 升序，那么我们可以认为初始 $ k = -\infty $，则 $ Y $ 对大小关系影响忽略不计，仅比较 $ X $ 即可。

然后对于修改之间的排序把式子推一下换成乘法即可。还有个细节就是我们在修改的时候应仅保留一些满足 $ X $ 偏序关系的，可以大概理解为保证我们变的这个 $ k $ 是单调的，当然这个点我也没有完全弄明白，如果有大佬知道的话欢迎解惑。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.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;

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 (998244353ll)

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

ll inv36;
int N, K;
ll C[1100];
ll A[1100][10];
ll X[1100], Y[1100];
struct Node{
    int l, r;
    friend const bool operator < (const Node &a, const Node &b){
        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]);
    }
};
basic_string < Node > mdfs;
multimap < ld, pair < int, int > > mp;
bitset < 1100 > inAns;
ll ansX(0), ansY(0);
ll ans(LONG_LONG_MIN);
int idx[1100];

ll qpow(ll a, ll b){
    ll ret(1), mul(a);
    while(b){
        if(b & 1)ret = ret * mul % MOD;
        b >>= 1;
        mul = mul * mul % MOD;
    }return ret;
}

int main(){
    // freopen("in.txt", "r", stdin);
    inv36 = qpow(36ll, MOD - 2);
    N = read(), K = read();
    for(int i = 1; i <= N; ++i)C[i] = read(), idx[i] = i;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= 6; ++j)
            A[i][j] = read(),
            X[i] += A[i][j], //6Xi
            Y[i] += 6 * A[i][j] * A[i][j]; //36Yi
        Y[i] -= X[i] * X[i] + 36 * C[i];
    }
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)if(X[i] < X[j])mdfs += Node{i, j};
    sort(mdfs.begin(), mdfs.end());
    sort(idx + 1, idx + N + 1, [](const int &a, const int &b)->bool{return X[a] < X[b];});
    for(int i = 1; i <= K; ++i)
        ansX += X[idx[i]], ansY += Y[idx[i]], inAns[idx[i]] = true;
    ans = max(ans, ansX * ansX + ansY);
    for(auto mdf : mdfs)
        if(inAns[mdf.l] && !inAns[mdf.r])
            inAns[mdf.l] = false, inAns[mdf.r] = true,
            ansX += -X[mdf.l] + X[mdf.r], ansY += -Y[mdf.l] + Y[mdf.r],
            ans = max(ans, ansX * ansX + ansY);
    printf("%lld\n", (ans % MOD * inv36 % MOD + MOD) % MOD);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int 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;
}

UPD

update-2022_12_19 初稿

标签：AtCoder,return,int,题解,sum,ret,void,257,define
From： https://www.cnblogs.com/tsawke/p/17032797.html

相关文章

  • AtCoder Beginner Contest 258 题解
    AtCoderBeginnerContest258Solution目录AtCoderBeginnerContest258Solution更好的阅读体验戳此进入题面链接题面Luogu链接abcd跳了[ABC258E]PackingPotatoes......
  • [ABC250Ex] Trespassing Takahashi 题解
    [ABC250Ex]TrespassingTakahashiSolution目录[ABC250Ex]TrespassingTakahashiSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给......
  • [ABC261E] Many Operations 题解
    [ABC261E]ManyOperationsSolution目录[ABC261E]ManyOperationsSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定正整数$X$......
  • [ABC261D] Flipping and Bonus 题解
    [ABC261D]FlippingandBonusSolution目录[ABC261D]FlippingandBonusSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面掷$n$......
  • [ABC264F] Monochromatic Path 题解
    [ABC264F]MonochromaticPathSolution目录[ABC264F]MonochromaticPathSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定一个$......
  • [ABC263F] Tournament 题解
    [ABC263F]TournamentSolution目录[ABC263F]TournamentSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$，存在$2^n$个......
  • AtCoder Beginner Contest 264 题解
    AtCoderBeginnerContest264Solution目录AtCoderBeginnerContest264Solution更好的阅读体验戳此进入题面链接题面Luogu链接abcd不说了[ABC264E]Blackout2题面......
  • [ABC264Ex] Perfect Binary Tree 题解
    [ABC264Ex]PerfectBinaryTreeSolution目录[ABC264Ex]PerfectBinaryTreeSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面存在一......
  • [ABC265F] Manhattan Cafe 题解
    [ABC265F]ManhattanCafeSolution目录[ABC265F]ManhattanCafeSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面在$n$维空间中......
  • AtCoder Beginner Contest 251 题解
    AtCoderBeginnerContest251Solution目录AtCoderBeginnerContest251Solution更好的阅读体验戳此进入题面链接题面Luogu链接老样子abc太水了就跳了[ABC251D]AtM......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99