题解atcoder agc 004
[CSP-J 2023] 公路 题解
题目传送门 一道 dp 题。 好像大家写的都是贪心,这里给出一种 dp 的写法。 在 dp 之前,我们需要明确以下几个东西: 状态的表示,状态转移方程,边界条件跟答案的表示。 状态的表示 \(dp_i\) 表示到达第 \(i\) 个站点所需要的最少钱数,\(w_i\) 表示在使用最少钱数到达第 \( ......
Dasha and Nightmares 题解
题目传送门 一道字符串题。 既然两个字符串拼接后有一种字符不能出现,那么可以枚举这个字符,我们就只需要关注没有出现过这种字符的字符串了。 剩下的字符串仅会出现 \(25\) 种字符,而我们并不关心字符串里字符的顺序,仅关心字符出现的个数的奇偶性,因此我们可以把字符串看做是一个长度为 \(25\) 的 ......
[ABC326C] Peak 题解
题目传送门 一道二分题。 首先非常显然,你选择的这个区间左端点在 \(a_i\) 上肯定更优,因此我们可以枚举左端点 \(l\)。然后剩下的就是使用二分求出有多少个 \(a_i\) 满足 \(l\le a_i< l+m\),具体可以使用 std :: upper_bound 实现。 Code #in ......
2023年11月第一周题解-------数组
1. 问题A:LY学长的随机数 解题思路 第一种思路是先去重后排序 第二种思路是先排序再去重 解题方法 暴力遍历 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #i ......
AtCoder Beginner Contest(abc) 327
B - A^A 难度: ⭐ 题目大意 给出一个数n, 问是否存在一个数m, 使mm = n; 解题思路 因为n的数据范围很大, 到1e18, 经过打表可以发现, 当m=16时就已经大于1e18了, 因为数很多所以用了__int128, 因为double会损失精度; 神秘代码 #include<bit ......
『AtCoder做题记录』I
放假之后回机房第一天,后面洛谷永久封了,第一次尝试AT 随便打打,先试试 不知道那场比赛 T1 题面: In AtCoder city, there are five antennas standing in a straight line. They are called Antenna \(A, ......
AtCoder Beginner Contest(abc) 317
B - MissingNo. 难度: ⭐ 题目大意 给定n个数, 这n个数中最小值到最大值之间缺一个数, 输出这个数; 解题思路 数据不大, 暴力即可; 神秘代码 #include<bits/stdc++.h> #define int long long #define IOS ios::sync_ ......
【杂题乱写】AtCoder-ARC115
AtCoder-ARC115_F Migration * 把问题转化成在某个限制 \(mid\) 下求初始局面和最终局面能到达的最小代价局面,如果相等则说明可达。 比较局面的方式是比较权值,如果相等按字典序比较。 对每个节点 \(u\) 求出权值比 \(u\) 小或权值与 \(u\) 相等且编号比 ......
CF689E 题解
很无语。 一开始脑抽,把交集和并集的概念搞混了。 后面猛然一想:并集?这不是大水题么。 然后 coding,ans 还忘记取模了。 回归正题,求的是 在 \(n\) 条线段中取 \(k\) 条线段,其中有多少个点被 \(k\) 条线段覆盖,求所有方案的答案和。 规约为贡献计算。 考虑点的贡献,假设本 ......
CF1651F 题解
首先是数学表达这道题 考虑第 \(i\) 个怪物。 它跑完自己的全程扣得血是: \[\sum\min\{c_j,m_{j,lst} + \Delta t \times r_j\} \]\(\min\) 有点难搞,没啥好性质。 考虑拆开为两个部分: \[\sum c_j + \sum (m_{j,ls ......
CF1838C题解
显然 \(1\) 不是质数,除二外偶数不是质数。 然后分类讨论 对于 \(m\) 为偶数,构造 \[\begin{bmatrix} 1 & 2 & 3 & \cdots & m \\ m+1 & m+2 & m+3 & \cdots & 2m \\ &&\cdot\\ &&\cdot\\ &&\cd ......
CF773A 题解
真的是蓝题?这真的不是小学数学题? 我们是要求满足(其中 \(a\) 为正确数,\(b\) 为总数) \[\frac{x + a}{y + b} = \frac{p}{q} \]的最小 \(b\)。 我们可以先把右式的分子分母变化到与 \(\frac{x}{y}\) 类似的大小。 int bs1 = ......
CF859G 题解
总结题意 显然可以转化为序列问题嘛。 给出序列 \(A\{a_i\}\),你需要通过若干次操作使其归零。 操作: 选定 \(d | n\)、\(k\)、\(r\),对于序列中所有满足 \(i \bmod d = r\) 的位置加上 \(k\)。 题解 很明显,加减相互抵消,对于所有 \(d\)、\( ......
USACO铂金题解
USACO 铂金题解 USACO 2018 Platium B. Sort It Out 很巧妙的转换 注意到操作并不会影响没有被选中的牛的相对顺序 所以没有被选中的一定单调递增 要使得选中的尽可能少,就要选尽可能长的没有被选中的序列,即原序列的 \(LIS\) 所以原题等价于求原序列第 \(k\) ......
[ARC140B] Shorten ARC 题解
分析 自然,我们可以想到利用贪心去解题。 我们可以证明,$\texttt{ARC}$ 左右两边 $\texttt{A}$ 和 $\texttt{C}$ 个数多的比少的变为 $\texttt{R}$ 贡献能更多,第奇数次操作比第偶数次能使操作次数更多。 于是,我们可以得出这样的一个算法: 若为奇数次操 ......
UVA1328题解
前情提要 本题解重在使大家理解。 本题需要 KMP,相信阅读本篇的大佬都会吧。 没学过也没关系,点这里。这是一篇我喜欢的讲解,不喜勿喷。 分析 看见本题的第一感就是会与 KMP 中的 $next$ 数组有关。 我们通过下面证明可以得出:满足 $i \bmod len = 0$,且 $S[1 \sim ......
哈理工新生赛题解
A小亮的睡眠时间 思路:求一下一共花了多少时间思考,注意思考时间大于睡觉时间上限的特殊情况。 #include <iostream> using namespace std; int main() { int n; scanf("%d", &n); int sum = 0; int cur; int ......
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 ......
CF1089K King Kog's Reception 题解
题目传送门 前置知识 线段树 解法 第一眼感觉和 luogu P1083 [NOIP2012 提高组] 借教室 很像。本题同样采用线段树维护,\(sum_{l,r}(1 \le l \le r \le 10^6)\) 表示从 \(l \sim r\) 时刻内骑士拜访的总时间,\(maxx_{l,r} ......
ABC326G 题解
blog。简单最小割。 发现 \(L_{i,j}\le5\),所以对 Level 拆点。初始源点 \(S\xrightarrow{0} \text{Lvl}1_i, S\xrightarrow{c_i} \text{Lvl}2_i,\text{Lvl}3_i,\text{Lvl}4_i,\text{ ......
[ABC327G] Many Good Tuple Problems 题解
题意 对于一对长度均为 \(M\) 且元素值在 \(\left[1, N\right]\) 之间的序列 \((S, T)\),定义其为好的当且仅当: 存在一个长度为 \(N\) 的 \(01\) 序列 \(X\),使得其满足如下条件: 对于任意 \(i \in \left[1, M\right]\) ......
CF1721A Image题解
转裁自我的洛谷博客:https://www.luogu.com.cn/blog/653832/Code-of-CF1721A-Image 题意简述 给你一个2×2的矩阵,每次可以将一个或两个字母变成任意的其他字母,问最少用几步能将矩阵中的字母变成一样的。 思路 可以先分类讨论可能会出现的情况(如下表 ......
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) ......
B3610 [图论与代数结构 801] 无向图的块 题解
题目传送门 前言 本题解内容均摘自我的 Tarjan 学习笔记 。 解法 Tarjan 与无向图 无向图与割点(割顶) 在一个无向图中,不存在横叉边(因为边是双向的)。 一个无向图中,可能不止存在一个割点。 割点(割顶):在一个无向图中,若删除节点 \(x\) 以及所有与 \(x\) 相关联的边之后 ......
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 ......