题意：给你一个长度为n的数组，每次可以进行一种操作把第i个数和第i+1个数替换为第i个数或者第i+1个数的gcd，问最少多少步能够使得序列全部变成1. 思路：这道题的只要数组里面有一个1 ，操作就变得简单了。如果只有一个1那么只要再执行n - 1步操作就可以全变成1，i个1就执行n-i步操作，就可以了，如果给的初始数组没有1那么我们就化出一个1来再加上n - 1，考虑每一段区间i ~ j(i < j)上的情况：记g(i,j)=gcd{a[i]|i=i,...,j}，则有以下递推关系式：g( i , j + 1 ) = gcd( g ( i , j ) , a [ j + 1])。若存在...

题意：给你一个长度为n的数组，每次可以进行一种操作把第i个数和第i+1个数替换为第i个数或者第i+1个数的gcd，问最少多少步能够使得序列全部变成1. 思路：这道题的只要数组里面有一个1 ，操作就变得简单了。如果只有一个1那么只要再执行n - 1步操作就可以全变成1，i个1就执行n-i步操作，就可以了，如果给的初始数组没有1那么我们就化出一个1来再加上n - 1，考虑每一段区间i ~ j(i < j)上的情况：记g(i,j)=gcd{a[i]|i=i,...,j}，则有以下递推关系式：g( i , j + 1 ) = gcd( g ( i , j ) , a [ j + 1])。若存在...

  题意：有n个人，每个人都有长度不一样的爪子，所有人同时杀人，且只能杀在你前面的人（也就是数组小标比你小的人） 爪子长度的大小决定你可以杀在你前面的人数，问最后还剩多少人？ 思路：这道题可以从最后面开始进行遍历，每次声明一个变量len把当前爪子当前所能够到的最前面的位置存进去，与前一个所能够到的位置(j - a[j])进行比较最小值，变量len就更新，循环不断判断当前位置是否大于len，循环一次就相当于杀一个人，最后再吧总人数减去杀掉的人数，就可以得到活下来的人数。 AC代码： #include<stdio.h> #define min(a, b) a<b?a:...

  题意：有n个人，每个人都有长度不一样的爪子，所有人同时杀人，且只能杀在你前面的人（也就是数组小标比你小的人） 爪子长度的大小决定你可以杀在你前面的人数，问最后还剩多少人？ 思路：这道题可以从最后面开始进行遍历，每次声明一个变量len把当前爪子当前所能够到的最前面的位置存进去，与前一个所能够到的位置(j - a[j])进行比较最小值，变量len就更新，循环不断判断当前位置是否大于len，循环一次就相当于杀一个人，最后再吧总人数减去杀掉的人数，就可以得到活下来的人数。 AC代码： #include<stdio.h> #define min(a, b) a<b?a:...