头像

我是java同学




离线:7小时前


最近来访(297)
用户头像
冠生
用户头像
日川纲坂
用户头像
Paren
用户头像
源泉
用户头像
冷静对待一切
用户头像
Amaryllis_
用户头像
我才不认识这个人
用户头像
源泉-小号
用户头像
sealt
用户头像
optimjie
用户头像
111111
用户头像
NANAWOAKARI
用户头像
y总的小迷弟cxr
用户头像
hyh_OneSelf
用户头像
Lucky_Man
用户头像
吊车尾92
用户头像
啦啦啦啦啦啦啦啦
用户头像
18910310021
用户头像
给梁梁买小狗
用户头像
三.小

活动打卡代码 AcWing 1112. 迷宫

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;
}



双指针

  • 第一类:两个序列上的双指针
  • 第二类:同一序列的双指针
  • 写法:QQ图片20230204172113.png
  • 时间复杂度:$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;
}


题目讨论 AcWing 1222. 求助

为什么这两条语句交换顺序答案就不一样了

  • 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]之间的回文子序列的集合
    • 属性:长度的最大值
    • 状态计算:98C1AEB891426F1334327041B60449A9.png
#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 线代矩阵乘法

  • 分析
    • QQ图片20230203140018.jpg
  • 集合:所有将(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;
}


活动打卡代码 AcWing 4800. 下一个

#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;
}