服务好的网站制作建设,合优人才网合川,网站设计行业背景,品牌网站设计工作室T1 给出树的一度点和三度点的数量#xff0c;构造树的形态#xff0c;节点数不超过 2000 2000 2000。我考虑先构造出三度点#xff0c;发现这一度点至少是三度点2#xff0c;打完后测样例不对#xff0c;发现加一度点时要特判是否为三度点#xff0c;花 5min 打完#…T1 给出树的一度点和三度点的数量构造树的形态节点数不超过 2000 2000 2000。我考虑先构造出三度点发现这一度点至少是三度点2打完后测样例不对发现加一度点时要特判是否为三度点花 5min 打完不放心又手写 spj。用时 40min
T2 一个图用 1 1 1 走到 n n n 代价为 ∑ i 1 t t w t \sum\limits_{i1}^ttw_t i1∑ttwt w t w_t wt 是第 t t t 条经过的点求最小代价 n , m ≤ 3 × 1 0 5 n,m\le3\times10^5 n,m≤3×105。想了一会代价很难维护想到了二分答案然后求出每条边经过的最大时间这就是一个最短路问题由于边权为 1 1 1bfs 搞定。用时 20min
T3 一个图可以删若干条边求使奇点最多的字典序最小的删边方案。 n ≤ 6 × 1 0 5 n\le6\times10^5 n≤6×105。一开始我想贪心地删偶偶边但是手模样例假了看了部分分20pts 状压40pts 图是树还有关于 n n n 的奇偶性的当时想做一个树型 dp 骗分但发现没办法求方案也始终没想出题目跟 n n n 的奇偶性有什么关系。想了 1h 无果就赶紧打 20pts 暴力跑路了。看完题解发现是要从生成树方面考虑后面题解还用线段树维护一个标记没看懂后面看了其他人代码学习了并查集做法。
T4 有 n n n 个矩形每次询问给出一个矩形这个矩形与给定的 n n n 个矩形相交的面积之并的面积不会维护矩形面积 n ≤ 1 0 5 n\le10^5 n≤105。好像想到用扫描线但是不会。暴力只有 5pts 不如不打浪费时间就返回去看 T3 了。题解还要用猫树不会。
DYOJ 有同步赛担心打了掉 rating 就没交。结果赛后发现 220 能拿下rk1……
期望得分100100200220
实际得分100100200220
总结感觉T1T2水后面很难。没挂分YES。注意细节可以把重要变量和分类讨论先在纸上简要写下来。对于生成树和并查集不够熟练看 dalao 代码学习代码实现能力。信息难维护时二分答案还是多考虑一下。构造题先从关键的重要的无可替代的条件或要求入手。数据结构是弱项抽时间学一下扫描线和猫树。
