xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

AtCoder ExaWizards 2019 D Modulo Operations

题意给出一个长度为\(n\)的数列和数字\(X\)，对于数列的每一种排列，其权值\(X\)依次对排列中的数取模，求出\(n!\)种情况最后剩下的数的权值和分析如果大的数字排在小的数字后面，那么大的数字对答案无影响。可以将数列从大到小排序，然后考虑\(dp\)每个数字经过\(n\)次操...

动态规划 AtCoder

2019-04-18

0 429

AtCoder ExaWizards 2019 D Modulo Operations

题意给出一个长度为\(n\)的数列和数字\(X\)，对于数列的每一种排列，其权值\(X\)依次对排列中的数取模，求出\(n!\)种情况最后剩下的数的权值和分析如果大的数字排在小的数字后面，那么大的数字对答案无影响。可以将数列从大到小排序，然后考虑\(dp\)每个数字经过\(n\)次操...

动态规划 AtCoder

2019-04-18

0 452

BZOJ 2818 GCD 素数筛+欧拉函数+前缀和

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2818 题意：给定整数N，求1<=x,y<=n且Gcd(x,y)为素数的数对(x,y)有多少对思路：先筛出n以内所有的素数顺便筛出欧拉函数，\(gcd(x,y)=k\)等价...

素数筛欧拉函数前缀和 BZOJ

2019-04-17

0 526

BZOJ 2818 GCD 素数筛+欧拉函数+前缀和

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2818 题意：给定整数N，求1<=x,y<=n且Gcd(x,y)为素数的数对(x,y)有多少对思路：先筛出n以内所有的素数顺便筛出欧拉函数，\(gcd(x,y)=k\)等价...

素数筛欧拉函数前缀和 BZOJ

2019-04-17

0 406

codeforces 1053D 树形DP

题意：给一颗树，1为根节点，有两种节点，min或者max，min节点的值是它的子节点的值中最小的，max节点的值是它的子节点的值中最大的，若共有k个叶子，叶子的值依次为1~k。问给每个叶子的值赋为几使根节点的值最大。思路：设\(dp[x]\)为节点x为根的子树中x的最大值,\(sz[x]\)...

2019-04-15

0 367

codeforces 1053D 树形DP

题意：给一颗树，1为根节点，有两种节点，min或者max，min节点的值是它的子节点的值中最小的，max节点的值是它的子节点的值中最大的，若共有k个叶子，叶子的值依次为1~k。问给每个叶子的值赋为几使根节点的值最大。思路：设\(dp[x]\)为节点x为根的子树中x的最大值,\(sz[x]\)...

2019-04-15

0 472

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 593D Happy Tree Party [LCA+并查集]

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

codeforces LCA 并查集 acm 算法

2019-04-08

0 366

欧拉降幂

指数爆炸的时候就要降幂就是求a^b mod c 可以转化为 a^(b mod phi©+phi©) mod c phi 为欧拉函数欧拉函数phi(n)的求法： 1 ll phi(ll n) 2 { 3 ll i,rea=n; 4 for(i=2;i...

2019-02-19

0 371

欧拉降幂

指数爆炸的时候就要降幂就是求a^b mod c 可以转化为 a^(b mod phi©+phi©) mod c phi 为欧拉函数欧拉函数phi(n)的求法： 1 ll phi(ll n) 2 { 3 ll i,rea=n; 4 for(i=2;i...

2019-02-19

0 332