显然要尽可能把 往高位放,如果放了两个 就来一个 来避免非法,所以 应该放在从左往右第 个,这些除以 余 的位置中。所以可以根据是否还有 来决定怎么输出。
if
打表的同学送的分数。满分参考代码:
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
freopen("three.in", "r", stdin);
freopen("three.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
if (m > 0)
{
if (i % 3 == 1 || i % 3 == 2)
{
cout << 1;
m--;
}
else
cout << 0;
}
else
cout << 0;
}
return 0;
}
显然这是段二分的代码,输出的是在 中找几次能找到 (虽然这件事本身挺无聊)。
题目问几个数可以得到最大的输出,显然一个暴力枚举的做法就是对 l\rim r 范围内的每个数都跑一遍这段代码看看输出是几。
但有不少同学这个写错了,主要原因是这段代码会修改 的值,所以外面枚举 的时候不能也用变量 来做了。可以把题目描述给的代码打包成一个函数,或者备份一份即可。
子任务 1,2 送了可以口算出来的 分。
60 分参考代码:
#include <bits/stdc++.h>
using namespace std;
int f(int l, int r, int x)
{
int cnt = 0;
while (l <= r)
{
cnt++;
int mid = (l + r) / 2;
if (mid == x)
return cnt;
if (mid < x)
l = mid + 1;
if (mid > x)
r = mid - 1;
}
}
int main()
{
freopen("guess.in", "r", stdin);
freopen("guess.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
cin >> l >> r;
int maxX = 0;
for (int i = l; i <= r; i++)
maxX = max(maxX, f(l, r, i));
int ans = 0;
for (int i = l; i <= r; i++)
if (f(l, r, i) == maxX)
ans++;
cout << ans;
return 0;
}
实际上手动模拟一下,可以算出来每个数是第几次被 命中的。比如 时:
这个过程显然可以用深搜或者广搜跑完,时间复杂度 。
还有一个做法,实际上容易发现 的答案可以等价对应到 或者 。然后其实是可以数学方法, 算算哪些数字最后一次被命中。但我懒得推了,作为第二题直接爆搜就好了。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int l, r, maxCnt;
int f[100'000'000 + 5];
void dfs(int l, int r, int cnt)
{
if (l > r)
return;
int mid = (l + r) / 2;
f[mid] = cnt;
maxCnt = max(maxCnt, cnt);
dfs(l, mid - 1, cnt + 1);
dfs(mid + 1, r, cnt + 1);
}
int main()
{
freopen("guess.in", "r", stdin);
freopen("guess.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
cin >> l >> r;
maxCnt = 0;
dfs(l, r, 1);
int ans = 0;
for (int i = l; i <= r; i++)
if (f[i] == maxCnt)
ans++;
cout << ans;
return 0;
}
这道题我觉得最好的是我这个配图用 ppt 画得真好看。
首先显然直接 dfs
爆搜能跑出来子任务 1,但大胆一点搜搜会发现子任务 3 的 的范围也跑的飞快,所以直接 dfs
是能拿到 分的。
子任务 1、3 参考代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 1'000'000;
int n, a, b;
int ans;
bool vis[MAXN + 5];
int dx[] = {1, -1, 2, -2};
void dfs(int now)
{
if (now == b)
{
ans = (ans + 1) % MOD;
return;
}
for (int i = 0; i < 4; i++)
{
int nxt = now + dx[i];
if (nxt < 0 || nxt > n || vis[nxt])
continue;
vis[nxt] = true;
dfs(nxt);
vis[nxt] = false;
}
}
int main()
{
freopen("cow.in", "r", stdin);
freopen("cow.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
ans = 0;
vis[a] = true;
dfs(a);
vis[a] = false;
cout << ans;
return 0;
}
很多同学就止步于此了,实际上能拿到 分之后,子任务 2 的 分就在嘴边了。用这个代码来跑一跑 1 0 1
、2 0 2
、3 0 3
这些数据,会发现其实是有规律的,n 0 n
的答案等于前三个答案之和(实际上这个规律也是我出完题目之后才发现的)。所以子任务 1,2 直接一个递推就好了。两个代码总结在一起就是个 分了。
子任务 1,2 参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 1'000'000;
int n, a, b;
int f[MAXN + 5];
signed main()
{
freopen("cow.in", "r", stdin);
freopen("cow.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
f[0] = 1;
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++)
f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % MOD;
cout << f[n];
return 0;
}
首先要注意到,n a b
和 n b a
的答案一样,所以可以先把人调整到左边,牛调整到右边。
然后抓牛得情况看上去很多,但是仔细想想会发现一旦某个地方回头了,就不可能再折返回去了。所以只有三种情况:
如果往左一段然后回头,那么必然是 -2 -2 -2 -2 -1 +2 +2 +2...
这样或者 -2 -2 -2 -2 +1 +2 +2 +2 ...
。前面的两步走几次有多种情况,但是一旦开始回头了,就是唯一的一种走法了。
所以从 走到 其实就看左边从哪儿开始往右走,一共有 这些折返点,共 个方案能“走到 这个位置且能继续往右”。
后半部分就两种结果了,要么精准往右到 ,要么跳过了 到达 再回头。我一开始没发现子任务 2 那个规律,所以我是 dp 写的。
表示往右走到了 且 被走过了, 表示往右走到了 且 没走(跳过去了)。然后状态转移方程其实很好退出来。
那么精准抵达 的方案是就是 ,跳过 到达 的方案就是 。
我们可以惊喜得发现,从 回头到 的方案数和前部分从 到 的计算方法一样。这道题就这么做完了。
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 1'000'000;
int n, a, b;
int f[MAXN + 5]; // 往右走到 i,且 i-1 走过了,i 右面都没走过
int g[MAXN + 5]; // 往右走到 i,且 i-1 没走过,i 右边都没走过
signed main()
{
freopen("cow.in", "r", stdin);
freopen("cow.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b;
if (a > b)
swap(a, b);
f[a] = 0, f[a + 1] = a + 1;
g[a] = 1, g[a + 1] = 0;
for (int i = a + 2; i <= n; i++)
{
// 左边走过
f[i] = (f[i - 1] + g[i - 1]) % MOD; // 直接左边往右走一步
f[i] = (f[i] + g[i - 1]) % MOD; // 左边回撤一步再往前
// 左边没走过
g[i] = (f[i - 2] + g[i - 2]) % MOD; // 只能从 i-2 一次两步过去
}
int ans1 = (f[b] + g[b]) % MOD; // 左边直达
int ans2 = 0;
if (b != n)
ans2 = (g[b + 1] * (n - (b + 1) + 1)) % MOD;
cout << (ans1 + ans2) % MOD;
return 0;
}
其实这题是为了给初赛服务的。为了给大家科普下 J 组初赛常考的哈夫曼编码。
所以可以先学学咋求哈夫曼编码。核心就是每次贪心选两个权值最小的节点,合到一个节点上。拿个优先队列建树就好,这题数据范围小也可以直接纯暴力找俩权值小的节点建树就好了。
然后从根节点开始 dfs 往下跑就能得到每节点的编码了,这题我给的数据范围的编码直接用一个 long long
就能存,我用两个数组分别存了编码长度和编码,当然直接用字符串存左子树 +"0"
右子树 +"1"
也能造出来的。
就一个单词,直接给这个单词编码 0
或 1
就好了,文章长度就是单词数量乘以 了。很多同学这部分分数没拿到有点可惜。
既然给的就是个合法的哈夫曼编码,直接用这套编码算文章长度就好了。文章长度就是“每个单词数量乘以编码长度”之和。
只要长度合法就行,所以这里就需要把哈夫曼编码给先求出来。然后输入不合法就输出你的方案就好,合法就输出就直接算算文章长度输出就好。
这个子任务保证了互不为前缀,所以只要文章长度对了就行。所以用自己的编码算一个文章长度,然后算算输入给的文章长度。如果一样就是 Yes
,不一样就是 No
。
前面的基础上再加一个判断是否有前缀关系就好。这题数据范围小,直接 的枚举单词对,然后检查两个单词是否满足其中一个是不是另一个的前缀就好。
实际上也有更简单的方法。把所有单词按照字典序排序,那么如果存在前缀关系,必然存在相邻的前缀关系。且前一个是后一个的前缀。
满分参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[60 + 5];
string s[60 + 5];
// huffman 建树
priority_queue<pair<int, int>> q;
int tot, l[60 * 2 + 5], r[60 * 2 + 5];
// 算 huffman 编码
int len[60 * 2 + 5], code[60 * 2 + 5];
void dfs(int x, int nowLen, int nowCode)
{
if (x <= n)
{
len[x] = nowLen;
code[x] = nowCode;
return;
}
dfs(l[x], nowLen + 1, nowCode * 2);
dfs(r[x], nowLen + 1, nowCode * 2 + 1);
}
signed main()
{
freopen("huffman.in", "r", stdin);
freopen("huffman.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
// 算输入的文章总长度
int inf_ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
inf_ans += s[i].size() * a[i];
}
// 特判
if (n == 1)
{
if (s[1].size() == 1)
cout << "Yes\n"
<< inf_ans << "\n";
else
cout << "No\n1\n";
return 0;
}
// 构建一个哈夫曼编码
tot = n;
for (int i = 1; i <= n; i++)
q.push(make_pair(-a[i], i));
while (q.size() > 1)
{
tot++;
pair<int, int> x = q.top();
q.pop();
pair<int, int> y = q.top();
q.pop();
q.push(make_pair(x.first + y.first, tot));
l[tot] = x.second;
r[tot] = y.second;
}
dfs(tot, 0, 0);
// 检查
bool flag = true;
// 检查文章总长度
int ans = 0;
for (int i = 1; i <= n; i++)
ans += a[i] * len[i];
if (inf_ans != ans)
flag = false;
// 检查前缀问题
sort(s + 1, s + n + 1);
for (int i = 1; i <= n - 1; i++)
{
if (s[i] > s[i + 1])
continue;
bool now = true; // 是否为前缀
for (int j = 0; j < s[i].size(); j++)
if (s[i][j] != s[i + 1][j])
{
now = false;
break;
}
if (now)
{
flag = false;
break;
}
}
// 输出
if (flag)
{
cout << "Yes\n";
cout << ans << "\n";
}
else
{
cout << "No\n";
for (int i = 1; i <= n; i++)
{
for (int j = len[i] - 1; j >= 0; j--)
cout << ((code[i] >> j) & 1);
cout << "\n";
}
}
return 0;
}