DEF Java题解，代码已去除冗余~~~ D 红魔馆的馆主（二） 筛出495所有的约数，以及a中每个数相对于每一个约数的前缀和，数组a中每一个数字的贡献是，它自己需要乘的最小的495的余数的个数，，再次遍历数组a，计算该位置的数字加一后的贡献变化即可，时间复杂度(O(495+n*12))，其中12代表495的约数个数 import java.util.*; public class Main{ static List<Integer> divisor=new ArrayList<>(); static{ for(int i=1;i<500;i++){ if(49...

DEF Java题解，代码已去除冗余~~~ D K 最多有n个极大不同区间，且每个区间的长度为n-k+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(),k=sc.nextInt(); if(k>n){ System.out.println("NO"); } else{ System.out.println("YES"); for...

C~F Java题解，代码已去除冗余 C 小红打怪 假设a次可以打完，那么多打一次更可以打完，因此答案满足二段性，二分即可。。在check的时候，可以假设最初全部进行了全打击，先保证不浪费的情况下进行相邻打击，在用单点打击处理残局，最后在进行一波相邻打击首尾，check返回真的条件为全体不大于0，时间复杂度O(nlogC)，其中C==1e9 import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextI...

D~G Java题解，代码已去除冗余 D 小苯的蓄水池（easy） && E 小苯的蓄水池（hard） 本质上就是一个区间合并，为保证可以查询修改某个不大于端点的值，选用有序映射来表示区间，每个区间端点最多插入或者删除一次，时间复杂度O(nlogn+m) import java.util.*; import java.io.*; public class Main{ public static void main(String args[]) throws IOException{ BufferedReader bf=new BufferedReader(new InputSt...

D~G Java题解，代码已去除冗余 D 医生 用二进制数位来表示每种药可以值得病，以及每个病人的得病情况，对于每个病人，百里暴力检查每种组合是否可以治病，同时更新答案，时间复杂度O((n+k)m+n*2^k) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(),m=sc.nextInt(),patient[]=new int[n]; for(int i=0;i<n;i++){...

C~F Java题解，代码已去除冗余 C 冰冰的异或 通过打表1-100时的答案，可以找到规律：答案即为不小于n的最小2的整数次幂，其中n<=2的情况特判一，时间复杂度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++){ long n=sc.nextLong(); System.out.println(n<=2?...

D~G Java题解，代码已去除冗余 D 小红和小紫的博弈游戏 每次相当于从两个对角线中的数字各取一个数，计算哪一个先取到0即可，时间复杂度O(T) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(),a[]=new int[4]; for(int i=0;i<t;i++){ for(int j=0;j<4;j++){ a[j]=sc.nextInt(); } Syste...

DEF Java题解~~~代码已去除冗余，并保留必要的注释 D 小红的行列式构造 好烦啊，瞎做呗，令上边俩角的元素相同，下边俩角的元素相同，可以消掉一部分，剩下的代数式分解因式即可拼凑，时间复杂度O(1) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); System.out.println("99 100 99\n101 1 "+(sc.nextInt()+101)+"\n1 1 1"); } }  E 小红的 re...

本题解中，代码已去除冗余，并保留简要注释 A 序列中的排列 只需判断序列中是否包含全部1-k的数字即可，时间复杂度O(Tn) 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 n=sc.nextInt(),k=sc.nextInt(); Set<Integer> set=new HashSet<>(...

AtCoder Beginner Contest 374 代码中已去除冗余 A Takahashi san 2 直接判断末尾字符串是否为"san"即可，时间复杂度O(1) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); System.out.println(sc.next().endsWith("san")?"Yes":"No"); } }  B Unvarnished Report 遍历字符串找到第一个不同的字符，...

D~G Java题解，代码已去除冗余 D 小红的树上移动 不妨把树看做是以1为根的，可知，在停下来之前，移动方向是远离根节点的，因此只需要统计通往叶节点的概率即可，时间复杂度O(nlog(mod)) import java.util.*; public class Main{ static int mod=(int)1e9+7; public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); List<Integer> path[]=new List[n+5...

C~F Java题解，代码已去除冗余 C tb的路径问题 暴力模拟一下n<100时的结果即可找到规律，时间复杂度O(1) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println(Math.min(n*2-2,n%2==1?6:4)); } }  D tb的平方问题 对于任何一个下标，包含它的好数组，就是总的好数组数，减去左边不包含它的好数组数...

DEF Java题解~~代码已去除冗余 D 我们N个真是太厉害了 求第一个空白区间的问题，需要从小数开始累加，假如已经遍历过的数字最大值为max，那么假如一个新数字a，则能表示的心得区间的最小数为a，其中区间(max,a)之间的数字是无法表示的，倘若区间不空，其中的最小数即为不能表示的最小数值，时间复杂度O(Tnlogn) import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for...

DEF Java题解，代码已去掉冗余 D 构造mex 特殊讨论k==0，以及必须至少有每一个[0,k-1]的数字，其他的数字需用不是k的数字填充，时间复杂度O(Tn) 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 Buffer...