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≤100002 ≤ 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。