最近由于工作变动开始学习Shader。虽然本科学过计算机图形学和数字图像处理，但是由于学完后基本没有实践，所以也忘得差不多了，只好从基础开始一点点捡起来。这篇笔记主要记录在阅读人民邮电出版社出版的冯乐乐的《Unity Shader入门精要》时遇到的一些问题以及重点难点，方便以后复习和查缺补漏。至于Cg、HLSL、GLSL，它们的关系就跟C、Java、Python类似，只是Shader编程的不同语言，且差异并不大，具体问题在实践时解决即可。 第二章 渲染流水线 本章中主要需要掌握渲染流水线，渲染管线，GPU流水线这三个概念。渲染流水线包含三个阶段，应用阶段->几何截断->光栅化阶段。...

从题目中给出的n个结点n-1条边可知输入的是一棵树，可知是树形DP。简历二维dp数组，dp[i][0]表示在第i个结点住宿时能旅游的最长天数，dp[i][1]表示不在第i个结点住宿时能旅游的最长天数。第二维只有0和1两个取值，表示是否在第i个结点住下。在计算dp数组时，采用深度优先遍历。为此，使用邻接表存储树结构。转移函数也比较好推，在i住下时，则dp[i][1]等于不在所有与i邻接的结点住下的最长天数之和。不在i住下时，对每个与i邻接的结点，要对在该结点住下的最长天数以及不在该结点住下的最长天数取最大值。这里在递归进行深度优先遍历时，要多开一个参数，来记录是从哪一个结点转入这次递归的，以避免...

开始时考虑的是暴力解法。构建树的过程就不说了。这里有一点需要注意，题目中的树并非二叉树，只是一个无环连通图，所以树节点中只能设定保存父节点的指针。在每次统计节点x的子节点中红色节点的个数时，使用一个辅助队列，开始时将x结点入队。进入循环后，查看队头结点是否为红色，然后遍历整棵树的所有结点，当遇到父节点指向队头结点的结点时，将其入队，重复以上过程，直到队空。这种遍历思想是层序遍历的遍历思想，既然无法通过子节点来深度优先遍历，那么就用层序遍历的方法实现遍历统计。这样做确实没有用到动态规划的思想，寻找红色结点的时间复杂度为O(q*n^2)，在第4个用例(共6个)处超时。看来要AC必须考虑使用动态规划...

区间DP问题。与涂色问题大同小异，但如果想不明白就会觉得这两者有很大区别。用一个四维数组dp[l1][r1][l2][r2]表示从第一个字符串中取l1到r1，从第二个字符串中取l2到r2是否能组成回文字符串，若不能则为0，能则为1。状态转移方程分4种情况，因为字符串Ａ、Ｂ有四种情况可以组成会问字符串。第一种是A在左B在右，直接拼接，若其能组成回文字符串，则有A[l1]==B[r2]，此时有状态转移方程dp[l1][r1][l2][r2]|=dp[l1+1][r1][l2][r2-1]；第二种是B在左，A在右，直接拼接，则有A[r1]==B[l2]，此时有状态转移方程dp[l1][r1][l2]...

区间dp。我也对这类题型比较陌生，只能写下自己浅薄的理解，欢迎大佬指教。开始时对这道题没什么头绪，查阅了一些资料后写下了这段程序。不敢说已经完全理解，只记录下我写代码时的思路。这里dp数组记录的是将第i个位置到第j个位置涂色的最少次数。初始化dp时，由于是求最小值，所以先将数组中所有元素初始化为一个极大正整数，这里用的是0x3f3f3f3f，可以替换成别的整数，够大就可以。然后将对角线上的元素，即所有的dp[i][i]初始化为1。这里也好理解，因为单独涂一个方格，自然是不多不少涂一次。dp初始化完成后，就要开始循环计算了，这里先说一下循环框架。最外层循环，控制的是待涂***间长度。由于要从小区...

这道题的思路与背包问题有些许相似。转移方程是df[i][(j+arr[i])%k]=max(df[i-1][j]+arr[i],df[i-1][(j+arr[i])%k])。其中df[i][j]表示添加第i个数时对k取模得j的最大和。在实现时考虑是否能像背包问题一样，仅使用一维数组，通过遍历的顺序来控制其添加数的顺序，以避免重复累加。事实证明不行，因为这个问题中，j==0时对应的位置是随机的，不一定在前或在后，在j++过程中也不一定就对应着下一个位置，可能去到前面。所以无法通过控制正序或逆序遍历的方法来避免重复，只能使用二维数组来完整保存上一状态。另一个需要注意的问题与背包问题中求刚好装满时的...

