C~F Java题解，代码已去除冗余 C 小红的双好数（easy） 1在任意进制下都符合，2只能在2进制下，其他数字在2进制和自己进制下符合，时间复杂度O(1) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); long n=sc.nextLong(); System.out.println(n==2?"NO":"YES\n"+2+" "+Math.max(n,3...

C~F题解 C 异或故事 对于比特位多于一个的正数，可以分解为该数字去掉最低位以及最低位的异或，而对于比特位单独的数字，则分解为该数字加1和“它自己跟它加1异或后的数”，时间复杂度O(T) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;i++){ int a=...

C~F Java题解 C 小红的数组重排 容易发现，只要数组排序后符合要求就一定有一种方案，否则没有，时间复杂度O(nlogn) import java.util.*; import java.io.*; public class Main{ public static void main(String args[]) throws IOException{ BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw=new Buffe...

牛客周赛 Round 53 Java题解 A 小红小紫投硬币 推导略，答案总是0.5，时间复杂度O(1) public class Main{ public static void main(String args[]){ System.out.println("0.5"); } } B 小红的字符串 对应位置的字母要么正着移动，要么反着移动，取较小的距离，时间复杂度O(len(s)) import java.util.*; public class Main{ public static void main(String args[]){ ...

B-F Java题解 未完待续 B 小红装匣子 容易观察，竖着放两列1x2的块儿等同于横着放两排，而1x3的只能横着放，因此分类讨论有一个竖着放的和没有竖着放的两种情况，在每种前提下，一行需要先尝试用1x3的填满，或者剩余偶数列，剩下的用1x2横向填满，时间复杂度O(T) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); ...

DEF Java~ D 小红的 gcd 先把a按位求得对于b的余数，再利用辗转相除法求结果，时间复杂度O(len(a)+logb) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); long a=0; String s=sc.next(); long b=sc.nextLong(); for(char c:s.toCharArray...

DEF Java D 切割 01 串 2.0 区间动态规划，前缀和记录分别01的个数，从小区间开始更新，每个区间的方案数都是由旗下的分割更新而来的，时间复杂度O(n^3) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(),l=sc.nextInt(),r=sc.nextInt(),pre[][]=new int[n+1][2],ans[][]...

BDEF Java B 小红的伪回文子串（easy） && E 小红的伪回文子串（hard） 遍历每个字符，字符需要跟前边遍历过的字符的配对儿计算贡献（必须跟当前不同），贡献量要么是当前位置距离串尾的距离，要么是前边某个字符距离串首的距离，两者距离取较小值，实现的时候可以按照26个字母记录两个前缀和：一个是字母距离串首的距离之和，一个是遍历到该位置字母数量总和；贡献求得时候分成两部分求即可，时间复杂度O(nC),其中是n是字符串长度，C==26 import java.util.*; public class Main{ public static void main(...

DEF Java D 嘤嘤不想求异或喵 不妨先求出1到l-1的异或和再求出1到r的异或和，二者再异或就是lr异或和，这里有需要计算每一个比特位的数量，或者更具体的，是奇数还是偶数，每个比特总是呈现周期出现的，1<<i这个比特会每隔1<<(i+1)出现1<<i次，而且是在周期后半部分出现，时间复杂度O(TC)，其中C==62 import java.io.*; public class Main{ public static void main(String args[]) throws IOException{ BufferedRea...

C~F Java C 苗苗的气球 方法一：猜结论 假如能够销完的话，总数一定是偶数，并且最大的数量的二倍不大于总数，那么就假设每种颜色是剩下的颜色，判断剩下的（剩下的假如是奇数的话需要从当前遍历的气球种类借一个进来），能留下的条件妖魔石剩下的可以自我消耗完，要么剩下的最大数量被抵消完后的数量小于当前遍历，实现上利用了有序映射计数，时间复杂度O(nlogn) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System...

C~F Java C 爱音开灯 折半枚举所有x的约数，看是否不大于n，时间复杂度O(sqrt(x)) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); long n=sc.nextLong(),x=sc.nextLong(); int ans=0; for(int i=1;(long)i*i<=x;i++){ if(x...

C~G Java题解 C 相助 && E 相依 最佳的方式就是分段的连续的段，直到删完，因为要是两段存在包含，那么删除外边的一大段次数减1，更优，因此记录每个下标结尾的删完需要的最少次数，另外还要记录一下之前同数字之前所有删完的最少次数以备查阅，时间复杂度O(n) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(),a[]=n...

D~F Java D 小黑的区间 利用双指针，左指针固定为子数组起点，右指针试图加入数字，当加入的右指针处数字上一个在i前边或者距离小于k的时候可以加入，时间复杂度O(n) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(),k=sc.nextInt(),col[]=new int[n],last[]=new int[100005]; ...

C~F Java题解 C 连锁进位 其实是从最低位开始到次高位，判断把这一位加到10的倍数需要最少加几，注意需要考虑进位，时间复杂度O(sum(len(n))) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;i++){ String n=sc.next(); ...