头像

直接偷偷学习




离线:3天前


活动打卡代码 AcWing 1070. 括号配对

/*
本题的大意就是要使得括号进行匹配
是一个类似于回文串匹配的问题
f[i][j] : 表示 区间 i -> j 完成匹配之后需要的最小操作次数
具体dp的划分查看 word 文档

而且你根据这个状态转移的前驱和后继的关系,这是一个区间dp
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;
char a[N];
int f[N][N];
int n;

bool is_match(char a, char b)
{
    if (a == '[' && b == ']')   return true;
    else if(a == '(' && b == ')')   return true;
    return false;
}

int main()
{
    cin >> a;
    n = strlen(a);

    memset(f, 0, sizeof f);
    for (int len = 1; len <= n; len ++ )
    {
        for (int i = 0; i + len - 1 < n; i ++ )
        {
            static int j;
            j = i + len - 1;
            f[i][j] = INF;
            if (len != 1 && is_match(a[i], a[j]))
            {
                f[i][j] = min(f[i][j], f[i+1][j-1]);
            }
            else
            {
                f[i][j] = min(f[i][j], min(f[i+1][j], f[i][j-1]) + 1);
            }

            for (int k = i; k < j; k ++ )
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j]);
            }
        }
    }

    cout << f[0][n-1] << endl;

    return 0;
}



活动打卡代码 AcWing 1226. 包子凑数

直接就是进行动态规划

/*
    或许可以直接dp进行写,看看是否存在连续几个的
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int M = 101010, N = 110, INF = 0x3f3f3f3f;
int a[N];
int n;
bool st[M + 10];

bool Check(int x)
{
    for (int i = 1; i <= n; i ++ )
    {
        if (x - a[i] >= 0 && st[x - a[i]])
        {
            return true;
        }
    }
    return false;
}

int main()
{
    cin >> n;
    int mmin = INF;
    memset(st, false, sizeof st);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        mmin = min(mmin, a[i]);
    }
    int cnt = mmin - 1, con = 0;
    bool flag = false;

    st[0] = true;
    for (int i = mmin; i < M; i ++ )
    {
        // printf("I:%d\n", i);
        if (Check(i))  
        {
            st[i] = true;
            con ++;
            if (con >= mmin)
            {
                flag = true;
                break;
            }
        }
        else
        {
            st[i] = false;
            con = 0;        // 注意这个是清0,不是 1
            cnt ++;
            // printf("%d\n", i);
        }
    }

    if (flag)
    {
        printf("%d\n", cnt);
    }
    else
    {
        printf("INF\n");
    }
    return 0;
}

先进行gcd特判,然后动态规划,不过使用的是完全背包dp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010, M = 10010;
int a[110];
bool f[110][N];
int n;

// 求解最大公因数
int gcd(int a, int b)
{
    if (b == 0) return a;
    else    return  gcd(b, a % b); 
}

int main()
{
    int res = 0;

    cin >> n;
    for (int i = 1; i <= n; i ++ )  scanf("%d", &a[i]);

    int d = a[1];
    for (int i = 2; i <= n; i ++ )
    {
        d = gcd(d, a[i]);
    }

    if (d != 1)
    {
        printf("INF\n");        // 结果具有无穷多个
        return 0;
    }

    // 直接进行完全背包问题进行求解
    //  f[i][j] 使用前 i 个数字,能否凑出来 j
    //  f[i][j] = f[i-1][j] | f[i-1][j-a[i]] | f[i-1][j-2a[i]] | f[i-1][j-3a[i]]...
    //  f[i][j] = f[i-1][j] | f[i][j-a[i]]

    memset(f, false, sizeof f);
    f[0][0] = true;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j < M; j ++ )
        {
            f[i][j] = f[i-1][j];
            if (j >= a[i])  f[i][j] |= f[i][j-a[i]];
        }
    }

    int cnt = 0;
    for (int j = 0; j < M; j ++ )
    {
        if (!f[n][j]) 
        {
            cnt ++;
            // printf("%d, ", j);
        }
    }

    cout << cnt << endl;

    return 0;
}



#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 3;
LL n, m;

void mul(LL *c, LL *a, LL b[][N])
{
    static LL tmp[N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            tmp[i] = (tmp[i] + a[j] * b[j][i]) % m;
        }
    }

    memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

void mul(LL c[][N], LL a[][N], LL b[][N])
{
    static LL tmp[N][N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % m;
            }
        }
    }
    memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

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

    LL a[N][N] = {
        {1LL, 0LL, 0LL},
        {1LL, 1LL, 1LL},
        {1LL, 1LL, 0LL},
    };

    LL f1[N] = {1, 1, 0};


    n--;        // 需要进行n-1次
    // 
    /*
    for (int i = 1; i <= n; i ++ )
    {
        mul(f1, f1, a);
        printf("I:%d; ", i + 1);
        for (int j = 0; j < N; j ++ )
        {
            printf("%d ", f1[j]);
        }
        cout<<endl;
    }
    */

    while (n)
    {
        if (n & 1)
        {
           mul(f1, f1, a); 
        }
        mul(a, a, a);
        n >>= 1;
    }

    cout << f1[0] << endl;
    return 0;   
}
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 3;
LL n, m;

