首页 > 其他分享 >第三周训练题单

第三周训练题单

时间：2023-07-28 09:45:36浏览次数：35  
标签：训练 int 第三周 cin long vector rA rB 题单

数字三角形

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    while( cin >> n){
        for( int i = 1 ; i <= n ; i ++ ){
            for( int j = 1 ; j <= i ; j ++ )
                cout << j << " ";
            cout <<"\n";
        }
    }
    return 0;
}

走楼梯

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> f(n+1);
    f[0] = f[1] = 1;
    for( int i = 2 ; i <= n ; i ++ )
        f[i] = f[i-1] + f[i-2];
    cout << f[n] << "\n";
    return 0;
}

最大子串和

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n , res = 0;
    cin >> n;
    for( int i = 1 , x , cnt = 0; i <= n ; i ++ ){
        cin >> x;
        cnt = max( 0ll , cnt + x );
        res = max( res , cnt );
    }
    cout << res << "\n";
    return 0;
}

失衡天平

\(f[i][j]\)从前 i 个物品中选择，且重量差为\(j\)时可以选择到的最大重量。转移的时候其实考虑三种情况

  1. \(a_i\)不要
  2. \(a_i\)要，且放在之前更重的一侧，此时\(j\)会变大。
  3. \(a_i\)要，且放在之前更轻的一侧，此时\(j\)会变小，但是\(j\)可能会变成负数，所以要取绝对值
#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k, m = 0;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i], m += a[i];
    vector f(n + 1, vector<int>(m + 1, INT_MIN));
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++){
            f[i][j] = f[i-1][j];
            f[i][j] = max( f[i][j] , f[i-1][ abs( j - a[i] ) ] + a[i] );
            if( j + a[i] <= m ) f[i][j] = max( f[i][j] , f[i-1][j+a[i]] + a[i] );
        }

    }
    int res = 0;
    for( int i = 0 ; i <= k ; i ++ )
        res = max( res , f[n][i] );
    cout << res << "\n";
    return 0;
}

多重背包

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n , m;
    cin >> n >> m;
    vector<int> t(n+1) , w(n+1) , v(n+1);
    for( int i = 1 ; i <= n ; i ++ )
        cin >> t[i] >> w[i] >> v[i];
    vector f( n+1 , vector<int>(m) );
    int res = 0;
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 0 ; j <= m ; j ++ ){
            f[i][j] = f[i-1][j];
            for( int k = 1 ; k <= t[i] && k * w[i] <= j ; k ++ )
                f[i][j] = max( f[i][j] , f[i-1][ j - k * w[i] ] + k * v[i] );
            res = max( res , f[i][j] );
        }
    cout << res << "\n";
    return 0;
}

货币系统

从小到大逐个检查当前货币能否被替代。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a)
        cin >> i;
    sort(a.begin(), a.end());
    vector<int> v(a.back() + 1);
    int res = 0;
    for (auto i: a) {
        if (v[i]) continue;
        v[i] = 1, res++;
        for (int j = 0; i + j < v.size(); j++)
            if (v[j] ) v[i + j] = 1;
    }

    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    for (; t; t--)
        solve();
    return 0;
}

合并回文子串

\(f[lA][rA][lB][rB]\)表示字符串\(A[lA,rA]\)和\(B[lB,rB]\)能否拼成回文串，然后考虑区间 dp 去扩展。因为要求了串内是顺序不能改变，所以新扩展的只能是\((A[lA],A[rA]),(B[lB],B[rB]),(A[lA],B[rB]),(B[lB],A[rA])\)四种情况。逐个去判断能够扩展即可。注意所有长度小于等于 1 的串都可以认为是回文串。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 55;
int f[N][N][N][N];


void solve() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    memset( f , 0 , sizeof(f) );
    int res = 0;
    for (int lenA = 0; lenA <= n; lenA++)
        for (int lenB = 0; lenB <= m; lenB++)
            for (int lA = 1, rA = lenA; rA <= n; lA++, rA++)
                for (int lB = 1, rB = lenB; rB <= m; lB++, rB++) {
                    if (lenA + lenB <= 1) f[lA][rA][lB][rB] = 1;
                    else {
                        if (rA > 0 && a[lA - 1] == a[rA - 1])
                            f[lA][rA][lB][rB] |= f[lA + 1][rA - 1][lB][rB];
                        if (rB > 0 && b[lB - 1] == b[rB - 1])
                            f[lA][rA][lB][rB] |= f[lA][rA][lB + 1][rB - 1];
                        if (rB > 0 && a[lA - 1] == b[rB - 1])
                            f[lA][rA][lB][rB] |= f[lA + 1][rA][lB][rB - 1];
                        if (rA > 0 && b[lB - 1] == a[rA - 1])
                            f[lA][rA][lB][rB] |= f[lA][rA - 1][lB + 1][rB];
                    }
                    if (f[lA][rA][lB][rB]) res = max(res, lenA + lenB);
                }
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    for (; t; t--)
        solve();
    return 0;
}

没有上司的舞会

\(f[i][0/1]\)表示\(i\)的子树中\(i\)不选或选的最大收益

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<int> a;
vector<array<int,2>> f;
vector<vector<int>> e;

