家人们
我这次大概5000名
没救了
下辈子再一起拿徽章
※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
:
: 第一题
: 给你一个字串s和数字k 把所有的s字串替换成他的索引+k，索引越界就从左边继续走。
```cpp
class Solution {
public:
string getEncryptedString(string s, int k)
{
int len = s.size();
string res;
for(int i = 0 ; i < len ; i ++)
{
res.push_back(s[(i+k)%len]);
}
return res;
}
};
```
: 第二题
: n才10，直接用回溯法穷举二进制字串，然后把符合条件的加入结果集。
:
要弄出长度为n的bot串
然后0不能相邻
思路
写一写 干你娘好麻烦
丢给gpt 过
```cpp
class Solution {
public:
unordered_set<string> save;
void find(string k, int pos)
{
int len = k.size();
for (int i = pos; i < len; i++)
{
if (k[i] == '0') continue;
if ((i > 0 && k[i - 1] == '0') || (i < len - 1 && k[i + 1] == '0'))
continue;
k[i] = '0';
if (save.find(k) == save.end()) {
save.insert(k);
find(k, i + 1);
}
k[i] = '1';
}
}
vector<string> validStrings(int n)
{
string pre(n,'1');
if(n == 1)return {"1","0"};
find(pre, 0);
save.insert(pre);
vector<string> res(save.begin(), save.end());
return res;
}
};
```
: 第三题
: 简单dp，因为起始点在左上所以一列一列的扫就好。
:
多少个包含grid最左上角的子矩阵
xy数量一样
思路
这算前缀和还是dp
反正加起来看就好
```cpp
class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& grid)
{
int res = 0;
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> xcount(n,vector<int>(m,0));
vector<vector<int>> ycount(n,vector<int>(m,0));
if(grid[0][0] == 'X')xcount[0][0] =1;
if(grid[0][0] == 'Y')ycount[0][0] =1;
for(int i = 1 ; i < m ; i ++)
{
xcount[0][i] += xcount[0][i-1];
if(grid[0][i]=='X')xcount[0][i]++;
ycount[0][i] += ycount[0][i-1];
if(grid[0][i]=='Y')ycount[0][i]++;
}
for(int i = 1 ; i < n ; i ++)
{
xcount[i][0] += xcount[i-1][0];
if(grid[i][0]=='X')xcount[i][0]++;
ycount[i][0] += ycount[i-1][0];
if(grid[i][0]=='Y')ycount[i][0]++;
}
for(int i = 1 ; i < n ; i ++)
{
for(int j = 1 ; j < m ; j ++)
{
xcount[i][j] += xcount[i-1][j];
xcount[i][j] += xcount[i][j-1];
xcount[i][j] -= xcount[i-1][j-1];
if(grid[i][j]=='X')xcount[i][j]++;
ycount[i][j] += ycount[i-1][j];
ycount[i][j] += ycount[i][j-1];
ycount[i][j] -= ycount[i-1][j-1];
if(grid[i][j]=='Y')ycount[i][j]++;
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
if(xcount[i][j] > 0)
{
if(xcount[i][j]==ycount[i][j])res++;
}
}
}
return res;
}
};
```
: 第四题
: 我看了一下感觉是dp 然后看看测资大小我选择死亡
: 遇到困难睡大觉
:
给你一堆小字串
跟他们的cost
要用最少的钱组合出大字串
思路
先找到位子然后纪录然后dp
然后我TLE + MLE
渍鲨
这题听我朋友说
确实是记录后dp
但是要用字典树来记录才可以
干你娘
我又没学过字典树
狗屎烂题目
```cpp
class Solution {
public:
int minimumCost(string target, vector<string>& words, vector<int>& costs)
{
int tlen = target.size();
int len = words.size();
unordered_map<int, vector<pair<int,int>>> save;
for(int i = 0 ; i < len ; i ++)
{
int po = target.find(words[i]);
while(po != std::string::npos)
{
save[po].push_back({costs[i], po + words[i].size()});
po = target.find(words[i], po + 1);
}
}
vector<int> paper(tlen+1,INT_MAX);
paper[0]=0;
for(int i = 0 ; i < tlen+1 ; i ++)
{
if(paper[i] == INT_MAX) continue;
for(auto& k : save[i])
{
if(k.second <= tlen)
{
paper[k.second] = min(paper[k.second], paper[i] + k.first);
}
}
}
if(paper[tlen] == INT_MAX)return -1;
return paper[tlen];
}
};```