xyq0220

未归档

题解(3)

/ 注册

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

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

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

数位dp 打表 codeforces 思维

2019-04-24

0 769

HDU 6191 2017ACM/ICPC广西邀请赛 J Query on A Tree 可持久化01字典树+dfs序

题意给一颗\(n\)个节点的带点权的树，以\(1\)为根节点，\(q\)次询问，每次询问给出2个数\(u\),\(x\),求\(u\)的子树中的点上的值与\(x\)异或的值最大为多少分析先dfs一遍，得到dfs序，就可以将这个问题转化为求区间\([l,r]\)中的值与\(x\)异或值最大...

可持久化01字典树 dfs序

2019-04-23

0 422

HDU 6191 2017ACM/ICPC广西邀请赛 J Query on A Tree 可持久化01字典树+dfs序

题意给一颗\(n\)个节点的带点权的树，以\(1\)为根节点，\(q\)次询问，每次询问给出2个数\(u\),\(x\),求\(u\)的子树中的点上的值与\(x\)异或的值最大为多少分析先dfs一遍，得到dfs序，就可以将这个问题转化为求区间\([l,r]\)中的值与\(x\)异或值最大...

可持久化01字典树 dfs序

2019-04-23

0 340

51nod 1295 XOR key 可持久化01字典树

题意给出一个长度为\(n\)的正整数数组\(a\),再给出\(q\)个询问，每次询问给出3个数,\(L,R,X(L<=R)\).求\(a[L]\)至\(a[R]\)这\(R-L+1\)个数中，与\(x\)进行异或运算(Xor)，得到的最大值为多少。分析前置知识：通过01字典树可...

51nod 可持久化01字典树

2019-04-23

0 382

51nod 1295 XOR key 可持久化01字典树

题意给出一个长度为\(n\)的正整数数组\(a\),再给出\(q\)个询问，每次询问给出3个数,\(L,R,X(L<=R)\).求\(a[L]\)至\(a[R]\)这\(R-L+1\)个数中，与\(x\)进行异或运算(Xor)，得到的最大值为多少。分析前置知识：通过01字典树可...

51nod 可持久化01字典树

2019-04-23

0 400

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 1155 D Beautiful Array DP，最大子段和

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

DP codeforces

2019-04-23

0 404

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