题解p2951 usaco open
USACO23DEC Pt T3
首先要把 A 和 B 分别按顺序排序,然后有一个显然的思路是记录 $dp_{i,j,k,l,0/1,0/1}$ 表示 A 做到 $i$,B 做到 $j$,当前时刻是 $a_k+l\times T$,是 $a_k$ 还是 $b_k$,上一个走的 A 还是 B 的最小答案,转移比较简单,复杂度 $O(n ......
百度之星2023决赛简要题解
A 找矩阵 #include<bits/stdc++.h> #define I using #define love namespace #define Elaina std I love Elaina; const int N=3010; int read(){ int x=0,f=1; char ......
CF1392H ZS Shuffles Cards 题解
题目链接 点击打开链接 题目解法 很牛逼的概率题,参考了题解区 定义取到鬼牌,重新洗牌,为一轮 则 \(ans=E(\)轮数\()\times E(\)这一轮取到鬼牌的期望步数\()\),轮数为在 \(S=\{1,...,n\}\) 之前取到鬼牌的次数 先计算 \(E(\)这一轮取到鬼牌的期望步数\ ......
USACO23DEC P
A. Cowntact Tracing 设病牛集合为 \(S\)。首先用多源 BFS 可以求出哪些位置可能初始有病,即满足 \(S_k(u) = \{v | d(v,u) \le k\} \in S\) 的所有 \(u\)。有解当且仅当这些位置全染上之后合法,这个可以再跑一次多源 BFS 看看是不是 ......
P2911 [USACO08OCT] Bovine Bones G
原题链接 题解,\(O(1)\)做法 简述 先从两个骰子入手,得出\([b+1,a+1]\)内的数出现次数最多 然后再加一个骰子相当于把分布图向右平移c个单位的过程中,每平移一个单位的长度累加和,也就是以c为宽的矩形方框的截面积 然后分类讨论,一定是把方框放在中间偏左位置是最优解 code #inc ......
CF295B Greg and Graph 题解 floyd性质题
题目链接:https://codeforces.com/problemset/problem/295/B 题目描述可参见 洛谷 解题思路完全来自 aiiYuu巨佬的博客 一道很好地利用了 floyd 算法性质的题目。 floyd算法 示例程序: #include <bits/stdc++.h> us ......
1.3模拟赛 T2题解
题目大意 有一个矩形,上面有若干个关键点,每次随机一个相邻的位置,问全部关键点被选取的期望时间 思路 设每个关键点被选取的时间为 \(t_i\) ,则答案就为 \(E(max(t_i))\) 然后我们发现 \(E(min(t_i))\) 是好求的,只需要保证在此之前全部都不被选即可,所以可以 \(m ......
1.3模拟赛 T1题解
题意 给一棵树,带点权(可为负),单点修改,求直径,求过某一点的直径 \((n<=100000)\) 思路 发现强制过某一点,可以转化为单点改成正无穷,求直径 于是就只用考虑单点修改求直径 考虑点分树,在每个重心维护到他的最长链,和不同子树中的次长链,全部答案取个max即可(但是被卡常) code ......
P4402 [Cerc2007] robotic sort 机械排序题解
题目链接:[Cerc2007] robotic sort 机械排序 前置知识点:文艺平衡树 具体的我们会将序号下标作为平衡树的键值,这样一来每个节点其实就是数组中的每个位置,又因为这个位置是具有有序性的,所以我要找某个位置的当前值是可以在树上二分出来的,同时考虑平衡树的一段子树打翻转标记,交换左右子 ......
CF1905F Field Should Not Be Empty题解
题目链接:https://codeforces.com/contest/1905/problem/F 题意简述 对一个排列 \(p\),一个下标 \(x\) 被称作“好下标”当且仅当 \(\forall y < x\) 满足 \(p_y < p_x\),且 \(\forall y> x\) 满足 \ ......
[CF594D] REQ 题解
[CF594D] REQ 题解 思路 用欧拉函数的公式来求解,可以发现,对于每一个质因数都只会做一次贡献,然后是区间查询,联想到 HH的项链 一题,考虑离线询问,按右端点排序,在树状数组里面维护最靠右的质因数的位置做贡献,然后区间积一下就有了。 注意质因数分解暴力做根号应该会爆,可以筛质数之后对质数 ......
CF676C 题解
使用尺取法(双指针法)。 由于字符种类只有 \(2\) 种,答案一定是全 a 或全 b。 情况 \(1\):全 a 快指针循环移动,并统计字符 b 的数量 \(cntb\),直到 \(cntb\) 即将超过 \(k\)。 情况 \(2\):全 b 同上。 答案即为两种情况取到的最大值。 AC cod ......
洛谷P3101 题解
输入格式 第 \(1\) 行,三个整数 \(m,n,t\)。 第 \(2\) 到 \(m+1\) 行,\(m\) 个整数,表示海拔高度。 第 \(2+m\) 到 \(2m+1\) 行,\(m\) 个整数。第 \(i\) 行,第 \(j\) 个整数表示 \(i,j\) 是否为起点。 输出格式 所有起点 ......
[USACO11OPEN] Corn Maze S
[[USACO11OPEN] Corn Maze S](https://www.luogu.com.cn/training/311806#problems)# 这道题就是一个BFS的题,因为他要求最短路径而不是方案数,还行吧,想明白了就不难。这道题如果去掉了传送门的话就太简单了,但是又了这个传送门就 ......
迷宫题解( •̀ ω •́ )y
这道题很明显是一个dfs的问题 这道题首先要在主函数里完成建造迷宫但在建造迷宫之前,你要把所有的位置标为可以去 memset(a,'.',sizeof(a)); 他给你了下标,所以你就可以直接建造迷宫,代码如下 for(int i=1;i<=T;i++){ cin>>xx>>yy; a[xx][yy ......
[USACO1.5]八皇后 Checker Challenge
这道题很明显就是用深度优先搜索,也就是DFS 那到底要怎么去DFS呢? 它说行,列,两条对角线不能在一起。所以DFS的行参就可以是行,再用一个数组存列,两个数组去存放两条对角线。(注:存两个对角线的要是行的2倍,要不然会数组越界 ) 那么还有一个问题,就是每一种方法存的答案。 可以用一个a数组去存放 ......
[ABC271E] Subsequence Path 题解
[ABC271E] Subsequence Path 题解 思路解析 很好的一道题,很有迷惑性,表面上是一道图论实际上是 dp,定义 \(f_{i}\) 为从 \(1\) 到 \(i\) 的最短 “好路”。先把每条边对应的起点,终点和边权记录下来,然后输入每个 \(e\),由于是子序列顺序不会改变, ......
CF1886C Decreasing String 题解
Problem - C - Codeforces Decreasing String - 洛谷 p.s. 本题提到的所有 \(s_i\) 的 \(i\) 均表示 \(s\) 字符串的下标,而不是第 \(i\) 个字符串。因为我懒不想改了 每次遇到这种题都想不到最好的解决方法,我是不是应该把所有比赛的 ......
HDU2544 最短路 题解 Bellman-Ford算法
题目链接:https://acm.hdu.edu.cn/showproblem.php?pid=2544 题目大意:一道简单的最短路。主要是记录一下 bellman-ford 算法的实现。 示例程序(bellman-ford): #include <bits/stdc++.h> using name ......
AT_joisc2016_k 题解
传送门 题意 通信题。Anya 和 Boris 有一棵有根树,每一天 Anya 会标记一些边,她可以给 Boris 发送一个不超过 1000 位的二进制串,Boris 要多次回答一个点到根的路径上有多少条边被标记过,他不知道这个二进制串,但是每次回答可以查看这个二进制串的 20 位。要求你给出两人的 ......
UVA10364 题解
题意简述 给定 \(n\) 根木棍,第 \(i\) 根的长度为 \(a_{i}\),求能否使用全部木棍拼成一个正方形。 题目分析 这道题和 P1120 很像,都考察了对于 DFS 的剪枝优化。 具体地,我们有以下几个剪枝策略 计算出每根木棍的长度之和,记为 \(sum\),若 \(sum \bmod ......
P2726 [SHOI2005] 树的双中心 题解
Description \(n\leq 5\times 10^4\),树的深度 \(\leq 100\)。 Solution 对于每个 \(x,y\),满足 \(d(v,x)\leq d(v,y)\) 或者 \(d(v,x)\geq d(v,y)\) 的点一定构成一个子树,所以可以枚举这个子树的根, ......
编辑文件后保存报错E212: Can't open file for writing
报错如下图: 1、编辑的时候是 root 用户,但还是有报错,退出文件查看该文件是否上了 i 锁: lsattr $文件名 查看输出显示未上 i 锁,若是上了 i 锁则会在红线上显示一个 i,有 i 锁的情况下需要执行解锁: chattr -i $文件名 2、编辑时候使用的是root用户,所以不用查 ......
CF763E Timofey and our friends animals题解
题目链接:CF 或者 洛谷 简单来说就是求 \([l,r]\) 这些点都存在的情况下,连通块的数量,看到七秒时限,而且每个点相连的边数很少,可以想到离线下来使用莫队类的算法解决 连通块问题,一般可以考虑使用并查集解决。对于并查集来说,它的增加是非常简单的,但删除是困难的,可持久化并查集时空常数都较大 ......
P8078 [WC2022] 秃子酋长题解
题目链接: P8078 [WC2022] 秃子酋长 题目所求较难理解,我们考虑转化下,首先这是个 \(1 \sim n\) 的排列,而且要求相邻对应的原位置的绝对值最大我们先考虑最简单的一种情况:\([1,n]\) 的答案。 来看这张我画的丑图。 以样例为例,如果求 \([1,n]\) 的答案,我们 ......
P9474 [yLOI2022] 长安幻世绘题解
题目链接: [yLOI2022] 长安幻世绘 比较不错的综合题。考虑下处理极差的绝对值我们应该怎么做,很显然排序是有必要的,我们需要带着下标排序。 考虑几个核心点: 1.假如没有其他限制考虑极差与序列长度有啥关系,很显然长度越长,极差单调不降,具备单调性。 2.考虑对于一个长度为 \(L\) 的连续 ......
[ABC271G] Access Counter 题解
[ABC271G] Access Counter 题解 思路 挺难的 DP。 状态里面不能含有天数,只能从时间点入手,一眼矩阵快速幂所以考虑以登录次数作为阶段设计状态。 可以得到这个DP:\(g_{i ,j}\) 表示登录 \(i\) 次,且第 \(i\) 次登录在 \(j\) 时刻的概率。 转移可 ......
「ABC334F Christmas Present 2」题解
Cnblogs 线段树优化 dp?线段树优化 dp! Solution 题目来源:ABC334F(in 洛谷| in AtCoder)题目大意很清晰就不讲了。 我们发现礼物是固定从 \(1\sim n\) 房间送的,唯一要分讨的地方就是什么时候要回去拿礼物。所以很容易想到二维 dp。 定义 \(f_ ......
CF1545C AquaMoon and Permutations 题解
题目链接 点击打开链接 题目解法 很不错的题 首先题目保证了一定有解,所以不用考虑奇怪的无解情况 从列中的数字种类入手 如果一列中有数字 \(c\) 恰好只有第 \(x\) 行存在,那么第 \(x\) 行一定在答案序列中 考虑选了第 \(x\) 行会牵连一些行不能选,那么把这些行去掉,继续跑上面的操 ......