蓝桥杯国赛训练 day1

目录

k倍区间

舞狮

交换瓶子

---

k倍区间

取模后算组合数就行

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main {static Scanner sc = new Scanner(System.in);public static void main(String[] args) {solve();}public static void solve() {int n = sc.nextInt();long k = sc.nextLong();//        System.out.println(calC(2,5));long[] arr = new long[n + 1];long[] pre = new long[n + 1];for (int i = 1; i <= n; i++) {arr[i] = sc.nextLong();pre[i] = pre[i - 1] + arr[i];}HashMap<Long,Long>hm=new HashMap<>();for(int i=1;i<=n;i++) {long preKey=pre[i]%k;hm.put(preKey, hm.getOrDefault(preKey, 0L)+1);}long cnt=0;if(hm.containsKey(0L)) cnt+=hm.get(0L);for(long l:hm.keySet()) {long preVal=hm.get(l);if(preVal>=2) {cnt+=calC(2,preVal);} }System.out.println(cnt);}/***   计算组合数* @param m 上标* @param n 下标* @return*/public static long calC(long m, long n) {m = Math.min(m, n - m); long result = 1;for (long i = 1; i <= m; i++) {result *= (n - m + i) ;result /= i;}return result;}
}

组合数模版

    /*** 计算组合数* @param m 上标* @param n 下标* @return*/public static long calC(long m, long n) {m = Math.min(m, n - m); long result = 1;for (long i = 1; i <= m; i++) {result *= (n - m + i) ;result /= i;}return result;}

舞狮

暴力就完了

不然应该是一个dfs 找环

import java.util.*;// xixi♡西
public class Main {static Scanner sc = new Scanner(System.in);public static void solve() {int n=sc.nextInt();long arr[]=new long[n];for(int i=0;i<n;i++) {arr[i]=sc.nextLong();}Arrays.sort(arr);ArrayList<ArrayList<Long>>list=new ArrayList<>();loop:for(long num:arr) {boolean isAdd =false;for(ArrayList<Long> forList:list) {if(num>forList.size()) {isAdd=true;forList.add(num);continue loop;}}if(isAdd==false) {ArrayList<Long>newList=new ArrayList<>();newList.add(num);list.add(newList);}}System.out.print(list.size());}public static void main(String[] args){int t = 1;
//        t = sc.nextInt();while (t-- > 0) {solve();}}}

交换瓶子

import java.util.*;public class Main {static Scanner sc = new Scanner(System.in);public static void main(String[] args) {solve();}public static void solve() {int n = sc.nextInt();int[] arr = new int[n + 1];for(int i = 1; i <= n; i ++){arr[i] = sc.nextInt();}int count = 0;for(int i = 1; i <= n; i ++){if(arr[i] != i){int temp = arr[i];arr[i] = arr[temp];arr[temp] = temp; count++;i = 1;}}System.out.println(count);}}