Codeforces Round #528 (Div. 2) 题解记录

Codeforces Round #528 (Div. 2) 题解记录

本次比赛有幸rating暴涨，由1500->1661，rank 140

但是….

Problem A.

分字串奇偶长度讨论，对于奇数长度的起始点则位于最中间，偶数长度则位于中点左侧。

然后向左一位，向右两位，向左三位….. 显而易见（水题）

nowt = len / 2 + len % 2;
printf("%c", str[nowt - 1]);
for (int i = 1; i 

Problem B.

结论题目，由$2 \leq k\le1000 $可以想到枚举 $ x\mod k$ 的值，然后由$\lfloor x/k \rfloor = n / (x\mod k) $可以计算出对应$x=n / (x\mod k) * k + (x\mod k)$。最终，取枚举得出的min_ans （简单的数学题）

scanf("%I64d%I64d",&n,&k);

for(int i=1;i

Problem C.

一道模拟题，可能稍微有点结论。距离最短即找到一点 $O$，令$A,B,C$三点到该点的曼哈顿距离最短。将距离分解为水平水平距离$x$和垂直距离$y$。$O$的坐标则取$A,B,C$ 的第二高的$y_2$ ，第二大的$x_2$ 。得到目标点。然后垂直扩展或水平扩展，模拟。对于$\forall y_x \ne y2$,存在$\sum{i=1}^{i\le3}|y_i-yx| \gt \sum{i=1}^{i\le3}|y_i-y_2|$，同理 可证$x_2$为最优

#include
using namespace std;

struct node{
    int x,y;
} adds[5];
int ans;

bool cmp_1(node a,node b){

    return a.yspx;i--)
        printf("%d %d\n",adds[2].x,i);

    return 0;
}

Problem D.

一道有一点难度的结论（贪心）题目，将所有边权都放到叶子节点所连的边上，然后$s/edges*2$ 就是结果。但是对于$n=2$时，$ans=s$。

证明：若有一边的值$v_i$被置于非叶子结点所连接的边，则对于所有途径该边的点，权重增加了$v_i$，则$ans$ 变大。非最优

#include 
using namespace std;

int n, s, tpx, tpy, cnt;
vector pt[100500];
int sizes[100500];

void dfs(int nowx, int lstx)
{
    if (sizes[nowx] == 1 && nowx != 1){

        cnt++;
        return;
    }
    for (int i = 0; i 

Problem E.

爆搜

代码待续

Problem F.

观察结论+线段树or树状数组。

代码待续