void mul(LL *c, LL *a, LL b[][N])
{
    static LL tmp[N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            tmp[i] = (tmp[i] + a[j] * b[j][i]) % m;
        }
    }

    memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

void mul(LL c[][N], LL a[][N], LL b[][N])
{
    static LL tmp[N][N];
    memset(tmp, 0, sizeof tmp);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % m;
            }
        }
    }
    memcpy(c, tmp, sizeof tmp);       // 注意一定要使用tmp
}

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

    LL a[N][N] = {
        {2LL, 1LL, 0LL},
        {0LL, 0LL, 1LL},
        {-1LL, 0LL, 0LL},
    };

    LL f1[N] = {2, 1, 0};


    n -= 2;        // 需要进行n-2次
    /*
    for (int i = 1; i <= n; i ++ )
    {
        mul(f1, f1, a);
        printf("I:%d; ", i + 1);
        for (int j = 0; j < N; j ++ )
        {
            printf("%d ", f1[j]);
        }
        cout<<endl;
    }
    */

    while (n)
    {
        if (n & 1)
        {
           mul(f1, f1, a); 
        }
        mul(a, a, a);
        n >>= 1;
    }

    cout << (f1[0] + m) % m << endl;
    return 0;   
}



活动打卡代码 AcWing 1220. 生命之树

