头像

Mr.Szz




离线:1天前


最近来访(4)
用户头像
WBSLZF
用户头像
周肥

活动打卡代码 AcWing 1221. 四平方和

Mr.Szz
5个月前

暴力三重循环

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int n; 

// 暴力 -- 三次循环解法 
int main()
{
    scanf("%d", &n);

    for (int a=0; a*a<=n; a++)
        for (int b=a; a*a+b*b<=n; b++)
            for (int c=b; a*a+b*b+c*c<=n; c++)
            {
                int t = n - a*a - b*b - c*c;    //此处可以有效地减少一重循环 
                int d = sqrt(t);
                if (d*d == t)
                {
                    printf("%d %d %d %d", a, b, c, d);
                    return 0;
                }
            }

    return 0;
}

二分法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 250010;

int n, m;
// m的含义: 

struct Sum
{
    int s, c, d;
    // ????
    // 返回较小的那个值 
    bool operator < (const Sum &t)const
    {
        if (s != t.s)   return s < t.s;
        if (c != t.c)   return c < t.c;
        return d < t.d;
    }   
}sum[N];

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

    for (int c=0; c*c<=n; c++)
        for (int d=c; c*c+d*d<=n; d++)
            sum[m++] = {c*c+d*d, c, d};

    sort(sum, sum+m);

    for (int a=0; a*a<=n; a++)
        for (int b=a; a*a+b*b<=n; b++)
        {
            int t = n - a*a - b*b;
            int l = 0, r = m-1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t)
                    r = mid;
                else
                    l = mid + 1;
            }
            if (sum[l].s == t)
            {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }

    return 0;
}

哈希表

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

using namespace std;

const int N = 500010;

int n;
int C[N], D[N];

int main()
{
    scanf("%d", &n);
    memset(C, -1, sizeof C);

    for (int c=0; c*c<=n; c++)
        for (int d=c; c*c+d*d<=n; d++)
        {   //哈希 
            int s = c*c + d*d;
            if (C[s] == -1)
                C[s] = c, D[s] = d;
        }

    for (int a=0; a*a<=n; a++)
        for (int b=a; a*a+b*b<=n; b++)
        {
            int s = n - a*a - b*b;
            if (C[s] != -1)
            {
                printf("%d %d %d %d", a, b, C[s], D[s]);
                return 0;
            } 
        }

    return 0;
}


活动打卡代码 AcWing 1212. 地宫取宝

Mr.Szz
5个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m, k;
int w[N][N];
int f[N][N][13][14];
//  f[i][j][k] [c] 
// 所有从起点走到f(i, j),且已经取了k件物品,
// 且最后一件物品的价值是c的合法方案的集合 

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

    // 初始化
    f[1][1][1][w[1][1]] = 1;
    f[1][1][0][0] = 1; 

    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            if (i==1 && j==1)
                continue;
            for (int u=0; u<=k; u++)    // u,v的循环范围 
                for (int v=0; v<=13; v++)
                {
                    int &val = f[i][j][u][v];   // 引用

                    val = (val + f[i-1][j][u][v]) % MOD;
                    val = (val + f[i][j-1][u][v]) % MOD;
                    // 上半部分 最后一步不取 的方案数

                    // 下半部分 最后一步  取 的方案数
                    if (u>0 && v==w[i][j])  // u-1>=0
                        for (int x=0; x<v; x++)
                        {       // 注意:此时 倒数第二个数为x ,最后一个数为v 
                            val = (val + f[i-1][j][u-1][x]) % MOD;
                            val = (val + f[i][j-1][u-1][x]) % MOD;
                        }                   
                }
        }

    int res = 0;
    for (int i=0; i<=13; i++)
        res = (res + f[n][m][k][i]) % MOD;

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000 + 10;

// 二维前缀和 思想 
int n, m, q;
int a[N][N]; // 原矩阵 
int s[N][N]; // 前缀和矩阵 
// 最大10e9 不需要考虑 爆int 

int main()
{
    cin >> n >> m >> q;

    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i-1][j] + s[i][j-1]
                     - s[i-1][j-1] + a[i][j];
        }

    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);

        int res = s[x2][y2] + s[x1-1][y1-1]
                 - s[x1-1][y2] - s[x2][y1-1];
        printf("%d\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 795. 前缀和

Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

// 前缀和 理解
// 前缀和 Si 为数组的前 i 项和
// 前缀和 Sn 为数组的前 n 项和

// 作用:快速求出元素组中某段区间的和

using namespace std;

const int N = 100010;

int n, m;
int l, r;
int a[N]; // 原数组
int s[N]; // 前缀和数组 
// ***全局数组 初值 s[0] = 0 
// ***局部数组 初值 为 随机值 

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

    // 前缀和的下标一定要从 1开始, 避免进行下标的转换
    for (int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
    } 

    while (m -- )
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l-1]);      
    }

    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    double x; scanf("%lf", &x);
    double l = -10000, r = 10000;

    while (r - l > 1e-8)
    {
        // 实数二分,不存在"+1"的问题 
        // 区间划分成 [l, m] & [m, r] 
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    // 默认保留6位小数 
    printf("%lf\n", l);

    return 0;
}


活动打卡代码 AcWing 789. 数的范围

Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

/*
二分 注意点
①更新方式:r = mid   -> 不处理 -> mid = l + r    >> 1
②更新方式:l = mid ->   处理 -> mid = l + r + 1 >> 1
*/

using namespace std;

const int N = 100000 + 10;

