“范式杯”2023牛客暑期多校训练营1 – H – Matches
题目链接 链接 题目大意 给定两个序列ai,bi,现在可以选择其中一个序列交换其中的两个数字，问经过至多一次操作后最小的|ai - bi|的总和是多少？ 题解 参考了这篇题解，可以得出我们要想把他减小，那我们必须交换两种不同形式的序列，然后问题就转换成为求若干…
Tag: 思维
“范式杯”2023牛客暑期多校训练营1 – J – Roulette
题目链接 题目链接 题目大意 有n元钱，要赚到m元。规则是第一局压1元，输了压之前压的2倍，否则继续压1元，输赢的概率都是0.5，问赢到m元的概率是多少 题解 以“输输输……输赢”为一个周期，可以赢到一块钱。因而需要经过 m 个这样的周期，有x元可以输，赚1块…
“范式杯”2023牛客暑期多校训练营1 – K – Subdivision
题目链接 链接 题目大意 给你一个无向图，n个点，m条边，你可以在任意一条边中间增加一个点，边的长度还是1，问你从1到各点距离小于等于k的点的个数最多是多少。 题解 比赛过程中只想到了这道题的一部分，想着将加点转换成断环和在叶子节点增加儿子，但是在对深度没有印…
2021 RoboCom 世界机器人开发者大赛-本科组（初赛）- 7-4 疫情防控
题目链接 链接 题目大意 n个点，m条路径，d次询问，每次锁定一个点c,给出q条边，问，q条边在锁定c点后多少条边无法连通 题解 并查集支持加一些点进去来判断是不是在一个集合，但是如果删去一个点就不知道多少个点会受影响，所以，这道题的精华就是倒过来，先将那些从…
Codeforces Round 882 (Div. 2) – C. Vampiric Powers, anyone?
题目链接 链接 题目大意 一个长度为n的数组，你可以选择序列中的一个位置，从i到m全部元素异或，然后把异或后的值放在最后，问你，能生成最大的的元素大小是多少？ 题解 我们发现，s[i]为一个序列的前缀异或和，s[i, j] = s[i] ^ s[j - 1]，…
Codeforces Round 878 (Div. 3) – D. Wooden Toy Festival
题目链接 链接 题目大意 给一个长度为n的数组，问你有三个数，x,y,z,使得min(ans, max(abs(x - ai), abs(y - ai), abs(z - ai))的值是多少？ 题解 这就相当于一个排完序的数组，然后分成三段，这三段分别是最集中…
Codeforces Round 878 (Div. 3) – B. Binary Cafe
题目链接 链接 题目大意 有 k 种商品，编号为 0 至 k−1，编号为 i 的商品的价格为2^i，问你在花的钱数不超过 n 且每种商品最多买一个（可以不买所有商品）的前提下，有多少种购买商品的方式。 某个商品只有两种情况，买还是不买，这就像二进制，从右往左，…
AtCoder Beginner Contest 306 – E – Best Performances
题目链接 链接 题目大意 题目意思是，长度为n的序列，q次询问，每次输入p,w把a[p]改成y,问你前k大的元素和是多少 题解 这个题目的难点是要每次修改元素后还要求序列的前k大，这就有点麻烦了，如果使用暴力不可能能过，n,k=5e5;所以使用新的一个STL容…
Codeforces Round 685 (Div. 2) – C. String Equality
题目链接 链接 题目大意 给你长度为n的两个字符串，你有两种操作，第一个操作你可以交换a[i], a[i + 1]，操作二，你可以将连续的k个相同的字符自增1，例如a->b, b->c,最大到z 题解 错误示范： 刚开始想的是排序一下，然后用双指针…
Codeforces Round 576 (Div. 1) – B. Welfare State
题目链接 链接 题目大意 给你一个长度为n的数列，有两个操作，1操作把第c个元素改成x，2操作把数列所有小于x的数改成x 题解 有两种写法。 第一种 简单版本，每个元素只有两种情况，如果只有2情况，那他的值的大小就是本身大小和2操作最大改的数两者之间的最大值，…