注意到 ，于是我们可以将每一个条件当作一条边建立无向图（ 可以转为 并建立自环）。目标为将每一个点匹配一条边。第一步，不断寻找度数为 的点并将其唯一邻边和此点匹配；第二步，对于剩余的点，如果度数为 ，则无解，否则此时图必然为若干个环，对于每一个环，按同一方向匹配环上的边和点即可。维护点的度数，在
展开全文
1. 问题分析
本问题的核心在于从给定的约束中寻找一个排列。每个“步骤”（Step）对应 1 或 2 个可选的“柱子”（Pillar）。我们需要在满足每个步骤选且仅选一个柱子的前提下，确保所有柱子都被恰好使用一次。
核心约束：
规模： ，要求算法必须在线性 或 复杂度内完成。
结构： 这是一个
展开全文
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N = 1e5+5;
int n;
int cnt[N], ans[N];
vector<int&g
展开全文
本题大致题意是，给出打击柱子数量即打击次数，然后给出每次打击中可能的目标对象，然后确定一个合理的打击序列，这让我们想到了基于二分图匹配的匈牙利算法：确定一个元素的匹配值，如果匹配值已经有其他元素占领，那么让占领此匹配值的元素换一个匹配值，最终达到一个合理的匹配。代码如下：
#include<b
展开全文
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
vector<int>a[N];
展开全文
匈牙利算法 + 时间戳优化
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(), x.end()
using namespace std;
using i128 = __
展开全文
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
vector<ll>e[N];
int match[N];
bool vis[N];
bool
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
