目录
- P9955 [USACO20DEC] Do You Know Your ABCs? B
- P5436 【XR-2】缘分
- P1182 数列分段 Section II
- P1032 [NOIP2002 提高组] 字串变换
- P1020 [NOIP1999 提高组] 导弹拦截
- P1077 [NOIP2012 普及组] 摆花
- T264125 黑暗能量
P9955 [USACO20DEC] Do You Know Your ABCs? B
有三个正整数 \(A\)、\(B\) 和 \(C\)（\(A\le B\le C\)）。这些数字范围在 \(1\ldots 10^9\) 之间的整数（不一定各不相同），并且是 \(A\)、\(B\)、\(C\)、\(A+B\)、\(B+C\)、\(C+A\) 和 \(A+B+C\) 的某种排列。
给定这七个整数，求出 \(A\)、\(B\) 和 \(C\)。可以证明，答案是唯一的。
输入格式：输入一行，包含七个空格分隔的整数。
输出格式：输出 \(A\)、\(B\) 和 \(C\)，用空格分隔。
in:
2 2 11 4 9 7 9
out:
2 2 7
【分析】7个数字中选3个数，匹配要求，推导一下有如下信息
\[\begin{align*} &A\le B \le C \\ &A \le B\le C, A+B \le C+ A \le B+C \le A+B+C\\ &C = A+B+C - A-B \quad \text{(^_^)} \end{align*} \]点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int main(int argc, char* argv[]) {
int a[10], n = 7;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
a[3] = a[7] - a[1] - a[2];
cout << a[1] << " " << a[2] << " " << a[3];
return 0;
}
P5436 【XR-2】缘分
一禅和师父约定一个正整数 \(n\)，接着他们各自在心里想一个不超过 \(n\) 的正整数，这两个数的最小公倍数最大会是多少。
输入格式：
多组数据，第一行一个正整数 \(T\)，表示数据组数。
接下来的 \(T\) 行，每行一个正整数 \(n\)，表示一禅和师父约定的正整数。
输出格式：对每组数据，一行一个正整数，表示答案。
in：
1
3
out:
6
【样例说明】不超过 \(3\) 的两个正整数的最小公倍数的最大值为 \(\mathrm{lcm}(2,3) = 6\)。
【数据规模与约定】
对 \(50\%\) 的数据，\(1 \le T,n \le 100\)。
对 \(100\%\) 的数据，\(1 \le T \le 100, 1 \le n \le 10^9\)。
【分析】\(a,b\le n,\quad ans = max(lcm(a,b))\)
方法1：枚举 \(a,b\)，复杂度 \(O(Tn^2)\)，得分 50；
方法2：推导一下，\(lcm(a,b) = a*b/gcd(a,b)\)，想 \(lcm\) 越大，那么 \(a*b\) 越大，\(gcd(a,b)\) 越小
\(gcd(n-1, n)=1\)，所以 \(a=n-1, b=n\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
typedef long long ll;
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
// 求 max(lcm(a,b)) = max(a*b/gcd(a,b))，则a b互质就是答案
int main() {
ll t, n;
cin >> t;
while (t--) {
cin >> n;
cout << (n == 1 ? 1 : n * (n - 1)) << endl;
}
return 0;
}
P1182 数列分段 Section II
对于给定的一个长度为 \(N\) 的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq N\)）段，并要求每段连续，且每段和的最大值最小。
in:
5 3
4 2 4 5 1
out:
6
【数据规模与约定】
对于 \(20\%\) 的数据，\(N\leq 10\)。
对于 \(40\%\) 的数据，\(N\leq 1000\)。
对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超过 \(10^9\)。
【分析】最大值最小，典型二分答案
二分左边界 x, chk 当最大值 x 的时候是否合法
思考 是否需要 long long
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, a[N];
// 最大值 x 的情况下能否分出至多 m 段
bool chk(int x) {
int s = 0, t = 0;
for (int i = 1; i <= n; i++) {
if (t + a[i] < x) t += a[i];
else if (t + a[i] == x) t = 0, s++;
else t = a[i], s++;
}
if (t) s++;
return s <= m;
}
int main() {
int l = 1, r = 1e9, ans = r;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], l = max(l, a[i]);
while (l <= r) {
int mid = l + r >> 1;
chk(mid) ? r = mid - 1, ans = mid : l = mid + 1;
}
cout << ans << endl;
return 0;
}
P1032 [NOIP2002 提高组] 字串变换
已知有两个字串 \(A,B\) 及一组字串变换的规则（至多 \(6\) 个规则），形如：
- \(A_1\to B_1\)。
- \(A_2\to B_2\)。
规则的含义为：在 \(A\) 中的子串 \(A_1\) 可以变换为 $ B_1\(，\)A_2$ 可以变换为 \(B_2\cdots\)。
输入格式：第一行有两个字符串 \(A,B\)。接下来若干行，每行有两个字符串 \(A_i,B_i\)，表示一条变换规则。
输出格式：若在 \(10\) 步（包含 \(10\) 步）以内能将 \(A\) 变换为 \(B\)，则输出最少的变换步数；否则输出 NO ANSWER!。
in:
abcd xyz
abc xu
ud y
y yz
out:
3
【数据规模与约定】
对于 \(100\%\) 数据，保证所有字符串长度的上限为 \(20\)。
【分析】最小步数，一眼bfs
题目主要在数据的处理上面有点难度，现在 x,y 是字符串类型，不好记录 g[x][y]=1 的情况。
思考一下，可以使用 map<pair<string,string>, bool> mp;
问题解决， bfs 即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
string A, B, a, b;
map<pair<string, string>, bool> mp;
map<string, int> st;
void bfs() {
queue<string> q;
q.push(A), st[A] = 1;
while (q.size()) {
auto u = q.front(); q.pop();
if (st[u] > 10) continue;
if (u == B) {
cout << st[u] - 1 << endl;
return;
}
for (auto it : mp) {
a = it.first.first, b = it.first.second;
int p = u.find(a);
while (p != -1) {
string v = u;
v.replace(v.begin() + p, v.begin() + p + a.size(), b);
if (!st[v]) st[v] = st[u] + 1, q.push(v);
p = u.find(a, p + a.size());
}
}
}
cout << "NO ANSWER!" << endl;
}
int main() {
cin >> A >> B;
while (cin >> a >> b) mp.insert({make_pair(a, b), 1});
bfs();
return 0;
}
P1020 [NOIP1999 提高组] 导弹拦截
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式：一行，若干个整数，中间由空格隔开。
输出格式：两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
in:
389 207 155 300 299 170 158 65
out:
6
2
【数据规模与约定】
对于前 \(50\%\) 数据（NOIP 原题数据），满足导弹的个数不超过 \(10^4\) 个。该部分数据总分共 \(100\) 分。可使用\(\mathcal O(n^2)\) 做法通过。
对于后 \(50\%\) 的数据，满足导弹的个数不超过 \(10^5\) 个。该部分数据总分也为 \(100\) 分。请使用 \(\mathcal O(n\log n)\) 做法通过。
对于全部数据，满足导弹的高度为正整数，且不超过 \(5\times 10^4\)。
【分析】题目含有两个问题
// v1 : 最长不上升子序列长度
// v2 : 需要多少导弹
解法1：DP，复杂度 \(O(n^2)\)
解法2：贪心+二分，复杂度 \(O(nlogn)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n = 0, a[N], f[N], h[N];
// v1 : 最长下降子序列长度
// v2 : 需要多少导弹
namespace dp {
void solve() {
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
ans1 = max(ans1, f[i]);
}
for (int i = 1; i <= n; i++) {
int k = 0;
while (k <= ans2 && h[k] < a[i]) k++;
h[k] = a[i];
if (k > ans2) ans2++;
}
cout << ans1 << endl << ans2 << endl;
}
}; // namespace dp
namespace binary_Search {
void solve() {
int ans1 = 0, ans2 = 0;
for (int i = n; i >= 1; i--) {
if (i == n || f[ans1 - 1] <= a[i]) f[ans1++] = a[i];
else *upper_bound(f, f + ans1, a[i]) = a[i];
}
for (int i = 1; i <= n; i++) {
int k = lower_bound(h + 1, h + 1 + ans2, a[i]) - h;
h[k] = a[i];
if (k > ans2) ans2++;
}
cout << ans1 << endl << ans2 << endl;
}
}; // namespace binary_Search
int main() {
while (cin >> a[++n]); n--;
// dp::solve();
binary_Search::solve();
return 0;
}
P1077 [NOIP2012 普及组] 摆花
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 \(m\) 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 \(n\) 种花，从 \(1\) 到 \(n\) 标号。为了在门口展出更多种花，规定第 \(i\) 种花不能超过 \(a_i\) 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入格式：第一行包含两个正整数 \(n\) 和 \(m\)，中间用一个空格隔开。第二行有 \(n\) 个整数，每两个整数之间用一个空格隔开，依次表示 \(a_1,a_2, \cdots ,a_n\)。
输出格式：一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 \(10^6+7\) 取模的结果。
in:
2 4
3 2
out:
2
【数据范围】
对于 \(20\%\) 数据，有 \(0<n \le 8,0<m \le 8,0 \le a_i \le 8\)。
对于 \(50\%\) 数据，有 \(0<n \le 20,0<m \le 20,0 \le a_i \le 20\)。
对于 \(100\%\) 数据，有 \(0<n \le 100,0<m \le 100,0 \le a_i \le 100\)。
【分析】
好好阅读理解这句话的含义：摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
也就意味着，不需要考虑花的位置，只需要考虑数量
那么问题就很显然，这是一个多重背包的裸题。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, a[N], mod = 1e6 + 7;
namespace DP1 {
int dp[N][N]; // dp[i][j] 用前 i 种花摆 j 盆的方案数
void solve() {
for (int i = 0; i <= n; i++)
dp[i][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k <= a[i] && k <= j; k++) {
int& t = dp[i][j];
t = (t + dp[i - 1][j - k]) % mod;
}
cout << dp[n][m] << endl;
}
}; // namespace DP1
namespace DP2 {
int dp[N]; // dp[j] 摆 j 盆的方案数
void solve() {
dp[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--)
for (int k = 1; k <= a[i] && k <= j; k++) {
int& t = dp[j];
t = (t + dp[j - k]) % mod;
}
cout << dp[m] << endl;
}
}; // namespace DP2
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
DP1::solve();
DP2::solve();
return 0;
}
T264125 黑暗能量
有\(n\) 瓶装有黑暗能量的容器，第 \(i\) 个容器里装有质量为 \(a_i\) 的黑暗能量。
两人尽可能多的平分黑暗能量，剩下无法平分的黑暗能量只能放弃使用。
【数据规模与约定】
本题共有 \(20\) 个测试点。
对于 \(50\%\) 的数据，\(n \le 13\)；
对于 \(70\%\) 的数据，\(n \le 50\)，提供的黑暗能量的总质量不超过 \(10^3\)；
对于 \(100\%\) 的数据，\(n \le 500\)，提供的黑暗能量的总质量不超过 \(10^5\)。
注意：对于以上三档数据，每档数据中分别含有 \(1\) 个测试点空间限制为 \(2\) MB，即总共有 \(15\%\) 的测试点空间限制为 \(2\) MB，其余测试点空间限制为 \(256\) MB。
【分析】
对于 \(50\%\) 的数据，\(n \le 13\)；--- 枚举所有情况 \(3^{13}\)，很小
满分解法，DP + 滚动数组优化，具体描述看代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 501, INF = 0x3f3f3f3f;
int n, m, a[N];
// 枚举 TLE：3^n ---- 012
void solve1() {
int ans = 0, tt = pow(3, n);
for (int i = 0; i < tt; i++) {
int t = i, p = n, b[3] = {0};
while (t) {
b[t % 3] += a[p--], t /= 3;
}
if (b[1] == b[2])
ans = max(ans, b[1]);
}
cout << 2 * ans << endl;
}
// dp[i][j][k] -- 前 i件物品，羊j 狼k 的情况是否存在
void solve2() {
bool dp[501][501][501];
memset(dp, 0x00, sizeof dp);
dp[0][0][0] = 1;
int p = 500;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
for (int k = 0; k <= p; k++) {
bool& t = dp[i][j][k];
t = dp[i - 1][j][k];
if (!t && j >= a[i])
t = dp[i - 1][j - a[i]][k];
if (!t && k >= a[i])
t = dp[i - 1][j][k - a[i]];
}
}
}
int ans = 0;
for (int i = 0; i <= p; i++)
ans = max(ans, dp[n][i][i] ? i : 0);
cout << 2 * ans << endl;
}
// dp[i][j] -- 前 i件物品，羊狼差距 j 的最大质量
void solve3() {
int dp[501][50001];
memset(dp, 0x80, sizeof dp);
dp[0][0] = 0;
int p = 50000;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
int& t = dp[i][j];
t = dp[i - 1][j];
if (j + a[i] <= p)
t = max(t, dp[i - 1][j + a[i]] + a[i]);
t = max(t, dp[i - 1][abs(j - a[i])] + a[i]);
}
}
cout << dp[n][0] << endl;
}
// dp[i][j] -- 前 i件物品，羊狼差距 j 的最大质量
void solve4() {
int dp[2][100001];
memset(dp, 0x80, sizeof dp);
dp[0][0] = 0;
int p = 50000;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
int& t = dp[i & 1][j];
t = dp[(i - 1) & 1][j];
if (j + a[i] <= p)
t = max(t, dp[(i - 1) & 1][j + a[i]] + a[i]);
t = max(t, dp[(i - 1) & 1][abs(j - a[i])] + a[i]);
}
}
cout << dp[n & 1][0] << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], m += a[i];
solve1();
solve2();
solve3();
solve4();
return 0;
}