头像

理想世界

whpu




离线:25分钟前


最近来访(87)
用户头像
坠明
用户头像
圆圆_5
用户头像
菜狗一个
用户头像
XCX
用户头像
_huge
用户头像
kuan525
用户头像
super_0
用户头像
xuanxuanxuan
用户头像
1711619194
用户头像
用户头像
open-source
用户头像
夏日的小提琴
用户头像
10631179
用户头像
snkz5qing
用户头像
晓龙coding
用户头像
余睿
用户头像
limie
用户头像
would
用户头像
一只奇怪的小魔女
用户头像
我代码呢

活动打卡代码 AcWing 3783. 第 k 个除数

理想世界
12小时前

一时间没有想到可以用数组把所有可能加进来后排个序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
using LL = long long;
LL m, k;
vector<LL>num;

bool check(LL x)
{
    return !(m % x);
}

int main()
{
    cin >> m >> k;

    for(LL i = 1; i * i <= m; ++ i)
    {
        if(check(i)) 
        {
            num.push_back(i);
            if(i != m / i) num.push_back(m / i);
        }
    }
    sort(num.begin(), num.end());
    if(k <= num.size()) cout << num[k - 1];
    else cout << -1;
    return 0;
}


活动打卡代码 AcWing 3782. 点

当输入很多时还得用本地的来调式

//单向  每个点的平方出现(n - 1)次    减去
//10的5次方跑几次就爆了吧
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;
long long a[N], b[N];
int n;

int main()
{
    cin >> n;
    long long t1 = 0, t2 = 0;
    long long ans = 0;

    for (int i = 0; i < n; i ++ ) 
    {
        scanf("%lld %lld", &a[i], &b[i]);
        t1 += a[i];
        t2 += b[i];
        ans += n * (a[i] * a[i] + b[i] * b[i]);
    }

    //ans *= n;

    for (int i = 0; i < n; i ++ )
    {

        ans -= a[i] * t1;
        ans -= b[i] * t2;
    }

    cout << ans;
    return 0;
}


活动打卡代码 AcWing 3781. 乘车问题

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

using namespace std;

const int N = 105;
int T, a[N], m, n;

int main()
{
    cin >> T;
    while (T --)
    {
        memset(a, 0, sizeof a);
        cin >> n >> m; //每个大巴车可以容纳 m 个小朋友
        for(int i = 0; i < n; ++ i) cin >> a[i];
        int tmp = a[0], ans = 1;
        for(int i = 1; i < n; i ++ )
        {
            if(tmp + a[i] <= m)
            {
                tmp += a[i];

            }

            else
            {
                ans ++ ;
                tmp = a[i];
            }
        }

        cout << ans << endl;
    }

    return 0;
}



参考大神题解

//一个从正下方到结果的左  正右边到结果的上
//两人的下标不能相同
//走 n + m - 1 步
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int n, m;
int w[N][N];
int f[N * 2][N][N];

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

    //f[k, i, j]
    //只有一步是在起点
    for(int k = 2; k <= n + m; ++ k)
        //看需不需要向右走
        //i j 都是横坐标
        for(int i = max(1, k - m); i <= n && i < k; ++ i)
            for(int j = max(1, k - m); j <= n && j < k; j ++ )
                //四个方向  下下 下右 右下 右右
                if(i != j)
                    for(int a = 0; a <= 1; a ++ )
                        for(int b = 0; b <= 1; ++ b)
                        {
                                //f[k, i, j]
                                //都少走一步,从上一步转移  i j都是横坐标 + 当前
                                //后面的会先被遍历
                                //f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
                                f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
                        }
    //刚好在 一个正上方 一个正左方  还有一步不用走, 也走不到
    printf("%d\n", f[n+m-1][n][n-1]);
    return 0;
}


活动打卡代码 AcWing 3777. 砖块

可以只改变两个颜色而不改变它们中间的颜色
判断下能不能改变 以及 要怎么改变

//B or W要是偶数
//改变有偶数且个数少的
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int ou, ji, T, n;
char x;
const int N = 205;
bool b[N];

void f(){
    exit(0);
}

int main()
{
    cin >> T;
    while(T -- )
    {
        ji = ou = 0;
        memset(b, 0, sizeof b);
        vector<int> a1 , a2;   //把下标找到
        cin >> n;
        for(int i = 1; i <= n; ++ i)
        {
            cin >> x;
            if(x == 'B')
            {
                a1.push_back(i);
                b[i] = true;
                ji ++ ;
            }
            else 
            {
                ou ++ ;
                a2.push_back(i);
            }
        }

        int s1 = 0, s2 = 0;
        if(a1.size() >= 2) for(int i = 1; i < a1.size(); i += 2) s1 += a1[i] - a1[i-1]; 
        if(a2.size() >= 2) for(int i = 1; i < a2.size(); i += 2) s2 += a2[i] - a2[i-1];
        //cout << s1 << ' ' << s2 << endl;

        //f();

        if((ji & 1) && (ou & 1))    puts("-1");
        else if(!ji || !ou) puts("0"); 

        else
        {
            int flag = 0;  //默认改变true ji B
            //B是ji  W是ou
            if((ji & 1)) flag = 1;
            else if(ou & 1);
            else if(ou < ji) flag = 1;

            printf("%d\n", flag ? s2 : s1);

            //如果 0 改 true   1 改 false
            if(!flag)
            {
                for(int i = 0; i < a1.size(); i += 2)
                {
                    for(int j = a1[i]; j < a1[i + 1]; ++ j)
                    {
                        printf("%d ", j);
                    }
                }
            }

            else
            {
                for(int i = 0; i < a2.size(); i += 2)
                {
                    for(int j = a2[i]; j < a2[i + 1]; ++ j)
                    {
                        printf("%d ", j);
                    }
                }
            }
            puts("");
        }
    }
    return 0;
}



