vp补题-CCPC2024河南

type

status

date

slug

summary

Problem F. 优秀字符串

小A认为，一个字符串S是优秀字符串，当且仅当： • S 的长度|S|恰好为5； • S 的第三个字符与第五个字符相同； • S 的前四个字符互不相同。例如henan 是优秀字符串，但query、problem、queue 不是，因为： • query 的第三个字符为e，而第五个字符为y； • problem 的长度不为 5； • queue 的前四个字符中u出现了两次。现在，小A有n个仅包含英文字母与数字的字符串S1,S2,...,Sn，请你帮小A求出这些字符串中优秀字符串的数量。输入格式第一行，一个正整数n（1≤n≤105），表示字符串的数量。接下来n行，每行一个仅包含英文字母与数字的字符串Si。保证∑|Si|≤2× 105。输出格式一行，一个整数，表示给定字符串中优秀字符串的数量

解

按题目描述记录一下即可，签到

Problem J. 排列与合数

小A在2023年河南省CCPC大学生程序设计竞赛的赛场上遇到了一道名为“排列与质数”的题目。与大多数选手一样，小A并没能在赛场上解决这个棘手的题目。比赛结束后，小A想到了一个与之相关的题目：排列与合数，可是小A仍然没有能力解决。这个名为“排列与合数”的题目是这样的：给定一个有且仅有5 位，且各个数位互不相同的十进制正整数n。你可以重新排列n的各个数位，但需要保证重新排列得到的整数n′ 没有前导零。请问重新排列数位得到的n′ 能否为合数？若能为合数，请求出一个满足条件的n′。例如，当n=12345 时，任意排列得到的n′ 均是合数，因此可以任意取n′。当n=13579时，可以重新排列数位得到合数n′=97531=7×13933。一个正整数是合数，当且仅当它可以分解为两个不小于2的整数的乘积。现在，小A带着他的题目来到赛场上求助。你能帮助小A解决这个题目吗？输入格式本题测试点包含多组数据。第一行，一个正整数，表示数据组数。对于每组数据：一行，一个正整数，保证n的各个数位互不相同。输出格式对于每组数据：输出一行，一个整数。若能重新排列n的数位得到合数n′则输出n′，否则输出−1。

解

由于以”偶数“和”5“结尾的数必然是合数，而由于各位数不相同，所以一定存在合数排列，只需将数记录下标并特判输出即可，注意0的位置。签到题

Problem B. 扫雷 1

T0xel 喜欢玩扫雷，但是他玩的扫雷游戏有名为“地雷探测器”的特殊道具。具体来说，T0xel 会进行n轮扫雷。每轮扫雷开始之前，T0xel会获得1枚扫雷币。扫雷币在每轮扫雷结束后不会回收，可以保留至下一轮扫雷。T0xel知道，在第i轮扫雷中，花费ci 枚扫雷币可以购买一个地雷探测器，清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。现在T0xel 想知道，在这n轮扫雷中最多能购买多少个地雷探测器呢？输入格式第一行，一个正整数），表示扫雷轮数。第二行，n个正整数。输出格式一行，一个非负整数，表示答案。

解

贪心，但是难以想到先对大小进行排序或维护单调递增序列，排序后按照升序选择点，并记录原序列下标。

Problem M. 有效算法

给出长度为n的正整数序列和。对于每个（1≤i≤n），进行恰好一次以下操作： • 将变成满足的任意整数x。请你求出最小的非负整数k，使得存在至少一种方法使得操作后序列{an}所有数都相等。输入格式本题测试点包含多组数据。第一行包含一个正整数T（），表示数据组数。对于每组数据：第一行包含一个正整数n（）。第二行包含n个正整数a1,a2,...,an（）。第三行包含n个正整数b1,b2,...,bn（）。保证单个测试点中所有数据的。输出格式对于每组数据：输出一行一个整数，表示答案。

解

可以看出与位置和的长度有关，那么可以得出，对于每个的值来说，可以表示为，那么在数轴上的表示便非常明显，只需对于每个x的位置找到每个最大的使其最小即可。明显使用二分答案来解决。

对进行二分，每次判断对每个对影响最大的位置，移动，并同时记录最小的值

同时发现，若是在数轴上对各个值进行判断时，要找到的值为对每个扩展产生的交点。所以也可以直接对答案二分，只要找出最小可以产生交集的位置。