2.7万

Paren

Amaryllis_

sealt
optimjie
111111
NANAWOAKARI
y总的小迷弟cxr
hyh_OneSelf
Lucky_Man

18910310021

#### dfs

• 开头可能是#，所以要特判

#### 双指针

• 怎么判断下一个字符和当前不一样——s[j] = s[i]
• 怎么记录并输出当前长度最大字母—— if
#include <iostream>

using namespace std;

int main()
{
int n;
cin >> n;
while (n -- )
{
string s;
cin >> s;

char c;
int res = 0;
for (int i = 0; i < s.size(); i ++ )
{
int j = i;

while (j < s.size() && s[i] == s[j]) j ++ ;
if (j - i > res) c = s[i], res = j - i;
i = j - 1;
}
cout << c << ' ' << res << endl;
}

}


#### 双指针 二分 哈希

• 单调性：两个序列都是单调上升的，当a[i]不断变大的过程中，b[j]会不断变小
#include <iostream>

using namespace std;

const int N = 100010;

int n, m, x;
int a[N], b[N];

int main()
{
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i ++  ) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++  ) scanf("%d", &b[i]);

for (int i = 0, j = m - 1; i < n; i ++ )
{
while (j >= 0 && a[i] + b[j] > x) j -- ;
if (a[i] + b[j] == x)
{
cout << i << ' ' << j << endl;
return 0;
}

}

return 0;
}


#### 二分

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], b[N];

int n, m, x;

int main()
{
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++) scanf("%d", &b[i]);

for (int i = 0; i < n; i ++)
{
int k = x - a[i];

int l = 0, r = m - 1;
while (l < r)
{
int mid = l + r >> 1;
if (b[mid] >= k) r = mid;
else l = mid + 1;
}
if (a[i] + b[l] == x)
{
printf("%d %d\n", i, l);
break;
}
}
return 0;
}


int t = x - a[i];
int l = 0, r = m - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (b[mid] <= t) l = mid;
else r = mid - 1;
}


for (int i = 0; i < n; i ++ )
{
int l = 0, r = m - 1;
while (l < r)
{
int mid = l + r >> 1;
if (a[i] + b[mid] >= x) r = mid;
else l = mid + 1;
}

if (a[i] + b[l] == x)
cout << i << ' ' << l << endl;
}


for (int i = 0; i < n; i ++ )
{
int l = 0, r = m - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[i] + b[mid] <= x) l = mid;
else r = mid - 1;
}

if (a[i] + b[l] == x)
cout << i << ' ' << l << endl;
}


#### 哈希

#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 100010;

int n, m, x;
int a[N], b[N];
unordered_map<int, int> h;

int main()
{
cin >> n >> m >> x;
for (int i = 0; i < n; i ++ ) cin >> a[i], h[a[i]] = i;
for (int i = 0; i < m; i ++ ) cin >> b[i];

for (int i = 0; i < m; i ++ )
{
if (h.count(x - b[i]))
cout << h[x - b[i]] << ' ' << i << endl;
}

return 0;
}


#### 双指针

• 第一类：两个序列上的双指针
• 第二类：同一序列的双指针
• 写法：
• 时间复杂度：$o(n)$
• 作用：把$n^2$优化到$o(n)$，优化一重循环
• 做法：先写暴力，看是否具有单调性，再用双指针优化
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) cin >> a[i];

int res = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
s[a[i]] ++ ;
while (s[a[i]] > 1)
{
s[a[j]] -- ;
j ++ ;
}
res = max(res, i - j + 1);
}
printf("%d\n", res);
return 0;
}



#### 双指针

• 涉及到二元组(时间、id)，用pair来排序
暴力
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, d, k;
PII log[N];
int cnt[N];
bool st[N];

int main()
{
scanf("%d%d%d", &n, &d, &k);
int maxt = 0;
for (int i = 0; i < n; i ++ )
{
scanf("%d%d", &log[i].x, &log[i].y);
maxt = max(maxt, log[i].x);
}

for (int i = 0; i <= maxt; i ++ )//时间
{
memset(cnt, 0, sizeof cnt);
for (int j = 0; j < n; j ++ ) //日志
{
int time = log[j].x;
int id = log[j].y;

if (time >= i && time < i + d)
cnt[id] ++ ;

if (cnt[id] >= k) st[id] = true;
}
}

for (int i = 0; i <= 100000; i ++ )
if (st[i])
cout << i << endl;
return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, d, k;
int cnt[N];
PII log[N];
bool st[N];

int main()
{
scanf("%d%d%d", &n, &d, &k);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &log[i].x, &log[i].y);

sort(log, log + n);

for (int i = 0, j = 0; i < n; i ++ )
{
int id = log[i].y;
cnt[id] ++ ;

while (log[i].x - log[j].x >= d)
{
cnt[log[j].y] -- ;
j ++ ;
}

if (cnt[id] >= k) st[id] = true;
}

for (int i = 0; i < 100010; i ++ )
if (st[i])
cout << i << endl;
return 0;
}


