2024上半年JLU_ACM讲题

虽然临近退役，但是既然ACM队的训练需要讲题，还是得把这些题都码一遍，也顺便维持一下思维能力。

第三周训练_习题网址

A - Sasha and the Casino

题目大意

给定k,x,a，一次打赌赢了本金增加到k倍，输了清零，保证最多输x次，初始资金为a，问是否有策略使得在操作后金额任意大

解法

考虑在本问题中，提供的条件不仅包含当前金额，还包含了已经连续输的次数，所以说，我们需要确保当赢了一次之后，金额比之前要高。又考虑到本金有限，所以应该在保证前一条件的情况下，尽可能降低金额的数值。所以在一段连续输后的下一次金额cur=max((cost+k-1)/(k-1),1)其中cost是这一段连续输花钱的总金额。

B - Equalize

题目大意

给定一个长度为n的数组，要求其与一个排列相加，使得出现次数最多的数的出现次数尽可能大，求这一最大值。

解法

对所有数进行排序并去重，问题即变成求最大的满足最大数减最小数的差小于n的区间长度，可以用一个单调队列完成。

C - Physical Education Lesson

题目大意

1…k..1..k..1依次报数，已知位置n和报数的值x，求可能的k的数量

解法

以1…k…2作为一个循环，已知n,x的情况下，循环要么在n-x要么在n+x-2,也有可能同时出现。这样2k-2肯定是循环结束位置的约数，枚举复杂度是根号的。此外还需要保证k不小于x。最后对于所有的k放set去重就可以了。

D - XOR-distance

题目大意

给定a,b,r，求|(a xor x)-(b xor x)|的最小值，其中$0\leq x\leq r$

解法

只需要考虑a,b不同的位，所以其它位都置为0，然后再取两个里大的数，令其最高位为不动，尽量使剩余位都变成0，在满足r的限制下贪心取就能解决此题。

E - A Balanced Problemset?

题目大意

给一个整数x，要求将x分成n个数的和，使得所有数的最大公因数最大，求这个最大的最大公因数

解法

设最大公因数为k，那么k肯定是x的因数，且x/k不能小于x，枚举出满足条件的最大k即可。

F - Did We Get Everything Covered?

题目大意

给定字符串长度n和字符集k以及一个字符串s，问长度为n的字符集为k的字符串是否都是s的子序列，如果不是，请输出反例。

解法

扫一遍，当凑齐一套字符集的字符后开始下一套，一共要n套，如果有责输出yes，不够则可以输出每套最后一个补全的字符和那个缺失的字符。

G - Partitioning the Array

题目大意

一个长度为$n$的数组a，划分成相等长度的k部分，问存在多少种k，存在m使得所有数模m后，每个部分都相同。

解法

合法的k只有$sqrt(n)$个，对于每个k只需要判断是否存在m即可，而m的条件是任意位置相差k的数之差都是m的倍数，所以用gcd即可求得。

H - Watering an Array

题目大意

一个数组a，第i天可以给数组的前vi个数都加一，也可以选择收获ai=i个点数并清空数组a，其中vi是循环的。问d天后点数最多是多少。

解法

容易发现清空数组a后，再收获的时候最多收获1，所以一旦清空最优策略就是加一收获来回进行。所以本题要考虑什么时候第一次收获，容易发现n不大，一次收获最多只有n，而一开始收获则只需要2n天就可以获得n，所以第一次收获一定不晚于2n。枚举时刻取最优就能解决此题。

I - Largest Subsequence

题目大意

一个字符串，每次选择字典序最大的子序列，将子序列对应位置的字符进行重排，原来最后一个字符到第一个字符的位置上，其它字符均向后移一个字符。问多少次操作，字符串变得有序。

解法

考虑先求出最大的子序列（直接扫一遍），然后操作的结果即将这些字符翻转，花的步数即其中不是最大那个字符的字符数量。最后记得判断一下是否有序即可。

J - Array Game

题目大意

给你一个由$n$个正整数组成的数组$a$。在一次操作中，选取
$(i,j)$，将$|a_i-a_j|$加到$a$ 的末尾。要求在执行$k$次操作后，最小化数组$a$的最小值。

解法

如果k大于等于3，那么答案为0；如果k=0，答案为最小值；如果k=1，答案还需对差取min；如果k=2，那么答案还需要对两个数的和减去一个数的绝对值的最小值取min。

K - StORage room

题目大意

现在有一个n*n的表格M，是一把锁。锁的密码是一个长度为n的序列a，满足$M_{i,j}=a_i|a_j$

解法

对于一个a相关的所有要求都取与，再判断这个尽可能大的a是否满足所有条件即可

L - Theofanis’ Nightmare

题目大意

给定一个数组a,大小为n,现在将数组a分割成几个非空子数组,并且保证每个元素只在一个一个子数组中,例如，数组 [1,−3,7,−6,2,5]可以划分为 [1][−3,7][−6,2][5]。
这种分割的值等于第i个子数组的和乘以i，再求和。求分割的最大值。

解法

考虑一次划分后面的所有数贡献都加一，所以只需要找到大于等于0的后缀并且都加一即可，特判第一个位置。