atcoder digit 060d arc
【杂题乱写】AtCoder-ARC115
AtCoder-ARC115_F Migration * 把问题转化成在某个限制 \(mid\) 下求初始局面和最终局面能到达的最小代价局面,如果相等则说明可达。 比较局面的方式是比较权值,如果相等按字典序比较。 对每个节点 \(u\) 求出权值比 \(u\) 小或权值与 \(u\) 相等且编号比 ......
[ARC140B] Shorten ARC 题解
分析 自然,我们可以想到利用贪心去解题。 我们可以证明,$\texttt{ARC}$ 左右两边 $\texttt{A}$ 和 $\texttt{C}$ 个数多的比少的变为 $\texttt{R}$ 贡献能更多,第奇数次操作比第偶数次能使操作次数更多。 于是,我们可以得出这样的一个算法: 若为奇数次操 ......
Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) 赛后总结
Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) 赛后总结 可悲的是:我没来得及写题解。 Task A Same 秒切。 直接输入排一遍序再遍历即可。 #include <bi ......
HHKB Programming Contest 2023(AtCoder Beginner Contest 327) 赛后总结
HHKB Programming Contest 2023(AtCoder Beginner Contest 327) 赛后总结 又没来得及写题解。。。 赛时 A - ab 查找 ab 和 ba,只要其中一者存在就行。 #include <bits/stdc++.h> using namespace ......
HHKB Programming Contest 2023(AtCoder Beginner Contest 327)
HHKB Programming Contest 2023(AtCoder Beginner Contest 327) A - ab int main() { IOS; string s; cin >> n >> s; bool f = false; for (int i = 1; i < n; + ......
HHKB Programming Contest 2023(AtCoder Beginner Contest 327)
HHKB Programming Contest 2023(AtCoder Beginner Contest 327) A. ab 解题思路: 模拟即可。 代码: #include <bits/stdc++.h> using namespace std; using ll = long long; ......
AtCoder Beginner Contest 327
A - ab (abc327 A) 题目大意 给定一个字符串\(s\),问是否包含 ab或ba。 解题思路 遍历判断即可。 神奇的代码 #include <bits/stdc++.h> using namespace std; using LL = long long; int main(void) ......
Atcoder Grand Contest 016
给我贺完了? A - Shrinking 给定一个串 \(s\),每次可以进行如下操作: 记串长为 \(n\). 构造长为 \(n-1\) 的串 \(s'\),满足 \(s'_i\) 为 \(s_i\) 或 \(s_{i+1}\),令 \(s\leftarrow s'\). 问使 \(s\) 中所有 ......
AtCoder Beginner Contest 326 (ABC326)
A. 2UP3DOWN 直接模拟即可。 Code B. 326-like Numbers 枚举,每次拆除百、十、个位,再判断。 Code C. Peak Description 数字线上放置了 \(N\) 个礼物。第 \(i\) 个礼物放置在坐标 \(A_i\) 处。 可以在数轴上选择长度为 \(M ......
CF1866D Digital Wallet 题解
Problem - 1866D - Codeforces Digital Wallet - 洛谷 不妨为选数钦定一个顺序:不同行之间无影响,列从左到右取一定不劣。 设计状态:设 \(dp_{i,j}\) 表示前 \(i\) 次操作操作到第 \(j\) 列的最大答案 转移:因为对于同一列不互相影响, ......
AtCoder Beginner Contest(abc) 315
B - The Middle Day 难度: ⭐ 题目大意 在某颗星球上一年有n个月, 给定每个月的天数, 设一年的总天数是m, 请问第m/2(小数向上取整)天是第几个月的第几天; 解题思路 数据不大, 暴力即可; 神秘代码 #include<bits/stdc++.h> #define int l ......
AtCoder Beginner Contest 224 H Security Camera 2
洛谷传送门 AtCoder 传送门 直接糊一手线性规划对偶板板。 要求: \[\min \sum A_i l_i + \sum B_i r_i \]\[\forall i, j, l_i + r_j \ge C_{i, j} \]\[l_i, r_i \ge 0 \]\[l_i, r_i \in \ ......
ARC159F
传送门 solution 神仙 dp 题。 下文认为 \(n\) 是题目中给定 \(n\) 的两倍。 先考虑一个给定的序列是否能被消除的条件。 猜测一下应该是 序列长度是偶数 不存在一个数,在序列中出现超过 \(\lfloor\dfrac{n}{2}\rfloor\) 次,其中 \(n\) 是序列长 ......
[ARC104F] Visibility Sequence 题解
题意 对于一个长度为 \(N\) 的序列 \(H\),可以通过如下方式构造一个序列 \(P\): 若存在 \(j \in \left[1, i\right)\),使得 \(H_j > H_i\),则 \(P_i = \max\limits_{j \in \left[1, i\right) \land ......
[ARC122E] Increasing LCMs
Problem StatementWe have a sequence of $N$ positive integers: $A_1,A_2,\cdots,A_N$. You are to rearrange these integers into another sequence $x_1,x_2 ......
[ARC122D] XOR Game
Problem StatementThere are $2N$ integers written on a blackboard. The $i$-th integer is $A_i$. Alice and Bob will play a game consisting of $N$ rounds ......
[ARC104E] Random LIS 题解
题意 给定一个长度为 \(N\) 的序列 \(A\),按照下列方式生成一个长度为 \(N\) 的序列 \(X\): \(\forall i\in[1,n]\),\(X_i\) 在 \([1,A_i]\) 中的整数中均匀随机生成。 求其最长上升子序列长度的期望,对 \(10^9+7\) 取模。 \(1 ......
[ARC098F] Donation 题解
[ARC098F] Donation 题解 题目描述 给定一张 \(n\) 点,\(m\) 边的无向图,到达一个点需要拥有 \(a_i\) 的权值,对于一个点操作需要消耗 \(b_i\) 的权值,询问最少需要多少权值才能够对每个点都进行一次操作(权值在任何时候都不能小于 \(0\))。 题目分析 提 ......
AtCoder Beginner Contest(abc) 314
B - Roulette 难度: ⭐ 题目大意 有一个猜数字的游戏, 有n个人参加, 每人都猜了若干个数; 最后给出答案数字; 在所有猜中数字的人中输出猜数数量最少的人的编号;(可能不止一个); 解题思路 数据不大, 暴力即可; 神秘代码 #include<bits/stdc++.h> #defin ......
ARC078F
这是一道容易想假的题(个人认为)。 首先有一个转化,我们发现直接删边不好做,我们考虑如果已经知道这条唯一路径该怎么做。我们画完图后发现,保留的图一定会是路径中的点挂着若干个路径以外的点,并且这些点可以任意互相连边,路径中不同点挂着的点集一定不能互相连边。 但是直接枚举这条路径会超时,这时候我们发现, ......
[ARC104B] DNA Sequence 题解
题意 对于一个只含有 A,C,T,G 的字符串 \(s\), 定义其为匹配的当且仅当其中 A 的数量和 T 的数量相等,C 的数量和 G 的数量相等。 给定一个长度为 \(N\) 的字符串 \(S\),求其有多少个非空子串是匹配的。 \(1 \le N \le 5000\)。 题解 \(\mathc ......
[ARC104C] Fair Elevator 题解
题意 有 \(N\) 个区间 \([a_i,b_i](a_i<b_i)\),都是 \([1,2n]\) 内的整数且互不相同(\(a_i\ne b_j,a_i\ne a_j,b_i\ne b_j\))。 现在给定一些 \(a\) 和 \(b\) 的值,剩下不知道的用 \(-1\) 表示。问是否存在一种 ......
[ARC104D] Multiset Mean 题解
题意 给定 \(N,K\) 和 \(M\)。对于每个大小在 \([1,N]\) 中的 \(x\),求每个元素大小在 \([1,N]\) 中,平均数为 \(x\) 且相同元素不超过 \(K\) 个的可重集的数量,对 \(M\) 取模。 \(1 \le N,K \le 100\),\(M\) 为质数。 ......
All Possible Digits
here 单调性:多加几次,出现的数不会变少,肯定可以二分。 最多操作\(p-1\)次,也就是最多进位一次。 而且最多只会进位一次,对于最后一位在加的过程中出现的值,直接用式子算,然后为了统计出现的数的次数,在其他位的数,如果在最后一位变化的范围里,就不应该加1。 但是题解又有不用二分的做法…… 首 ......
[ARC159F] Good Division 题解
[ARC159F] Good Division 题解 首先对于题目要求的划分方式转化一下,转化为划分的每一段都没有 绝对众数,可以证明这与题目中的要求是完全等价的,证明如下: 充分性:考虑构造一种操作方法,就是每次操作都消去一个出现次数最多的数,按照这样操作可以保证每次操作之后该区间仍然不会出现绝对 ......
ARC167 | 宿命
ARC167 A. 题目明示,让每组的和尽可能平均就是平衡。 那相当于 \(a\) 升序排序后,前 \(2(n-m)\) 个数首尾配对成组,其余数单独成组即可。 题解有一个值得借鉴的技巧,补 \(0\) 使得 \(a\) 长度为 \(2m\)。 \(\color{green}{\checkmark} ......
AtCoder Beginner Contest(abc) 313
B - Who is Saikyo? 难度: ⭐ 题目大意 选择有n个人, 给出m个强弱关系, 例如a比b强, 这种强弱关系是可以传递的, 如果b比c强, 那么a就b强; 请问这n个人中最强的是谁, 如果根据给出的强弱关系无法确定最强者, 那么就输出-1; 解题思路 我们可以用建树的思想找入度即可, ......
题解 [ARC149B] Two LIS Sum
题解 [ARC149B] Two LIS Sum 大胆猜结论,按照 \(a\) 数组为关键字进行排序,求更改后 \(b\) 的 \(LIS\) 。 证明:每次移动,都有 \(a\) 中增加一个长度, \(b\) 中贡献可能为 \(\{-1,0,1\}\) , 总体贡献为 \(\{0,1,2\}\) ......
AtCoder Beginner Contest 326 F
F - Robot Rotation 一句话不开LL,见祖宗 感谢大佬,和洛谷上的题解 上面已经将的很清楚了,但是如果你跟我一样一开始看不懂他们的代码,那么这篇可能为你解惑 点击查看代码 #include <bits/stdc++.h> using namespace std; #define LL ......