直接采访|第13集

在CodeChef上进行了3个小时的编码循环。不能在IDE中使用自定义测试用例，也不能在运行后编辑代码。

编码问题1 阿曼达是一名小学生，正在学习英语字母表。她的老师设计了一个小游戏来让任务变得有趣。由“m”行和“n”列组成的网格由英文字母填充。她需要通过在任何相邻的网格单元中一次移动一步来搜索该网格中的英语单词。给出了一组字母表和一组英语单词。Amanda可以从网格中的任何位置开始，可以在8个相邻网格单元中的任何一个单元中移动，一次一步。每个网格单元只能使用一次。

输入： 您将获得一个模板，需要在其中实现一个函数，其签名如下所示。

C 
/* return 0 for false, 1 for true. */ 
int findWordInAGrid(char grid[128][128], int m, int n, char word[32]) 

C++ 
bool findWordInAGrid(char grid[128][128], int m, int n, char word[32]) 

Java 
static boolean findWordInAGrid(char[][] grid, int m, int n, String word) 

• 网格[][]表示给定网格中的字符。只有前m行和前n列应视为相关。单词是指出现在网格中的单词。
• 记住，单词可以从网格中的任何位置开始。word包含的字符永远不会超过30个。如果在网格中找到单词，则返回true，否则返回false。

输出 ：如果可以在网格中找到单词，则函数应返回true，否则返回false。让我们考虑下面给出的网格：一个B C D E F G H i和一组要搜索的单词：ABC AbEdHIFEGFH。

上述示例的输出应该是：abc:true abedhi:true efgh:false Constraints 1？m、 n？100

编码问题2：解决这个问题你会得到2分

你得到了一棵有根的树。树不一定是二进制的。该树包含N个节点，标记为1到N。该树以大小为N的数组P[1..N]的形式给出。P[i]表示标记为i的节点的父节点的标签。为清楚起见，您可以假设该树满足以下条件。

• 树的根被标记为1。因此P[1]被设置为0。节点T的父节点总是有一个小于T的标签。因此P[i]
• 要求您执行以下类型的多个操作ADD X Y：将Y添加到节点X的值中。ADD up X Y：将Y添加到节点X的值中。然后，将Y添加到P[X]（即X的父节点）的值中。然后，在P[P[X]]处的值上加上Y（即P[X]的父项）。。依此类推，直到你把Y加到根的值上。
• 执行所有给定操作后，系统会要求您回答以下类型的几个查询：VAL X：打印节点X处的值。VALTREE X：打印以X（包括X）为根的子树中所有节点处的值之和。
• 输入——输入的第一行包含数字T，即测试用例的数量。接下来是T测试用例的描述。每个测试用例的第一行分别包含数字N、M和Q（由单个空格字符分隔）。N表示节点数。M表示必须执行的操作数。Q描述了你必须回答的问题的数量。接下来的N行各包含一个数字，表示数组P[1..N]。当然，第一行的数字总是0。接下来的M行包含各自操作的说明。操作将是“ADD X Y”或“ADD up X Y”（不带引号）。
• 请参考问题陈述和示例I/O说明，以明确操作的含义。操作完成后，接下来的Q行包含查询的描述。查询将是“valx”或“VALTREE X”（不带引号）。请参考问题陈述和示例I/O解释，以明确查询的含义。输出在一行上单独打印每个查询的结果。由于某些查询的答案可能太大，请以100000007为单位打印结果。不要在测试用例之间打印任何空行。限制条件1？T10 1 ? N50000 1 ? M50000 1 ? Q50000 1 ? 十、N 1？Y50000输入文件将小于2MB。

样本输入 2 5 5 3 0 1 1 1 3添加1 10添加2 20添加3 30添加4 40相加5 50 VAL 3 VALTREE 1 7 4 5 0 1 2 2 1 2添加6 76相加1 49添加4 48相加2 59 VALTREE 1 VALTREE 5 VAL 5 VALTREE 2 VAL 2 2

样本输出 80 130 250 291 0 0 107 59解释在第一个示例案例中，在应用程序操作结束时，每个节点上的值如下：1:60 2:20 3:80 4:40 5:50此外，在每个节点上根的子树中所有节点的值之和如下：1:250 2:20 3:130 4:40 5:50

编码问题3：解决此问题得1分

在二叉树中，两个叶节点之间的直径和被定义为从一个叶到另一个叶时唯一路径中所有节点的总和。假设这棵树是一棵完整的二叉树，每个叶节点距离树的根的深度相同。求二叉树中最大直径和的值。请注意，最大直径也可以是单个叶节点（因为单个叶节点也是有效直径，即从叶节点到自身的长度为0的平凡路径）。

输入 ：输入的第一行是数字T，表示测试用例的数量。每个案例的输入由两行组成。第一行由树中的节点数N组成。下一行由数字A[1..n]组成，表示树中每个节点的值。输入中的第一个元素是树的根元素。考虑到下面问题中根元素的索引是1，输入中第i个元素的左子元素是第（2*i）个元素，第i个元素的右子元素是第（2*i+1）个元素。

输出 ：输出由T行组成，表示每个测试用例在二叉树中的最大直径和的值。在解决方案模板中提供解决方案模板，完成其签名为C/C++ INT最大直径和（int节点，int tree（511））java静态int Max MealEthand（int节点，int [tree）的函数。第二个参数是tree，它以数组格式显示，如上面输入部分所述。maxDiameterSum应返回二叉树中最大直径和的值。注意：您可以随意编辑代码。添加/删除标题。添加/删除方法。等等只要您的最终代码解决了上述输入和输出问题。

您可以提交自己的代码，而无需使用模板。不是吗？100N？511节点的值范围在100000到100000之间，N的形式为2k-1，其中k是树的高度。样本输入1 7 2 4 5 8-4 3-6

在这种情况下，获取最大直径和所遵循的示例输出22解释路径是8（叶节点）=>4=>2=>5=>3（叶节点） 如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论