题解1203 div cf
CF1887B Time Travel
早到可以选择停留在原地,所以我们一定会尽早地到达每一个节点,这样一定不劣。 考虑若我们最早可以在 \(t_u\) 时刻到达节点 \(u\),则对于边 \((u,v)\),我们一定会在它最早的解锁时刻由 \(u\) 向 \(v\) 扩展。实现时可以使用 dijkstra,并对每张图的出现时刻用 set ......
CF1777B题解
分析 首先计算单个排列中的逆序对数量。 我们发现这东西可以分为两类,一类是两个数在原排列和倒着的排列(这里称为“反排列”),另一类是两个数一个在原排列,一个在反排列的。 对于第一类,我们发现,原排列中的顺序对是反排列中的逆序对,所以原排列的所有数对要么在原排列中是逆序对,要么在反排列中是逆序对,所以 ......
题解 UVA437
题解 UVA437 每种方块都可以将 \(x\times y,x\times z,y\times z\) 的面放在水平面上,所以每块都有 \(3\) 种状态,每次从剩余所有 \(n-1\) 个块的 \(3\) 种状态中选取能放置在此方块上方的方块,(即选取水平面矩形对应的边小于当前水平面边权),并且 ......
CF1777A题解
分析 发现操作2不会改变数的奇偶性,故无视。 那么操作就是单纯删一个数。 对于一个连续出现 \(x\) 个奇偶性相同的数的序列,需要删 \(x - 1\) 个数(因为只剩下一个数就不会和相邻的数奇偶性相同了)。 觉得找序列太麻烦,观察到连续出现 \(x\) 个奇偶性相同的数的序列有 \(x - 1\ ......
CF1523D Love-Hate 题解
抽象化题意: 一共有 \(m\) 个元素,给定 \(n\) 个集合,每个集合的元素不超过 \(15\) 个,求出一个元素个数最多的集合 \(S\) 是至少 \(\lceil \dfrac{n}{2} \rceil\) 个集合的子集。 其中$ p $ $ (1 \le n \le 2 \cdot 10 ......
2023级HAUT新生周赛题解汇总
2023级HAUT新生周赛(零)熟悉周赛规则专场: 2023级HAUT新生周赛(一)@21级学长专场(张子豪,张鑫,李昊阳): 2023级HAUT新生周赛(二)@曹瑞峰专场: 2023级HAUT新生周赛(三)@22级学姐专场(杨焱,刘振歌,周欣滢): 2023级HAUT新生周赛(四)@牛浩然专场: ......
Educational Codeforces Round 127(CF1671 D~E) 题解
D. Insert a Progression 题目链接 可以瞪出来的一个结论就是当我们在位置 \(p\) 插入了一个数 \(x\) 时,如果存在一对 \(l,r\) 满足 \(l<p\),\(r>p\) 且 \(x\in[a_l,a_r]\),那么我们插入的这个 \(x\) 就不会对序列的答案产生 ......
JWT Tool:针对 JSON Web Tokens 的测试工具题解JWT cracking
什么是JWT? JWT是JSON Web Token的缩写,它是一串带有声明信息的字符串,由服务端使用加密算法对信息签名,以保证其完整性和不可伪造性。Token里可以包含所有必要的信息,这样服务端就无需保存任何关于用户或会话的信息了。JWT可用于身份认证,会话状态维持以及信息交换等任务。 JWT由三 ......
CSP20230917-3 梯度求解 题解
〇、题目 太长了懒得写。 简单来说就是求对于一个后缀表达式,每个询问给出一个下标和一些值,求以该下标变量为自变量其它变量为常数时的偏导数。 一、思路 考虑直接对于表达式建出表达式树。 建树的过程比较直接:每次栈里面放节点编号,遇到符号就取出当前栈顶两个节点作为子节点。 每次查询直接对整棵树爆搜,因为 ......
Codeforces Round 886 (Div. 4) 题解
link 我为什么还要 vp div4 场。。。 A 直接找最大的两个判断一下。 void solve() { int a[3]; cin >> a[0] >> a[1] >> a[2]; sort(a, a + 3); if(a[2] + a[1] >= 10) cout << "YES\n"; ......
P3657 题解
是不是有点恶意评分了 题目链接 Sol 看完题目就想到了这个题。 这道题同样是求线段,不过这个加了点限制,发现一个点最多连 4 条边出去,暴力连边的复杂度是正确的,于是就把这题变成黄了。 利用刚刚那道题的 trick,把边按左端点排序后右端点的 LIS 就是答案。 这里给一个更方便的做法,不用真的去 ......
CF466E
题目传送门 这个人只会做这种水题了。。。 Solution 直接做显然不太好做,考虑把询问离线下来在静态森林中查询。 对于操作 1,直接连边就可以了。 对于操作 2,容易发现能看到这个文件的一定是一条从祖先到子节点的一条链,记录这个文件被看到的链顶和链底即可。 对于操作 3,只需要知道 \(x\) ......
P9681 幽默的世界。 题解
题目传送门 这个人想不出普及组做法。。。 Solution 不难发现符合题目要求的序列是最后一个数为正数,前面的数都为负数,且全部加起来大于等于 0。 考虑对于每一个右端点,都求出他往前能到的左端点,满足这一段的和大于 0 且只有右端点是正数。 显然前面一段负数的前缀和有单调性,直接二分就可以求。 ......
P9753 [CSP-S 2023] 消消乐 题解
考前天天祈祷不考串串和数数结果靠这个翻盘好好好。 为什么都说 D 比 B 简单。 题目传送门 Solution 按照一般的计数 dp 的状态设计,我们不妨设 \(f_i\) 为以 \(i\) 为右端点的合法子串个数。 最后答案是 \(\sum_{i=1}^{n} f_i\)。 考虑合法的子串有哪几种 ......
Codeforces Round 905 (Div. 3)
Codeforces Round 905 (Div. 3) A. Morning 解题思路: 首先\(4\)个数字都要打印出来,所以\(ans\)起始值为\(4\)。 接着就是从左向右移动绝不回头,鼠标移动的距离和就是两两数字之差。 注意:这里\(0\)位置其实是\(10\). 代码: #inclu ......
P2679 [NOIP2015 提高组] 子串 题解
#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1000000007; int n,m,k,dp[205][205][2]; char A[1005],B[205]; signed ......
P9754 [CSP-S 2023] 结构体 题解
考前内心 OS:“CCF 不会出大模拟吧(((”。 前置声明 辅助函数:偏移量 考虑一个结构体的偏移量。已知首个空地址 \(\mathrm{address}\) 和该结构体的对齐要求 \(\mathrm{align}\),则该结构体正确的起始地址为 \(\mathrm{\lceil address ......
CF1710 题解
CF1710 题解 A 看图写话。 想象一个格子以及周围同色格的颜色必须呈一个三叉的形状: # # # ## ## ### ### # # # 这些三叉拼起来最小的形状,就是两个以上的整行,或整列。所以遍历每一种颜色,通过整除观察它最多能填几列,如果 \(1\) 列就不能放,如果奇数列就要看是否一个 ......
CSP-S 2023 游记 & 总结 & 题解
游记 到了机房发现是 Windows10,感觉不错。 比赛开始果断启动虚拟机,怎么今年PDF密码这么复杂啊,我记得去年挺简单的来着,好像是 believe2022 ? 看了一遍题,有理由怀疑 T1 是 J 的题,但是一开始读错了,以为只能转一下,后来计算转动幅度的时候忘记对 \(10\) 取模,怒调 ......
Codeforces Round 905 (Div. 2) D1. Dances (Easy version)(贪心+二分)
Codeforces Round 905 (Div. 2) D1. Dances (Easy version) 思路: 对于 \(a\),它的头默认为 \(1\),则 \(a_0\) = \(1\) 对于排完序的 \(a\) 与 \(b\) 数组 最优为从 \(a\) 的结尾删除,从 \(b\) 的 ......
CF1887C Minimum Array
CF1887C Minimum Array 小丑做法。 首先差分一下,转化成两次单点加。每次考虑前 \(i\) 位,然后一直维护当前合法的时刻区间,这个东西怎么做呢?可以离线下来记录每个点被那些操作波及,然后算一遍前缀和,对于合法的区间区间打标记。需要支持区间加 \(1\) 和查询最大值,用线段树维 ......
「解题报告」Codeforces Round 905 (Div. 3)
A. Morning You are given a four-digit pin code consisting of digits from \(0\) to \(9\) that needs to be entered. Initially, the cursor points to the ......
【题解】CF1710 合集
CF1710A Color the Picture 标签:思维题 \(C^-\) 典型的有图有真相,嘻嘻(抽风了? 显然有一个结论,我们颜色要么一行一行天,要么一列一列填。 并且填进去的颜色必须不少于两行/列 然后就是记一个 ans 和 一个 over 表示如果每个颜色都两行/列填进去能填的最多列数 ......
Codeforces Round 905 (Div. 2) C. You Are So Beautiful(数据结构)
Codeforces Round 905 (Div. 2) C. You Are So Beautiful 定义: 设数组 abcd 子数组定义:从原数组砍去前面若干元素,后边若干元素,剩余的数组。如:bc、ab 子序列定义:从原数组删除若干元素,剩余元素拼凑一起,组成的数组。如:ac、bd 思路: ......
CF16A
CF16A Flag \[\large \text{Seek the truth from facts.} \]\[\large \text{实事求是} \] \[\mathtt{\text{2023.10.23 星期一}} \]\[\text{Program Difficulty = }\colo ......
CF5A
CF5A Chat Server's Outgoing Traffic \[\large \text{Seek the truth from facts.} \]\[\large \text{实事求是} \] \[\mathtt{\text{2023.10.22 星期六}} \]\[\text{Pr ......
Educational Codeforces Round 144(CF1796 D~E) 题解
D. Maximum Subarray 题目链接 十分钟秒了一道 *2000,非常爽,但是个人感觉确实非常简单。 下面令 \(b_i=a_{i}-x\),\(b_i'=a_i+x\) 。 因为 \(k<=20\),因此考虑一个复杂度与 \(k\) 相关的做法。 不妨 dp:设 \(f_{i,j,0/ ......
CF1893E题解
分析 第一眼:博弈论。 第二眼:呃……贪心? 实际:DP。 首先想这个游戏大抵存在必胜策略,否则不会让我们求。 思考先手必胜条件,就是如何让这个数组最后只剩下一个数。 设数列之和为\(sum\)。 发现每次操作给两个数减的数字是一样的。那么对于每次操作,\(\Delta sum\)都为两者之间更少的 ......
Codeforces Round 905 (Div. 3)
E. Look Back 因为每次都是2,可以推出x<=y2^(n),转化成 x/y<=2^(n),求n直接取对数即可 注意: 1.答案很大要开LL 2.不要直接乘,会爆LL,直接利用原式即可,如果后面的大,就减去大多少的对数 3.记得向上取整 点击查看代码 #include<bits/stdc++ ......
CSP-S 2023 种树-题解
CSP-S 2023 种树-题解 闲话 Mark.Down看错题面了,我一直以为树是倒着长的。 题目描述 给定一棵树,每天可以选择一个与已种树的地块相连的地块种树,每棵树每天会长\(max(1,c_i\times x+b_i)\)米(\(x\)代表从任务开始第一天的天数),问最少多少天可以使\(\f ......