牛客周赛85 题解 Java ABCDEFG 准AK
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
通过观察我们发现
操作 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());
}
}
牛客算法 校招 Java 合集 文章被收录于专栏
Java写算法
投递中国移动等公司6个岗位