头像

直接偷偷学习




离线:1天前


活动打卡代码 AcWing 2816. 判断子序列

#include <bits/stdc++.h>
using namespace std;
queue<int>q;
queue<int>p;

int main(){
    int n , m , t ;
    cin >> n >> m ;
    while(n--){
        cin >> t;
        q.push(t);
    }
    while(m--){
        cin >> t;
        p.push(t);
    }
    while( !q.empty() && !p.empty() ){
        if( q.front() == p.front())q.pop();
        p.pop();
    }
    if( q.empty() )cout << "Yes";
    else cout << "No";
} 


活动打卡代码 AcWing 2875. 超级胶水

#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);\
           cin.tie(0);\
           cout.tie(0)
#define FI(x) fixed<<setprecision(x)<<
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n;
priority_queue<int> q;
ll sum = 0;
int main()
{
    IO; // 加快cin和cout的速度(基本和scanf差不多)
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        q.push(x);
    }
    while(q.size() > 1)
    {
        int x = q.top();
        q.pop();
        int y = q.top();
        q.pop();
        q.push(x + y);
        sum += 1ll * x * y;
    }
    cout << sum << '\n';
    return 0;
}



活动打卡代码 AcWing 1324. 五子棋

按照五子棋连子的方向进行模拟检验即可

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n;
int g[N][N];


bool check(int x, int y, int val, int dx, int dy)
{
    int cnt = 1;
    int nx = x, ny = y;
    while (true) {
        nx += dx, ny += dy;
        if (g[nx][ny] != val)
            break;
        else {
            cnt ++;
        }
    }

    nx = x, ny = y;
    while (true) {
        nx -= dx, ny -= dy;
        if (g[nx][ny] != val)
            break;
        else {
            cnt ++;
        }
    }
    return cnt >= 5;
}

bool Check(int x, int y, int val)   
{
    // shang xia, zuoyou, zuoxie, youxie
    if (check(x, y, val, 1, 0))
        return true;
    else if (check(x, y, val, 0, 1))
        return true;
    else if (check(x, y, val, 1, -1))
        return true;
    else if (check(x, y, val, 1, 1))
        return true;
    else
        return false;
}

int main()
{
    memset(g, -1, sizeof g);

    bool flag = false;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        static int x, y;
        scanf("%d%d", &x, &y);
        if (i & 1) {    // A ,, 0
            g[x][y] = 0;
            if (Check(x, y, 0)) {
                cout << "A " << i << endl;    
                flag = true;
                break;
            }
        }
        else {  // B ,, 1
            g[x][y] = 1;
            if (Check(x, y, 1)) {
                cout << "B " << i << endl;
                flag = true;
                break;
            }
        }
    }

    if (!flag)   cout << "Tie" << endl;

    return 0;
}


活动打卡代码 AcWing 1323. 出现

一个比较简单的模拟题目

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
bool st[N];
int n;


int main()
{
    cin >> n;
    memset(st, false, sizeof st);
    for (int i = 1; i <= n; i ++ ) {
        static int x;
        scanf("%d", &x);
        st[x] = true;
    }

    int cur = 0;
    while (true) {
        if (st[cur] == false) {
            cout << cur << endl;
            break;
        }
        cur ++;
    }

    return 0;
}


活动打卡代码 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;
}