初中组第一题
【题目概述】
用数字 \(4,5,6\) 去组合出一个给定的数字 \(n\)（\(8 \le n \le 10^5\)）,用的数字尽可能多，在满足前者的条件下，数越大越好，分别输出 \(4,5,6\)的数目。
【题目解析】
第一要求：用的数字越多越好。
和相等的情况下，每一个选择的数要尽可能小，所以数量最多\(\le n/4\),考虑余数
\(n\) % 4 = 0 => n/4 0 0
\(n\) % 4 = 1 => n/4 - 1 1 0
\(n\) % 4 = 2 => n/4 - 1 0 1
\(n\) % 4 = 3 => n/4 - 2 1 1
根据余数情况一换一，保证第一要求的同时，满足第二要求
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
int main(){
cin>>n;
a=n/4;
if (n % 4 == 1 || n % 4 == 3)
a--, b++;
if (n % 4 == 2 || n % 4 == 3)
a--, c++;
cout << a << ' ' << b << ' ' << c;
return 0;
}
初中组第二题
【题目概述】
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点\(N\)(\(0≤N≤100000\))，牛位于点\(K\)(\(0≤K≤100000\))。农夫有两种移动方式：
1、从\(X\)移动到\(X-1\)或\(X+1\)，每次移动花费一分钟
2、从\(X\)移动到\(2*X\)，每次移动花费一分钟
假设农场的范围是0-100000，牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
【题目解析】
BFS裸题原题，通过队列找到距离点\(n\)位0,1,2,3,...距离的所有点,第一次到达\(k\)的即为答案
【参考代码】
#include<iostream>
#include<queue>
using namespace std;
int n, k;
int s[100050];
bool map[100050];
queue<int> q;
int main()
{
cin >> n >> k;
for (int i = 0; i < 100050; i++) s[i] = -1;
s[n] = 0;
map[n] = true;
queue<int> q;
q.push(n);
while (q.size() > 0) {
int a = q.front();
q.pop();
if (a + 1 <= 100000) {
if (!map[a + 1]){
q.push(a + 1);
map[a+1] = true;
s[a + 1] = s[a] + 1;
}
}
if (0 <= a - 1) {
if (!map[a - 1]){
map[a-1] = true;
q.push(a - 1);
s[a - 1] = s[a] + 1;
}
}
if (a * 2 <= 100000) {
if (!map[a * 2]){
map[a*2] = true;
q.push(a * 2);
s[a * 2] = s[a] + 1;
}
}
}
cout << s[k] << endl;
return 0;
}
初中组第三题
【题目概述】
终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。
这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。
小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 W 的采集车，洞穴里总共有 n 种宝物，每种宝物的价值为 \(v_{i}\)，重量为 \(w_{i}\)，每种宝物有\(m_{i}\)件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
【题目范围】
对于 \(30\%\) 的数据，\(n\leq \sum m_i\leq 10^4\)，\(0\le W\leq 10^3\)。
对于 \(100\%\) 的数据，\(n\leq \sum m_i \leq 10^5\)，\(0\le W\leq 4\times 10^4\)，\(1\leq n\le 100\)。
【题目解析】
多重背包的二进制优化
直接当简单背包问题可解前\(30\%\)的数据，时间复杂度为O(m*w)
二进制优化类似于压缩的思想。一个物品有很多，我们有很多很多的选择方法，可以选1..2..3...n个。那么我们就需要一种很快的选择方法，而不是朴素的暴力筛选。我们选择二进制方法
例如，我们有20个物品，我们如何快速的找出来任意个呢，比如选7个？可以一个一个选出来。也可以事先把物品分成五堆，分别是1，2，4，8，5个硬币，我们只需要选择1+2+4就能选出来7个硬币, 显然任意数都可以通过这五堆中组合选出。这种方法在数据比较大的时候优势尤为明显，将O(n)优化成了O(logn)，n个一样的物品就转化成了log2n个不同的物品。
时间复杂度O(nlogmw)
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int n, W, v, w, m;
struct node {
int v, w;
};
vector<node> vec;
int s[40010];
int main(){
cin >> n >> W;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> m;
for (int i = 1; i <= m; i *= 2) {
vec.push_back({v * i, w * i});
m -= i;
}
vec.push_back({v * m, w * m});
}
for (int i = 0; i < vec.size(); i++) {
v = vec[i].v;
w = vec[i].w;
for (int j = W; j >= w; j--)
s[j] = max(s[j], s[j - w] + v);
}
int maxn = 0;
for (int i = 1; i <= W; i++) {
maxn = max(maxn, s[i]);
}
cout << maxn << endl;
return 0;
}
初中组第四题
【题目概述】
博览馆正在展出由世上最佳的 m 位画家所画的图画。游客在购买门票时必须说明两个数字，a 和 b，代表他要看展览中的第 a 幅至第 b 幅画（包含a,b）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的a,b，数据保证一定有解。
若存在多组解，输出 a 最小的那组。
【题目解析】
双指针做法，枚举每一个左边界，找右边界的最小值，一个数组记录当前范围内每个画家的最后一幅画位置在哪，这样前面枚举l的时候去掉l-1的图画，就可以知道当前画家是否依然有图画在范围内，只有当范围内有所有画家的图画。且范围更小才更新答案
【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int s[N], h[N];
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf("%d", &s[i]);
int minn = n, a = 1, b = n, r = 0, tot = 0;
for (int l = 1; l <= n; l++) {
if (l > 1 && h[s[l-1]] == l - 1) {
h[s[l-1]] = 0;
tot--;
}
while (tot < m && r + 1 <= n) {
r++;
if (h[s[r]] == 0) {
tot++;
}
h[s[r]] = r;
}
if (tot == m && r - l < b - a)
a = l, b = r;
}
cout << a << ' ' << b << endl;
return 0;
}