牛客练习赛122
黑白配
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> cnt(2);
for (int i = 1; i <= n; i++)
{
cnt[0] = cnt[1] = 0;
for (int j = 1; j <= m; j++)
{
int x;
cin >> x;
cnt[x]++;
}
cout << abs(cnt[0] - cnt[1]) << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
映射
解题思路:
按题意模拟，无冲突就有解。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
vector<int> v(n + 1, 0);
for (int i = 1; i <= n; i++)
{
if (v[a[i]] == 0 || v[a[i]] == b[i])
{
v[a[i]] = b[i];
}
else
{
puts("No");
return;
}
}
puts("Yes");
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
马走日
解题思路:
从\((3, 4),(4, 3)\)开始所有点都可以到达。\((3,3)\)以内分类讨论即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
ll n, m;
cin >> n >> m;
if (n == 1 || m == 1)
{
cout << 1 << endl;
}
else if (n == 2 || m == 2)
{
if (n == 2)
{
cout << (m - 1) / 2 + 1 << endl;
}
else
{
cout << (n - 1) / 2 + 1 << endl;
}
}
else if (n == 3 && m == 3)
{
cout << 8 << endl;
}
else
{
cout << n * m << endl;
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
圆
解题思路:
拆环成链。
注意，将链的长度应是\(2n\)，因为\((1, n)\)体现在环上可以是\((1,n),(n,1)\)，于是线段变为区间。
问题转换：使得序列中长度为\(n\)的连续区间段中无线段相交的线段集合的最大价值是多少。
我们通过区间\(dp\)找到区间不相交的最大价值线段集合。
\(dp[i][j]:区间[i,j]选取两两或互不相交，或被完全包含的线段，线段权值总和的最大值\)。答案就是所有线段价值减去这个最大值。
状态转移：
-
考虑不选左端点的解\(dp[i][j] = dp[i + 1][j]\)。
-
对于当前区间\([i,j]\),枚举以点\(i\)为左端点的所有线段\([i, r]\),改线段权值为\(w\)。
-
如果该线段存在覆盖区间，即\((i + 1 < r - 1)\)，我们要加上被覆盖区间的最优解\(w + dp[i + 1][r - 1]\)。
-
如果能通过拼接得到当前线段，即\((r + 1 < i)\)，我们进行拼接\(w + dp[r + 1][i]\)。
最后更新当前区间最优解。\(dp[i][j] = max(dp[i][j], w)\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 5e3 + 10;
ll dp[N][N];
vector<pii> e[N];
void solve()
{
ll n, m;
cin >> n >> m;
ll s = 0;
for (int i = 1; i <= m; i++)
{
ll a, b, c;
cin >> a >> b >> c;
if (a > b)
{
swap(a, b);
}
e[a].emplace_back((pii){b, c});
e[b].emplace_back((pii){a + n, c});
s += c;
}
// 枚举右端点
for (int i = 1; i <= 2 * n; i++)
{
for (int j = i - 1; j >= 1; j--)
{
if (i - j + 1 > n)
{
break;
}
dp[j][i] = dp[j + 1][i];
// j为左端点的线段
for (auto x : e[j])
{
auto r = x.fi;
auto w = x.se;
if (r > i)
{
continue;
}
// 被覆盖了也是不会相交的
if (j + 1 < r - 1)
{
w += dp[j + 1][r - 1];
}
// 区域外不相交
if (r + 1 < i)
{
w += dp[r + 1][i];
}
dp[j][i] = max(dp[j][i], w);
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ans = max(ans, dp[i][i + n - 1]);
}
cout << s - ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
类似例题
题目大意：
给定\(n\)条线段，求一个线段集合，要求该集合中的线段任意二者之间要么完全不相交，要么一个被另一个完全覆盖，求最大的线段集合，输出该集合中线段的数量。
解题思路:
根据数据范围，离散化。
\(dp[i][j]:区间[i,j]选取两两或互不相交，或被包含的线段，线段数量的最大值\)。
状态转移:
- 考虑不选左端点或右端点的解(其实二者从其一转移即可，因为区间拼接会包含另一个可行解)。\(dp[i][j] = max(dp[i + 1][j], dp[i][j -1])\)。
- 枚举线段\((l, r)\),考虑区间拼接。\(dp[i][j]= max(dp[i][j], dp[i][r] + dp[r + 1][j])\)。
- 本题中\((i, j)\)只要是\([i,j]\)内的线段，都可看作覆盖，所以最后记得加上\([i,j]\)线段的数量。
注意：不要边遍历边更新，会覆盖需要使用的数据。延迟更新。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
vector<vector<int>> dp, e, vis;
void solve()
{
int n;
cin >> n;
vector<int> l(n + 1), r(n + 1), v;
for (int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
v.emplace_back(l[i]);
v.emplace_back(r[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
auto find = [&](int x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
};
int siz = v.size() + 1;
dp = vector<vector<int>>(siz, vector<int>(siz));
e = vector<vector<int>>(siz);
for (int i = 1; i <= n; i++)
{
l[i] = find(l[i]);
r[i] = find(r[i]);
dp[l[i]][r[i]]++;
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
e[l[i]].emplace_back(r[i]);
}
for (int i = 1; i <= v.size(); i++)
{
for (int j = i; j > 0; j--)
{
int res = 0;
// 考虑不选择左端点为j的线段
if (j + 1 <= i)
{
res = max(res, dp[j + 1][i]);
}
// 考虑不选择右端点为j的线段
// if (i - 1 >= j)
// {
// res = max(res, dp[j][i - 1]);
// }
for (auto v : e[j])
{
if (v > i)
{
continue;
}
// 考虑区间拼接
if (v < i)
{
res = max(res, dp[j][v] + dp[v + 1][i]);
}
// 接的加上vis[j][i]，即刚好覆盖[j,i]的线段的数量
}
res += dp[j][i];
dp[j][i] = max(dp[j][i], res);
ans = max(ans, dp[j][i]);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}