JAN
Windows Subsystem for Android (WSA) 下载：在 Windows 11 上运行 Android 应用 (updated Jan 2024)
Windows Subsystem for Android (WSA) 下载：在 Windows 11 上运行 Android 应用 (updated Jan 2024) 适用于 Android™️ 的 Windows 子系统，2023 年 1 月更新：2311.40000.5.0 请访问原文链接： ......
P2898 [USACO08JAN] Haybale Guessing G 题解
题目传送门 前置知识 二分答案 | 并查集 解法 对条件的合法性判断其他题解已经讲得很明白了，这里不再赘述。这里主要讲一下用并查集实现黑白染色问题。 以下内容称被覆盖为黑色，不被覆盖为白色。 本题因为是单向染色，即从白到黑，故可类似 luogu P1840 Color the Axis 和 D 的并 ......
P3612 [USACO17JAN] Secret Cow Code S
P3612 [USACO17JAN] Secret Cow Code S 自我感想 哎，又是一道写不出来的。 完全没有这样的思路，只会笨b模拟只能得40. 解题前应该的思考 通过题目给的数据可以知道纯暴力模拟肯定爆空间。（基本否定正推） 这里根据题目所说的，其实可以知道是一个初字符串通过固定的规律形 ......
[USACO2021JAN] Minimum Cost Paths P
[USACO21JAN] Minimum Cost Paths P 题目描述 Farmer John 的牧草地可以看作是一个\(N×M\)（\(2≤N≤10^9, 2≤M≤2⋅10^5\)）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 \(x∈[1,N],y∈[1,M]\)，从上往下第 \ ......
P3071 [USACO13JAN] Seating G 题解
题意：维护两个操作，区间推平，求连续 \(0\) 的个数为 \(x\) 的最前位置。 线段树。 因为需要求连续 \(0\) 的个数，所以维护区间左边连续 \(0\) 的最大个数，区间右边连续 \(0\) 的最大个数以及区间连续 \(0\) 的最大个数。 注意修改的时候要看是修改为 \(1\) 还是修 ......
题解 LGP7294【[USACO21JAN] Minimum Cost Paths P】/ accoders::NOI 5696【棋子】
problem Farmer John 的牧草地可以看作是一个\(N×M\)（\(2≤N≤10^9, 2≤M≤2⋅10^5\)）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 \(x∈[1,N],y∈[1,M]\)，从上往下第 \(x\) 行、从左往右第 \(y\) 列的方格记为 \((x, ......
[USACO18JAN] Cow at Large P
题目链接 赛时只打了暴力。 Part1 我们考虑在什么情况下要放一个村民，我们设根节点的深度为 \(0\), 那么对于一个节点 \(u\) ,如果在其子树内有一个叶子结点 \(v\), 满足 \(dis_{u, v} \leqslant dep_u\), 那么只要在这个节点放一个村民，就可以把 \( ......
P4182 [USACO18JAN] Lifeguards P
P4182 [USACO18JAN] Lifeguards P 更好的阅读体验 提供一个比较优秀大常数的时间 \(\mathcal O(nm)\)，空间线性的做法。由于变量名冲突，本文中 \(m\) 均指题目中的 \(k\)。 推推性质，发现若区间包含了另一个区间，则一定删掉被包含的区间，正确性显然 ......
P3119 [USACO15JAN] Grass Cownoisseur G 题解
分析 大概是强连通分量里面最水的一道紫题，不过细节挺多的，做题的时候给蒟蒻震惊到了。 题目要求是从 \(1\) 走到某个点，然后再走回 \(1\) 号点，中途可逆行一次，问最多能经过几个点。 有一个明显的思路是存两个图，一个正图一个反图，正图是为了求 \(1\) 到各个点的距离，反图是为了求各个点到 ......
洛谷P3607 [USACO17JAN] Subsequence Reversal P 题解
Subsequence Reversal P 思路： 发现，翻转一个子序列，就意味着两两互换子序列里面的东西。 于是我们就可以设 \(f[l][r][L][R]\) 表示： \(\max[1,l)=L,\min(r,n]=R\) 时的最长长度。 则边界为： \(L>R\) 时， \(f=-\inft ......
洛谷P3118 [USACO15JAN] Moovie Mooving G 题解
Moovie Mooving G 设 \(f[i][S]\) 表示在第 \(i\) 场（注意是场，不是部）电影时，已经看了 \(S\) 里面的电影是否合法。 然后贪心地取 \(|S|\) 最小的状态保存。光荣 MLE 了， \(21\%\)。 发现当一场电影结束后，无论这一场是在哪里看的都没关系。 ......
[USACO17JAN] Promotion Counting P 题解
[USACO17JAN] Promotion Counting P 题解 前言 好久没写题解了，今天趁我心情好赶紧水一篇。 思路 首先拿到这题，关键词检索：子树，比 \(p_i\) 大的，树状数组！现在考虑如何去掉其他子树的贡献……emm，我直接在算贡献的时候去掉其他子树的贡献不就好了！ 当然，暴力 ......
P9019 [USACO23JAN] Tractor Paths P 题解
Description 有 \(n\) 个区间，第 \(i\) 个区间为 \([l_i,r_i]\)。保证 \(l_1<l_2<\cdots<l_n\) 且 \(r_1<r_2<\cdots<r_n\)。其中一部分区间是特殊的，输入会给定。 如果第 \(i\) 个区间和第 \(j\) 个区间相交，那 ......
P6066 [USACO05JAN] Watchcow S
prologue 这个题这么水的一个板子题。 analysis 这个题目我们正反建两条边，在跑欧拉回路的时候，看这个边是不是被走过，走过就不走，跳过这个边。如果没走，就走这条边并且标记这个边走过了。 code time #include <bits/stdc++.h> using namespace ......
洛谷P3612 [USACO17JAN] Secret Cow Code S
[USACO17JAN] Secret Cow Code S 题面翻译 奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。 给定一个字符串，让后面的字符旋转一次（每一次正确的旋转，最后一个字符都会成为新的第一个字符）。也就是说，给定一个初始字符串，之后的每一步都会 ......
一个树状数组求逆序对的进阶 [USACO17JAN] Promotion Counting P
题面就这样，就是在树上求一个逆序对但是我笨笨地求了对于每一个下属有几个上司能力比他低还一遍就写对了,结果发现看错题目了难得一遍过，但是没有完全过 ......
P9013 [USACO23JAN] Find and Replace S
前言 这是考试的时候放的一道题，考的时候没做出来。 调了一个晚上，心态爆炸，故作此篇。顺便，鸣谢泥土笨笨大佬的题解，给我的代码提供了强有力的对拍参照。 正题 首先看到题目，虽然字符串长度不超过 \(10^5\)，但是还是嫌多；再一看，至多只有52个字符。 那么从这个数据范围入手，思考可以按照变换前后 ......
题解 P9019 [USACO23JAN] Tractor Paths P
显然，对于给定的 \(l,r\)，最短路可以贪心求出，即每次走与当前区间相交且左端点最大的区间，这个可以用倍增加速。 定义 \(f_{i,j}\) 表示从区间 \(i\) 往右走 \(j\) 步后到达的区间，\(g_{i,j}\) 表示往左走的情况。 正反遍历一下即可求出 \(f_{i,1}\) 和 ......
P3101 [USACO14JAN] Ski Course Rating G
思路 晃一眼题目，这不和这道题一样吗？ 但是再仔细一看，有有些不一样，要求了起点至少到多少个点，不要求起点互通，求的也不是最小的 \(d\)，而是 \(d\) 之和。 首先，很容易地发现，这道题再去二分肯定不现实，每个点都去二分一次，所需要的时间也很恐怖。 所以我们尝试从其他的方面入手。 可以发现， ......
[USACO JAN 2011]交通灯 题解
题意很清晰，直接跑 SPFA 求最短路。 只是我们在松弛操作时，需要注意从 $u$ 是否可以到达 $v$。 怎么判断呢？ 请移步下面三个部分。 ## Part 1 先解释一下，下面点 $i$ 的信息分别为以下变量： + `color` 表示颜色， `1` 表示蓝色，`0` 表示紫色 + `num` ......
P3011 [USACO11JAN] Traffic Lights S
# P3011 [USACO11JAN] Traffic Lights S [TOC] ## 题目 ### **题目描述** 和FJ靠的最近的城市Kenosha市有 $M$条道路。(编号为$1-M$) 连接着$N$个路口 (编号为$1-N$) 。保证没有重边和自环。 从点$i$到点$j$需要的时间是 ......
P4183 [USACO18JAN] Cow at Large P 题解
### 题意分析 我们首先想到，枚举贝茜在 $x$ 点，枚举度数大于 $2$ 的点为 $y$。设 $x$ 的度数为 $a$，$y$ 的度数为 $b$。 我们首先发现每个 $x$ 点都有一个初始的贡献为 $a$ 条通往叶子的路径。 如果点 $y$ 到最近的叶子节点的距离大于到 $x$ 的点的距离（农夫 ......
[usaco2018 jan] sprinklers
# 题目 农夫约翰有一块很大的田，他正在考虑种甜玉米。经过对他农田的调查，FJ发现它形成了一个（N-1）×（N-1）的 正方形。西南角为坐标（0,0），东北角是（N-1，N-1）。在某些整数坐标的位置中有双头喷头，每一个都能够同 时喷洒水和肥料。一个在（i，j）处的双头喷头会将水洒在农田中所有在其东 ......
Tarjan例题：洛谷 P2863 [USACO06JAN] The Cow Prom S
### [在洛谷中查看](https://www.luogu.com.cn/problem/P2863) 模板题，缩完点后扫一遍就行了。 巩固基础。 ```cpp #include using namespace std; const int N = 1e4+5; int n,m,dfn[N],lo ......
「USACO2007JAN」Balanced Lineup 解题报告
# 「USACO2007JAN」Balanced Lineup [传送门](https://www.luogu.com.cn/problem/P2880) 挖个坑。。。 ```c++ #include using namespace std; int n,q,l,r,f1[50002][30],f2 ......
洛谷 P6010 - [USACO20JAN] Falling Portals P
先考虑怎么对一组询问求解答案。容易想到一种贪心策略：如果 $a_{q_i}a_i$ 的情况也类似，只不过要下落速度越慢越好。 考虑处理前一种情况，后一种情况则是镜像的。我们将 $a_j>a_i$ 的部分插入直线凸包，那么从 $i$ 开始经过的世界就是插入 $i$ 这条直线时，$i$ 这条直线右边的部 ......
洛谷 P7295 - [USACO21JAN] Paint by Letters P
考虑如果我们把这个图建出来，那么显然会得到一张平面图。根据欧拉定理 $V-E+F=C+1$，只要求出 $V,E,F$ 就能求出答案了。 $V$ 容易求得：就是 $(x_2-x_1+2)(y_2-y_1+2)$。 $E$ 也不难求，就是相邻且不同的元素对数，直接二维前缀和就可以求出。 考虑怎么求 $F ......
P8099 [USACO22JAN] Minimizing Haybales P
> $n$ 个草垛排成一排，第 $i$ 个的高度为 $h_i$，两个草垛 $i, j$ 之间能够交换当且仅当 $|h_i - h_j| \le k$，求交换任意次后字典序最小的草垛排列。 $n, k \le 10^5, h_i \le 10 ^ 9$。 一道古老的湖北省内测试题。 我们注意到对于任意 ......
P9017 [USACO23JAN] Lights Off G 题解
## Description 给定正整数 $N$，和两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为： 1. 将 $b$ 序列中的一个值翻转（即 $0$ 变成 $1$，$1$ 变成 $0$，下同）。 2. 对于 $b$ 序列中每个值为 $1$ 的位置，将 $a$ 序列中对应位 ......