GDPU 竞赛技能实践 天码行空 期末小测
1. 除法（原题）
👨🏫 实验二：1.简单枚举
输入正整数n，按从小到大的顺序输出所有形如abcde/fghij= n的表达式，其中a～j恰好为数字0～9的一个排列（可以有前导0），2≤n≤79。
样例输入：
62
样例输出：
79546 / 01283 = 62
💖 Main1.java
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
//文件名：Main1.java
public class Main1
{
static int n;
static Set<Integer> set = new HashSet<>();// 用于数字去重
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1234; i < 100000; i++)
{
if (repeat(i))
continue;
int y = cal(i);
if (y != -1)
{
System.out.print(y + "/");
System.out.printf("%05d", i);
System.out.println(" = " + n);
}
set.clear();
}
}
/**
*
* @param x
* @return 返回 x 对应的 x*n，非法值则返回 -1
*/
private static int cal(int x)
{
int y = x * n;
if (value(y))
return y;
return -1;
}
//返回 y 是否为有效值
private static boolean value(int y)
{
if (y < 10000 || y >= 100000)
return false;
Set<Integer> tmpSet = new HashSet<>();
while (y != 0)
{
int t = y % 10;
if (tmpSet.contains(t) || set.contains(t))
return false;
tmpSet.add(t);
y /= 10;
}
return true;
}
//返回 x 的每一位是否有重复的数字，有则返回 true
private static boolean repeat(int x)
{
if ((x + "").length() == 4)
x *= 10;
while (x != 0)
{
int t = x % 10;
if (set.contains(t))
{
set.clear();
return true;
}
set.add(t);
x /= 10;
}
return false;
}
}
2. 求逆序对（原题）
输入一个序列{a1, a2, a3,…, an}，交换任意两个相邻元素，不超过k次。交换之后，问最少的逆序对有多少个。
序列中的一个逆序对，是指存在两个数ai和aj，有ai > aj且1≤i<j≤n。也就是说，大的数排在小的数前面。
输入：第一行是n和k，1 ≤ n ≤ 105，0 ≤ k ≤ 109；第二行包括n个整数{a1, a2, a3,…, an}，0≤ ai ≤109。
输出：最少的逆序对数量。
Sample Input：
3 1
2 2 1
Sample Output：
1
💖 Main2.java
import java.util.Scanner;
public class Main2
{
static int N = 100010;
static int[] q = new int[N], tmp = new int[N];
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
for (int i = 0; i < n; i++)
q[i] = sc.nextInt();
long cnt = mergeSort(0, n - 1);
System.out.println(Math.max(0, cnt - k));
}
/**
* @param l 区间左边界
* @param r 区间右边界
* @return long 类型的区间内的逆序对
*/
private static long mergeSort(int l, int r)
{
if (l >= r)
return 0;
int mid = l + r >> 1;
long res = mergeSort(l, mid) + mergeSort(mid + 1, r);
int k = 0;// 临时数组指针
int i = l;// 左区间指针
int j = mid + 1;// 右区间指针
while (i <= mid && j <= r)
{
if (q[i] <= q[j])// 无逆序对
tmp[k++] = q[i++];
else
{
tmp[k++] = q[j++];
res += mid - i + 1;
}
}
if (i <= mid)
tmp[k++] = q[i++];
if (j <= r)
tmp[k++] = q[j++];
for (i = l, j = 0; i <= r; i++, j++)
{
q[i] = tmp[j];
}
return res;
}
}
3. 求最大子段和（分治法）
给出一个长度为 n的序列 a，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i个数字 ai。
输出格式
输出一行一个整数表示答案。
输入
7
2 -4 3 -1 2 -4 3
输出
4
💖 源代码
import java.util.Scanner;
public class Main3
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++)
nums[i] = sc.nextInt();
int ans = maxSubArray(nums);
System.out.println(ans);
}
public static int maxSubArray(int[] nums)
{
int len = nums.length;
if (len == 0)
{
return 0;
}
return maxSubArraySum(nums, 0, len - 1);
}
private static int maxCrossingSum(int[] nums, int left, int mid, int right)
{
// 一定会包含 nums[mid] 这个元素
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// 左半边包含 nums[mid] 元素，最多可以到什么地方
// 走到最边界，看看最值是什么
// 计算以 mid 结尾的最大的子数组的和
for (int i = mid; i >= left; i--)
{
sum += nums[i];
if (sum > leftSum)
{
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
// 右半边不包含 nums[mid] 元素，最多可以到什么地方
// 计算以 mid+1 开始的最大的子数组的和
for (int i = mid + 1; i <= right; i++)
{
sum += nums[i];
if (sum > rightSum)
{
rightSum = sum;
}
}
return leftSum + rightSum;
}
private static int maxSubArraySum(int[] nums, int left, int right)
{
if (left == right)
{
return nums[left];
}
int mid = left + (right - left) / 2;
return max3(maxSubArraySum(nums, left, mid), maxSubArraySum(nums, mid + 1, right),
maxCrossingSum(nums, left, mid, right));
}
private static int max3(int num1, int num2, int num3)
{
return Math.max(num1, Math.max(num2, num3));
}
}
原文地址：https://blog.csdn.net/lt6666678/article/details/138920573
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！