int n, m;   // 数组长度 & 查询个数 
int q[N];   // 数组 

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

    // 对m个数x进行查询 
    for (int i=0; i<m; i++)
    {
        int x; scanf("%d", &x);
        int l = 0, r = n-1; // 二分区间 

        // 查询二分x的左端点 
        // 不小于该元素的最小位置
        while (l < r)       
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) 
                r = mid;    // <<<=====
            else
                l = mid + 1;
        }

        if (q[r] == x)
        {
            // 输出左端点 
            cout << r << " ";

            // 查询二分x的右端点
            // 不大于该元素的最大位置
            r = n - 1; // 右端点一定在【左端点,n-1】之间
            while (l < r)
            {           // l = mid -> "+1"
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x)
                    l = mid;    // <<<=====
                else
                    r = mid - 1;
            } 
            // 输出右端点 
            cout << r << endl;
        }
        else cout << "-1 -1" << endl;       
    } 

    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

// 字符串 最后有一个“\0” 长度是5的字符串需要6位 
const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0};
int dy[5] = { 0, 1, 0,-1, 0};

void turn(int x, int y)
{
    for (int i=0; i<5; i++)
    {
        int a = x + dx[i];
        int b = y + dy[i];

        if (a<0 || a>=5 || b<0 || b>=5)
            continue;   //  在边界[0,4]外,直接忽略即可

        // 异或的结果 (0^1=1 & 1^1=0) (不同取1,同取0)
        // 使用位运算 (异或 ^ 一个1 即可)
        // 0 & 1 改变状态的互换 
        g[a][b] ^= 1;   // g[a][b] = g[a][b] ^ 1

        // 也可以用 if 判断 
        // 0 的 ASCII:48 = 32 + 16 = 110000 
        // 1 的 ASCII:49 = 32+16+1 = 110001 
        // 只有最后一位不一样 
    }
}

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

    while (T -- )
    {
        for (int i=0; i<5; i++)
            cin >> g[i];

        int res = 10;   // 最大值 最多需要多少步 (不超过6步的)

        // 32 = 2 ^ 5   枚举第一行的操作 即确定32种方案 
        for (int op=0; op<32; op++)
        {
            memcpy(backup, g, sizeof g);
            int step = 0;

            // 使用 *二进制* 表示 
            // 对第一行进行枚举 共 2^5=32 情况 
            for (int i=0; i<5; i++)
                // ******位运算******* 
                // i>>k & 1:i右移k位 
                if (op>>i & 1)
                {
                    step++;
                    turn(0, i);
                } 

            // 一直到倒数第二行 
            for (int i=0; i<4; i++)
                for (int j=0; j<5; j++)
                    if(g[i][j] == '0')  // 算法思想 
                    {
                        step++;
                        turn(i+1, j);   // 对下一行控制开关 来影响上一行的 0灯 
                    }

            bool dark = false;
            // 判断第5行(最后一行) 是否存在0灯 
            for (int i=0; i<5; i++)
                if (g[4][i] == '0')
                {
                    dark = true;
                    break;
                }

            if (!dark) res = min(res, step);
            memcpy(g, backup, sizeof backup);
            // copy回来 做下一次判断 共32次 

        }   // for 测试一组数据 

        if (res > 6) res = -1;      
        cout << res <<endl;                                     
    }

    return 0;
}


活动打卡代码 AcWing 717. 简单斐波那契

Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

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

    int f[46];
    f[1] = 0; f[2] = 1;

    for (int i=3; i<=n; i++)    f[i] = f[i-1] + f[i-2];

    for (int i=1; i<=n; i++)    cout<<f[i]<<" ";
    //cout<<endl;

    return 0;
}

减小空间复杂度 滚动数组的雏形

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

using namespace std;

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

    int a = 0, b = 1;
    for (int i=1; i<=n; i++)
    {
        // 滚动数组的雏形 
        cout << a << " ";
        int fn = a + b;
        a = b;
        b = fn; 
    }

    return 0;
}


活动打卡代码 AcWing 1209. 带分数

Mr.Szz
6个月前

dfs的嵌套组合


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

using namespace std;
typedef long long ll;

const int N = 20; 

int n;
bool st[N], backup[N];
int ans;

bool check(int a, int c)
{
    ll b = n * (ll)c - a * c;

    if (!a || !b || !c) return false;

    memcpy(backup, st, sizeof st);

    while (b)
    {
        int x = b % 10; // 取个位 
        b /= 10;        // 删个位 

        // !x
        if (!x || backup[x])    return false;
        backup[x] = true;
    }

    for (int i=1; i<=9; i++)
        if (!backup[i])
            return false;

    return true;
}

void dfs_c(int u, int a, int c)
{
    if (u == n) return;

    if (check(a, c))    ans ++ ;

    for (int i=1; i<=9; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
    }
}

void dfs_a(int u, int a)
{
    if (a >= n) return;

    if (a)  dfs_c(u, a, 0);

    for (int i=1; i<=9; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;  // 恢复现场 
        }
    }
}

int main()
{
    cin >> n;

    dfs_a(0, 0);

    cout << ans << endl;

    return 0;
}



Mr.Szz
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25 + 5;

int n, m;
int way[N]; // 0 表示 还没放数,1~n 表示放了哪个数

void dfs(int u, int start)
{
    // ****剪枝优化**** 此处 快3倍速度 
    if ( u+n-start < m) 
        return ;    // 如果把后面数都选上,都不够m个数,当前分支就一定无解 
    // ****剪枝优化**** 

    // u > m
    if (u == m+1)   // 递归出口 
    {
        for (int i=1; i<=m; i++)
            printf("%d ", way[i]);
        puts("");

        return;
    }

    for (int i=start; i<=n; i++)
    {
        way[u] = i;
        dfs(u+1, i+1);
        way[u] = 0;     // 恢复现场 
    } 
}

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

    dfs(1, 1);

    return 0;
}