头像

我是java同学




离线:1小时前


最近来访(523)
用户头像
神仙
用户头像
yxc的小迷妹
用户头像
wujiay
用户头像
Samuel_Yun
用户头像
因特麦克斯
用户头像
躺平与摆烂之神
用户头像
御键鼠
用户头像
mhmh
用户头像
萌新_摸索中
用户头像
Vegetable_Coder
用户头像
小郑同学
用户头像
高叶
用户头像
huangbq
用户头像
zst_2001
用户头像
柏原桃
用户头像
陳词.
用户头像
wcz
用户头像
Prime.浅梦
用户头像
北斗_76
用户头像
q2045891621


dfs 二进制枚举

dfs

很多值得学习的地方,很多细节

#include <bits/stdc++.h>

using namespace std;

const int N = 11, INF = 0x3f3f3f3f;

char str[N];
int res = INF;

bool check(int x)
{
    int t = (int)sqrt(x);//强制转换,可能是浮点数
    return x && t * t == x;//x>0很关键
}

void dfs(int u, int t, int s)
{
    if (!str[u]) {//枚举到字符串最后一位,注意不能写str[u] == '0',含义不一样,或者可以写str[u] == '\0'
        if (check(s)) res = min(res, t);
        return;
    }

    //t和t+1的理解:
    //t表示在当前位置不再删除新的数字
    //t + 1表示在当前位置删除一个新的数字

    dfs(u + 1, t + 1, s);//分割出完全平方数,s不变
    if (s || str[u] != '0') //s不能为0,同时避免添加前导零
        dfs(u + 1, t, s * 10 + str[u] - '0');

    //两个dfs递归函数参数t的理解、
    //思路是反向的,因为不是删数,而是添数(如果是正向,删除任意一位数字不好删)
    //如果s不变,那就是相当于删去一个数字,所以t+1
    //如果s变,那就是相当于数字不变,所以是t
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        scanf("%s", str);
        res = INF;//每组测试数据res要重置
        dfs(0, 0, 0);//搜索到第几位数字,已经删除了t个完全平方数,删除数字后的数字之和s
        if (res == INF) puts("-1");
        else cout << res << endl;
    }

    return 0;
}
二进制枚举
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        string str;
        cin >> str;
        int n = str.size();

        int res = INF;
        for (int i = 0; i < 1 << n; i ++ ) 
        {
            int x = 0;
            for (int j = 0; j < n; j ++ ) 
                if (i >> j & 1) 
                    x = x * 10 + str[j] - '0';

            int t = sqrt(x);                    //从 size_t 转换成整型
            if (x && t * t == x) res = min(res, n - (int)to_string(x).size());
        }   //减去的数字个数等于总的数字个数-添的数字个数
        if (res == INF) res = -1;
        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 3796. 凑平方

dfs 二进制枚举

dfs

很多值得学习的地方,很多细节

#include <bits/stdc++.h>

using namespace std;

const int N = 11, INF = 0x3f3f3f3f;

char str[N];
int res = INF;

bool check(int x)
{
    int t = (int)sqrt(x);//强制转换,可能是浮点数
    return x && t * t == x;//x>0很关键
}

void dfs(int u, int t, int s)
{
    if (!str[u]) {//枚举到字符串最后一位
        if (check(s)) res = min(res, t);
        return;
    }

    //t和t+1的理解:
    //t表示在当前位置不再删除新的数字
    //t + 1表示在当前位置删除一个新的数字

    dfs(u + 1, t + 1, s);//分割出完全平方数,s不变
    if (s || str[u] != '0') //!= '0'避免前导零
        dfs(u + 1, t, s * 10 + str[u] - '0');

    //两个dfs递归函数参数t的理解、
    //思路是反向的,因为不是删数,而是添数(如果是正向,删除任意一位数字不好删)
    //如果s不变,那就是相当于删去一个数字,所以t+1
    //如果s变,那就是相当于数字不变,所以是t
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        scanf("%s", str);
        res = INF;//每组测试数据res要重置
        dfs(0, 0, 0);//搜索到第几位数字,已经删除了t个完全平方数,删除数字后的数字之和s
        if (res == INF) puts("-1");
        else cout << res << endl;
    }

    return 0;
}
二进制枚举
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        string str;
        cin >> str;
        int n = str.size();

        int res = INF;
        for (int i = 0; i < 1 << n; i ++ ) 
        {
            int x = 0;
            for (int j = 0; j < n; j ++ ) 
                if (i >> j & 1) 
                    x = x * 10 + str[j] - '0';

            int t = sqrt(x);                    //从 size_t 转换成整型
            if (x && t * t == x) res = min(res, n - (int)to_string(x).size());
        }   //减去的数字个数等于总的数字个数-添的数字个数
        if (res == INF) res = -1;
        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 3795. 计算abc

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int x[5];
    for (int i = 1; i <= 4; i ++ ) cin >> x[i];

    sort(x + 1, x + 4 + 1);
    cout << x[4] - x[3] << ' ' << x[4] - x[2] << ' ' << x[4] - x[1] << ' ' << endl;
    return 0;
}


