个人空间 - AcWing

hbq

$\underbrace{\color{lime}{\Huge ACCCCC}}_{\infty\text{ times}}$

阅读量

3482

+关注发消息

在线

最近来访(192)

比奇堡不会acm

辉_1

xzqyn

zero1

hugo_lu

voidddd

石头_44

acwing_xyy

13386306663

meiis

硝基苯_5

Codemon

chtld

不拿周赛牌不改名

Kazimierz

欧耶

陈容升

Cola_85

平凡的小苏

incra

活动打卡代码 AcWing 1010. 拦截导弹

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

using namespace std;

const int N = 1010;

int n, q[N];
int f[N], g[N];

int main()
{
    while (cin >> q[n]) n ++;

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (q[j] >= q[i]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;

    // // 分开求
    // 最长上升自序里
    // res = 0;
    // for (int i = 0; i < n; i ++ )
    // {
    //     f[i] = 1;
    //     for (int j = 0; j < i; j ++ )
    //         if (q[j] < q[i]) f[i] = max(f[i], f[j] + 1);
    //     res = max(res, f[i]);
    // }
    // cout << res << endl;


    int cnt = 0; // 表示 g[] 中的元素个数

    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = cnt;
        while (l < r) // 二分出 >= q[i] 的最小的结尾
        {
            int mid = l + r >> 1;
            if (g[mid] >= q[i]) r = mid;
            else l = mid + 1;
        }
        if (g[r] < q[i]) r ++ ; // 边界问题 序列中所有结尾值都 < q[i]
        cnt = max(cnt, r);
        g[r] = q[i]; // 将 q[i] 插入序列

        // int k = 0;
        // while (k < cnt && g[k] < q[i]) k ++ ;
        // g[k] = q[i];
        // if (k >= cnt) cnt ++; // k >= cnt 表示 序列中所有结尾都 < 当前要插入的数 q[i]

    }
    cout << cnt << endl;


    return 0;
}

            

活动打卡代码 AcWing 804. n 的阶乘

hbq
23小时前

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

using namespace std;

const int N = 10;

int n;

int f(int n)
{
    return n ? f(n - 1) * n : 1;
}

int main()
{
    cin >> n;    
    cout << f(n) << endl;
    return 0;
}

            

活动打卡代码 AcWing 1012. 友好城市

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int f[N];
PII q[N];
int n;

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


    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (q[j].y < q[i].y) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    printf("%d\n", res);

    return 0;
}


            

活动打卡代码 AcWing 482. 合唱队形

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

using namespace std;

const int N = 110;

int a[N], n;
int f1[N], f2[N];

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

    for (int i = 1; i <= n; i ++ )
    {
        f1[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i]) f1[i] = max(f1[i], f1[j] + 1);
    }

    for (int i = n; i; i -- )
    {
        f2[i] = 1;
        for (int j = n; j > i; j -- )
            if (a[j] < a[i]) f2[i] = max(f2[i], f2[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f1[i] + f2[i] - 1);

    cout << n - res << endl;

    return 0;
}

            

活动打卡代码 AcWing 1014. 登山

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

using namespace std;

const int N = 1010;

int a[N], n;
int f1[N], f2[N];

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

    for (int i = 1; i <= n; i ++ )
    {
        f1[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i]) f1[i] = max(f1[i], f1[j] + 1);
    }

    for (int i = n; i; i -- )
    {
        f2[i] = 1;
        for (int j = n; j > i; j -- )
            if (a[j] < a[i]) f2[i] = max(f2[i], f2[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f1[i] + f2[i] - 1); // 需要 - 1 连接点被计算了两次

    cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 1017. 怪盗基德的滑翔翼

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

using namespace std;

const int N = 110;

int a[N], f[N];
int n;

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

        int res = 0; // 求最值可以和合并到循环中！！ ：小技巧
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = 1;
            for (int j = 1; j < i; j ++ )
                if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }

        for (int i = n; i; i -- )
        {
            f[i] = 1;
            for (int j = n; j > i; j -- )
                if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        printf("%d\n", res);
    }
    return 0;
}


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

using namespace std;

const int N = 110;

int a[N], n;
int f1[N], f2[N]; // f[i] 表示 以 a[i] 为结尾的 最长下降子序列

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

        // 从前往后的最长下降子序列
        for (int i = 1; i <= n; i ++ )
        {
            f1[i] = f2[i] = 1;
            for (int j = 1; j < i; j ++ )
                if (a[j] > a[i]) f1[i] = max(f1[i], f1[j] + 1);
                else if (a[j] < a[i]) f2[i] = max(f2[i], f2[j] + 1);
        }

        int res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, max(f1[i], f2[i]));
        cout << res << endl;
    }
    return 0;
}


// 75 33 43 49 34  // 3

            

活动打卡代码 AcWing 1016. 最大上升子序列和

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

using namespace std;

const int N = 1010;

int a[N], n;
int f[N];

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

    a[0] = -2e9; // 序列中所有数都 >= 0 因此a[0] < a[1 ~ n] 因此 a[1] 一定会初始化成功 // 因此a[0] = 0 也可以
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < i; j ++ )
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]); 

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    cout << res << endl;

    return 0;
}


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

using namespace std;

const int N = 1010;

int a[N], n;
int f[N];

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

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = a[i]; // 第一类为空的情况
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 4403. 修剪灌木

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

using namespace std;

const int N = 10010;

int n;
int w[N];

int main()
{
    scanf("%d", &n);
    int t = (n + 1) / 2; // 上取整
    for (int i = 1; i <= t; i ++ )
        w[i] = w[n - i + 1] = (n - i) << 1;
    for (int i = 1; i <= n; i ++ ) printf("%d\n", w[i]);
    return 0;
}

            

活动打卡代码 AcWing 4402. 刷题统计

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

using namespace std;

typedef long long LL;

const int N = 1e18;

LL a, b, n;

int main()
{
    cin >> a >> b >> n;
    LL x = 5 * a + 2 * b; // 一周做的题目数量
    LL t = n / x; // 需要几周
    n %= x; // 表示剩余的天数 ： 一定是 < 一周的

    LL sum = t * 7; // 整周做的题目

    // 分类
    if (n <= 5 * a) sum += (n + a - 1) / a; // 上取整
    else
    {
        n -= 5 * a;
        sum += 5 + (n + b - 1) / b; //上取整
    }

    printf("%lld\n", sum);
    return 0;
}

            

活动打卡代码 AcWing 816. 数组翻转

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

using namespace std;

const int N = 1010;

int w[N], n, m;

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

    reverse(w, w + m);
    for (int i = 0; i < n; i ++ ) printf("%d ", w[i]);
    return 0;
}

            