哭晕了

题解

/ 注册

全部文章 / 题解（共11篇）

题解 | #第17届FJUT校赛#

致歉由于出题人经验不足，给大家带来不好的体验，实在抱歉。在赛中忘记开答疑，发不了公告，发现的问题已经在尽量修补。出现的问题如下（均修复）： 1.薛薛的简单数学题，没写spj，题面不清晰 2.第K大数（hard）std锅 3.QQ的AC自动机，数据范围和题面不一致 4.人看人，数据弱，本意是想让大家...

2023-05-07

4 432

题解 | #钢筋切割#

D：敌情侦察令 a[i]=b[i-1]+b[i]+b[i+1] 特别的对于 i=1 有 a[1]=b[1]+b[2] 对于 i=n有 a[n]=b[n-1]+b[n] 枚举每个b[1]可能的值（0-a[i]）此时b[2]确定，从而递推出整个b数组若此时满足i=n的条件则为一种可行方案 #incl...

2022-08-10

1 369

题解 | #钢筋切割#

B交通改造：Kruskal 思路：1.接受改造的道路能够令所有的交叉路口直接或间接相连2.并且改造的道路数量应尽可能的少.这两条信息提示我们最终形成的是一颗生成树。但并非是最小生成树，而是最大边权最小生成树。那么只需要二分答案，每次看是否能够形成一棵生成树即可。形成的生成树的充要条件为共有n-1条边...

2022-08-10

0 255

题解 | #QQ宠物#

E:QQ宠物解题突破点：好消息是只有n-1对NPC直接认识，并且将所有相互认识的NPC连在一起能形成一个树形的结构图。可以发现只需要把给出的关系维护成树型结构，就可以在这棵树上跑一遍树形DP。具体的做法是用并查集维护两个人是否在同一棵树上，如果已经在同一棵树上，那就把这条边舍去。 DP[i][1...

2022-08-10

0 451

题解 | #小宝的幸运数组#

题意：找到一个数组中满足子数组之和可以被k整除的最大长度。暴力：求一个前缀和然后两重循环判断每一个子数组能否被k整除，这里值得注意的是正向循环和逆向循环所形成的子数组集合是一样的所以选取一个方向即可。时间复杂度为O（n^2^）优化：我们在用前缀和求是否能够被k整除所用的公式为（sum[r]-su...

2021-12-18

1 450

题解 | #Penguins#

广度优先搜索算法的思想主要是将每种状态用队列储存起来,再对每种状态进行拓展,例如说对于(20,1)这个状态,我们依次上下左右走一步得到除了(19,1)(21,1)(20,0)(20,2)将越界和障碍物外合法进入队列,储存下状态(19,1)(20,2)再依次扩展直到历遍所有可到达点. 对于该题目我们需...

2021-07-23

3 645

题解 | #Stack#

K题:(搞不懂拓扑排序的超小白讲解)总体思路为利用已知b[i]推出b[i-1]信息,将1-n每个数填充至ans数组构造答案.直接进行代码讲解:首先读入数据,我们用一个book数组来记录当前位置是否有约束,显然当下标小于需要长度或者两者大于n时输出-1 #include<bits/stdc++....

2021-07-22

1 610

题解 | #Unique Values#

C题:求无重复数字的子串个数本题使用双指针算法,用hash来检验是否存在相同的数双指针l,r我们先让r一直往右走直到出现重复元素,累加起始下标为l满足条件的子串个数,再将l往左走.样例二模拟:8 ****2 12 3 12 3 2 6 9初始l=r=1,未有重复元素直到l=1,r=4时出现重复元素我...

2021-07-20

5 594

题解 | #Game of Swapping Numbers#

G题：题目大意对于数组大小为n的两个数组a，b在a上操作k次交换使得最大。看到这题想到的是如果我能定量的知道每次交换带来的收益就好了，如果每次交换的收益都是最优的那么结果也是最优的这就是经典的贪心算法，下面对交换的贡献进行讨论：对于（a1，b1）（a2，b2）由于绝对值的存在无论a1，b1大小其值...

2021-07-19

9 831

题解 | #Find 3-friendly Integers#

F题题意寻找l到r区间中的一个数x连续子序列mod3=0的个数（1<=l<r<1e18）观察到数据范围十分的大，正常做法比如前缀和一定是不可做的，那么我们硬要暴力做第一时间想到的肯定是打表，打表后发现当x>=100答案数每次递增1，也就是每个x都满足条件，这样我们很容易得到...

2021-07-19

8 685