牛客周赛85-题解-Java-ABCDEFG
牛客周赛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 void dduo(T t){System.out.print(t);} static void dduoln(){System.out.println("");} static 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 0) { solve(); } } static void dduo(T t){System.out.print(t);} static void dduoln(){System.out.println("");} static 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 0) { solve(); } } static void dduo(T t){System.out.print(t);} static void dduoln(){System.out.println("");} static 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 0) { solve(); } } static void dduo(T t){System.out.print(t);} static void dduoln(){System.out.println("");} static 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();
Listlist=new ArrayList<>();
for(long i=0;i{
if(o1[0]==o2[0]) {
return Long.compare(o1[1], o2[1]);
}else {
return Long.compare(o1[0], o2[0]);
}
});
ArrayList anslist=new ArrayList<>();
long hongend=list.get(0)[1];
long ziend=-1;
for(int i=1;i void dduo(T t){System.out.print(t);}
static void dduoln(){System.out.println("");}
static 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; 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> 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 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 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 void dduo(T t){System.out.print(t);} static void dduoln(){System.out.println("");} static 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()); } }