有序嘛 dfs加上从i开始向后枚举
写的时候还忘记了if(!b[i])

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

using namespace std;

const int N = 26;
bool b[N];
int m, n;

//让u是填的个数
void dfs(int u, int x)
{
    //m里面挑n个
    //终止
    //printf("u : %d\n", u);
    if(u == n)
    {
        for(int i = 1; i <= m; ++ i)
        {
            if(b[i]) printf("%d ", i);
        }
        puts("");
        return ;
    }

    for(int i = x; i <= m; ++ i)
    {
        if(!b[i])
        {
            b[i] = true;
            dfs(u + 1, i);
            b[i] = false;
        }

    }
}

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

    dfs(0, 1);

    return 0;
}



//有四种可能
//但是要标记个数
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 355, M = 45;
int n, m, w[N], dp[M][M][M][M], c[5];

int main()
{
    int x;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    for(int i = 1; i <= m; ++ i) 
    {
        cin >> x;
        c[x] ++ ;  //卡牌数
    } 

    //要不要用n步经过该点
    for(int i = 0; i <= c[1]; ++ i)
    {
        for(int j = 0; j <= c[2]; ++ j)
        {
            for(int k = 0; k <= c[3]; ++ k)
            {
                for(int q = 0; q <= c[4]; ++ q)
                {
                    int we = w[1 + i + 2 * j + 3 * k + 4 * q];  //0也要算
                    int &W = dp[i][j][k][q];
                    //最基础的初始值
                    W= we; 
                    //再算出能不能由前面的状态转移过来
                    if(i) W = max(W, we + dp[i-1][j][k][q]);    //用一张1跑
                    if(j) W = max(W, we + dp[i][j-1][k][q]);
                    if(k) W = max(W, we + dp[i][j][k-1][q]);
                    if(q) W = max(W, we + dp[i][j][k][q-1]);
                    //cout << W << ' ';
                }
            }
        }
    }
    cout << dp[c[1]][c[2]][c[3]][c[4]];
    return 0;
}


活动打卡代码 AcWing 3776. 水果拼盘

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

using namespace std;
int T, a, b, c, d, e, f;

int main()
{
    cin >> T;
    while (T --)
    {
        int ans = 0;
        cin >> a >> b >> c >> d >> e >> f;
        if(e >= f)
        {
            ans += min(a, d) * e;
            d -= min(a, d);
            ans += min(min(b, c), d) * f;
        }
        else
        {
            ans += min(min(b, c), d) * f;
            d -= min(min(b, c), d);
            ans += min(a, d) * e;
        }
        cout << ans << endl;
    }

}



最后一个数据爆int
a是每个方案
f[i][j]代表i下标最大j个

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

using namespace std;

const int N = 33;
long long n, L, I;
long long f[N][N], a[N][N];  //f dp   a 方案

int main()
{
    //几位数 1的个数 第I个最小的数
    cin >> n >> L >> I;
    //算a
    for (int i = 0; i <= n; i ++ )
    {
        for (int j = 0; j <= i; j ++ )
        {
            if(!j) a[i][j] = 1;
            else a[i][j] = a[i-1][j] + a[i-1][j-1];
        }
    }

    //算dp
    //第i位的最大位数   j可以大于i
    for(int i = 0; i <= n; i ++ )
    {
        for (int j = 0; j <= n; j ++ )
        {
            for(int k = 0; k <= j; ++ k)
            {
                f[i][j] += a[i][k];
            }
        }
    }

    //从总数I里面减 L个1
    for(int i = n; i > 0; -- i)
    {
        if(f[i-1][L] < I)
        {
            cout << 1;
            //减去小于自己的
            I -= f[i-1][L];
            -- L;
        }
        else cout << 0;
    }

    return 0;
}


活动打卡代码 AcWing 3775. 数组补全

把要填的先逆序一下 这个时候最多只会有一个点的下标不满足要求 判断下就行了

//遍历两遍暴力求解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 2e5 + 5;
int T, a[N], n, x;
bool b[N];
int main()
{
    cin >> T;
    while (T --)
    {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        cin >> n;
        for(int i = 1; i <= n; ++ i)
        {
            scanf("%d", &x);
            //a 填入能直接输出的
            if(x) a[i] = x;
            //能直接被输出的数字标记
            b[a[i]] = 1;
        }

        vector<int> bu;
        //将要补全的数字全部列出来
        for(int i = 1; i <= n; ++i )
        {
            if(!b[i]) bu.push_back(i);
        }

        //逆序  最多有一个不符要求
        reverse(bu.begin(), bu.end());
        int qq = bu[0];
        int k = 0;
        for(int i = 1; i <= n; ++ i)
        {
            if(!a[i])
            {
                if(bu[k++] == i)
                {
                    if(k != 1)
                        swap(bu[k - 1], bu[0]);
                    else
                        swap(bu[k - 1], bu[bu.size() - 1]);
                    break;
                }
            }
        }

        k = 0;
        for(int i = 1; i <= n; ++ i)
        {
            if(a[i]) printf("%d ", a[i]);
            else
            {
                printf("%d ", bu[k++]);
            }
        }
        puts("");
    }
    return 0;
}