曾经不是人

分类

题解(9)

/ 注册

全部文章（共9篇）

B题

B题：简单的前缀和问题唯一的坑是输入量较大，需采用scanf输入。设sum[i]代表从1~i中所有异于前者的雪糕数量。所以区间[x,y]的愉悦值就等于 sum[y]-sum[x]+1加1 是因为吃第一个雪糕时愉悦值也会加1。代码如下： #include <iostream> using ...

2020-11-06

1 448

A题

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

2020-11-06

6 629

排列题解（快速幂的思想）

A 排列做法，先建模，然后快速幂 m次反转为一次操作，第一次操作后的得到的数组为模式mode。例如 mode=[3,2,1]，其中mode[1]=3的含义为after[1]=before[3],即变换后数组的第1个位置存放原数组第3个位置的数。操作之间满足交换率和结合律，可以类比乘法计算，...

2020-09-06

5 467

关于java 做图论题的时候，dfs总是爆栈报数组越界问题的解决方案，但是不知道原理

关于java 做图论题的时候，dfs总是爆栈报数组越界问题的解决方案，但是不知道原理，求大佬讲解查看别人ac的java代码时，发现了一段神仙代码！！ public int solve (int n, int x, Point[] Edge) { try{ T...

2020-08-16

2 859

C题路径积

C题路径积有个比较笨的方法以1为根节点dfs整棵树，把每个节点的深度记录下来（deep[]）,并记录每个节点的父节点（pre[]）然后，对于(x,y),依据deep[]和pre[],可以向上找到x,y第一个公共的父节点root。路径积就是x->root->y，再向上找公共父节...

2020-08-14

1 577

动态规划，滚动数组优化空间复杂度

动态规划设f[i,j]代表str[0-i]是否匹配pattern[0-j]状态转移方程为注意条件的等号代表两字符匹配，如'.'与'a'匹配，'a'与'a'匹配。还要注意s[i]对应的实际上时str[i-1],p[j]对应的时partten[j-1] 解释一下：当p[i]!=*时，为常规情...

2020-07-28

2 985

流浪者与宝藏

处理输入。题目中提到一个点可能有多个宝藏，但一个点只能取一个宝藏，显然同一个位置只需保留最大的那个宝藏。我们开一个500*500的数组作为地图 map。map记录点上最大宝藏的金币数。动态规划。构建状态空间站在一个中间位置向后看，我们发现此时能影响到后...

2020-07-12

2 623

又见台阶——交替记录奇数前缀和与偶数前缀和

设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的偶数)由于每次计算都只涉及奇数和与偶数和，那我们完全没...

2020-07-12

0 740

魔法数字——寻找距离m最近的完全平方数

A题不使用深搜或广搜的方法，通过寻找距离m最近的完全平方数的方法来减小问题规模时间复杂度应该小于o(n);思路：若n>m,n的平方只会变大不会缩小，所以只能进行-1操作，步数为n-m若n<m,则从n到达m的最短路径里，要么从n一路+1到m,要么通过一个中间值k平方跳转到kk,在从kk一...

2020-07-09

8 1728