hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共119篇）

Xor Path

题意：有一棵n个节点的树，树的每一个节点有一个权值，定义path(i,j)表示 i 到 j 的最短路径上，所有点的点权异或和。求所有path(i,j)的异或和。思路：我们可以统计一个点被计算了多少次来求解，一个节点x，以x为终点的path有（n-1）条，然后包括它的路径与它的子树有关，一棵子树的节...

2020-08-08

1 609

Max Power

题意：有一颗n层的技能树，第i层有n-i+1个技能,学习第i层第j个技能则必须先学习第i-1层第i和i+1个技能，第一层的技能可以直接学。你能学m个技能，求你最大的战力加成为多少？思路：dp我们发现如果第i层第j个技能学习了，则以它为底的倒三角的技能一定学习了。设dp[i][j][r]为第n列到第...

dp

2020-08-07

1 652

Interesting Computer Game

题意：有n轮游戏，每轮你可以从二个数中选择其中一个数，求你选择数的种类最多为多少？思路：先离散化数据，然后我们将每一轮游戏当成一条边，如果成环了，则该环所以端点都能选择，且与环连通的点也能全部选择，你画个图就很容易理解了，由环往外扩散。如果连通块无环，则有一个端点无法选择。所以我们用并查集来处理数...

并查集

2020-08-03

1 587

[CQOI2007]涂色PAINT

题意：让你对n个长度的木板染色，每次可以对连续的任意长度染同一种颜色，初始没有颜色，求最少需要染多少次能染成目标颜色？思路：区间dpdp[i][j]表示从i到j的区间染成目标颜色的最少染色次数。当第i个格子和第j个格子的颜色相同时，第i个格子可以被dp[i+1][j]顺便染成、第j个格子可以被dp...

dp

2020-08-02

1 811

乌龟棋

题意：有一个长度为n的一维数组，每个元素有一个分值，你一开始在第一个元素的位置（1），你有m张卡片，有1，2，3，4四种类型，使用卡片可以让你移动等价于卡片数值的格数，然后将移动后到达位置的分值加上，求最大分值为多少？（使用完所以卡片后一定到位置n）思路：像这种类型的题九成用dp，做dp题你需要考...

dp

2020-08-02

1 850

wpy的请求

题意：给你一个n个结点m条边的有负权边无负环的有向图，为每条边赋一个非负新值，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不变。思路：参考了多篇题解，我们造一个超级源点与每一个点相连，且边权为0，从超级源点开始跑spfa;我们这m条边的新值为d[u]-d[v]+cost(u,v);...

spfa

2020-07-30

0 604

Rinne Loves Data Structure

题意：告诉你有n个整数，按顺序构建一棵二叉查找树，既树中每一个节点满足左儿子小于节点，右儿子大于节点。求每次插入一个整数后树中每一个节点深度之和？思路：学过二叉查找树的都知道插入操作最坏情况为O(n^2)（链状时），所以模拟肯定过不了。仔细观察二叉查找树，再分析下插入时进行的操作，我们可以发现对于...

二叉查找树

2020-07-28

0 645

Binary Vector

题意：随机n个n维01向量，询问这个n个向量线性无关的概率？思路：观察样例，我们发现f(i)初始为1，分子开始乘1，分母乘2，然后每次乘前一次乘的2倍+1，分母每次乘前一次的二倍。由于n<=2*10^7,所以我们打表。我们先打出f(i)的表，f(1)=1/2的逆元ans[1]=5000000...

数学

2020-07-27

3 553

Easy Construction

题意：给你两个整数n和k。求你用 1~ n构造一个存在 1~n 长度的连续子列都能加起来之和取模n等于k，如果不能，输出-1. 思路：我们可以知道长度为n时的子列只有一个，和为n * (n+1)/2 ,所以当(n * (n+1)/2)%m=k时才有解。当n为偶数时，1+（n-1）=n、2+（n-2)...

2020-07-27

3 516

Combination of Physics and Maths

题意：给你一个n*m的矩阵，求矩阵的子矩阵最大压强为多少，压力F为子矩阵所有元素之和，受力面积为子矩阵最后一行的元素之和？思路：由于我们只要求最大压力，所以我们根据公式求每一列的子列的最大压力即可。代码： #include <iostream> #include <cstdio...

数学

2020-07-27

1 582