Codeforces Round #528 (Div. 2) 题解记录
本文最后更新于 72 天前,其中的信息可能已经有所发展或是发生改变。


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

但是….5c23aef931cea

Problem A.

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

然后向左一位,向右两位,向左三位….. 显而易见(水题)

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

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<k;i++)
{
    if(n%i!=0)
        continue;
    ans=min(ans,n/i*k+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<bits/stdc++.h>
using namespace std;

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

bool cmp_1(node a,node b){

    return a.y<b.y;
}

bool cmp_2(node a,node b){

    return a.x<b.x;
}

int main()
{
    for(int i=0;i<3;i++)
        scanf("%d%d",&adds[i].x,&adds[i].y);

    sort(adds,adds+3,cmp_1);
    ans+=adds[2].y-adds[0].y+1;
    int spx=adds[1].y;
    sort(adds,adds+3,cmp_2);
    ans+=adds[2].x-adds[0].x;
    printf("%d\n",ans);

    for(int i=adds[0].x;i<=adds[2].x;i++)
        printf("%d %d\n",i,spx);

    sort(adds,adds+3,cmp_1);
    for(int i=adds[0].y;i<spx;i++)
        printf("%d %d\n",adds[0].x,i);
    for(int i=adds[2].y;i>spx;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 <bits/stdc++.h>
using namespace std;

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

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

        cnt++;
        return;
    }
    for (int i = 0; i < sizes[nowx]; i++)
        if (pt[nowx][i] != lstx)
            dfs(pt[nowx][i], nowx);
    return;
}

int main()
{
    scanf("%d%d", &n, &s);
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &tpx, &tpy);
        sizes[tpx]++;
        sizes[tpy]++;
        pt[tpx].push_back(tpy);
        pt[tpy].push_back(tpx);
    }
    dfs(1, 0);
    if (n==2){

        printf("%lf", (double)(s));
        return 0;
    }
    else if (sizes[1] == 1)
        cnt++;
    printf("%lf", double(s) / cnt * 2.0);
    return 0;
}

Problem E.

爆搜

代码待续

Problem F.

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

代码待续

暂无评论

发送评论 编辑评论


				
上一篇
下一篇