Codeforces Round #678 (Div. 2)补题

B. Prime Square
传送门

题目大意：输出一个方阵，使方阵每行每列的和都是素数，同时方阵的组成不能是素数
解法：

1. 我原来的思路是素数筛，然后发现太麻烦，方阵中允许重复数字出现，我无法用代码实现
2. 正确思路：方阵行列最小为2，找到两个数字a,b,是的a+b=素数，吧这两个数字放进数组中，然后对这个数组全排列输出。对此可以建立一个方阵,行列相同

1	2	3	4
2	3	4	1
3	4	1	2
4	1	2	3

代码如下：

import java.util.*;
public class B1 {
	public static void main(String args[])throws java.lang.Exception
	{
		Scanner sc  = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0) {
			int  n = sc.nextInt();
			int arr []= new int[n];
			arr[0]=1;arr[1]=1;
			int count=0;
			for(int i=0;i<n;i++) {
				int j=i;
				count=0;
				while(count<n) {
				
					System.out.print(arr[j]+" ");
					j++;
					j=j%n;//保证下标不越界
					count++;
				}
				System.out.println();
			}
		}
	}
}

C. Binary Search

传送门

题意：一个不是顺序的数字队列（1—n）,给你一个数字x和x所在的位置pos，问这个队列有多少种可能可以用二分查找查出？
思路：

1. 二分查找是通过改变区间来搜索的，用中间值a[mid]来比较确定所改变的区间。这个题是比较的位置mid、pos
2. 二分查找满足的条件，mid和pos的比较结果，设a=mid<pos的次数,b=mid>pos的次数。这里就要有a个数字小于x，b个数组大于x。而其他的数可以随意排列
3. 例如： 1、x、3、4、5，中间值为3,3就必须大于x的位置2，才能找到
4. 设置greater为大于x的数字数，less为小于x的数字数，
5. 于是通过全排列可以得到
6. 此外还有a>less,b>greater的情况，不过cf样例中没有出现

代码如下：

import java.util.Scanner;
public class C {
	public static void main(String[] args) {
		long mod=(int)(1e9+7);
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int x=sc.nextInt();
		int pos=sc.nextInt();
		int greater=n-x;//大于的数字数
		int less=x-1;//小于的数字数
		//System.out.println("less:"+less+" "+"greater: "+greater);
		int	l=0,r=n;
		int a1=0,a2=0;//a2是大于的
		while(l<r) {
			int mid=(r+l)>>1;
			if(mid>pos)	{r=mid;a2++;}
			if(mid<pos) {l=mid+1;a1++;}
			if(mid==pos)	l=mid+1;
		}
		//System.out.println("a1:"+a1+" "+"a2:"+a2);
		long sum=1;
		for (int i = 0; i < a1; i++) {
			sum=sum*(less-i)%mod;
			
		}
		for (int i = 0; i < a2; i++) {
			sum=sum*(greater-i)%mod;
			
		}
		int temp=n-(a1+a2)-1;//还要除去pos
		for (int i = 1; i <=temp; i++) {
			sum=sum*i%mod;
			
		}
		System.out.println(sum);
	

}

}

本文地址：https://blog.csdn.net/ba7bc/article/details/109269974