活动打卡代码 AcWing 3788. 截断数组

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
int s[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i], s[i] += s[i - 1];

    int res = 0;
    for (int i = 1; i < n; i ++ ) //注意i不能取到n,不然第二部分数组的值就为0
        if (2 * s[i] == s[n]) res ++ ;//s[i] = s[n] - s[i];

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 3787. 整除

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int a, b;
        cin >> a >> b;
        if (!(a % b)) puts("0");
        else cout << b - (a % b) << endl;
    }

    return 0;
}



状态压缩dp

维护三层状态来保证合法性,第i - 2层为c,第i - 1层为b,第i层为a
QQ图片20230602201453.png

[行内合法]一行中合法状态:不能有相邻的两个1,不能含有101的状态
[行间合法]排除任意两行同列不能存在1,同时要适配地形,只有平原才能被放置

状态表示:f[i][a][b]表示已摆放前i行,当前是第i行第a个状态,并且是第i-1行第b个状态时,能摆放的最大数量

滚动数组优化:i & 1,奇数&1就是1,偶数就是0

未优化

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1 << 10;

int n, m;
int g[N];
int cnt;
int s[M];
int num[M];
int f[N][M][M];

int main()
{
    scanf("%d%d", &n, &m);
    //预处理地图
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < m; j ++ ) 
        {
            char c;
            cin >> c;                              //保存地图各行数值
            if (c == 'P') g[i] += 1 << (m - j - 1);//比如:phhp->g[1]=9, hphp->g[2]=5
        }

    //预处理合法状态和1的个数
    for (int i = 0; i < (1 << m); i ++ ) 
        if (!(i & i >> 1) && !(i & i >> 2))//如果不存在11或101
        {
            s[cnt ++ ] = i;
            for (int j = 0; j < m; j ++ ) 
                num[i] += (i >> j & 1);//统计合法状态包含1的个数(炮兵的个数)
        }

    //状态计算
    for (int i = 1; i <= n + 2; i ++ ) 
        for (int a = 0; a < cnt; a ++ ) 
            for (int b = 0; b < cnt; b ++ ) 
                for (int c = 0; c < cnt; c ++ ) 
                    if (!(s[a] & s[b]) && !(s[a] & s[c]) && !(s[b] & s[c])//1是否合法,是否时平原
                        && (g[i] & s[a]) == s[a] && (g[i - 1] & s[b]) == s[b])//能否在地图上放置炮兵 
                        f[i][a][b] = max(f[i][a][b], f[i - 1][b][c] + num[s[a]]);

    cout << f[n + 2][0][0] << endl;
    return 0;
}

优化

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1 << 10;

int n, m;
int g[N];
int cnt;
int s[M];
int num[M];
int f[2][M][M];