/*
问题分析:
    类似于dp树的直径,不过是把边权换成了点的权值
    分析错误,这个更像是一个连通块的问题
  连通块进行dp,往往需要进行按照 树形dp进行考虑, 也就是需要
    f[i] 表示以i为根的连通块
    而且因为树这个数据结构的特殊性,他的子树自己是相互独立的,更方便我们的dp的规划
状态表示:
    f[i] 表示 以 i 为根的连通块的最大值
    f[fa] = w[fa] + segment(f[son], 0);

注意因为是无向边,所以说dp时候 传一个fa 避免往回搜索
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 200010;
int h[N], e[N], ne[N], idx;
int w[N];
int n;
LL f[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;    
}

void dfs(int u, int fa)
{
    f[u] = w[u];
    int v;
    for (int i = h[u]; ~i; i = ne[i])
    {
        v = e[i];           // 注意,这里不可以进行static,因为这个是dfs,wc
        if (v == fa)    continue;
        dfs(v, u);
        f[u] += max(0ll, f[v]);     // 注意这里需要加的 long long
    }
}

int main()
{
    // input
    cin>>n;
    for (int i = 1; i <= n; i ++ )  scanf("%d", &w[i]);
    idx = 0;    
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ )
    {
        static int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    // inital and dp
    memset(f, 0, sizeof f);
    dfs(1, -1);


    // output
    LL res = f[1];
    for (int i = 2; i <= n; i ++ )
    {
        res = max(res, f[i]);
    }
    cout<<res<<endl;

    return 0;
}



活动打卡代码 AcWing 1248. 灵能传输

/*
问题分析: 此问题就是相邻 a[i+1] += a[i], a[i-1] += a[i], a[i] -= 2a[i]
            进行 n 次数列的处理,然后使得 max(abs(a[i])) 尽可能的小
问题求解:
        首先将原问题转换为 前缀和进行分析求解
        swap(s[i-1], s[i]),  2 <= i <= n-1 (即为 1 ~ n-1 数组的数据是可以任意交换的)

        问题也就是变成了 如何 调整 s1 - sn-1 让 s0 ~ (n-1个数字的数组) ~ sn 的 max abs差值最小

        S0 --> Min --> Max --> Sn 

        也就是说 Min ~ S0
                Sn ~ Max 需要拆开成两条路径使用,关键是如何进行拆,使得相邻的绝对值之差小

                可以证明使用隔一个拆一下最好,而且为了方便代码的书写,我们直接使用st数组记录隔一个取一个的路径
                之后直接使用按照st数组过一遍,就知道哪些没取,作为第二个路径

注意:
    小心分析过程中的 LL 问题
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 300010;
LL a[N], s[N];
int n;
bool st[N];

int main()
{
    int T;  cin>>T;
    while (T--)
    {
        cin>>n;
        memset(s, 0, sizeof s);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            s[i] = s[i-1] + a[i];
        }

        if (s[0] > s[n])    swap(s[0], s[n]);

        LL s0 = s[0], sn = s[n];

        sort(s, s + n + 1);

        // 寻找 s0, sn 排序之后的位置
        for (int i = 0; i <= n; i++)
        {
            if (s[i] == s0)
            {
                s0 = i;
                break;
            }
        }
        for (int i = n; i >= 0; i--)
        {
            if (s[i] == sn)
            {
                sn = i;
                break;
            }
        }

        // 装配方案
        memset(st, false, sizeof st);   // 有了st数组,特别方便代码书写
        int l = 0, r = n;
        for (int i = s0; i >= 0; i -= 2)
        {
            a[l++] = s[i];
            st[i] = true;
        }
        for (int i = sn; i <= n; i += 2)
        {
            a[r--] = s[i];
            st[i] = true;
        }

        for (int i = 0; i <= n; i++)
        {
            if (!st[i])
            {
                a[l++] = s[i];
            }
        }

        LL res = 0;
        for (int i = 1; i <= n; i++)    res = max(res, abs(a[i] - a[i-1]));

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


活动打卡代码 AcWing 1222. 密码脱落

/*
这是一个典型的区间dp问题
    f[i][j] 
        1.0 a[i] == b[j]
            f[i][j] = f[i+1][j-1]
        2.0 a[i] != b[j]
            f[i][j] = min(f[i+1][j] + 1, f[i][j-1] + 1);
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
char ch[N];
int f[N][N];
int n;

int main()
{
    // input
    scanf("%s", ch + 1);

    // initial
    n = strlen(ch + 1);
    memset(f, 0, sizeof f);

    // dp
    for(int len = 2; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            static int j;
            j = i + len - 1;
            if(ch[i] == ch[j]){
                f[i][j] = f[i+1][j-1];
            }else{
                f[i][j] = min(f[i+1][j] + 1, f[i][j-1] + 1);
            }
        }
    }

    // output
    cout<<f[1][n]<<endl;

    return 0;
}


活动打卡代码 AcWing 1047. 糖果

/*
    f[i][j]: 在第i件商品(无论选不选),余数为 j 的最大糖果数量选择方案
    f[i][j] = max(f[i-1][j], f[i-1][((j-a[i])%K+K)%K] + a[i])
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1010;
int f[N][N];
int n, k;
int a[N];

int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    memset(f, 0xcf, sizeof f);
    f[0][0] = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < k; j++){
            f[i][j] = max(f[i-1][j], f[i-1][((j-a[i])%k+k)%k]+a[i]);
        }
    }

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


活动打卡代码 AcWing 1050. 鸣人的影分身

低效写法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 20;
int f[N][N][N];
int m, n;

int main()
{
    int T;  cin>>T;
    while(T--){
        scanf("%d%d", &m, &n);
        memset(f, 0, sizeof f);
        //f[1][1][1] = 1;
        f[0][0][0] = 1;

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= i && j <= n; j++){
                for(int ed = 1; ed <= i - j + 1; ed++){
                    for(int k = 0; k <= ed; k++)
                        f[i][j][ed] += f[i-ed][j-1][k];
                }
            }
        }

        int res = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                res += f[m][i][j];
            }
        cout<<res<<endl;
    }
    return 0;
}

高效dp

/*
    按照整数划分的高效写法
    f[i][j] : 表示把i整数,划分成j个数字,数字>=0

    按照最小值可不可能是0可以进行状态转移
    f[i][j] = f[i][j-1] + f[i-j][j]
                最小值为0, 最小值 >= 1
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 15;
int f[N][N];
int m, n;

int main()
{
    int T;  cin>>T;    
    while(T--){
        // input
        cin>>m>>n;
        // initial
        memset(f, 0, sizeof f);
        for(int j = 1; j <= n; j++) f[0][j] = 1;    // j start 0 is also ok
        // dp
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                f[i][j] = f[i][j-1];
                if(i >= j)  f[i][j] += f[i-j][j];
            }
        }
        // output
        cout<<f[m][n]<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 1247. 后缀表达式

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 200010;       // 请注意这里需要是取两倍 啊
int n, m, k;

int a[N];

int main()
{
    cin>>n>>m;
    k = n + m + 1;
    for(int i = 1; i <= k; i++){
        static int x;
        scanf("%d", &a[i]);
    }

    sort(a + 1, a + 1 + k);

    LL res = 0;

    if(m == 0){
        for(int i = 1; i <= k; i++) res = res + a[i];
    }else{
        res = a[k] - a[1];
        for(int i = 2; i < k; i++)  res += abs(a[i]);
    }

    cout<<res<<endl;

    return 0;
}



活动打卡代码 AcWing 1239. 乘积最大

/*
这道题目可以看作是一个分类讨论之后的问题,分为了贪心主要是因为他有一个排序
代码不难,主要是这个封装的函数实现了多次使用,下面我们来介绍分类讨论的过程
n 个数字中选择 k 使其乘积最大
1. n == k:
    直接就是mul即可
2. n < k:
    2.1 k % 2 == 0:
        因为k是偶数,我们是可以通过控制性的行为,是得 乘积得到的 res >= 0 的,假设你拿的k个数字乘积是负数,
        那么我们把其中一个正数换成负数,或者是把其中一个负数换成正数即可
        (因为外面还有数字可以换,因为你乘积是负数,因子有偶数个,所有说既有正数,也有负数)
        那么如何是 res 最大呢? 因为是 res > 0 正数和负数就是成对出现的,我们直接双指针就好
    2.2 k % 2 == 1:
        2.2.1 原数列中至少有一个正数    res 可以通过调整使其是一个正数(1, k - 1), (3, k - 3), (5, k - 5)...
        而且他肯定是会取最大的那个正数的,直接递归调用函数即可
        2.2.2 与数列中无正数    res < 0
        直接就是选择abs最小
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long LL;

const int N = 100010, MOD = 1000000009;
LL a[N];
int n, k;

int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n);

    LL res = 1;
    int sign = 1;       // 后面函数会用到,主要是为了方便模块化
    int l = 1, r = n;
    if(k & 1){
        res = a[r--];
        k--;
        if(res < 0) sign = -1;  // 全部是负数
    }


    while(k){       // 直接就是成对的进行查找就可以了
        static LL x, y;
        x = a[l] * a[l+1], y = a[r] * a[r-1];
        if(x * sign > y * sign){
            res = x % MOD * res % MOD;
            l += 2;
        }else{
            res = y % MOD * res % MOD;
            r -= 2;
        }
        k -= 2;
    }

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