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());}
}
