AtCoder Beginner Contest 306 – E – Best Performances
题目链接 链接 题目大意 题目意思是，长度为n的序列，q次询问，每次输入p,w把a[p]改成y,问你前k大的元素和是多少 题解 这个题目的难点是要每次修改元素后还要求序列的前k大，这就有点麻烦了，如果使用暴力不可能能过，n,k=5e5;所以使用新的一个STL容…
Tag: 模拟
Codeforces Round 237 (Div. 2) – C. Restore Graph
题目链接 链接 题目大意 有n个房子，每个房子到其他房子最多有k条路，给你给出一栋房子到其他房子的最短距离，让你构造一个图，问你这张图构造出来是什么样的，输出a,b即a-b边长为1的路及有多少条这样的边. 题解 刚开始想的是dfs深搜,但是不知道为啥re7,然…
Manthan, Codefest 18 (rated, Div. 1 + Div. 2) – D. Valid BFS? time limit per test2 seconds
题目 题目大意 给你一堆双向边，保证能够形成一个树，再给你一个一个序列，问你这个序列和给出的边形成的树一样不？ 题目链接 链接 题解 刚开始想的是先bfs，然后计算出下一层的儿子的位置在哪，然后这个这么太难写了，所以瞅了眼题解重新写一下。思路是把bfs的顺序重…
USACO 2011 November Contest Bronze Division – 2058 – 笨拙的手指
题目链接 题目链接 题解 这道题目的坑好多，来浅浅列举一下然后就能ac了 首位是0那么肯定只能修改首位，因为原数肯定不存在前导零 如果只有一位那么是允许把首位改成0的，因为0只有一个是不存在前导零的 必须要对原串进行修改的，如果修改结果和原来的是一样的那么肯定…
2023牛客寒假算法基础集训营6-I-阿宁前往沙城
题目链接 solution 这道题目用的是dijkstra，如果边数大于最短路径，那么就可以认为我们的最短路径就是dist[n]，因为我们可以挑选一条不用的路摧毁，然后每经过以后摧毁走过的路就好，所以dist[n]就是最短1-n经过最少数目的点，因为权值是1，…
2023牛客寒假算法基础集训营5-D-小沙の赌气
solution 这道题的难点是按照顺序给出区间，然后问你每次能从1到达的位置。 错误点有一个地方，我以为是贪心到最远的地方，结果后来发现是不可以调整顺序的 正解是把每个区间都放到一个set里面，因为set会自己排序，所以根据pair的第一个值进行排序，然后将…
UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)-D – Match or Not
solution 这道题卡了好久，题目意思看了好久没看懂。题目大意是有两个字符串s,t，s的长度大于t,每次删去s比t长的那部分，从开始删除，删到结束，每次删除多的，如果每个字符都相同输出yes，否则no。 这道题的解法刚开始是想办法把字符串截断再拼接，发现每…
2023牛客寒假算法基础集训营3 G-严肃古板的秩序
这道题的解法是暴力搜索出可能，看三种情况哪种符合，dfs,bfs均可 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio&g…
2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers
2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers solution 我们先来分析一下，我们需要寻找三个数，然后满足一定的条件，由于n=5000,n的三次方的复杂度肯定是不可取的，我们就得想办法优化常数。 1.第…