2026小码王自招辅导Day01-思维
2026-06-29 18:58:29
发布于：广东
26阅读
0回复
0点赞
P3661 [USACO17FEB] Why Did the Cow Cross the Road S
代码演示
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 20010;
/*
* 区间结构体
* l：左端点
* r：右端点
*/
struct node{
int l, r;
} e[N];
int n, m;
/*
* 区间排序规则：
* 1. 优先按右端点升序
* 2. 如果右端点相同，按左端点升序
* 典型“区间贪心”排序方式
*/
bool cmp(const node &a, const node &b){
if(a.r == b.r) return a.l < b.l;
return a.r < b.r;
}
int main(void){
cin >> n >> m;
/*
* multiset 用来存放所有“牛的位置”
* multiset支持：
* - 自动排序
* - lower_bound（查找第一个 >= x 的元素）
* - 允许重复元素
*/
multiset<int> st;
// 输入 n 个点（牛的位置）
for(int i = 1; i <= n; i++){
int x;
cin >> x;
st.insert(x);
}
// 输入 m 个区间
for(int i = 1; i <= m; i++){
int l, r;
cin >> l >> r;
e[i].l = l;
e[i].r = r;
}
// 按右端点排序区间（贪心核心）
sort(e + 1, e + m + 1, cmp);
int ans = 0;
/*
* 贪心策略：
* 对每个区间，尽量匹配一个“尚未使用的点”
* 且该点必须落在区间 [l, r] 内
*/
for(int i = 1; i <= m; i++){
/*
* 在 multiset 中找到第一个 >= 左端点 l 的点
* 即：可能落入区间的最左候选点
*/
auto it = st.lower_bound(e[i].l);
/*
* 判断：
* 1. 找得到点（it != end）
* 2. 该点不超过右端点 r
* 满足则说明这个区间可以“覆盖/匹配一个点”
*/
if(it != st.end() && (*it) <= e[i].r){
ans++; // 成功匹配一个区间
st.erase(it); // 删除该点（避免重复使用）
}
}
cout << ans << '\n';
return 0;
}
P1209 [USACO1.3] 修理牛棚 Barn Repair
代码演示
#include<bits/stdc++.h>
using namespace std;
int m, s, c; // m:最多可以使用的木板数（切割次数= m-1），s:牛棚总长度(本代码未直接使用)，c:有牛的牛棚数量
int a[1010]; // 存储所有有牛的牛棚编号
int b[1010]; // 存储相邻有牛牛棚之间的“空隙长度”
int main(){
cin >> m >> s >> c;
// 输入每头牛所在的牛棚编号
for(int i = 1; i <= c; i++){
cin >> a[i];
}
// 将牛棚编号排序，方便计算间隔
sort(a + 1, a + c + 1);
/*
* 计算相邻牛棚之间的空档长度
* b[i] 表示 a[i] 和 a[i+1] 之间没有牛的连续空棚数量
* = a[i+1] - a[i] - 1
*/
for(int i = 1; i < c; i++){
b[i] = a[i + 1] - a[i] - 1;
}
/*
* 将空档从大到小排序
* 贪心思想：优先“切断最大空隙”，可以最大化节省木板长度
*/
sort(b + 1, b + c, greater<int>());
/*
* 初始覆盖长度：
* 从最左牛棚到最右牛棚之间的全部长度
* （假设全部连成一段）
*/
int sum = a[c] - a[1] + 1;
/*
* m块木板 = 最多可以切 m-1 次
* 每切一次，就可以“去掉一个最大的空隙”
* 每去掉一个空隙，覆盖长度减少 b[i]
*/
for(int i = 1, j = 1; i < c && j < m; j++, i++){
sum -= b[i]; // 减去当前最大的空隙
}
cout << sum << '\n';
return 0;
}
代码演示
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
/*
* e[i]：第 i 个虫洞的坐标
* x：横坐标
* y：纵坐标
*/
struct node{
int x, y;
} e[N];
/*
* ne[i]：在同一水平线上（y相同），
* i 右侧最近的虫洞（“传送后走到的下一个点”）
*/
int ne[N];
/*
* p[i]：配对关系（虫洞配对）
* p[i] = j 表示 i 和 j 互相传送
*/
int p[N];
int ans; // 最终答案：可能产生无限循环的配对方案数量
bool st[N]; //（本代码中未使用，可忽略）
/*
* 按 y 从小到大排序，如果 y 相同按 x 排序
* 作用：构建“同一水平线的右邻关系”
*/
bool cmp(const node a, const node b){
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
/*
* dfs1：模拟“走虫洞 + 传送”的路径，判断是否会形成环
*
* 参数解释：
* step ：当前走了多少步
* u ：当前所在虫洞编号
* begin ：起点
* fl ：状态标记（0表示刚进入，1表示已经移动过）
*/
bool dfs1(int step, int u, int begin, int fl){
/*
* 如果已经走过至少一步，并且回到了起点，
* 说明形成了一个环
*/
if(step != 0 && u == begin && fl == 0)
return 1;
/*
* fl == 0：当前处于“虫洞入口”，先进行配对传送
*/
if(fl == 0){
// 从当前虫洞 p[u] 传送出去
return dfs1(step + 1, p[u], begin, 1);
}else{
/*
* fl == 1：已经传送过，接下来沿 x 方向走
*/
if(ne[u] == 0) return 0; // 没有右侧虫洞，无法继续
// 走到同一行的下一个虫洞，再进入（fl变回0）
return dfs1(step + 1, ne[u], begin, 0);
}
return 0;
}
/*
* check：判断当前配对方案是否存在“无限循环”
* 即是否存在任意起点可以形成环
*/
bool check(){
for(int i = 1; i <= n; i++){
if(dfs1(0, i, i, 0)) return true;
}
return false;
}
/*
* dfs：枚举所有虫洞配对方式（暴力回溯）
*
* u：当前处理到第 u 个虫洞
*/
void dfs(int u){
// 所有虫洞都已经配对完成
if(u > n){
// 如果存在环，则计数
if(check() == true){
ans++;
}
return;
}
/*
* 如果当前虫洞已经被配对，则直接处理下一个
*/
if(p[u] != 0){
dfs(u + 1);
}else{
/*
* 枚举与 u 配对的 j（j > u）
*/
for(int j = u + 1; j <= n; j++){
if(p[j] == 0){
// 建立配对关系
p[u] = j;
p[j] = u;
dfs(u + 1);
// 回溯
p[u] = 0;
p[j] = 0;
}
}
}
}
int main(void){
cin >> n;
// 输入虫洞坐标
for(int i = 1; i <= n; i++){
cin >> e[i].x >> e[i].y;
}
// 按 y 再按 x 排序（构建“同行关系”）
sort(e + 1, e + n + 1, cmp);
/*
* 构建 ne[i]：
* 如果 i 和 i+1 在同一水平线（y相同），
* 则 i 可以直接走到 i+1
*/
for(int i = 1; i < n; i++){
if(e[i].y == e[i + 1].y){
ne[i] = i + 1;
}
}
// 从第1个虫洞开始枚举配对
dfs(1);
cout << ans << '\n';
return 0;
}
P11671 [USACO25JAN] Farmer John's Favorite Operation S
代码演示
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4e5 + 10;
ll a[N], sum[N], n, m;
/*
* solve()：处理单个测试用例
*/
void solve(){
cin >> n >> m;
/*
* 输入数组，并对 m 取模
* 将所有数限制在 [0, m-1] 内
*/
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] %= m;
}
/*
* 排序：便于后续做“环形最优区间处理”
*/
sort(a + 1, a + n + 1);
/*
* 关键技巧：复制一份数组 + m
* 用于模拟“环形数组”
*
* a[i + n] = a[i] + m
* 表示绕一圈后的等价位置
*/
for(int i = 1; i <= n; i++){
a[i + n] = a[i] + m;
}
/*
* 前缀和，用于 O(1) 区间求和
*/
for(int i = 1; i <= 2 * n; i++){
sum[i] = sum[i - 1] + a[i];
}
ll ans = 1e18;
/*
* 枚举“环形区间起点 i”
* 取长度为 n 的窗口 [i, i+n-1]
*/
for(int i = 1; i <= n; i++){
int ed = i + n - 1;
/*
* mid：当前区间的中位点（用于绝对值最小化）
* 排序数组中，最优点通常取中位数
*/
int mid = (i + ed + 1) / 2;
/*
* l：左半部分代价
* = mid * 左侧元素个数 - 左侧元素和
*
* 本质：将左侧所有数移动到 a[mid] 的代价
*/
ll l = a[mid] * (mid - i + 1) - (sum[mid] - sum[i - 1]);
/*
* r：右半部分代价
* = 右侧元素和 - mid * 右侧元素个数
*
* 本质：将右侧所有数移动到 a[mid] 的代价
*/
ll r = (sum[ed] - sum[mid - 1]) - a[mid] * (ed - mid + 1);
/*
* 当前窗口的总代价
*/
ans = min(ans, l + r);
}
cout << ans << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
return 0;
}
P1208 [USACO1.3] 混合牛奶 Mixing Milk
代码演示
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+10;
struct node{
int p,a;
}e[N];
int m,n;
bool cmp(const node &x,const node &y){
return x.p<y.p;
}
void solve(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>e[i].p>>e[i].a;
}
sort(e+1,e+n+1,cmp);
ll ans=0;
for(int i=1;i<=n;i++){
int temp=min(e[i].a,m);
ans+=temp*e[i].p;
m-=temp;
}
cout<<ans<<'\n';
}
int main(){
solve();
return 0;
}
P10135 [USACO24JAN] Potion Farming S
代码演示
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
/*
* v[u]：邻接表，存树结构
*/
vector<int> v[N];
int n;
/*
* a[i]：输入的顺序数组（表示某种节点映射/顺序需求）
* b[i]：每个节点当前“可用资源/药水/需求次数”
*/
int a[N], b[N];
int ans = 0;
/*
* dfs(u, fa)：树形DFS
*
* 返回值 f 表示：
* 当前子树“向父节点上交的未匹配需求数量”
*
* 类似：
* - 叶子产生需求
* - 内部节点尝试消化需求
*/
int dfs(int u, int fa){
/*
* 情况1：叶子节点（非1号根）
* 即：度为1且不是根节点
*/
if(v[u].size() == 1 && u != 1){
/*
* 如果当前节点还有可用资源 b[u]
* 就直接匹配一个需求
*/
if(b[u] > 0){
b[u]--; // 消耗一个资源
ans++; // 匹配成功计数
return 0; // 无需向上返回需求
}
/*
* 如果没有资源，则产生一个“未满足需求”
*/
return 1;
}
/*
* f：当前节点子树累计“未满足需求数”
*/
int f = 0;
/*
* 遍历子节点
*/
for(int i = 0; i < v[u].size(); i++){
int ne = v[u][i];
// 防止回到父节点
if(ne == fa) continue;
// 累加子树返回的未匹配需求
f += dfs(ne, u);
}
/*
* 如果子树有未匹配需求
* 尝试在当前节点 u 进行匹配
*/
if(f > 0){
/*
* 如果当前节点有资源 b[u]
* 可以消化一部分需求
*/
if(b[u] > 0){
/*
* temp：最多匹配的数量
* = min(子树需求, 当前资源)
*/
int temp = min(f, b[u]);
ans += temp; // 成功匹配
b[u] -= temp; // 消耗资源
f -= temp; // 剩余未匹配需求减少
}
}
/*
* 返回仍然未被满足的需求，向上继续传递
*/
return f;
}
int main(void){
cin >> n;
/*
* 输入 a[i]：某种节点映射顺序（题目关键构造）
*/
for(int i = 1; i <= n; i++){
cin >> a[i];
}
/*
* 建树
*/
for(int i = 1; i < n; i++){
int l, r;
cin >> l >> r;
v[l].push_back(r);
v[r].push_back(l);
}
/*
* cnt：叶子节点数量（除根1外）
*/
int cnt = 0;
for(int i = 2; i <= n; i++){
if(v[i].size() == 1) cnt++;
}
/*
* 初始化资源分配
* b[a[i]]++ 表示按输入顺序给节点分配“药水/资源”
*/
for(int i = 1; i <= cnt; i++){
b[a[i]]++;
}
/*
* 从根节点开始DFS
*/
dfs(1, 0);
cout << ans << endl;
return 0;
}
P11452 [USACO24DEC] Cake Game S
代码演示
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10; // 定义最大数组大小（500,010）
int n; // 蛋糕数量（每组测试数据）
int a[N]; // 存储每个蛋糕的价值
signed main() {
int t;
cin >> t; // 读入测试用例数量
while (t--) {
cin >> n; // 读入当前测试用例的蛋糕数量
ll sum = 0; // 初始化所有蛋糕的总价值
vector<ll> pre(n + 10, 0); // 前缀和数组（长度n+10，初始化为0）
// 读入n个蛋糕的价值，并计算前缀和
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i]; // 累加总价值
pre[i] = pre[i - 1] + a[i]; // pre[i] = 前i个蛋糕的价值和
}
ll ans = 0; // 存储玩家A能获得的最大价值
int step = n / 2 - 1; // 关键参数：玩家A总共可取走的蛋糕数（n/2 - 1）
// 枚举玩家A从左侧取走的蛋糕数量 i（0 <= i <= step）
for (int i = 0; i <= step; i++) {
// 计算当前方案下玩家A的价值：
// pre[i] = 左侧连续i个蛋糕的价值和
// pre[n] - pre[n - (step - i)] = 右侧连续(step - i)个蛋糕的价值和
// 总和即为玩家A取走的总价值
ll candidate = pre[i] + (pre[n] - pre[n - (step - i)]);
ans = max(ans, candidate); // 更新最大值
}
// 输出结果：
// sum - ans = 玩家B获得的价值（剩余蛋糕总价值）
// ans = 玩家A获得的最大价值
cout << sum - ans << " " << ans << endl;
}
return 0;
}
P2882 [USACO07MAR] Face The Right Way G
代码演示
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5050; // 定义最大牛的数量（5050头）
char a[N]; // 存储每头牛的初始方向：'F'=面朝前，'B'=面朝后
int b[N]; // 差分数组：记录翻转操作的影响（b[i]表示从位置i开始的翻转次数变化）
int n; // 牛的总数
int main() {
cin >> n;
// 读入牛的方向（1-indexed，从a[1]到a[n]）
for (int i = 1; i <= n; i++)
cin >> a[i];
int cnt = 1e9; // 记录最小翻转次数（初始化为极大值）
int k = 1e9; // 记录最优的翻转器长度K（初始化为极大值）
// 枚举所有可能的翻转器长度K（从大到小遍历：n → 1）
for (int i = n; i >= 1; i--) {
int cnt1 = 0; // 当前K(i)下的翻转次数
memset(b, 0, sizeof(b)); // 重置差分数组（清零）
int cur = 0; // 当前位置的累计翻转次数（模2：0=偶数次，1=奇数次）
// 模拟翻转过程：遍历所有可开始翻转的位置j
for (int j = 1; j + i - 1 <= n; j++) {
cur += b[j]; // 累加差分数组的影响（cur = 位置j的总翻转次数 mod 2）
// 情况1：当前牛面朝后('B')且需要翻转（累计翻转次数为偶数）
if (cur % 2 == 0 && a[j] == 'B') {
// 在j位置开始翻转长度为i的区间
b[j] += 1; // 差分数组：起始位置+1
b[j + i] -= 1; // 差分数组：结束位置后-1
cnt1++; // 翻转次数+1
cur++; // 当前翻转影响cur（相当于立即应用翻转）
}
// 情况2：当前牛面朝前('F')但需要翻转（累计翻转次数为奇数）
else if (cur % 2 == 1 && a[j] == 'F') {
// 在j位置开始翻转长度为i的区间
b[j] += 1;
b[j + i] -= 1;
cnt1++;
cur++;
}
}
// 验证剩余部分（j > n-i+1的位置）是否全部面朝前
int fl = 0; // 标记是否失败（0=成功，1=失败）
for (int j = 1; j <= n; j++) {
b[j] += b[j - 1]; // 计算差分数组前缀和（得到每个位置的实际翻转次数 mod 2）
// 检查翻转后方向是否合法：
// - 若翻转奇数次(b[j]%2=1)：'F'→'B'（非法），'B'→'F'（合法）
// - 若翻转偶数次(b[j]%2=0)：'F'保持，'B'保持（非法）
if ((b[j] % 2 == 1 && a[j] == 'F') || (b[j] % 2 == 0 && a[j] == 'B')) {
fl = 1; // 出现非法方向，方案失败
break;
}
}
// 当前K(i)方案可行
if (fl == 0) {
// 更新最优解：
// 优先选择翻转次数更少的方案
// 翻转次数相同时选择更小的K（题目要求）
if (cnt > cnt1) {
cnt = cnt1;
k = i;
} else if (cnt == cnt1 && i < k) {
k = i; // 相同翻转次数时取更小的K
}
}
}
// 输出结果：最优翻转器长度K 和 最小翻转次数
cout << k << " " << cnt << endl;
return 0;
}
有帮助，赞一个