java - 竞赛编程算法思维提升

Question

我是这个社区的新手，已经获得了很多 -1 票，所以我正在尽最大努力改进我提出问题的方式。

最近我在 CodeChef 尝试了这个问题。这是问题定义。

这可能是本问题集中最简单的任务。为了帮助您理解任务，让我们定义两个关键函数:f(n,k)，(k <= n)它给出了我们可以从一组 n 个不同的对象中抽取 k 个对象样本的方法的数量，其中绘图顺序并不重要，我们不允许重复。 G(x1, x2, x3, ... , xn) 是能整除 {x1, x2, x3, ... , xn} 的最大整数。 给定一个整数 N，你的任务是计算 Y 的值，其中 Y = G( f(2*N,1), f(2*N,3), f(2*N,5), ..., f(2*N,2*N-1)).

输入

输入的第一行包含一个整数 T，表示测试用例的数量。 T 测试用例的描述如下。每个测试用例的第一行也是唯一的一行包含一个整数，表示问题陈述中描述的给定 N。

输出

对于每个测试用例，输出包含 Y 值的一行。 约束条件

1≤T≤10000 2 ≤ N ≤ 10¹¹

例子

输入:

3

6

5

4

输出:

4

2

8

现在我用 Java 编写了一段代码，它运行良好，但 CodeChef 在线判断给出了 TLE 错误，所以我尝试了几种不同的方法但没有成功。所以我检查了其他人发布的一些解决方案，我不知道他们的算法做了什么，但神奇的是它总是得出正确的答案 所以我关心的是我应该引用哪些书籍来改进这些算法的编写方式。 附言是的，我读过 Corman

一些其他的解决方案做了一些正常的加减法和 Bang!!他们的回答是正确的 这是一个这样的解决方案

   import java.util.*;
    class Main 
 {
     public static void main(String[] args) {

//public static void main(String[] args) {
    Scanner scan=new Scanner(System.in);
    long T=scan.nextLong();
    long fin;
    while(T>0){
        T--;
        long N=scan.nextLong();
        fin=-(-N^N);
        System.out.println(fin);
}
}
 }

我也展示了我的尝试:-

           import java.io.BufferedReader;
         import java.io.IOException;
         import java.io.InputStreamReader;
          import java.util.ArrayList;


       class Code1 
       {
static ArrayList<Long> combValues=new ArrayList<Long>();
static ArrayList<Long> input=new ArrayList<Long>();
static ArrayList<Long> output=new ArrayList<Long>();
public static void main(String args[])throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    //System.out.println("Enter the values of 'T' ");
    //System.out.println("Input:");
    int T=Integer.parseInt(br.readLine());
    //System.out.println("Enter the value of 'N' ");
    for(int i=1;i<=T;i++)
    {
        input.add(Long.parseLong(br.readLine()));
    }
    for(int i=0;i<T;i++)
    {
        output.add(computeFX(input.get(i)));
    }
    //System.out.println("Output:");
    for(long i:output)
    {
        System.out.println(i);
    }
}
public static long computeFX(long N)
{
    combValues=new ArrayList<Long>();
    for(int i=1;i<=2*N-1;i+=2)
    {
        combValues.add( factorial(2*N)/(factorial(2*N-i)*factorial(i)));
    }
    return computeGX();
}
public static long computeGX()
{
    boolean flag=false;
    long tempY=0;
    long limit=combValues.get(0);
    outer:for(int i=new Long(limit).intValue();i>=1;i--)
    {
        inner:for(int j=0;j<(combValues.size()/2)+1;j++)
        {
            if(combValues.get(j)%i!=0)
            {   
                flag=false;
                break inner;
            }
            else
            {
                flag=true;
            }
        }
        if(flag)
        {
            tempY=i;
            break outer;
        }
    }
    return tempY;
}
public static long factorial(long n)
{
    long fact=1L;
    for(int i=1;i<=n;i++)
    {
        fact*=i;
    }
    return fact;
}

   }

好吧，这个问题可能是主观的，但我真的很想得到一些关于从哪里开始的建议。

Answer 1

当您尝试在一张纸上解决一个简单的解决方案时，您会发现给定解决方案的神奇之处。

尝试将 6 作为输入。你想找到 G(f(12,1), f(12,3), f(12,5), ..., f(12,11))。计算fs，你会得到:12, 220, 792, ... 然后将它们转换成二进制。

结果应该除以所有这些值，因此它不能大于最小值(在本例中为 12)。所以在二进制表示中，只看最右边的四个位(因为 12 只有 4 位)。在这个例子中所有大于 12 的值都将“1000”作为二进制表示中最右边的四个位。

所以基本上你需要找到 12 和 8 的 GCD(二进制为“1000”)!哒哒!现在你有一个更简单的问题，问题的标题是(最简单的问题)。正如 Code Chef 上的解决方案所示，其余的可以通过多种方式完成。

除了Introduction to Algorithms之类的书之外，关于如何提高算法技能的问题，你需要解决很多这样的问题。一个好的起点是 Project Euler .另一本能让你掌握很多算法知识的书是一本叫:The Algorithm Design Manual by Steven Skiena。