这道题在弄懂01背包问题后基本没有难度。基本思路与01背包问题相同。唯一不同的是，题目中的物品可以重复加入，而01背包问题中要避免物品重复加入。在01背包问题中，避免重复添加一件物品是通过逆序遍历来实现的，而在本题中要包含重复添加一件物品的情况，只需将逆袭改为正序遍历即可。 附01背包问题题解 #include <iostream> #include <vector> using namespace std; int main(){ int n, v; cin >> n >> v; vector<int> ...

经典01背包问题。解题思路比较常规。用辅助数组res存储容积为i时能装入物品的最大价值。对物品进行遍历，每次遍历中都逆序更新res，转移方程为res[j]=max(res[j-v[i]]+p[i],res[j])。最终res[v]即为要求的容积为v时所能装入物品的最大价值。这道题设置了两问，解题上有细微差别。需要分开用两个辅助数组来存储结果。第一问求能装入物品的最大价值，没有要求刚好装满，所以直接把数组res的元素全部初始化为0即可。而第二问要求刚好装满时的最大价值。需要将res第一个元素初始化为0，代表容积为0的背包装满时最大价值为0；将其余元素全部初始化为一个很大的负数，要保证就算将所有物...

使用一个辅助数组sum记录从起点走到当前位置的最大值，即sum.at(i).at(j)表示从(0,0)走到(i,j)的所有路径中的最大值。最后返回sum.at(n-1).at(m-1)即为走完整个矩阵的最大值。由于遍历了存储矩阵的二维数组，时间复杂度为O(nm)。由于使用了sum辅助数组，空间复杂度为O(nm)。 #include <iostream> #include <vector> using namespace std; int main(){ int n, m; cin >> n >> m; vector&l...

和#【模板】差分#的思路完全一致。使用一个二位数组sum来记录每一位改变的信息，然后通过求前缀和的形式求出每一位一一对应的改变值。最后将sum中的每一个元素与原始数组arr中对应的元素加起来即可得到结果数组。唯一有区别的地方在记录改变信息以及求前缀和上的操作略微复杂化。这里记录的方式与求前缀和的方式是一一对应的。若记录时以列为起点，则求前缀和时也要以上一列作为迭代对象；若记录时以行为起点，则求前缀和时也要以上一行为迭代对象。这里采用以列为起点的方式，即处理输入的(x1,y1), (x2,y2), k时，将(x1, y1), (x1+1,y1), ..., (x2,y1)，即待改变矩阵的第一列，...

因为本题直接解决实现起来不难，故一开始选择直接暴力解法。每次接受l，r，k后，直接遍历数组中的第l个到第r个元素，将其加k。这种做法时间复杂度O(n^2)，空间复杂度O(1)。会在第七个用例(共8个)处超时。由于用例输入数据量过大，无法验证是由于循环逻辑出错导致超时，还是由于算法时间复杂度过高导致超时。这里暂且认为是由于时间复杂度过高导致超时。转而寻找时间复杂度更低的做法。 #include <iostream> #include <vector> using namespace std; int main(){ int n, m; cin >...

思路是用一个二维数组sum来储存(0, 0)到该点所形成的子矩阵中所有数的和。即sum.at(i).at(j)储存着以(0,0)(i,j)为反对角线的矩阵的所有元素的和。当要计算(x1, y1)与(x2, y2)所形成的矩阵中所有元素的和时，只需要用(0, 0)(x2, y2)这个大的矩形，减去(0, 0)(x1 - 1, y2)和(0, 0)(x2, y1 - 1)这两个矩形。当x1或y1为0时需分类讨论。这种做法的时间复杂度主要体现在建立sum数组上，建立sum时用到了三重循环，时间复杂度在O(nm)之上。空间复杂度为O(nm)。时间复杂度过高这个问题在提交时暴露无遗。此时我开始意识到我的...

开始时设想使用前缀和的方法，建立一个sum数组，其中sum.at(i)保存的是前i项中abb的个数。按顺序遍历字符串，使用一个二重循环，对每一个字符都统计其在之前出现的次数以及其他字符出现的位置，按照C(2,n)的组合数计算规则可以发现C(2,1), C(2,2), ..., C(2,n)组成的数列满足差后等差，且差后的等差数列公差为1。按照这一性质，即可得到下面的处理方法。对每一个字符c，从该字符的前一个字符向前遍历，每遇到一个与c相同的字符，count++，每遇到一个与c不同的字符，使sum.at(i)+=count。这种做法时间复杂度为O(n^2)，比较高。所以在提交后第8个用例处超时，...

经典前缀和问题。具体做法是在接受输入数字创建数组时，同时创建一个前缀和数组sum，sum.at(i)维护的是数组前i+1项的和(0为首项)。在处理每一组l与r时，直接让前r项的和减去前l项的和在加上第l项的和即可。时间复杂度O(n)，空间复杂度O(n)。 #include <iostream> #include <vector> using namespace std; int main(){ int n, q; cin >> n >> q; vector<int> arr(n); vector&l...