xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共101篇）

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 C 张老师的旅行

题目链接分析设\(dp[l][r][0]\)为走过区间\([l,r]\)的景点且落脚点为\(l\)用的最短时间，\(dp[l][r][1]\)为走过区间\([l,r]\)的景点且落脚点为\(r\)用的最短时间。则有转移: \(dp[l][r][0]=min(dp[l+1][r][...

区间dp DP

2020-05-13

0 389

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 H-时空栈

题目链接分析将时间\(t\)离散化，按\(t\)建线段树，维护每个时间\(t\)的栈的大小\(s[t]\)。在时间\(t\)入栈一个数即为将区间\([t,n]\)加\(1\) 在时间\(t\)出栈即为将区间\([t,n]\)减\(1\) 查询时间\(t\)的栈顶元素，找到...

线段树

2020-05-13

0 477

Codeforces 1349A 1350C Orac and LCM

题意给出一个长度为\(n\)的数组\(a\)，计算\(\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})\)。分析对每个数质因子分解，对每个质因子用数组存下出现的幂次。单独考虑一个质因子\(p\)对答案的贡献，若\(a_i,a_j\)中质因子...

质数思维 codeforces

2020-05-13

0 463

gym-102307 A. Amazon

题意给定\(n\)个点对，每个点对\((x1,y1),(x2,y2)\)确定一条直线，问这\(n\)条直线在二维平面中构成了多少个“十字路口”，若两条直线垂直相交，交点即为一个十字路口，多个重合的交点算做一个十字路口。分析根据直线方程的一般式\(y=kx+b\)，其中\(k=\frac{...

计数分数几何

2020-05-01

0 457

gym-102307 D. Do Not Try This Problem

题意给定一个长度为\(n\)的字符串\(s\)，给定\(q\)个操作，每次操作给定\(i,a,k,c\)，表示将\(s_i,s_{i+a},\dots,s_{i+ka}\)赋值为字符\(c\)，输出经过\(q\)次操作后的字符串\(s\)。分析分类讨论：若\(a>\sqr...

分块并查集

2020-05-01

0 364

AtCoder Beginner Contest 161 E - Yutori

AtCoder Beginner Contest 161 E - Yutori 题意神仙\(LFX\)要在接下来的\(N\)天中工作\(K\)天，当他工作一天之后在接下来的\(C\)天都不能工作，给一个长度为\(N\)的字符串\(S\)，\(S[i]=\text' \mathit x\text...

贪心 AtCoder

2020-04-07

0 463

Codeforces 1270E 构造+数学

题意有\(n\)个二维平面上的点，每两个点之间连一条线段，将这些点划分为两个非空的集合\(A\)，\(B\)，同一个集合内的两点之间线段用黄色标注，不同集合的两点之间线段用蓝色标注，使距离相同的线段颜色相同。分析先将所有点的坐标以其中一个点作为原点转化一下，使其中必定有一个点是\((0,...

构造数学

2019-12-31

0 410

2019牛客暑期多校训练营（第七场）E 线段树+离散化区间

题意每次插入区间\([L_i,R_i]\)之间的数，查询中位数。分析把区间离散化为点，就可以用线段树来支持更新和查询了。我们将区间右端点+1，那么一个区间的长度就是右端点减去左端点，然后我们将所有端点离散化一下用线段树维护就行了。例如区间\([1,2],[2,4]\) 区间右端...

线段树

2019-12-24

0 347

codeforces 1272F dp+记录路径

题意给出两个括号序列 \(S\) 和 \(T\)，让你构造一个最短的合法括号序列使 \(S\) 和 \(T\) 是它的子序列。分析设 \(dp[i][j][k]\) 为这个最短的合法括号序列的前缀包含 \(S\) 的前 \(i\) 个字符，T的前 \(j\) 个字符且左括号的数量大于右括...

DP

2019-12-18

0 325

牛客练习赛55 E-树树形DP

题意你有一颗大小为\(n\)的树，点从\(1\)到\(n\)标号。设\(dis⁡(x,y)\)表示\(x\)到\(y\)的距离。求\(\sum_{i=1}^{n}\sum_{j=1}^{n}dis^2(i,j)\)对\(998244353\)取模的结果。分析设\(d_x\)为点\(x...

树形DP

2019-12-15

0 362