本次周赛不讲武德,出博弈论来为难我们这些老同志。
他说对不起,说他是乱出的,他可不是乱出的啊,分明是有备而来,先是一个动态规划,再是一个二分答案,最后还搞个博弈论,这好吗?这不好!算法要以和为贵,不要搞窝里斗,谢谢朋友们!
说正经的,本次周赛涉及知识点:动态规划,前缀和,树状数组,博弈论,二分答案,下面一起来看一看
给你长为
的二进制字符串 s
如果字符串中由 1
组成的 最长子串严格长于 由 0
组成的 最长子串,返回 true
,否则,返回 false
。
例如,s = "110100010"
中,由 1
组成的最长连续子字符串的长度是 2
,由 0
组成的最长连续子字符串的长度是 3
。
注意,如果字符串中不存在 0
,此时认为由 0
组成的最长连续子字符串的长度是 0
。字符串中不存在 1
的情况也适用此规则。
数据规定
定义
表示到
位置,连续
子串的最大长度
定义
表示到
位置,连续
子串的最大长度
转移完毕,维护两个最大值,最后比较即可,时间复杂度
事实上,可以滚动掉状态,使用两个变量代替
数组,从而将空间复杂度优化到
class Solution {
public:
bool checkZeroOnes(string s) {
int n = s.length();
vector<int> dp1(n, 0);
vector<int> dp2(n, 0);
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
dp1[i] = 0, dp2[i] = 1;
if (i > 0 && s[i] == s[i - 1]) dp2[i] = max(dp2[i - 1] + 1, dp2[i]);
}
else {
dp1[i] = 1, dp2[i] = 0;
if (i > 0 && s[i] == s[i - 1]) dp1[i] = max(dp1[i - 1] + 1, dp1[i]);
}
}
int ans1 = 0, ans2 = 0;
for (int i = 0; i < n; ++i) {
ans1 = max(ans1, dp1[i]);
ans2 = max(ans2, dp2[i]);
}
//cout << ans1 << ' ' << ans2 << endl;
return ans1 < ans2;
}
};
给你一个浮点数 hour
,表示你到达办公室可用的总通勤时间。
要到达办公室,你必须按给定次序乘坐 n
趟列车。
给定一个长度为 n
的整数数组 dist
,其中 dist[i]
表示第 i
趟列车的行驶距离
每趟列车均只能在整点发车,所以你可能需要在两趟列车之间等待一段时间。
例如,第 1
趟列车需要 1.5
小时,那你必须再等待 0.5
小时,搭乘在第 2
小时发车的第 2
趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速,如果无法准时到达,则返回 -1
。
生成的测试用例保证答案不超过
,且 hour
的小数点后最多存在两位数字。
考虑二分答案,然后 check
具体来讲,二分速度,对于每一个速度
,我们计算一下通勤的时间
,如果
,返回
,二分右边界缩小,否则返回
,二分左边界扩大
class Solution {
public:
#define INF 0x3f3f3f3f
bool check(int res, vector<int> &vec, double hour) {
double ans = 0;
int n = vec.size();
for (int i = 0; i < n; ++i) {
int temp = vec[i];
if (i < n - 1) {
ans += ceil(double(temp) / double(res));
}
else ans += double(temp) / double(res);
//printf("%.6f\n", ans);
}
return ans <= hour;
}
int minSpeedOnTime(vector<int>& vec, double hour) {
int L = 1, R = INF;
int ans = -1;
while (L <= R) {
int mid = L + R >> 1;
//cout << L << ' ' << mid << ' ' << R << endl;
if (check(mid, vec, hour)) {
R = mid - 1;
ans = mid;
}
else L = mid + 1;
}
return ans;
}
};
给定一个长为
下标从
开始的
串,保证第一个位置一定是
给定两个正整数
,当同时满足以下条件时,你可以从下标
转移到下标
如果可以到达
处,返回
,否则返回
数据保证
定义
表示能否跳到第
个位置
考虑前继状态转移到当前状态,即
也就是说,对于
,只要
,那么
为
可以通过判断区间和
是否为
来完成上述转移,因此我们需要在转移的过程中维护前缀和,时间复杂度
如果从当前状态转移到后继状态,即
,需要对区间
作区间修改操作,转移的时候使用单点查询,有以下几种处理方式
/* 前继状态转移到当前,维护前缀和 */
class Solution
{
public:
bool canReach(string s, int minJump, int maxJump)
{
int n = s.length();
vector<int> dp(n + 7, 0), sum(n + 7, 0);
dp[1] = 1;
for (int i = 1; i < 1 + minJump; ++i) {
sum[i] = sum[i - 1] + dp[i];
}
for (int i = 1 + minJump; i <= n; ++i)
{
if (s[i - 1] == '0')
{
int L = max(1, i - maxJump), R = i - minJump;
if (sum[R] - sum[L - 1])
dp[i] = 1;
}
sum[i] = sum[i - 1] + dp[i];
}
return dp[n];
}
};
/* 当前状态转移到后继状态,维护差分数组与前缀和 */
class Solution
{
public:
bool canReach(string s, int minJump, int maxJump)
{
int n = s.length();
vector<int> d(2 * n + 7);
d[0]++, d[1]--;
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += d[i];
if (sum > 0 && s[i] == '0' || i == 0) {
int L = i + minJump, R = i + maxJump;
d[L]++, d[R + 1]--;
}
}
return sum > 0 && s[n - 1] == '0';
}
};
和
玩一个游戏,两人轮流操作,
先手
总共有
个石子排成一行。轮到某个玩家的回合时,如果石子的数目大于
,他将执行以下操作
,并且 移除 最左边的
个石子。
和
的分数之差为 (
的分数减去
的分数) 。
的目标是 最大化 分数差,
的目标是 最小化 分数差。
给你一个长度为
的整数数组 stones
,其中 stones[i]
是 从左边起 第 i
个石子的价值。请你返回在双方都采用 最优 策略的情况下,
和
的分数之差
选取前
个石子获得的分数为
,这个可以用前缀和
维护
设
表示可选石子范围为
时,
和
的分差最大值
考虑
是否选择
石子
要在
内进行选择,因此有
获得分数
,同时
在
内选择,因此
所以
博弈论
通常倒序转移,最后返回
数据保证
class Solution {
public:
int stoneGameVIII(vector<int>& stones) {
int n = stones.size();
vector<int> pre(n), dp(n);
pre[0] = stones[0];
for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + stones[i];
dp[n - 1] = pre[n - 1];
for (int i = n - 2; i >= 1; --i) {
dp[i] = max(dp[i + 1], pre[i] - dp[i + 1]);
}
return dp[1];
}
};
博弈论
还是挺难的,看了题解想半天才明白,不过似乎也有对应的套路,还是要多刷题