本文最后更新于 1664 天前,其中的信息可能已经有所发展或是发生改变。
本次比赛有幸rating暴涨,由1500->1661,rank 140
但是….
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树状数组。
代码待续