牛客周赛85 题解 Java ABCDEFG

A小紫的均势博弈

判断输入的 n 是奇数还是偶数

import java.io.*;
import java.math.*;
import java.util.*;public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);static void solve() throws IOException {int n=sc.nextInt();if(n%2==0) {dduoln("yukari");}else {dduoln("kou");}} public static void main(String[] args) throws Exception {int t = 1;
//        t = sc.nextInt();while (t-- > 0) {solve();}}static <T> void dduo(T t){System.out.print(t);}static <T> void dduoln(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}

B小紫的劣势博弈

排序 然后一人拿一个

import java.io.*;
import java.math.*;
import java.util.*;public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);static void solve() throws IOException {int n=sc.nextInt();long arr[]=new long[n];for(int i=0;i<n;i++) {arr[i]=sc.nextLong();}Arrays.sort(arr);long ans=0;for(int i=0;i<n;i++) {if(i%2==0) {ans+=arr[i];}else {ans+=arr[i]*(-1);}}dduoln(ans);} public static void main(String[] args) throws Exception {int t = 1;
//        t = sc.nextInt();while (t-- > 0) {solve();}}static <T> void dduo(T t){System.out.print(t);}static <T> void dduoln(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}

C小紫的01串操作

通过观察我们发现

操作 1001 等效于操作 101

操作 100010011000 等效于操作 101010

然后发现经过小红和小紫操作

10 可以 10 -> 11

101 可以 101 -> 111

1010 可以 1010 -> 1110 -> 1111

10101 可以 10101 -> 10001 -> 11111

101010 不可以
...

所以只要判断出现多少次 01 就可以

import java.io.*;
import java.math.*;
import java.util.*;public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);static void solve() throws IOException {String str=sc.next();int a=1;for(int i=1;i<str.length();i++) {if(str.charAt(i)!=str.charAt(i-1)) {a++;}}if(a<=5) {dduoln("Yes");}else {dduoln("No");}} public static void main(String[] args) throws Exception {int t = 1;t = sc.nextInt();while (t-- > 0) {solve();}}static <T> void dduo(T t){System.out.print(t);}static <T> void dduoln(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}

D小紫的优势博弈

准备先暴力一发的 结果直接过了

10010

小红操作会有 5 种情况 这等于 n

0010

010

10

1

我的想法是一个一个从头开始遍历这些字符串

统计 1 0 出现的次数

如果都出现偶数次 那么小紫获胜

import java.io.*;
import java.math.*;
import java.util.*;// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);static void solve() throws IOException {int n=sc.nextInt();String str=sc.next();int cnt=0;for(int i=1;i<n;i++) {int cnt0=0;int cnt1=0;for(int j=i;j<n;j++) {if(str.charAt(j)=='1')cnt1++;if(str.charAt(j)=='0')cnt0++;if(cnt0!=0||cnt1!=0) {if(cnt0%2==0&&cnt1%2==0) {cnt++;break;}}}}dduoln((double)cnt/(double)n);} public static void main(String[] args) throws Exception {int t = 1;
//        t = sc.nextInt();while (t-- > 0) {solve();}}static <T> void dduo(T t){System.out.print(t);}static <T> void dduoln(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}

E小紫的线段染色

首先要知道的是 有符合的情况

一部分染紫色 一部分染红色 等效于 一部分染红色 一部分染紫色

我们可以将结构体排序

int arr []{起始 l，结束 r，当前次序 i}

按照 l 从小到大 r 从小到大次之

第一段为红色 那么红色的末尾为 arr[0][2]

然后 从第二段 进行遍历

如果第二段的起始 l 小于红色末尾

那必须染成紫色

但如果起始 l 小于紫色末尾

那就无法染成了（输出-1 return）

如果 l 大于紫色末尾 则可以染成紫色 更新紫色末尾为第二段结束的 r

同时记录当前 arr[][3]

继续遍历

如果第三段的起始 l 大于红色末尾 更新红色末尾为第二段结束的 r

...

这边有个坑 就是

得 必须 选出一个染成紫色...

不能全是红色

import java.util.*;
import java.io.*;
import java.math.*; public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);public static void main(String[] args) throws IOException {int n=sc.nextInt();List<Long []>list=new ArrayList<>();for(long i=0;i<n;i++) {long l=sc.nextLong();long r=sc.nextLong();list.add(new Long[] {l,r, i+1});}Collections.sort(list,(o1,o2)->{if(o1[0]==o2[0]) {return Long.compare(o1[1], o2[1]);}else {return Long.compare(o1[0], o2[0]);}});ArrayList<Long> anslist=new ArrayList<>();long hongend=list.get(0)[1];long ziend=-1;for(int i=1;i<n;i++) {long start=list.get(i)[0];long end=list.get(i)[1];if(start<=hongend) { // 要变成紫色if(ziend==-1) {// 直接赋值ziend=end;}else {if(start<=ziend) {dduoln("-1");return;}else {ziend=end;}}// 变成紫色anslist.add((list.get(i)[2]));}else {// 继续红色hongend=end;}}if(anslist.size()==0) {anslist.add((long) 1);}dduoln(anslist.size());Collections.sort(anslist);for(long i:anslist) {dduo(i+" ");}}static <T> void dduo(T t){System.out.print(t);}static <T> void dduoln(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}
}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}

F小紫的树上染色

import java.util.*; 
import java.io.*;
import java.math.*; public class Main {static IoScanner sc = new IoScanner();static final int mod=(int) (1e9+7);static int n;static int k;// 邻边矩阵static List<List<Integer>> list;public static void main(String[] args) throws IOException {n = sc.nextInt(); k = sc.nextInt(); if(k==n) {dduoln("0");return;}list = new ArrayList<>();for (int i = 0; i <= n; i++) {list.add(new  ArrayList<>());}for(int i=0;i<n-1;i++){ // 无向图int u=sc.nextInt();int v=sc.nextInt();list.get(u).add(v);list.get(v).add(u);}int low = 1;int high = n;int ans=n;while (low <= high) {int mid = (low + high) >> 1;if (check(mid, k)) {ans = mid;high = mid - 1;} else {low = mid + 1;}}dduoln(ans); }static boolean check(int mid, int k) {int[] res = new int[n+5];int cnt = 0;Deque<Object[]> stack = new ArrayDeque<>();stack.push(new  Object[]{1, -1, false});while (!stack.isEmpty())  {Object[] cur = stack.pop(); int u = (Integer) cur[0];int p = (Integer) cur[1];boolean judge = (Boolean) cur[2];if (judge==false) { // 未染色stack.push(new  Object[]{u, p, true});List<Integer> children = new ArrayList<>();for (int v : list.get(u))  { // v邻点  u当前顶点  p父顶点if (v != p) {children.add(v); }}
//                for(Integer i:children) {
//                	dduo(i);
//                }
//                dduoln();Collections.reverse(children); for (int v : children) {stack.push(new  Object[]{v, u, false});}} else { // 染色int sum = 0;for (int v : list.get(u))  {  // v邻点  u当前顶点  p父顶点if (v != p) {sum += res[v];}}if (sum + 1 > mid) {cnt++;res[u] = 0;} else {res[u] = sum + 1;}}}if(cnt <= k)return true;else return false;}static <T> void dduo(T t){System.out.print(t);}static <T> void dduoln(){System.out.println("");}static <T> void dduoln(T t){System.out.println(t);}
}class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}