int main()
{
    scanf("%d%d", &n, &m);
    //预处理地图
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < m; j ++ ) 
        {
            char c;
            cin >> c;                              //保存地图各行数值
            if (c == 'P') g[i] += 1 << (m - j - 1);//比如:phhp->g[1]=9, hphp->g[2]=5
        }

    //预处理合法状态和1的个数
    for (int i = 0; i < (1 << m); i ++ ) 
        if (!(i & i >> 1) && !(i & i >> 2))//如果不存在11或101
        {
            s[cnt ++ ] = i;
            for (int j = 0; j < m; j ++ ) 
                num[i] += (i >> j & 1);//统计合法状态包含1的个数(炮兵的个数)
        }

    //状态计算
    for (int i = 1; i <= n + 2; i ++ ) 
        for (int a = 0; a < cnt; a ++ ) 
            for (int b = 0; b < cnt; b ++ ) 
                for (int c = 0; c < cnt; c ++ ) 
                    if (!(s[a] & s[b]) && !(s[a] & s[c]) && !(s[b] & s[c])//1是否合法,是否时平原
                        && (g[i] & s[a]) == s[a] && (g[i - 1] & s[b]) == s[b])//能否在地图上放置炮兵 
                        f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + num[s[a]]);

    cout << f[n + 2 & 1][0][0] << endl;
    return 0;
}


活动打卡代码 AcWing 292. 炮兵阵地

状态压缩dp

维护三层状态来保证合法性,第i - 2层为c,第i - 1层为b,第i层为a
QQ图片20230602201453.png

[行内合法]一行中合法状态:不能有相邻的两个1,不能含有101的状态
[行间合法]排除任意两行同列不能存在1,同时要适配地形,只有平原才能被放置

状态表示:f[i][a][b]表示已摆放前i行,当前是第i行第a个状态,并且是第i-1行第b个状态时,能摆放的最大数量

滚动数组优化:i & 1,奇数&1就是1,偶数就是0

未优化

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1 << 10;

int n, m;
int g[N];
int cnt;
int s[M];
int num[M];
int f[N][M][M];

int main()
{
    scanf("%d%d", &n, &m);
    //预处理地图
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < m; j ++ ) 
        {
            char c;
            cin >> c;                              //保存地图各行数值
            if (c == 'P') g[i] += 1 << (m - j - 1);//比如:phhp->g[1]=9, hphp->g[2]=5
        }

    //预处理合法状态和1的个数
    for (int i = 0; i < (1 << m); i ++ ) 
        if (!(i & i >> 1) && !(i & i >> 2))//如果不存在11或101
        {
            s[cnt ++ ] = i;
            for (int j = 0; j < m; j ++ ) 
                num[i] += (i >> j & 1);//统计合法状态包含1的个数(炮兵的个数)
        }

    //状态计算
    for (int i = 1; i <= n + 2; i ++ ) 
        for (int a = 0; a < cnt; a ++ ) 
            for (int b = 0; b < cnt; b ++ ) 
                for (int c = 0; c < cnt; c ++ ) 
                    if (!(s[a] & s[b]) && !(s[a] & s[c]) && !(s[b] & s[c])//1是否合法,是否时平原
                        && (g[i] & s[a]) == s[a] && (g[i - 1] & s[b]) == s[b])//能否在地图上放置炮兵 
                        f[i][a][b] = max(f[i][a][b], f[i - 1][b][c] + num[s[a]]);

    cout << f[n + 2][0][0] << endl;
    return 0;
}

优化

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1 << 10;

int n, m;
int g[N];
int cnt;
int s[M];
int num[M];
int f[2][M][M];

int main()
{
    scanf("%d%d", &n, &m);
    //预处理地图
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j < m; j ++ ) 
        {
            char c;
            cin >> c;                              //保存地图各行数值
            if (c == 'P') g[i] += 1 << (m - j - 1);//比如:phhp->g[1]=9, hphp->g[2]=5
        }

    //预处理合法状态和1的个数
    for (int i = 0; i < (1 << m); i ++ ) 
        if (!(i & i >> 1) && !(i & i >> 2))//如果不存在11或101
        {
            s[cnt ++ ] = i;
            for (int j = 0; j < m; j ++ ) 
                num[i] += (i >> j & 1);//统计合法状态包含1的个数(炮兵的个数)
        }

    //状态计算
    for (int i = 1; i <= n + 2; i ++ ) 
        for (int a = 0; a < cnt; a ++ ) 
            for (int b = 0; b < cnt; b ++ ) 
                for (int c = 0; c < cnt; c ++ ) 
                    if (!(s[a] & s[b]) && !(s[a] & s[c]) && !(s[b] & s[c])//1是否合法,是否时平原
                        && (g[i] & s[a]) == s[a] && (g[i - 1] & s[b]) == s[b])//能否在地图上放置炮兵 
                        f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + num[s[a]]);

    cout << f[n + 2 & 1][0][0] << endl;
    return 0;
}



