xyq0220

未归档

题解(3)

/ 注册

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

CodeForces 593D Happy Tree Party [LCA+并查集]

题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，再搞...

codeforces LCA 并查集 acm 算法

2019-04-08

0 361

Codeforces 1155 D Beautiful Array DP，最大子段和

题意给出一个长度为\(n\)的数列和数字\(x\),经过最多一次操作将数列的一个子段的每个元素变为\(a[i]*x\),使该数列的最大子段和最大分析将这个数列分为3段考虑，第一段和第三段是未修改的，第二段是修改的子段设\(dp[i][j]\)为第\(i\)个数字为第\(j+1\)段的...

DP codeforces

2019-04-23

0 404

Codeforces 914 C 数位DP+暴力打表+思维

题意给出一个二进制数\(n\)，每次操作可以将一个整数\(x\)简化为\(x\)的二进制表示中\(1\)的个数，如果一个数简化为\(1\)所需的最小次数为\(k\)，将这个数叫做特殊的数，问从\(1\)到\(n\)一共有多少个特殊的数，答案对\(1e9+7\)取模。分析 \(n\)最大...

数位dp 打表 codeforces 思维

2019-04-24

0 769

codeforces 914 D 线段树+数学

题意给出一个长度为\(n\)的数列\(a\)，两种询问，第一种给出三个数\(l,r,x\)，区间\([l,r]\)的\(gcd\)值是否和\(x\)相似，若最多改变区间\([l,r]\)中的一个数使区间\([l,r]\)的\(gcd\)值等于\(x\)，则相似，第二种给出两个数\(i,y\)，将...

线段树数学 codeforces

2019-04-24

0 387

Codeforces 1167 E Range Deleting 双指针+思维

题意给一个数列\(a\),定义\(f(l,r)\)为删除\(a\)中所有满足\(l<=a_i<=r\)的数后的数列,问有多少对\((l,r)\),使\(f(l,r)\)是一个非递减的数列分析若\(f(l,r)\)合法，则\(f(l,r+1),f(l,r+2),\...

codeforces 双指针

2019-05-16

0 474

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

codeforces 1367 F1，F2 Flying Sort

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

DP codeforces

2020-06-18

0 537

CodeForces 593D Happy Tree Party [LCA+并查集]

题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，再搞...

codeforces LCA 并查集 acm 算法

2019-04-08

0 479

Codeforces 1155 D Beautiful Array DP，最大子段和

题意给出一个长度为\(n\)的数列和数字\(x\),经过最多一次操作将数列的一个子段的每个元素变为\(a[i]*x\),使该数列的最大子段和最大分析将这个数列分为3段考虑，第一段和第三段是未修改的，第二段是修改的子段设\(dp[i][j]\)为第\(i\)个数字为第\(j+1\)段的...

DP codeforces

2019-04-23

0 548

Codeforces 914 C 数位DP+暴力打表+思维

题意给出一个二进制数\(n\)，每次操作可以将一个整数\(x\)简化为\(x\)的二进制表示中\(1\)的个数，如果一个数简化为\(1\)所需的最小次数为\(k\)，将这个数叫做特殊的数，问从\(1\)到\(n\)一共有多少个特殊的数，答案对\(1e9+7\)取模。分析 \(n\)最大...

数位dp 打表 codeforces 思维

2019-04-24

0 486