void dfs( int i){
    f[i][1] = a[i];
    for( int j : e[i] ){
        dfs(j);
        f[i][1] += f[j][0];
        f[i][0] += max(f[j][0] , f[j][1]);
    }
    return ;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    a=vector<int>(n+1);
    f = vector<array<int,2>>(n+1);
    e = vector<vector<int>>(n+1);
    for( int i = 1 ; i <= n ; i ++ )
        cin >> a[i];
    int root = n * (n+1) / 2;
    for( int i = 1 , x , y ; i < n ; i ++ )
        cin >> x >> y , e[y].push_back(x) , root -= x;
    dfs(root);
    cout << max( f[root][0] , f[root][1] );
    return 0;
}

小G有一个大树

统计子树大小\(cnt_i\)，这\(f_i=\max( n - cnt_i,cnt_j)\)，其中\(j\)是\(i\)的子节点

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
vector<vector<int>> e;
vector<int> cnt, fa;

void dfs(int x) {
    cnt[x] = 1;
    for (auto y: e[x]) {
        if (y == fa[x]) continue;
        fa[y] = x, dfs(y);
        cnt[x] += cnt[y];
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    while (cin >> n) {
        e = vector<vector<int>>(n + 1), cnt = vector<int>(n + 1, -1), fa = vector<int>(n + 1, -1);
        for (int x, y, i = 1; i < n; i++)
            cin >> x >> y, e[x].push_back(y), e[y].push_back(x);
        dfs(1);
        int res = -1, val = INT_MAX;
        for (int i = 1, f; i <= n; i++) {
            f = n - cnt[i];
            for (auto y: e[i])
                if( y != fa[i] ) f = max(f, cnt[y]);
            if (val > f) val = f, res = i;
        }
        cout << res << " " << val << "\n";
    }
    return 0;
}

石子合并

首先破环成链，然后然后这道题就可以转换成区间 dp。

先考虑最大得分

设\(f[l][r]\)表示把\([l,r]\)合并的最大得分，枚举合并的中间点\(k\)，则\(f[l][r] = \max( f[l][k] + f[k+1][r] +\sum a[i])\)

这里注意，当前区间一定是从更短的区间转移过来，所以枚举区间的时候，先枚举区间长度，然后根据左端点算出右端点，同样是\(O(N^2)\)的枚举，这样可以保证更短的区间一定会更早的被枚举。最小得分操作基本相同。

#include <bits/stdc++.h>

using namespace std;

const int N = 405;
int a[N], f[N][N], g[N][N];

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i++) cin >> a[i], a[i + n] = a[i];
    for (int i = 1; i <= n * 2; i++) a[i] += a[i - 1], g[i][i] = 0;
    for (int len = 2; len <= n; len++) {
        for (int l = 1, r = len; r <= 2*n; l++, r++) {
            for (int k = l, W = a[r] - a[l - 1]; k < r; k++) {
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + W);
                g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + W);
            }
        }
    }
    int res = INT_MIN, ans = INT_MAX;
    for (int l = 1, r = n; l <= n; l++, r++)
        res = max(res, f[l][r]), ans = min(ans, g[l][r]);
    cout << ans << "\n" << res;
    return 0;
}

炮兵阵地

首先统计出所有可能的合法放置方法。

设状态\(f[i][j][k]\)表示前\(i\)行且第\(i,i-1\)行状态是\(j,k\)情况下最多可以放的炮兵数量。

对于第\(i\)我们可以暴力的枚举出第\(i,i-1,i-2\)行的状态\(j,k,l\)，判定合法后就可以转移\(f[i][j][k]=\sum f[i-1][k][l] + val[j]\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define lowbit(x) ( x & -x )

typedef bitset<4> T;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int M = (1 << m) - 1;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (auto j: s)
            a[i] = (a[i] << 1) | (j == 'H');
    }
    vector<array<int, 2>> P;
    for (int i = 0, j, t; i <= M; i++) {
        if (i & ((i << 1) | (i << 2) | (i >> 1) | (i >> 2))) continue;
        j = i, t = 0;
        while (j) t++, j -= lowbit(j);
        P.push_back({i, t});
    }

    int N = P.size();
    vector f(N, vector(N, 0ll)), g(N, vector(N, 0ll));
    for (int i = 0; i < N; i++) {
        if (a[1] & P[i][0]) continue;
        for (int j = 0; j < N; j++) {
            if (P[j][0] & (P[i][0] | a[0])) continue;
            g[i][j] = P[j][1] + P[i][1];
        }
    }

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

        for (int j = 0; j < N; j++) {
            if (P[j][0] & a[i]) continue;
            for (int k = 0; k < N; k++) {
                if (P[k][0] & (a[i - 1] | P[j][0])) continue;
                for (int l = 0; l < N; l++) {
                    if (P[l][0] & (a[i - 2] | P[k][0] | P[j][0])) continue;
                    f[j][k] = max(f[j][k], g[k][l] + P[j][1]);
                }
            }
        }
        g.swap(f), f = vector(N, vector(N, 0ll));
    }
    int res = 0;
    for (const auto &i: g)
        res = max(res, *max_element(i.begin(), i.end()));
    cout << res << "\n";
    return 0;
}

