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开始枚举
  • 环形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)

法一：给能走过的地方都变成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;
}