hnust_yangyanjun

分类

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

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

排座椅

题意：在一个m*n的教室中，有D对交头接耳的同学，你可以用k行l列隔开，问怎么隔开上课时交头接耳的学生对数最少？思路：我们可以发现列和行之间没有联系，所以行列分别单纯贪心从最多隔断到最少。注意：输出结果时两行答案是升序的。代码： #include <bits/stdc++.h> ty...

2020-08-10

1 715

购物

题意：有一家糖果店，每天可以生产m颗糖果，你在接下来n天会去买糖果，你每天必须吃一颗糖果，你买的糖果可以保存以后吃，你每天买糖果还需要额外花当天买的糖果个数的平方的钱，求这n天你最少花多少钱？思路：dpdp[i][j]表示前i天买j颗糖果的最少花费。sum[i][o]表示第i天买o颗糖果的糖果花费...

dp

2020-08-09

1 690

小A的最短路

题意：有一颗n个节点的树，经过一条边消耗一点体力。有两个特殊点之间有一个观光缆车，他们之间不需要消耗体力。有Q个询问，每个询问求从x点到y点消耗体力值最少为多少？思路：求任意两点树上的距离应该用LCA.由于多了个电缆，所以我们从x到y是有3种方案：①从x直接到y，不坐电缆。②从x到u，再从u坐电缆...

LCA

2020-08-09

1 647

兔子的区间密码

题意：给与一个区间，求在区间选二个数的异或值最大为多少？思路：对于区间[L,R]: ①：L的二进制串长度小于R的二进制串长度，例如L=101（5），R=1110(14)。由于3<4,所以111和1000一定在[L,R]区间，因为1000为二进制长度为4的最小值，111为二进制长度为3的...

数学

2020-08-09

8 776

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