hnust_yangyanjun

题解

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

/ 注册

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

华华和月月种树

题意：一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。操作3：输入格式为3 i 表示输出i节点的权值。 ...

dfs 树状数组

2020-08-21

1 666

地斗主

题意：给你一个4 * n的矩阵，让你用1 * 2的矩阵填满，求有多少种方法？思路：n=1时有1种n=2时有5种n=3时有11种n=4时有36种由官方题解可知dp[i]=dp[i-1]+5d[i-2]+dp[i-3]-dp[i-4].所以我们可以用矩阵快速幂求结果。为了防止产生负数，所以-1可以等价...

矩阵快速幂

2020-08-14

1 1230

双栈排序

题意：给你一个长度为n的序列，你是否能用两个栈用以下操作进行排序？操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列不能输出0，能则输出最小字...

模拟

2020-08-13

0 693

追债之旅

题意：有n个城市，小明再1号城市，它的欠债人在n号城市，城市之间有道路连接，不过需要交路费，而且欠债人每天都会花费一些钱，每天你只能走一条道路从一个城市到另一个城市，求你最少的花费（路费+欠债人花费）为多少？思路：最短路的变形题，多了个欠债人每天的花费。用val[i][j]表示第i天在第j个城市的...

最短路

2020-08-13

1 598

蓝魔法师

题意：给与一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。思路：树形dp：从叶子节点向根转移，dp[i][j]表示以i为根的树删边时i处于的连通块大小为j的方案数。sum...

树状dp

2020-08-12

2 817

矩阵消除游戏

题意：有一个n*m的矩阵，你可以进行k回合的游戏，每一回合将矩阵的一行或者一列的值置零并将分数加上。求你最后最多能得多少分？思路：由于消除行对列有影响，所以不能简单的贪心，但你n和m小于15，所以我可以枚举消除列的状态，然后对每一种合理状态再对行进行贪心操作，然后取最大分数值。代码： #incl...

枚举贪心

2020-08-10

1 867

排座椅

题意：在一个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