企业网站建设计什么科目,做购物网站的初衷,广州效果图制作公司,乐清网站制作公司有哪些前言 整体评价
很普通的一场比赛#xff0c;t2思维题#xff0c;初做时愣了下#xff0c;幸好反应过来了。t3猜猜乐#xff0c;感觉和逆序数有关#xff0c;和奇偶性有关。不过要注意int溢出。
欢迎关注: 珂朵莉的天空之城 A. 客人数量
题型: 签到
累加和即可
import…
前言 整体评价
很普通的一场比赛t2思维题初做时愣了下幸好反应过来了。t3猜猜乐感觉和逆序数有关和奇偶性有关。不过要注意int溢出。
欢迎关注: 珂朵莉的天空之城 A. 客人数量
题型: 签到
累加和即可
import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(new BufferedInputStream(System.in));int n sc.nextInt();long res 0;for (int i 0; i n; i) {long v sc.nextLong();res v;}System.out.println(res);}}B. 指针运动
思路: 思维题
其实只要找到最小值然后模拟这样时间复杂度就能控制在 O ( n ) O(n) O(n)
值域很大这是最佳的策略
不过枚举应该也可以
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(new BufferedInputStream(System.in));int n sc.nextInt();long[] arr new long[n];for (int i 0; i n; i) {arr[i] sc.nextLong();}long minTimes Arrays.stream(arr).min().getAsLong();int now (int)(minTimes % n);long cutoff minTimes;while (arr[now] cutoff) {now (now 1) % n;cutoff;}System.out.println(now 1);}}C. 随机排列
思路: 逆序对数 奇偶分析
求逆序数的大概有两种解法
CDQ, 分治归并排序树状数组
这边采用了树状数组因为是1~n的排列所以不用离散化处理
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
当然更好的解法是置换群(置换环)因为侧重于交换的奇偶次数
这样的话时间复杂度可以控制在 O ( n ) O(n) O(n)
树状数组解法
// package acwing.acw141;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;public class Main {static class BIT {int n;int[] arr;public BIT(int n) {this.n n;this.arr new int[n 1];}void update(int p, int d) {while (p n) {arr[p] d;p p -p;}}int query(int p) {int r 0;while (p 0) {r arr[p];p - p -p;}return r;}}public static void main(String[] args) {AReader sc new AReader();int n sc.nextInt();int[] arr new int[n 1];for (int i 1; i n; i) {arr[i] sc.nextInt();}long res 0;BIT bit new BIT(n);for (int i 1; i n; i) {int v arr[i];int d bit.query(n) - bit.query(v);res d;bit.update(v, 1);}if (res % 2 ! n % 2) {System.out.println(2);} else {System.out.println(1);}}staticclass AReader {private BufferedReader reader new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer new StringTokenizer();private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine innerNextLine();if (nextLine null) {return false;}tokenizer new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer new StringTokenizer();return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}// public BigInteger nextBigInt() {
// return new BigInteger(next());
// }// 若需要nextDouble等方法请自行调用Double.parseDouble包装}}写在最后
