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;
}
}
双指针 二分 哈希
#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;
}
双指针
#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;
}
双指针
#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;
}
为什么这两条语句交换顺序答案就不一样了
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);
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]
n + 1
,且长度从3开始枚举dp
的N
都要变成数据范围的两倍#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 + 1
或scanf("%s", s + 1)
#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;
}