状态压缩dp

[行内合法]:同一行不能有相邻的1
[行间兼容]:同一列不能有相邻的1
状态表示:f[i][a]:表示已经种植前i行,第i行第a个状态时的方案数

#include <bits/stdc++.h>

using namespace std;

const int N = 14, M = 1 << N, mod = 1e8;

int n, m;
int s[M];
int g[N];
int cnt;
int f[N][M];

int main()
{
    scanf("%d%d", &n, &m);
    //预处理
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) 
        {
            int x;
            cin >> x;               //保存各行的状态值
            g[i] = (g[i] << 1) + x; //1 0 1 -> 101
        }

    for (int i = 0; i < 1 << m; i ++ ) //枚举一行所有的状态
        if (!(i & i >> 1)) //如果不存在相邻的1
            s[cnt ++ ] = i; //保存一行的合法状态

    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ ) //枚举行
        for (int a = 0; a < cnt; a ++ ) //枚举第i行的合法状态
            for (int b = 0; b < cnt; b ++ ) //枚举第i - 1行的合法状态
                if ((s[a] & g[i]) == s[a] && !(s[a] & s[b]))//a种在1上,a、b同列不同时为1
                    f[i][a] = (f[i][a] + f[i - 1][b]) % mod;

    cout << f[n + 1][0] << endl;
    return 0;
}


活动打卡代码 AcWing 327. 玉米田

状态压缩dp

[行内合法]:同一行不能有相邻的1
[行间兼容]:同一列不能有相邻的1
状态表示:f[i][a]:表示已经种植前i行,第i行第a个状态时的方案数

#include <bits/stdc++.h>

using namespace std;

const int N = 14, M = 1 << N, mod = 1e8;

int n, m;
int s[M];
int g[N];
int cnt;
int f[N][M];

int main()
{
    scanf("%d%d", &n, &m);
    //预处理
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) 
        {
            int x;
            cin >> x;               //保存各行的状态值
            g[i] = (g[i] << 1) + x; //1 0 1 -> 101
        }

    for (int i = 0; i < 1 << m; i ++ ) //枚举一行所有的状态
        if (!(i & i >> 1)) //如果不存在相邻的1
            s[cnt ++ ] = i; //保存一行的合法状态

    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ ) //枚举行
        for (int a = 0; a < cnt; a ++ ) //枚举第i行的合法状态
            for (int b = 0; b < cnt; b ++ ) //枚举第i - 1行的合法状态
                if ((s[a] & g[i]) == s[a] && !(s[a] & s[b]))//a种在1上,a、b同列不同时为1
                    f[i][a] = (f[i][a] + f[i - 1][b]) % mod;

    cout << f[n + 1][0] << endl;
    return 0;
}



哈希表

判断给定的 k 个序列中是否存在两个序列,它们在去掉任意一个元素后的剩余元素之和相等。

思路:首先读入每个序列,并计算该序列中所有元素的和 sum。然后枚举序列中每一个元素,在 map 中查找是否存在一个key 值等于 sum 减去当前元素的值的项。如果存在,则说明存在两个序列在去掉一个元素后剩余元素之和相等,输出相应的信息并结束程序;否则将 sum 减去当前元素的值作为新的 key 值,并记录当前元素所在序列的编号和元素的下标。

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int w[N];

int main()
{
    int k;
    scanf("%d", &k);

    unordered_map<int, PII> S;
    for (int i = 1; i <= k; i ++ ) 
    {
        int n, sum = 0;
        scanf("%d", &n);
        for (int j = 1; j <= n; j ++ ) 
        {
            scanf("%d", &w[j]);
            sum += w[j];
        }

        for (int j = 1; j <= n; j ++ ) 
        {
            int t = sum - w[j];
            if (S.count(t) && S[t].x != i) 
            {
                puts("YES");
                printf("%d %d\n", S[t].x, S[t].y);
                printf("%d %d\n", i, j);
                return 0;
            }
            S[t] = {i, j};
        }
    }

    puts("NO");

    return 0;
}