传纸条

一正一反找两条路径，等价于正着直接找两条不相同的路径。因为\((n,m)\)的权值为零，所以我们可以直接找两条路分别到达\((n,m-1),(n-1,m)\)。如何实现过程中不想交？保证在每一行第一条路径到达\((i,j)\)后，第二条路径只能到达\((i,j+1)\)及其右侧的点即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 55;
int g[N][N] , f[N][N][N][N];


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for( int i = 1 ; i <= n  ; i ++ )
        for( int j = 1 ; j <= m ; j ++)
            cin >> g[i][j];
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            for( int x = 1 ; x <= n ; x ++ )
                for(  int y = j+1 ;y <= m ; y ++ ){
                    f[i][j][x][y] = max( {f[i][j-1][x][y-1] , f[i][j-1][x-1][y] , f[i-1][j][x][y-1],f[i-1][j][x-1][y]}) + g[i][j] + g[x][y];
                }
    cout << f[n][m-1][n-1][m];
    return 0;
}

标签：训练,int,第三周,cin,long,vector,rA,rB,题单
From： https://www.cnblogs.com/PHarr/p/17586760.html

相关文章

  • 代码随想录算法训练营第二天| LeetCode 977.有序数组的平方 ，209.长度最小的子数组 ，59.
    977.有序数组的平方     题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/    文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html    视频讲解： https://www.bili......
  • AI训练营-baseline代码中参数精读
    #数据准备train_dataset=pd.read_csv("./train.csv")#原始训练数据。test_dataset=pd.read_csv("./test.csv")#原始测试数据（用于提交）。submit=pd.DataFrame()#定义提交的最终数据。submit["序号"]=test_dataset["序号"]#对齐测试数据的序号。MAE_scores=......
  • 暑假专题训练 dp 2023-7-26
    L.HamiltonianWall算法：dp做法：由于要一笔将所有黑块都划出来。所以我们状态转移方程应尽可能从左上角或者右下角的黑方块转移过来。$$f[i,j]=f[i,j-1]+1\(wall[i,j-1]=B,w[i,j]=B)$$$$f[i][j]=f[i+1][j-1]+2\(i==1,wall[i+1][j-1]==B,wal......
  • 第三周题单
    互不侵犯KING思路：dp[i][j][k]表示前i行，且已经用了j个国王，且第i行的摆放状态为k（二进制）；dp[i][j][k]=dp[i-1][j-num[now]][pre]，now表示第i行的状态，pre表示上一行的状态，num[i]维护一行的状态为i的国王数量，且需保证now和pre满足为相邻行的条件#include<bits/stdc++.h>usingname......
  • 贪心（不同情况下有不同策略）题单报告
    书接上回。感觉这个标题起得云里雾里的颇有上次讲的“反悔自动机”的奇妙风范，坏了会回旋镖插我自己身上了（感觉这样的贪心很厉害。什么叫不同情况下有不同策略呢？就是说你要分讨，分讨的每一种情况我们都要保证这是当前的最优解。这听起来是不是还是很扯，其实这是为了方便我自己看的......
  • MMRotate-Dev中的RetinaNet训练过程中的包导入问题
     错误如下：File"<frozenimportlib._bootstrap>",line1014,in_gcd_importFile"<frozenimportlib._bootstrap>",line991,in_find_and_loadFile"<frozenimportlib._bootstrap>",line973,in_find_and_load_u......
  • 代码随想录算法训练营第一天| LeetCode 704. 二分查找、LeetCode 27. 移除元素
    704.二分查找    题目链接：https://leetcode.cn/problems/binary-search/   视频链接：https://www.bilibili.com/video/BV1fA4y1o715     文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html    卡哥的题目建......
  • WhaleScheduler 2.4.5 版本重磅发布！WhaleGPT 赋能企业私有化模型训练
    重点一览：随着现代数据技术体系的发展，数据驱动已经成为企业管理不可或缺的一部分，数据遍布在企业内部的每一个角落。每个企业积累的海量的大数据，但真正发挥效能的数据微乎其微，形成了大量的“沉睡”数据。而企业内部的数据用户，从数据分析师到市场营销人员再到销售人员，每个员工现在都......
  • 贪心（反悔贪心）题单报告
    Democy爷给了一份贪心的题单，但是由于我是小笨比，所以很多题我都不是很会做，现在来简单写一份总结，加强一下印象qwq。首先什么叫贪心？贪心就是我每次都选择一个最大值。比如说我现在有\(n\)个物品，每个物品都有一个价值，我们可以选\(k\)件物品，我们怎么样让选择的价值和最大呢？傻子......
  • AI训练营—Python的一些基础知识
    目录列表字典复制对象列表切片：左开右闭倒取值字典集合：无序的，元素是唯一的dk_set=set()#也可以是dk_set={},创建一个空的集合#集合的并union()，交intersection()，差difference()#集合不会出现重复元素foriin"Dkfor3,Dkfor3":dk_set.add(i)#添加元素i的值进集合......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99