当前位置：首页 > news >正文

E - Bad Juice

news 2025/8/26 23:01:41

解题思路

由于最后返回一个01字符串表示所选人的状态
要求人数最少，即字符串长度最少
而要用最少的字符，找出 $Bad\ juice$
则返回的字符为二进制下 $Bad\ juice$ 的编号
这样利用了所有的01字符
$i$ 号人表示二进制下 $i$ 位的情况
注意对于2的次方项 $n=2^k$ ，只需要有 $k-1$ 位， $n$ 可以用 $k-1$ 位均为0表示

import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static class Node{int x;int y;public Node(int u,int v) {x=u;y=v;}}public static void main(String[] args) throws IOException{
//		AReader input=new AReader();
//	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));	Scanner input=new Scanner(System.in);int n=input.nextInt();//返回的二进制字符串即为变质的编号int t=0;while((1<<t)<n)t++;System.out.println(t);int[] c=new int[n+1];for(int i=0;i<t;++i) {for(int j=1;j<=n;++j) {if(((j>>i)&1)==1)c[i]++;}}for(int i=0;i<t;++i) {System.out.print(c[i]);for(int j=1;j<=n;++j) {if(((j>>i)&1)==1)System.out.print(" "+j);}System.out.println();}String string=input.next();char[] s=string.toCharArray();int ans=0;for(int i=0;i<t;++i) {if(s[i]=='1')ans|=(1<<i);}if(ans==0)ans=n;System.out.println(ans);System.out.flush();
// 	    out.flush();
//	    out.close();}//System.out.println();//out.println();staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){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{//确定下一个token只有一个字符的时候再用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 byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

查看全文

http://www.lryc.cn/news/309211.html