$\large\color{orange}{比赛入口:}$$ \color{orange}{LCCUP} $$ \large\color{orange}{战队赛} $
$\large\color{green}{LCP 77. 符文储备}$
class Solution {
public:
int runeReserve(vector<int>& runes) {
sort(runes.begin(), runes.end());
int maxv = 0, n = runes.size();
for(int i = 0; i < n; i ++ ){
int j = i + 1;
while(j < n && runes[j] - runes[j - 1] <= 1) j ++ ;
maxv = max(maxv, j - i);
i = j - 1;
}
return maxv;
}
};
$\large\color{orange}{LCP 78. 城墙防线}$
class Solution {
public:
static const int N = 1e4 + 10;
int left[N], right[N];
int n;
bool check(int x){
int pre = left[1];
for(int i = 1; i < n - 1; i ++ ){
if(pre >= x){
pre = right[i];
continue;
}
if(right[i] + pre < x) return false;
pre = right[i] + pre - x;
}
return true;
}
int rampartDefensiveLine(vector<vector<int>>& rampart) {
memset(left, 0, sizeof left);
memset(right, 0, sizeof right);
n = rampart.size();
for(int i = 1; i < n - 1; i ++ ){
left[i] = rampart[i][0] - rampart[i - 1][1];
right[i] = rampart[i + 1][0] - rampart[i][1];
}
int l = 0, r = 1e8;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
};
$\large\color{orange}{LCP 79. 提取咒文}$
class Solution {
public:
static const int N = 110;
bool st[N][N][N];
struct node{
int x, y;
int length;
};
int len;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int extractMantra(vector<string>& matrix, string mantra) {
int n = matrix.size(), m = matrix[0].size();
len = mantra.size();
memset(st, 0, sizeof st);
queue<node> qu;
qu.push({0, 0, 0});
st[0][0][0] = true;
int step = 0;
while(!qu.empty()){
int k = qu.size();
for(int r = 0; r < k; r ++ ){
node cur = qu.front();
qu.pop();
int x = cur.x, y = cur.y;
int length = cur.length;
if(length == len) return step;
if(mantra[length] == matrix[x][y]){
st[x][y][length + 1] = true;
qu.push({x, y, length + 1});
}
for(int i = 0; i < 4; i ++ ){
int xx = x + dx[i], yy = y + dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
if(st[xx][yy][length]) continue;
st[xx][yy][length] = true;
qu.push({xx, yy, length});
}
}
step ++ ;
}
return -1;
}
};
$\large\color{red}{LCP 80. 生物进化录}$
class Solution {
public:
static const int N = 1E4 + 10;
int h[N], e[N], ne[N], idx;
void init(){
memset(h, -1, sizeof h);
memset(e, 0, sizeof e);
memset(ne, 0, sizeof e);
idx = 0;
}
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void establish(vector<int>& parents){
int len = parents.size();
for(int i = 0; i < len; i ++ ){
if(parents[i] == -1) continue;
add(parents[i], i);
}
}
static bool cmp(string &a, string &b){
int a_len = a.size(), b_len = b.size();
int i = 0;
while(i < a_len && i < b_len){
if(a[i] < b[i]) return true;
else if(a[i] > b[i]) return false;
i ++ ;
}
// if(a_len == b_len) return true;
if(i < a_len){
if(a[i] == '0') return true;
return false;
}
if(i < b_len){
if(b[i] == '0') return false;
return true;
}
return true;
}
string getMinSequence(int u){
string s = "0";
vector<string> sons;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
sons.push_back(getMinSequence(j));
}
sort(sons.begin(), sons.end(), cmp);
int len = sons.size();
for(int i = 0; i < len; i ++ ){
s += sons[i], s += '1';
}
return s;
}
string evolutionaryRecord(vector<int>& parents) {
init();
establish(parents);
string s = getMinSequence(0);
// 去除首位0(根节点的创建),和末尾的1
string res = "";
int len = s.size();
int ed = len - 1;
while(ed >= 0 && s[ed] == '1') ed -- ;
for(int i = 1; i <= ed; i ++ ) res += s[i];
return res;
}
};