1、球队对比赛
题目：
有三只球队，每只球队编号分别为球队1，球队2，球队3，这三只球队一共需要进行n 场比赛。现在已经踢完了k场比赛，每场比赛不能打平，踢赢一场比赛得一分，输了不得分不减分。已知球队1和球队2的比分相差d1分，球队2和球队3的比分相差d2分，每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k)场比赛，有没有可能三只球队的分数打平。
输入：
第一行包含一个数字 t(1<=t<=10)t(1<=t<=10)
接下来的tt行每行包括四个数字 n,k,d1,d2(1<=n<=1012;0<=k<=n,0<=d1,d2<=k)n,k,d1,d2(1<=n<=1012;0<=k<=n,0<=d1,d2<=k)
输出：
每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”
样例输入：
2
3 3 0 0
3 3 3 3
样例输出：
yes
no
解析
还是要先分析下题目，注意题中加粗的字体，这意味着，所有的比赛总分加起来一定是n，打了k场比赛，那么这k长比赛的总分是k；
现在相当于你是裁判，你想让那个对赢那个队就赢，前提是你在其余两个队中随便选一个队作为炮灰和赢的那个队打。
而知道的信息只有相邻两个队的比分差距，因此，这里可以假设第一个队的比分为xx，那么第二个队的比分就可能是x+d1x+d1或x−d1x−d1，那么第三个队的成绩就可以由第二个队的成绩得到，可能是x+d1+d2x+d1+d2、x+d1−d2x+d1−d2、x−d1+d2x−d1+d2、x−d1−d2x−d1−d2；
总共是4中情况，因此枚举这四种情况可以得到三个队打了k场比赛的比分a, b, c(a+b+c=k)(a+b+c=k)。
那么现在问题就转化成了，你有n个硬币，拿出了k个硬币，分成了数量为a, b, c的三堆。现在，你要把剩下的n - k个硬币分到这三个堆中，让三个堆的硬币数量相等。看下图。
这里写图片描述
a, b, c要满足一下条件：0 <= a, b, c <= k并且剩下的n - k个硬币要先把白阴影部分填满了，然后剩下的那些硬币要刚好填满黑阴影部分，只有这样，三个队才有可能分数一样。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void getabc(int i, LL a, LL *pb, LL *pc, LL d1, LL d2)
{
switch (i) {
case 0:
*pb = a + d1;
*pc = *pb + d2;
break;
case 1:
*pb = a + d1;
*pc = *pb - d2;
break;
case 2:
*pb = a - d1;
*pc = *pb + d2;
break;
case 3:
*pb = a - d1;
*pc = *pb - d2;
break;
}
}
int main()
{
int T;
for (cin >> T; T--; ) {
LL n, k, d1, d2;
scanf("%lld%lld%lld%lld", &n, &k, &d1, &d2);
LL x[] = {k - 2 * d1 - d2,
k - 2 * d1 + d2,
k + 2 * d1 - d2,
k + 2 * d1 + d2};
bool ans = false;
for (int i = 0; i < 4; i++) {
int sum = 0;
for (LL t = x[i]; t; sum += t % 10, t /= 10) {}
if (sum % 3 == 0 && 0 <= x[i] / 3 && x[i] / 3 <= k) {
LL a = x[i] / 3, b, c;
getabc(i, a, &b, &c, d1, d2);
if (0 <= b && b <= k && 0 <= c && c <= k) {
LL max_ele = max(a, max(b, c));
LL diff = 3 * max_ele - a - b - c;
if (n - k - diff >= 0 && (n - k - diff) % 3 == 0) {
ans = true;
break;
}
}
}
}
cout << (ans ? "yes" : "no") << endl;
}
return 0;
}
上面的这个代码和思路是我一开始的想法，但是后来一想，如果n不是3的倍数，那么无论怎么搞都不可能存在三个队分数一样的情况；看上图，从图中可以看出，如果你得到的a, b, c都小于或等于n3n3且n是3的倍数，那么你把剩下的n - k个硬币依次丢到三个堆中，直到a, b, c等于n3n3，这个时候绝对没有硬币剩下！不信你可以试试。
下面的这个代码是最终代码。
如果你不熟悉这三个函数，那么你自己可以手写一个求上界的二分，一个求下界的二分，具体可以参考你真的理解二分的写法吗 - 二分写法详解。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void getabc(int i, LL a, LL *pb, LL *pc, LL d1, LL d2)
{
switch (i) {
case 0:
*pb = a + d1;
*pc = *pb + d2;
break;
case 1:
*pb = a + d1;
*pc = *pb - d2;
break;
case 2:
*pb = a - d1;
*pc = *pb + d2;
break;
case 3:
*pb = a - d1;
*pc = *pb - d2;
break;
}
}
int main()
{
int T;
for (cin >> T; T--; ) {
LL n, k, d1, d2;
scanf("%lld%lld%lld%lld", &n, &k, &d1, &d2);
if (n % 3) {
cout << "no" << endl;
continue;
}
LL x[] = {k - 2 * d1 - d2,
k - 2 * d1 + d2,
k + 2 * d1 - d2,
k + 2 * d1 + d2};
bool ans = false;
for (int i = 0; i < 4; i++) {
int sum = 0;
for (LL t = x[i]; t; sum += t % 10, t /= 10) {}
if (sum % 3 == 0 && 0 <= x[i] / 3 && x[i] / 3 <= k && x[i] <= n) {
LL a = x[i] / 3, b, c;
getabc(i, a, &b, &c, d1, d2);
if (0 <= b && b <= min(k, n / 3) && 0 <= c && c <= min(k, n / 3)) {
ans = true;
break;
}
}
}
cout << (ans ? "yes" : "no") << endl;
}
return 0;
}
2、字符串
题目：
有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。
输入：
第一行两个整数 n,m(1<=m<=n<=50000)n,m(1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。
输出：
输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。
样例输入：
8 1
aabaabaa
样例输出：
5
解析
这个题和第二批今日头条2018校园招聘后端开发工程师(第二批)编程题 - 题解中的第三题：字母交换很相似啊。于是，顺手就写了一个区间动态规划，然后提交了一下，发现内存爆，于是，把dp数组的意义改了一下，从dp[i][j]表示区间[i, j]需要修改的最少次数变成了dp[i][j]表示区间[i, j]表示以j为左端点，区间长度为i的区间需要修改的最少次数。这个时候就可以使用滚动数组来优化存储空间了。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
string s;
for (; cin >> n >> m >> s; ) {
int ans = 0;
for (char c = 'a'; c < 'c'; ++c) {
vector<vector<int> > dp(2, vector<int>(s.size(), 0));
int ret = 1;
for (int i = 0; i < (int)s.size(); ++i)
dp[1][i] = s[i] != c;
for (int len = 2; len <= (int)s.size(); ++len) {
for (int i = 0; i + len - 1 < (int)s.size(); i++) {
dp[len % 2][i] = max((dp[(len - 1) % 2][i] + (s[i + len - 1] != c)),
(dp[(len - 1) % 2][i + 1] + (s[i] != c)));
if (dp[len % 2][i] <= m)
ret = len;
}
}
ans = max(ans, ret);
}
cout << ans << endl;
}
return 0;
}
提交了一下这个代码，发现超时了，这个时候才注意到n,m(1<=m<=n<=50000)n,m(1<=m<=n<=50000)，而这个区间动态规划的时间复杂度为O(n2)O(n2)，这个复杂度太高了；
动态规划其实属于优雅一点的暴力解法，那么遇到复杂度O(n2)O(n2)的算法，第一时间要想到优化成O(nlogn)O(nlogn)，这一点在我之前的博文中反复提到，因为你这样分析可以为你指明下一步的思考方向，反正我现在就形成了这样的思维。
注意到，上面这个动态规划从小到大枚举了区间长度，而且仔细想一想，求区间[i, j]中最少需要的修改次数并不需要子区间的最优解，可以直接看看区间[i, j]中有多少不是目标字母的字母，而这个数量可以通过前缀和来得到。
于是结合上面两点，可以得到下面的优化算法：二分枚举答案(连续区间长度),然后在序列中遍历所有区间长度为指定长度的子区间(前缀和可以的到最少修改次数)。这样一来，算法的时间复杂度就是O(nlogn)O(nlogn)了。
还要注意，二分答案的时候，求的是上界，那么二分的端点l, r的初始取值以及mid的取值要写对，不会写的可以看下这篇博客你真的理解二分的写法吗 - 二分写法详解。反正我以前不理解二分的时候我就会瞎蒙，但是自从思考清楚写下这篇博客后，二分求上下界，那是板上钉钉，很快很准确就搞出来了。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
string s;
for (; cin >> n >> m >> s; ) {
int ans = 0;
for (char c = 'a'; c < 'c'; ++c) {
vector<int> dp(s.size() + 1, 0);
for (int i = 1; i <= (int)s.size(); ++i)
dp[i] = dp[i - 1] + (s[i - 1] == c);
int l = -1, r = (int)s.size() - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
bool f = false;
for (int i = 0; i + mid - 1 < (int)s.size(); i++)
if (dp[i + mid] - dp[i] <= m) {
f = true;
break;
}
f ? l = mid : r = mid - 1;
}
ans = max(ans, r);
}
cout << ans << endl;
}
return 0;
}
3、附加题
题目：
存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i)pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A、如果访问过当前房间i偶数次，那么下一次移动到房间i+1；
B、如果访问过当前房间i奇数次，那么移动到房间pipi；
现在路人甲想知道移动到房间n+1一共需要多少次移动。
输入：
第一行包括一个数字n(30%数据1<=n<=1001<=n<=100，100%数据 1<=n<=10001<=n<=1000)，表示房间的数量，接下来一行存在n个数字pi(1<=pi<=i)pi(1<=pi<=i), pipi表示从房间i可以传送到房间pipi。
输出：
输出一行数字，表示最终移动的次数，最终结果需要对1000000007取模。
样例输入：
2
1 2
样例输出：
4
解析
这个题目有意思，一开始我也没想到做法，但是后面注意到了这个条件，pi(1<=pi<=i)pi(1<=pi<=i)，才想到这是个动态规划。
有了上面这个条件为什么就能用动态规划做了呢？因为满足了最优子结构。这个条件保证了可以利用子结构的最优解。
先来分析一下，pi(1<=pi<=i)pi(1<=pi<=i)，这句话意味着传送门不可能把你往前面的门传，如果你想向前走，那么你只能访问该房间偶数次；
假设你现在第一次到达i门，你觉得前面i - 1个房子你都访问了多少次？每个房子访问了多少次我不知道，但是我知道每个房子访问的次数都是偶数！这一点很重要，不然写不出状态转移方程；这是为什么呢，其实答案就在上一段话，仔细想想，假如前面i - 1中有一个房子的访问次数不是偶数次，那么，你不可能向前走，更不可能走到i门。
想清楚了这一点，动态规划方程很好写了，设dp[i]为到达i门，并且进入次数为偶数时需要移动的次数，看下图：
这里写图片描述
要进入i门，那么就要从i - 1门过来，故访问i - 1门的次数一定为偶数，故dp[i] = dp[i - 1] + 1；
这个时候到达了i门，由于第一次进入，故次数为奇数，因此被送会pos[i]门，dp[i] += 1；
这个时候到达pos[i]门，由于之前到达pos[i]门的次数为偶数，因此这次到达的次数就是奇数，故从pos[i]门走到i - 1个门，并且到达i - 1门的次数为偶数的移动次数就是红色部分；
红色部分怎么求呢，首先，黑色部分是dp[i - 1]，黄色部分是dp[pos[i] - 1]，红色部分就是red = dp[i - 1] - dp[pos[i] - 1] - 1，这里注意，红色部分表示的是值，而不是人移动的范围(实际上人还可以移动到黄色部分去，但最终还是会移动到红色部分的右端点)。dp[i] += red；
移动到了i - 1门，且访问次数为偶数次，那么下一步就会移动到i门，且这个时候i门的访问次数为偶数次，因此dp[i] += 1。
综上，dp[i] = 2 * dp[i - 1] + 2。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
int main()
{
int n;
while (cin >> n) {
vector<int> arr(n + 1, 0);
vector<LL> dp(n + 1, 0);
for (int i = 1, x; i <= n; cin >> x, arr[i++] = x) {}
if (n == 1) {
cout << "1" << endl;
continue;
}
for (int i = 1; i <= n; i++)
dp[i] = (2 * dp[i - 1] % mod - dp[arr[i] - 1] + 2) % mod;
cout << dp[n] % mod << endl;
}
return 0;
}
个人资料
推荐圈子
猜你感兴趣的圈子：
标签： d1、d2、dp、pi、pb、面试题
