数据有点鬼畜
题目一
试题名称:游戏
【题面描述】
你有四个正整数 n,a,b,c,并准备用它们玩一个简单的小游戏。
在一轮游戏操作中,你可以选择将 n 减去 a,或是将 n 减去 b。
游戏将会进行多轮操作,直到当 n≤c 时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同,当且仅当游戏操作轮数不同,或是某一轮游戏操作中,一种操作序列选择将 n 减去 a,而另一种操作序列选择将 n 减去 b。
如果 a=b,也认为将 n 减去 a 与将 n 减去 b 是不同的操作。
由于答案可能很大,你只需要求出答案对 1,000,000,007 取模的结果。
【输入格式】
一行四个正整数 n,a,b,c。
保证 1≤a,b,c≤n。
【输出格式】
一行一个整数,表示不同的游戏操作序列数量对 1,000,000,007 取模的结果。
【样例1】
1 1 1 1
1
【样例2】
114 51 4 1
176
【样例3】
114514 191 9 810
384178446
【数据范围】
对于 20% 的测试点,保证 a=b=c=1,n≤30。
对于 40% 的测试点,保证 c=1,n≤103。
对于所有测试点,保证 1≤n≤2×10^5。
这道题你可以先写一个暴力我用的是记忆化搜索,官方给的代码好像直接是一个线性dp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll n, a, b, c;
ll dfs(ll u)
{
if (u <= c) return 1;
return (dfs(u - a) % mod + dfs(u - b) % mod) % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b >> c;
cout << dfs(n);
return 0;
}
然后你就直接加一个记忆化搜索就完啦 QWQ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll n, a, b, c;
ll cnt;
map<ll, ll> f;
ll dfs(ll u)
{
if (f[u]) return f[u];
if (u <= c) return 1;
return f[u] = (dfs(u - a) % mod + dfs(u - b) % mod) % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> a >> b >> c;
cout << dfs(n);
return 0;
}
题目二
【问题描述】
你有 10^9 个牛棚,从左到右一字排开。你希望把 N 头牛安置到牛棚里。麻烦的是,你的牛很好斗,如果他们附近有其他的牛,他们就会不安分地去挑事。
其中,第 i 头牛的攻击范围是 (ai,bi),这意味着,如果他的左边 ai 个牛棚或右边 bi 个牛棚里有其他牛,他就会去挑事。
你想留下连续的一段牛棚,并把其他牛棚都卖掉。请问你最少需要留下多少牛棚,才能保证至少存在一种方案能够把所有的 N 头牛都安置进剩余的牛棚里,且没有牛会挑事?
【输入描述】
第一行 1 个正整数 N。
接下来一行 N 个用空格隔开的正整数 a1,…,aN。
接下来一行 N 个用空格隔开的正整数 b1,…,bN。
【输出描述】
输出一行一个整数,表示你最少需要留下多少牛棚。
【特别提醒】
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
【样例输入 1】
2
1 2
1 2
【样例输出 1】
4
【样例解释 1】
你可以留下 4 个牛棚,并如此安排你的牛:
牛棚 1 牛棚 2 牛棚 3 牛棚 4
牛 1 * * 牛 2
【样例输入 2】
3
1 2 3
3 2 1
【样例输出 2】
7
【数据规模】
对于 20% 的测试点,保证 N=2;
对于另外 20% 的测试点,保证 N=3;
对于 80% 的测试点,保证 N≤8;对于所有测试点,保证 N≤9,ai,bi≤1000。
这道题的话也很简单, 先写一个给出当前序列所需要的最小牛棚 由于数据很小 直接枚举一遍就完啦
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 10;
PII g[N];
map<int, int> st;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> g[i].first;
for (int i = 0; i < n; i++) cin >> g[i].second;
int ans = 1e9;
do
{
int res = 1, k = g[0].second;
for (int i = 1; i < n; i++)
{
res += max(k, g[i].first) + 1;
k = g[i].second;
}
ans = min(ans, res);
}
while(next_permutation(g, g + n));
cout << ans;
return 0;
}
感觉第一题的题目没有说清楚,看题意还以为要考虑a和b两种操作的排列顺序,看了题解才知道想多了。
如果考虑排列顺序的话,f[u] = dfs(u - a) + dfs(u - b)就不对了。
QWQ 有人看了我的题解呢 我还以为没人会看 呜呜~~
哈哈加油加油,感谢您的题解给我解惑