# Leetcode 第136场周赛解题报告

https://leetcode-cn.com/contest/weekly-contest-136

## 困于环中的机器人

#### 地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/robot-bounded-in-circle/

“G”：直走 1 个单位

“L”：左转 90 度

“R”：右转 90 度

#### 思路：

```class Solution {
public:
bool isRobotBounded(string instructions) {
int x = 0;
int y = 0;
int i = 0;
int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}};
do
{
for(auto ch : instructions)
{
if(ch=='G')
{
x+=dir[i][0];
y+=dir[i][1];
}
else if(ch=='R')
{
++i;
i%=4;
}
else
{
i+=4;
i--;
i%=4;
}
}
}while(i!=0);
if(x==0&&y==0)
return true;
return false;
}
};```

## 不邻接植花

#### 代码：

```class Solution {
public:
map<int, map<int, int>> mr;
vector<int> res;
int dfs(int index, int N)
{
if(index > N)
return 0;
for(int color=1;color<=4;++color)
{
res[index-1] = color;
map<int, int> & tmp = mr[index];
bool flag = false;
for(auto it=tmp.begin();it!=tmp.end();++it)
{
if(res[it->first-1]==color)
{
flag = true;
break;
}
}
if(flag == true)
continue;
int ret = dfs(index+1, N);
if(ret == 0)
return 0;
}
return -1;
}
vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
res.resize(N, 0);
for(int i=0; i<paths.size(); ++i)
{
int x = paths[i][0];
int y = paths[i][1];
mr[x][y] = 1;
mr[y][x] = 1;
}
dfs(1, N);
return res;
}
};```

## 分隔数组以得到最大和

#### 地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/partition-array-for-maximum-sum/

#### 代码：

```class Solution {
public:
int dp[501]={0};
int maxSumAfterPartitioning(vector<int>& A, int K) {
int n = A.size();
for(int i = n-1; i>=0; --i)
{
int ma = 0;
int j;
for(j=i;j<i+K && j < n ;++j)
{
ma = max(ma, A[j]);
dp[i] = max(dp[i], ma*(j - i + 1) + dp[j + 1]);
}
}
return dp[0];
}
};```

## 最长重复子串

#### 地址：

https://leetcode-cn.com/contest/weekly-contest-136/problems/longest-duplicate-substring/

#### 代码：

```namespace SA
{
bool cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int str[], int sa[], int rank[], int height[], int n, int m)
{
n++;
int i, j, p, *x = t1, *y = t2;
for (i = 0; i < m; i++)
c[i] = 0;
for (i = 0; i < n; i++)
c[x[i] = str[i]]++;
for (i = 1; i < m; i++)
c[i] += c[i - 1];
for (i = n - 1; i >= 0; i--)
sa[--c[x[i]]] = i;
for (j = 1; j <= n; j <<= 1)
{
p = 0;
for (i = n - j; i < n; i++)
y[p++] = i;
for (i = 0; i < n; i++)
if (sa[i] >= j)
y[p++] = sa[i] - j;
for (i = 0; i < m; i++)
c[i] = 0;
for (i = 0; i < n; i++)
c[x[y[i]]]++;
for (i = 1; i < m; i++)
c[i] += c[i - 1];
for (i = n - 1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
if (p >= n)
break;
m = p;
}
int k = 0;
n--;
for (i = 0; i <= n; i++)
rank[sa[i]] = i;
for (i = 0; i < n; i++)
{
if (k)
k--;
j = sa[rank[i] - 1];
while (str[i + k] == str[j + k])
k++;
height[rank[i]] = k;
}
}
int num_rank[MAXN], height[MAXN];
int num[MAXN];
int sa[MAXN];
} // namespace SA

class Solution
{
public:
string longestDupSubstring(string S)
{
using namespace SA;
int pos = 0;
int len = 0;
int n = S.length();
for (int i = 0; i <= n; ++i)
{
num[i] = S[i]&0x3f;
}
num[n] = 0;
da(num, sa, num_rank, height, n, 256);
for (int i = 2; i <= n; ++i)
{
if (height[i] > len)
{
pos = sa[i];
len = height[i];
}
}
return S.substr(pos, len);
}
};```