xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

gym-102082，2018-2019, ICPC, Asia Yokohama Regional Contest 2018 J Colorful Tree

题意给定一个\(n\)个点的树，每个点有个初始颜色\(c_i\)，有\(m\)次询问，询问有两种： \(U~x_k~y_k\)，将第\(x_k\)个点的颜色改为\(y_k\)。 \(Q~y_k\)，找到一个边数最少的子图，使得这个子图包括所有颜色为\(y_k\)的点，输出这个子图的边...

树链剖分 LCA

2020-06-29

0 653

codeforces 1367 F1，F2 Flying Sort

题意给出一个长度为\(n\)的数组\(a\)，每次操作能将一个数移动到数组的首位或末尾，问最少经过多少次操作能将这个数组变成单调不降的。分析在\(F_1\)中数组\(a\)的每个数字互不相同，我们发现只要找到最长的连续上升子序列（连续指在数组排序后两个数字是相邻的），n减去它的长度\(l...

DP codeforces

2020-06-18

0 537

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 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 388

“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 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