置顶文章

5.5k 字 5 分钟

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

精选分类

笔记

2 个子项，6 篇文章

题解

5 个子项，11 篇文章

文章列表

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...
3.5k 字 3 分钟

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

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

# Educational Codeforces Round 157 (Rated for Div. 2) # A Treasure Chest 连签到题都不怎么算 如果箱子是在钥匙的右边，那么答案就是钥匙的位置，走的过程中就得到了要是，没有任何力气的花费。 如果箱子是在钥匙的左边，那么答案就是先搬箱子，直到力气耗尽，然后继续走到钥匙，然后再走回来。 直接看代码吧 Code using namespace std;int main(){ int t; cin>>t; while(t--){ int a,b,c;...
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...
2.2k 字 2 分钟

# Atcoder ABC143 # D - Bridges # 题面 我们有两个序列 A1,…,AMA_1,\ldots, A_MA1​,…,AM​ 和 B1,…,BMB_1,\ldots,B_MB1​,…,BM​，分别由 111 和 NNN（含）之间的内格组成。 对于由 "0" 和 "1" 组成的长度为 MMM 的字符串，请考虑以下与该字符串对应的有 2N2N2N 个顶点和 (M+N)(M+N)(M+N) 条边的无向图。 如果字符串的 iii 个字符是 "0"...
9.1k 字 8 分钟

# 前导 今天就浅浅学了一下，这玩意比较看运气吧。 声明：我学模拟退火时间不长，很多需要严谨证明的地方，我都没有证明。 一张图介绍他的运行过程，随着温度的降低，跳跃越来越不随机，最优解也越来越稳定。 # 部分 1 退火算法一般是由两个部分完成的。 第一个是退火主体，找点，因为模拟退火是一个随机化算法，所以他找点也主打一个随机，所以一般模拟退火不只是做一次而是做多次。 Code void simulate_anneal(){ pair<double,double> cur(rand(0,10000),rand(0,10000));// 当前最优点...