数列 {An} 为N的一种排列。
例如N=3,可能的排列共6种:
1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1
定义函数F:
其中|X|表示X的绝对值。
现在多多鸡想知道,在所有可能的数列 {An} 中,F(N)的最小值和最大值分别是多少。
1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1
第一行输入1个整数T,表示测试用例的组数。
( 1 <= T <= 10 )
第二行开始,共T行,每行包含1个整数N,表示数列 {An} 的元素个数。
( 1 <= N <= 100,000 )
共T行,每行2个整数,分别表示F(N)最小值和最大值
2 2 3
1 1 0 2
对于N=3:
- 当{An}为3,2,1时可以得到F(N)的最小值0
- 当{An}为2,1,3时可以得到F(N)的最大值2
对于60%的数据有: 1 <= N <= 100
对于100%的数据有:1 <= N <= 100,000
题目一开始没读懂,意思是:在{An}的所有排列中,能让F(N)取得的最大最小值为多少。
每四个数 例如 5,6,7,8,我们把它们两两一组 |||8-6|-7|-5|=0,最小值是0;猜测最小值的变化也是4个一组
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int nums = sc.nextInt(); for (int i = 0; i<nums; i++){ int N = sc.nextInt(); maxandmin(N); } } public static void maxandmin(int N){ if (N==1||N==2){ System.out.println("1 1"); return; } //之后每4个一组 0011 int min = getmin(N); int max = N-getmin(N-1); System.out.println(min + " " + max); } public static int getmin(int N){ int temp = (N-2)%4; if (temp==1 || temp==2){ return 0; } else return 1; } }
t = int(input()) def getmin(n): if n % 4 == 1 or n % 4 == 2: return 1 if n % 4 == 3 or n % 4 == 0: return 0 for i in range(t): n = int(input()) print(getmin(n), n - getmin(n - 1))
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); for(int i=0;i<n;i++) { int N = scan.nextInt(); System.out.println(min(N)+ " "+max(N)); } } public static int min(int n) { if(n % 4 == 0 || (n+1) % 4 == 0) { return 0; }else { return 1; } } public static int max(int n) { if(n == 1) { return 1; } if(n == 2) { return 1; } return Math.abs(min(n-1)-n); } }
#include <iostream> #include <algorithm> using namespace std; int F[100001][2]; void getMinMax(int N){ for(int i=1;i<=N;i++){ if(i==1){ F[1][0] = 1; F[1][1] = 1; } F[i][0] = (i%4 == 1 || i%4 == 2)? 1:0; F[i][1] = abs(F[i-1][0]-i); } } int main(){ int t; cin>>t; while(t--){ int n; cin>>n; getMinMax(n); cout<<F[n][0]<<" "<<F[n][1]<<endl; } return 0; }
找规律的小游戏 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<n;i++){ int count=0; int a=sc.nextInt(); if(a%4==1 || a%4==2){ System.out.print(1); }else{ System.out.print(0); } System.out.print(" "); if(a%4==1||a%4==0){ System.out.print(a); }else{ System.out.print(a-1); } System.out.println(); } } }
题目一开始没读懂,意思是:在{An}的所有排列中,能让F(N)取得的最大最小值为多少。
每四个数 例如 5,6,7,8,我们把它们两两一组 |||8-6|-7|-5|=0,最小值是0;猜测最小值的变化也是4个一组。看到min只有2种取值。0,1,最大值自然就是N-getmin(N-1)
const readline = require('readline') const rl = readline.createInterface({ input:process.stdin, output:process.stdout }) let count = 0; const getMin = function(n){ return Math.ceil(n/2)%2 } rl.on('line',(input) => { if(count > 0){ let n = +input let min = getMin(n) let max = n - getMin(n-1) console.log(min,max) } count++ })
t = int(input()) for _ in range(t): n = int(input()) print((n + 1) // 2 & 1, end = ' ') print(n - (n // 2 & 1))
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { int cur = sc.nextInt(); int min = getMinSubstrctionAbs(cur); //留下最大值,然后去求剩下数字的最小值 int max = cur - getMinSubstrctionAbs(cur - 1); System.out.println(min + " " + max); } sc.close(); } /** * @return 获取[1, n]这些数的组合的最小绝对值 */ private static int getMinSubstrctionAbs(int n) { if (n == 1 || n == 2) { return 1; } else if (n == 0 || n == 3) { return 0; } //将后面的4个一组消为0 n %= 4; //取前 n - 4 * ?个值计算最小绝对值 return getMinSubstrctionAbs(n); } public static void main1(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) { int cur = sc.nextInt(); min = Integer.MAX_VALUE; max = 0; int[] nums = new int[cur]; for (int j = 1; j <= cur; j++) { nums[j - 1] = j; } dfs(nums); System.out.println(min + " " + max); } sc.close(); } private static int min, max; private static void dfs(int[] nums) { int n = nums.length; if (n == 1) { max = Math.max(nums[0], max); min = Math.min(nums[0], min); return; } //选出两个数求差的绝对值 int[] tmp = new int[n - 1]; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int idx = 0; for (int k = 0; k < n; k++) { if (k != i && k != j) { tmp[idx++] = nums[k]; } } tmp[idx] = Math.abs(nums[i] - nums[j]); dfs(tmp); } } } }
#include <iostream> using namespace std; int n,t; int main() { cin>>t; while(t--) { cin>>n; if(n<=2) cout<<"1 1"<<endl; else if(n%4==0) cout<<"0 "<<n<<endl; else if(n%4==3) cout<<"0 "<<n-1<<endl; else if(n%4==1) cout<<"1 "<<n<<endl; else cout<<"1 "<<n-1<<endl; } return 0; }
import java.util.Scanner; public class Main { public static void printMinAndMax(int N) { int min = 0; int max = 0; if (N % 4 == 0) { max = N; } else if (N % 4 == 3) { max = N - 1; } else if (N % 4 == 2) { min = 1; max = N - 1; } else { min = 1; max = N; } System.out.println(min + " " + max); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); for (int i = 0; i < T; i++) { printMinAndMax(scanner.nextInt()); } } }
public class Main { /* 运行部分结果 N= 2时, min= 1, max= 1 min=1,max=N-1 N= 3时, min= 0, max= 2 min-0,max=N-1 N= 4时, min= 0, max= 4 min=0,max=N N= 5时, min= 1, max= 5 min=1,max=N N= 6时, min= 1, max= 5 min=1,max=N-1 N= 7时, min= 0, max= 6 min=0,max=N-1 N= 8时, min= 0, max= 8 min=0,max=N N= 9时, min= 1, max= 9 min=1,max=N N=10时, min= 1, max= 9 min=1,max=N-1 N=11时, min= 0, max=10 min=0,max=N-1 N=12时, min= 0, max=12 min=0,max=N // 基本一目了然了 */ public static void main(String[] args) { for (int N = 2; N <= 12; N++) { // 跑到15左右就要挺久了...足够找到规律了 int[] arr = new int[N + 1]; for (int i = 1; i < arr.length; i++) { arr[i] = i; } FNMin = Integer.MAX_VALUE; FNMax = Integer.MIN_VALUE; quanpailie(arr, 1); System.out.printf("N=%2d时, min=%2d, max=%2d\n", N, FNMin, FNMax); } } private static int FNMin = Integer.MAX_VALUE; private static int FNMax = Integer.MIN_VALUE; // 全排列 public static void quanpailie(int[] arr, int currentIndex) { if (currentIndex >= arr.length) { calculate(arr); return; } for (int i = currentIndex; i < arr.length; i++) { swap(arr, currentIndex, i); quanpailie(arr, currentIndex + 1); swap(arr, currentIndex, i); // 回溯 } } public static void calculate(int[] arr) { int Fx = arr[1]; // F(1) = A1 for (int i = 2; i < arr.length; i++) { // F(x)=F(x-1)-Ax Fx = Math.abs(Fx - arr[i]); } FNMin = Math.min(Fx, FNMin); FNMax = Math.max(Fx, FNMax); } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
这道题没啥意义,直接作弊吧。
#include using std::cin; using std::cout; using std::endl; class An { private: int m_max; int m_min; int m_N; public: An(int n): m_N{n}, m_min{min(n)}, m_max{max(n)} {} int get_min() { return this->m_min; } int get_max() { return this->m_max; } private: int min(int x) { if (x % 4 == 1 || x % 4 == 2) { return 1; } if (x % 4 == 3 || x % 4 == 0) { return 0; } } int max(int x) { return x - min(x - 1); } }; int main(int argc, char** argv) { int T; // 输入T位数字 int N; // N 数列An的个数 cin >> T; while(T-- != 0 && cin >> N) { An tmp{N}; // 输出结果 cout << tmp.get_min() << " " << tmp.get_max() << endl; } return 0; }