题解1203 div cf
CF1809F Traveling in Berland - 倍增 -
题目链接:https://codeforces.com/contest/1809/problem/F 题解: 对一个点,考虑怎样在 $O(\log n)$ 的时间复杂度内求出答案,联想到倍增 但是,倍增合并的时候只能在两个状态相同的情况下合并,但是如果我们直接从 $i$ 到 $i+1$ 这样算的话, ......
中国石油大学(北京)第三届“骏码杯”程序设计竞赛题解
中国石油大学(北京)第三届“骏码杯”程序设计竞赛题解 感谢大家的参与,我是本次比赛所有$10$道题目的出题人,在接下来的题解中,所有C++与Python的标程均由我本人编写,因为我本人完全不懂Java,所以Java标程是由ChatGPT根据我其他语言的标程改编的,过程中由我提出改进建议,最终Chat ......
P5937 题解
前言 题目传送门! 更好的阅读体验? 提供一种不用并查集的,非常好想的做法。 思路 题目就是说给定一堆 $\sum\limits_{i=l}^r a_i \equiv w\pmod{2}$,判断哪个等式不合法。 这个形式明显可以前缀和优化:$s_r - s_{l-1} \equiv w \pmod{ ......
Codeforces Round 859 (Div. 4) 题解集
CF1807 题解集
CF1807A Plus or Minus
CF1807B Grab the Candies
CF1807C Find and Replace
CF1807D Odd Queries
CF1807E Interview
CF1807F Bouncy Ball
CF1807G1&... ......
[NOIP2013 普及组] 车站分级-题解
**题目简述:**一条单向的铁路线上,依次有编号为 $1, 2, …, n $的 $n $个火车站。每个火车站都有一个级别,最低为 $1$ 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 $x$,则始发站、终点站之间所有级别大于等于火车站$ x$ 的都必须停靠。( ......
Educational Codeforces Round 145 (Rated for Div. 2) A-D题解
比赛地址 A. Garland 1 void solve() 2 { 3 for(int i=1;i<=4;i++) 4 { 5 b[i]=a[i]=0; 6 } 7 int cnt=0; 8 string t;cin>>t; 9 set<int>st; 10 for(int i=0;i<4;i++ ......
「Gym102759B」Cactus Competition 题解
传送门 「Gym102759B」Cactus Competition 题目大意 有一个 $n \times m$ 的网格图,一个长度为 $n$ 的序列 $a$,和一个长度为 $m$ 的序列 $b$。 网格图中,第 $i$ 行第 $j$ 列的位置有一个数 $c_{i,j}=a_i+b_j$。$c_{i ......
【牛客小白月赛69】题解与分析A-F【蛋挞】【玩具】【开题顺序】【旅游】【等腰三角形(easy)】【等腰三角形(hard)】
比赛传送门:https://ac.nowcoder.com/acm/contest/52441 感觉整体难度有点偏大。 🎈 作者:Eriktse 🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持 ......
P1853 投资的最大效益 题解
题目传送门 题目大意 有初始总资产 $s$ 和债券种数 $d$,每种债券有投资额和年利息,求 $n$ 年后的最大总资产。 解题思路 完全背包问题(每种债券可以投资多次)。 把当前总资产看成背包,把债券看成物品。 枚举年数,每次做完全背包,并把最后得到的最大总资产累加,投资到下一年。 完全背包: 划分 ......
题解:【COCI2019-2020#6】 Trener
题目链接 本人于三月二十四日模拟赛本题中使用 $\mathcal O(n^2 k + n k^2)$ 哈希+DP,因神秘常数原因竟打不过 $\mathcal O(n^2 k^2)$,甚至被卡的TLE飞起,怒挂五十分。赛后交了一页的TLE,最后换成自然溢出才能过,~~铭记贰点贰叁~~。 不会吧不会吧不 ......
【思维题、KMP】P3526 [POI2011]OKR-Periodicity 题解
P3526 [POI2011]OKR-Periodicity 题解 前言 一道非常厉害的思维题。看题解得到了一些提示搞出来了。 作为 2011 年的题还是很厉害的。 约定 定义 $s[l,r]$ 为 $s$ 当中下标为 $[l,r]$ 的字符组成的子串。 $st,ed$ 表示字符串的某段前缀和后缀。 ......
训练round1题解
SMU Spring 2023 Trial Contest Round 1 A. 大意: 给出一个仅由0,1组成的字符串,该字符串是多次在首位各加0或1得到,问最短的原始字符串的长度。 思路: 一次操作增加两个字符, 特判字符串长度为1直接输出1. 首尾双指针进行判断,满足条件同时移动,不满足则退出 ......
Educational Codeforces Round 145 (Rated for Div. 2) - 题解
https://codeforces.com/contest/1809/problems A. Garland 只需要枚举颜色种类数即可。如果颜色为 $2$ 还要枚举一下颜色分布,形如 aabb 的答案为 $4$,形如 abbb 的答案为 $6$,如果形如 aaaa 无解,否则答案均为 $4$。 # ......
3 月 22 日测试题解
3 月 22 日测试题解 T1 题意 定义两个长度为 $n$ 的 01 串 $i$ 与 $j$ 的差异值 $d(i, j)$ 为: $$ \sum_{k = 0}^{n - 1}{i_k \oplus j_k} $$ 现在给你 $n$ 个 01 串的集合 $s$,你需要找到一个 01 串 $ans$ ......
CF R858 div.2
A 很简单的题,就过了 B 题意: 给定一个长度为 $n$ 的数组 $A$,你可以将其重新排序,并得到一个新数组 $B = [a_1 + a_2, a_2 + a_3, ..., a_{n-1} + a_n]$ ,使得 $mex(B)$ 最小,$mex$ 为在 $B$ 中找到一个最小的 $B$ 中不 ......
Two out of Three CF82D
给定一个序列,每次从前三个中选两个值并取他们的最大值累加,不足 3 个就取剩下的 1 个或 2 个的最大值累加, 求和的最小值以及取法。 每一次会取两个数,也就是会剩下一个数,所以我们可以把剩下的那个数来设状态 F[ i] [j ] 前i个数,剩余的数为j #include <iostream> # ......
CF1809C
我好像完全没做过啥构造题啊 =_=,这一场有一道就顺手补一下吧。 对于这种神秘的构造题,我们发现样例完全没有意义,它一定不会告诉你真正的构造方案。 一般而言,我们最终给出的构造方案总是更强一点点。对于这道题而言,比方说我们可以加一个限制:对于一个和为正的子区间 $[l,r]$ 而言,$[l,r\do ......
[ABC276G] Count Sequences 题解
考虑差分,设 $d_i=a_i-a_{i-1}$,特别的,$d_1=a_1$,那么约束就变成了 $\displaystyle\sum d_i\le m$。 对所有 $i>1$ 有 $d_i\not\equiv 0\pmod 3$。 发现 $d_1$ 非常特殊,于是可以单独考虑 $d_1\equiv ......
ARC070F 题解
前言 题目传送门! 更好的阅读体验? 牛逼构造题。 思路 代码 #include <iostream> #include <cstdio> #include <stack> using namespace std; bool query(int x, int y) { cout << "? " << ......
CF EC Round 145 D. Binary String Sorting
D 题意 给一个01串,交换两个数需要花费$10^{12}$,删除某个数需要花费$10^{12}+1$,问最少花费多少使得串单调不降 思路 线性dp,$f[i][0]$表示前i位构建的串结尾为0,单调不降的花费,$f[i][1]$同理,$f[i][2]$表示前i位构建的串结尾1的个数多于1的花费。 ......
CSP20230319-4 星际网络II 题解
〇、题目 题目描述 随着星际网络的进一步建设和规模的增大,一个新的问题出现在网络工程师面前——地址空间不够用了!原来,星际网络采用了传统的IPv6协议,虽然有 $2^{128}$ 级别的可用地址数量,但面对广袤无垠的宇宙和爆炸式增长的网络用户数,如此庞大的地址空间也面临了用尽的那一天。 新的通信协议 ......
T324159 卡空间的题目/电脑白吃 题解
https://www.luogu.com.cn/problem/T324159 题目大意: 给定一个大小为 $n$ 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 $\lfloor \frac{n}{2} \rfloor$ 的元素。 并且给定的数组总是存在多数元素。 我们现在希望使用 ......
CF1168C And Reachability 题解 线性dp
题目链接 https://codeforces.com/problemset/problem/1168/C 题目大意 给定一个数组 $a$,从下标 $x$ 能够转移到下标 $y$ 要满足 $x \lt y$ 且 $a_{p_i}, &, a_{p_{i+1}} > 0$,其中 $&$ 表示逻辑与。多 ......
【ACM算法竞赛日常训练】DAY2题解与分析【比赛】【数学考试】【简单瞎搞题】
DAY2共三题: 比赛(概率) 数学考试(前缀和与思维) 简单瞎搞题(dp) 视频讲解:https://www.bilibili.com/video/BV1hP411o7RD/ 🎈 作者:Eriktse 🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️ ......
CF1572C Paint
CF1572C Paint 一看感觉很有 dp 的感觉。所以就来吧。 设 $f_{l,r,c}$ 表示区间 $[l,r]$ 选了颜色 $c$ 的答案,先不管怎么转移。 状态太巨大,有种猜结论的冲动:若只保留 $c=a_l$ 和 $c=a_r$,答案依旧正确。 考虑证明:答案只和 $f_{1,n}$ ......
P3489 [POI2009]WIE-Hexer 题解
一、题目描述: 大陆上有 n 个村庄,m 条双向道路,p 种怪物,k 个铁匠,铁匠都在一个村庄里,他可会给你打造他所能打造的所有剑,特定的剑可以对付特定的怪物,每条道路上都可能出现一些特定的怪物,每条道路有一个通过时间。现在要从 1 走到 n,初始的时候你没有剑,要求在经过一条道路的时候,对于任意一 ......
Pawn CF41D
给定一个棋盘,你从最下面一行任选一个位置开始移动,每次只能向右上方或者左上方移动,求满足经过路径的权值和是 k+1k+1 (给定常数)的倍数的情况下最大权值和是多少。 #include <iostream> #include <cmath> #include <cstring> using name ......
CF1572B Xor of 3
CF1572B Xor of 3 做多了这种题,感觉好套路。。 首先观察操作性质,有一个有解的必要条件:所有值异或和为 $0$,因为每次操作不会改变 $1$ 的个数的奇偶性。然后再观察一下,发现如果从前缀异或和的角度看待这个操作会变得非常简单,大概就是 $$ s_{k-1}, s_k, s_{k+1 ......
Nebius Welcome Round (Div. 1 + Div. 2)
Preface 在课程的夹缝中补题,苦路西 不过这场的A~D极水,吃完晚饭一个小时不到就全写了,不过E转化想到了没设计好状态没写出来可惜可惜 A. Lame King SB题,显然要么往目标方向走要么停住,没有回头这一说 稍微手玩一下推一下式子即可,具体看代码 #include<cstdio> #i ......