A题 y|x 是能够整除的意思（这谁能想的出来）我们来找一下规律(这其实是一道思维题)，在选择数字放到瓶子里时应采用在满足约束条件的情况下尽可能的原则 1，1能被所有数字整除，所以第一个位置我们放最小的1,num[1]=12，2整除1，所以放比num[1]大的数，放最小的2，num[2]=2,其实所有的质数都只能整除1，所以质数放2即可3，质数，num[3]=24，4=22，num[4]>num[2]=2,num[4]=3;5，质数，num[5]=26，6=23 num[6]>num[2]=2,num[6]=3;7，质数，num[7]=28，8=2*4，num[8]>num[...

A 排列 做法，先建模，然后快速幂 m次反转为一次操作，第一次操作后的得到的数组为模式mode。 例如 mode=[3,2,1]，其中mode[1]=3的含义为after[1]=before[3],即变换后数组的第1个位置存放原数组第3个位置的数。 操作之间满足交换率和结合律，可以类比乘法计算，所以两次操作可以看作x*x,k次操作可以看作x^k。在这种类比下，我们可以重定义乘号的意义，然后应用快速幂的思想。 重定义乘法x,y是一个数组，代表操作模式，得到乘法定义如下x*y代表在x的基础上进行y变换，具体做法如下 void cheng(int a[],int b[])//a*=b; { ...

关于java 做图论题的时候，dfs总是爆栈报数组越界问题的解决方案，但是不知道原理，求大佬讲解 查看别人ac的java代码时，发现了一段神仙代码！！ public int solve (int n, int x, Point[] Edge) { try{ Thread t = new Thread(null,()->{ solve0(n, x, Edge); },"", 1 << 30); t.start(); t.join();...

C题 路径积 有个比较笨的方法 以1为根节点dfs整棵树，把每个节点的深度记录下来（deep[]）,并记录每个节点的父节点（pre[]） 然后，对于(x,y),依据deep[]和pre[],可以向上找到x,y第一个公共的父节点root。路径积就是x->root->y，再向上找公共父节点的过程中累乘经过的节点即可。 具体的做法是，取x,y中深度较大的向上查找，类似于x=pre[x]或y=pre[y]这样的形式。 时间复杂度大概在o(n+m*k) ，其中k为树的平均深度（大概是logn QaQ） 上代码： import java.util.*; public class S...

java写的题目总是报“请检查是否存在数组越界等非法访问情况” 然后我试着打开了所有提交，发现所有通过的代码都是c++的。 之前也遇到过这种情况，不知道怎么解决。哪位大佬可以解答一下吗？ 附上代码，检查过了应该不存在数组越界问题。 import java.util.*; class Node{ int next; int val; public Node(int next, int val) { this.next = next; this.val = val; } } public class Solution { ...

动态规划 设f[i,j]代表str[0-i]是否匹配pattern[0-j]状态转移方程为注意条件的等号代表两字符匹配，如'.'与'a'匹配，'a'与'a'匹配。还要注意s[i]对应的实际上时str[i-1],p[j]对应的时partten[j-1] 解释一下： 当p[i]!=*时，为常规情况，显然只有s[i]==p[i]且s[0...i-1]匹配p[0...j-1] (即f[i-1,j-1]==true) 时s[0...i]才与p[0...j]匹配；否则一定不匹配。从而到处第一个递推公式。 当p[i]==*时，若s[i]==p[j-1]（星号的前缀），要想匹配有两种可能： s[i...

输入数据要采用long，但java编写的程序总是提示“请检查是否存在数组越界等非法访问情况” 我又查看了别人通过的代码，发现通过的代码全都是c++的。竟然没有一个用java的。 所以我意识到要么是oj的问题，要么是java语言的问题。 有没有大佬帮忙解决这个问题？

处理输入。 题目中提到一个点可能有多个宝藏，但一个点只能取一个宝藏，显然同一个位置只需保留最大的那个宝藏。 我们开一个500*500的数组作为地图 map。map记录点上最大宝藏的金币数。 动态规划。 构建状态空间 站在一个中间位置向后看，我们发现此时能影响到后续选择的因素只有两个，位置与手中剩余的钥匙数量，所以建立一个三维的dp数组，分别对应横坐标、纵坐标、钥匙剩余数量。 所以我们的状态空间应该这样建： 设f[i][j][t]，代表在（x,y）(1<=x<=i,1<=y<=j)范围内，剩余t把钥匙时所能...

设f[i]表示0跳到i的方法数，显然有 若i是积水，f[i]=0; 若i为偶数，则i是由奇数跳转过来，有f[i] = sum(f[k]) (k为小于i的奇数) 若n为奇数，则n是由偶数跳转过来，有f[i] = sum(f[k]) (k为小于i的偶数)由于每次计算都只涉及奇数和与偶数和，那我们完全没必要在开数组。只需从1到n扫描一遍，记录并更新当前的奇数和sum1、偶数和sum2 即可。 另外值得注意的是，初始时应设置sum1=0、sum2=1。送上AC代码： import java.util.*; public class Solution { /** * 又见台阶 ...

A题 不使用深搜或广搜的方法，通过寻找距离m最近的完全平方数的方法来减小问题规模时间复杂度应该小于o(n);思路：若n>m,n的平方只会变大不会缩小，所以只能进行-1操作，步数为n-m若n<m,则从n到达m的最短路径里，要么从n一路+1到m,要么通过一个中间值k平方跳转到kk,在从kk一路走到m。最短路径为二者最小值。基于此思路，执行如下算法。 当m<n时，只可能进行n--的操作，返回n-m 找到距离m最近的完全平方数kk，时间复杂度o(n^1/2),然后将k作为新的m进行递归,步数为solve(n,k)+1+abs(m-kk),即n-》k的最短路径+平方的一次操作+从k...