• AC
f[l][r] = max(f[l + 1][r], f[l][r - 1]);
if (s[l] == s[r]) f[l][r] = max(f[l][r], f[l + 1][r - 1] + 2);

• WA
if (s[l] == s[r]) f[l][r] = max(f[l][r], f[l + 1][r - 1] + 2);
f[l][r] = max(f[l + 1][r], f[l][r - 1]);


#### 区间dp

• 添加字母数量 = 总长度 - 最长回文串长度
• 添加字母数量=删去字母数量
• 分析
• 集合：所有S[L,R]之间的回文子序列的集合
• 属性：长度的最大值
• 状态计算：
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

char s[N];
int f[N][N];

int main()
{
scanf("%s", s);
int n = strlen(s);

for (int len = 1; len <= n; len ++ )
for (int l = 0; l + len - 1 < n; l ++ )
{
int r = l + len - 1;
if (len == 1) f[l][r] = 1;
else
{
f[l][r] = max(f[l + 1][r], f[l][r - 1]);
if (s[l] == s[r]) f[l][r] = max(f[l][r], f[l + 1][r - 1] + 2);
}
}
cout << n - f[0][n - 1] << endl;
return 0;
}


#### 区间dp 线代矩阵乘法

• 分析
• 集合：所有将(L, R)合并成一个珠子 （矩阵）的方式
• 状态计算
• 用分界线，把合并后左右两边分开，但是分开后头尾的数是共用的
• f[L, R] = max(f(L, K) + f(k, R) + w[L] * w[K] * w[R]
• 将[L,K]合并，再将[k,R]合并，最后整个合并
• 注意：
• 区间长度是n + 1，且长度从3开始枚举
• 环形dpN都要变成数据范围的两倍
#include <iostream>

using namespace std;

const int N = 210;

int n;
int w[N];
int f[N][N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> w[i];
w[i + n] = w[i];
}

for (int len = 3; len <= n + 1; len ++ )
for (int i = 1; i + len - 1 <= n * 2; i ++ )
{
int j = i + len - 1;
for (int k = i + 1; k < j; k ++ )
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]);
}

int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i][n + i]);
cout << res << endl;
}


#### dfs

• 小细节：string不能从1开始读入，只能用字符数组，要么cin >> s + 1scanf("%s", s + 1)

#### 法一：给能走过的地方都变成true，最后遍历图看是否还有false。同时要搜两次，防止起点盲区

#include <iostream>
#include <cstring>

using namespace std;

const int N = 25;

int n, m;
char opx[N], opy[N];
bool st[N][N];

bool check(int i, int j)
{
return i >= 1 && i <= n && j >= 1 && j <= m && st[i][j] == false;//st防止往回走，只能走没有走过的
}

void dfs(int i, int j)
{
st[i][j] = true;

if (check(i - 1, j) && opy[j] == '^') dfs(i - 1, j);
if (check(i, j + 1) && opx[i] == '>') dfs(i, j + 1);
if (check(i + 1, j) && opy[j] == 'v') dfs(i + 1, j);
if (check(i, j - 1) && opx[i] == '<') dfs(i, j - 1);

}

int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", opx + 1, opy + 1);

dfs(1, 1);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (!st[i][j])
{
puts("NO");
return 0;
}

memset(st, false, sizeof st);

dfs(n, m);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (!st[i][j])
{
puts("NO");
return 0;
}

puts("YES");

return 0;
}


法二：计数dfs，看图里的每个点走过的次数是否都满足n*m

//用一个数组st表示已经走过的地方，防止往回走
//dfs边界逆向思维设置
//dfs可以巧妙用if-else减少代码
//可以枚举每个起点出发，但要记得重置st数组，这样就不用dfs两次

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30;

int n, m;
char a[N], b[N];
int cnt[N][N];
bool st[N][N];

void dfs(int i, int j)
{
if (i < 1 || i > n || j < 1 || j > m || st[i][j]) return;
st[i][j] = true;
cnt[i][j] ++ ;
if (a[i] == '<') dfs(i, j - 1);
else dfs(i, j + 1);
if (b[j] == 'v') dfs(i + 1, j);
else dfs(i - 1, j);
}

int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
int s = n * m;

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
memset(st, false, sizeof st), dfs(i, j);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (cnt[i][j] != s)
{
puts("NO");
return 0;
}
puts("YES");

return 0;
}


#include <iostream>

using namespace std;

bool check(int x)
{
int cnt[10]= {0};
while (x) cnt[x % 10] ++ , x /= 10;
for (int i = 0; i <= 9; i ++ )
if (cnt[i] >= 2)
return false;
return true;
}

int main()
{
int x;
cin >> x;

for (int i = x + 1; ; i ++ )
if (check(i))
{
cout << i << endl;
return 0;
}

return 0;
}
`