置顶文章

5.5k 字 5 分钟

# 2022.9 # 2022.9.6 今天上午做了 zhx 的题目，太 “可爱” 了，第一题和第三题都是给了代码，要用复杂度更低的代码实现以上代码所表示出来的操作，却发现 T1 题目中给出的代码在本地评测时，开个O2O_2O2​ 就过了，哪怕不开也有 80 分，T3 是最起码有 40 分的低保，最起码是个人都能敲出 60 与 80 分的，奈何我太傻了， 80 分的特殊性质没用前缀和做┭┮﹏┭┮。T2 与不等式有关，直接一眼差分约束，结果发现是个 DP，服了，T4 好像貌似是个 二分搜索 + 状压 ，可惜我只会暴力（结果暴力还没敲出来）。 今天开始补题（线段树，树剖，平衡树啥的），明天还得听...

精选分类

笔记

2 个子项，6 篇文章

题解

6 个子项，12 篇文章

文章列表

1.5k 字 1 分钟

# 前言 为了回顾题目内容，帮助同学学好编程，所以写了这篇博客，有问题请提出，感谢。 # A 输入输出 # 题面：ccc 正在完成他的老师布置给他的作业，作业的内容是：给你两个变量 x，y，与公式：S=(x∗y+x/y)∗(xS=(x*y+x/y)*(xS=(x∗y+x/y)∗(x%y−y)y-y)y−y)。 现在请你对于任意给定的x，yx，yx，y，输出SSS...
356 字 1 分钟

# 逆序对 # 概念 设i<ji<ji<j，且有ai>aja_i>a_jai​>aj​，则称这样的二元组(i,j)(i,j)(i,j) 为逆序对。 人话：整数序列中两个相邻的数，如果后面的数小于前面的数，则称这两个数值构成了一个逆序对。 # 寻找方法 找逆序对有三种常用方法...
718 字 1 分钟

# 排序 # 0、前言 我们常用的排序算法有十种。   通常分为以下两类： 比较类排序： 通过比较来决定元素间的次序，时间复杂度为 O (nlogn)~O (n2n^2n2)。 非比较类排序： 不通过比较来决定元素间的相对次序，时间复杂度可以突破 O (nlogn)，以线性时间运行。 排序算法的稳定性: 排序算法的稳定性是指在排序过程中，如果两个元素相等，它们在排序前后的相对位置是否保持不变。稳定的排序算法可以保证相等元素的相对顺序不变，而不稳定的排序算法则可能会改变相等元素的相对顺序。 说明 以下讲解排序时，目的都是为了从左往右越来越大。 # 1. 冒泡排序 # 1.1...
2.8k 字 3 分钟

# [USACO18JAN] Rental Service S 看题意很明显贪心可做，那么咱们就贪心做。 先根据产奶量从高到低给牛排序，有一个很直观的想法就是，如果是卖这个牛所挤出来的牛奶 所赚得的钱还没有 把这头牛卖了赚的钱多，那么咱就把这个牛给卖了，但是考虑一件事就是把他卖了，之后有个产奶量更少的，但正好想要租牛的邻居都已经租完牛了，那么咱只能把之后的那头奶牛拿去挤奶了，很明显这种方法没有咱们现在把这头牛不卖了更优秀～～（蚊子再小也有肉）~~。 把租户所出价格从低到高排序。 当奶牛个数多于租户的数量时，那我们就从 (n−q)(n-q)(n−q) 开始，然后开始按照上面的方法开始对比，第...
1.8k 字 2 分钟

# [USACO18JAN] MooTube G 题意： 给出一棵 nnn 个点的树及每条边的边权，定义任意两个点的熟悉度为连接这两个点的路径上边权的最小值。再给出 QQQ 个询问，每次询问给出数对（ki,vi）（k_i,v_i）（ki​,vi​），要求计算出有多少个节点与节点 viv_ivi​...
2.6k 字 2 分钟

题面: P 国的国土可以描述为有一张 nnn 个点 mmm 条的无向图，其中每个点表示 P 国的一座城市，编号为 1,2,…,n1,2,\dots,n1,2,…,n，每条边表示 P 国的一条道路，编号为 1,2,…,m1,2,\dots,m1,2,…,m。 P 国的每条道路都有一个宽度 wiw_iwi​，而一辆宽度为 xxx 的车能从城市 iii 走到城市 jjj 当且仅当存在一条从 iii 到 jjj 的路径使得路径上所有边的宽度都 ≥w\ge w≥w。 现在 P 国可能会有一些车辆无法从某个城市到达另一个，这时这些车辆便会投诉国王小 P，所以小 P...
1.4k 字 1 分钟

# [USACO18JAN] Cow at Large G 题意： 给定一个迷宫，构成一棵有根树，你开始在根节点，出口是每个叶子节点，L\text{L}L 可以在每个出口放一个守卫，每 1个 单位时间内，你和守卫都可以移动到相邻的一个点，如果某一时刻 守卫与你相遇了（在边上或点上均算），则你将被抓住。问为了保证抓住你，L\text{L}L 最少需要几个守卫。 解法： 在你屁股后面追的永远都追不上你，所以只用考虑往前走，对于一个节点 iii ，如果这个在 iii 的子树中中距离 iii...
3.5k 字 3 分钟

# 函数调用 操作三的存在就相当于给操作建了一个树，那先想没有操作三。没有操作三，那每个操作之间都是独立的，一次操作二可以使前面的加法翻倍，那么就倒着做，算出这个操作一所带的乘法系数。 那么加上了操作三，就大概以操作三为根节点，他所包含的函数为叶子节点，进行一次拓扑排序，得到拓扑序，那就可以倒着做，把乘法系数往上传递，最后得到这个操作三的总的乘法系数。 Code void toposort(){ for(int...
2.7k 字 2 分钟

# CF438D The Child and Sequence # 题面 给定数列，区间查询和，区间取模，单点修改。 (1≤n,m≤105) (1≤a[i]≤109)(1\leq n,m \leq 10^5) \ (1\leq a[i] \leq 10^9)(1≤n,m≤105) (1≤a[i]≤109) # 解法 看到这个数据范围和题目要求很明 `...
2.7k 字 2 分钟

# Atcoder ABC300 # E - Dice Product 3 # 题面 你有一个整数 1 和一个骰子，骰子以相等的概率显示出介于 111 和 666 之间的整数。当你的整数严格小于 NNN 时，你重复下面的操作掷骰子。如果骰子显示xxx ，则将你的整数乘以 xxx 。求你的整数最终是 NNN 的概率 (模为 998244353998244353998244353 ) 如何求模数为 998244353 的概率？ 我们可以证明所求的概率总是有理数。此外，在本题的限制条件下，当该值表示为 PQ\frac{P}{Q}QP​ 与两个共质整数 PPP 和 QQQ...