头像

重言




离线:8小时前


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

重言
11天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

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

int main()
{
    cin >> n;

    ans = 0;

    for(int i = 1; i <= n; i ++ )
        scanf("%d", a + i);    

    for(int i = 1; i <= n; i ++ )
    {
        f[i] = 1;

        for(int j = 1; j < i; j ++ )
            if(a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);

    }

    for(int i = n; i >= 1; i --)
    {
        f1[i] = 1;

        for(int j = n; j > i; j -- )
            if(a[i] > a[j])
                f1[i] = max(f1[i], f1[j] + 1);

    }

    for(int i = 1; i <= n; i ++ )
    {
        ans = max(ans, f[i] + f1[i] - 1);
    }

    cout << n - ans << endl;

    return 0;
}


活动打卡代码 AcWing 1014. 登山

重言
11天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

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

int main()
{
    cin >> n;

    ans = 0;

    for(int i = 1; i <= n; i ++ )
        scanf("%d", a + i);    

    for(int i = 1; i <= n; i ++ )
    {
        f[i] = 1;

        for(int j = 1; j < i; j ++ )
            if(a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);

    }

    for(int i = n; i >= 1; i --)
    {
        f1[i] = 1;

        for(int j = n; j > i; j -- )
            if(a[i] > a[j])
                f1[i] = max(f1[i], f1[j] + 1);

    }

    for(int i = 1; i <= n; i ++ )
    {
        ans = max(ans, f[i] + f1[i] - 1);
    }

    cout << ans << endl;

    return 0;
}



重言
11天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int t, n;
int a[N], dp[N];

int main()
{
    cin >> t;

    while(t -- )
    {
        cin >> n;

        for(int i = n; i >= 1; i -- )
        {
            scanf("%d", a + i);
            dp[i] = INF;            
        }


        for(int i = 1; i <= n; i ++ )
        {
            *lower_bound(dp + 1, dp + n + 1, a[i]) = a[i] ;
        }

        auto ans = lower_bound(dp + 1, dp + n + 1, INF) - dp - 1 ;

        for(int i = n; i >= 1; i -- )
        {
            dp[i] = INF;            
        }

        for(int i = n; i >= 1; i -- )
        {
            *lower_bound(dp + 1, dp + n + 1, a[i]) = a[i] ;
        }

        ans = max(ans, lower_bound(dp + 1, dp + n + 1, INF) - dp - 1 );

        cout << ans << endl;

    }


    return 0;
}


活动打卡代码 AcWing 787. 归并排序

重言
28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 110000;

ll n, ans;
int a[N], b[N];

void merge_sort(int l, int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;

    merge_sort(l, mid), merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k ++ ] = a[i ++ ];
        else b[k ++ ] = a[j ++ ];
    while(i <= mid) b[k ++ ] = a[i ++ ];
    while(j <= r) b[k ++ ] = a[j ++ ];

    for(int i = l, j = 0; i <= r; i ++, j ++  )
        a[i] = b[j];

}

int main()
{

    cin >> n;

    for(int i = 0; i < n; i ++ )
        scanf("%d", a + i);

    merge_sort(0, n - 1);

    for(int i = 0; i < n - 1; i ++ )
        cout << a[i] << " ";
    cout << a[n - 1] << endl;

    return 0;

}


活动打卡代码 AcWing 788. 逆序对的数量

重言
28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 110000;

ll n, ans;
int a[N], b[N];

void merge_sort(int l, int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;

    merge_sort(l, mid), merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k ++ ] = a[i ++ ];
        else {
            ans += mid - i +  1;
            b[k ++ ] = a[j ++ ];
        }
    while(i <= mid) b[k ++ ] = a[i ++ ];
    while(j <= r) b[k ++ ] = a[j ++ ];

    for(int i = l, j = 0; i <= r; i ++, j ++  )
        a[i] = b[j];

}

int main()
{

    cin >> n;

    for(int i = 0; i < n; i ++ )
        scanf("%d", a + i);

    merge_sort(0, n - 1);

    cout << ans << endl;

    return 0;

}


活动打卡代码 AcWing 2067. 走方格

重言
28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 31;

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

int main()
{

    cin >> n >> m;

    if(n % 2 == 0 && m % 2 == 0)
        cout << "0" << endl;
    else
    {
        f[1][1] = 1;
        for(int i = 1; i <= n; i ++ )
        {
            for(int j = 1; j <= m; j ++ )
            {
                if(i == 1 && j == 1 )
                    continue;
                if(i % 2 != 0 || j % 2 != 0)
                {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }

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

        cout << f[n][m] << endl;

    }

    return 0;

}


活动打卡代码 AcWing 2066. 解码

重言
28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string s;

int main()
{

    cin >> s;

    for(int i = 0; i < s.length(); i ++ )
    {
        if(s[i] >= '0' && s[i] <= '9')
        {
            for(int j = 1; j < s[i] - '0'; j ++ )
                cout << s[i - 1];
        }
        else
            cout << s[i];
    }

    cout << endl;    

    return 0;

}


活动打卡代码 AcWing 2065. 整除序列

重言
28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

ll n;

int main()
{

    cin >> n;

    int flag = 0;

    while(n)
    {
        if(flag == 0)
        {
            flag = 1;
            cout << n;
        }
        else
        {
            cout << " " << n;
        }
        n /= 2;
    }

    cout << endl;    

    return 0;

}


活动打卡代码 AcWing 1241. 外卖店优先级

重言
28天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m, t;
PII a[N];
int v[N];
int last[N];
bool st[N];

int main()
{

    cin >> n >> m >> t;

    for(int i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &a[i].first, &a[i].second);
    }

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

    // for(int i = 1; i <= m; i ++ )
    // {
    //     cout << a[i].first << " " << a[i].second << endl;
    // }

    for(int i = 1; i <= m; )
    {
        int j = i;
        while (j <= m && a[j] == a[i]) j ++ ;
        int id = a[i].second;
        int tim = a[i].first;
        int cnt = j - i;
        i = j;

        v[id] -= tim - last[id] - 1;
        if(v[id] < 0) v[id] = 0;
        if(v[id] <= 3) st[id] = false;

        v[id] += 2 * cnt;
        if(v[id] > 5) st[id] = true;

        last[id] = tim;
    }

    int ans = 0;

    for(int i = 1; i <= n; i ++ )
        if(t > last[i] && (v[i] - (t - last[i])) <= 3)
            st[i] = false;

    for(int i = 1; i <= n; i ++ )
        if(st[i])
            ans ++;

    cout << ans << endl;

    return 0;

}





活动打卡代码 AcWing 1096. 地牢大师

重言
29天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;

int l, n, m, flag;
char g[N][N][N];
bool st[N][N][N];
int dist[N][N][N];

struct node{
    int z, x, y;
};

int kk[6][3] = {{0, 0, 1}, {0, 1, 0}, {1, 0, 0}, {-1, 0, 0}, {0, -1, 0}, {0, 0, -1}};

node a, b;

void bfs()
{
    queue<node> q;
    q.push({a.z, a.x, a.y});
    dist[a.z][a.x][a.y] = 0;
    st[a.z][a.x][a.y] = true;

    while(!q.empty())
    {
        node t = q.front();
        q.pop();

        if(t.x == b.x && t.y == b.y && t.z == b.z)
        {
            cout << "Escaped in "  << dist[t.z][t.x][t.y] << " minute(s)."<< endl;
            flag = 1;
            break;
        }

        for(int i = 0; i < 6; i ++ )
        {
            int tx = t.x + kk[i][0];
            int ty = t.y + kk[i][1];
            int tz = t.z + kk[i][2];

            // cout << tx << " " << ty << " " << tz << endl;

            // cout << l << " " << n << " " << m << endl;

            if(tx >= 0 && ty >= 0 && tz >= 0 && tx < n && ty < m && tz < l && g[tz][tx][ty] != '#' && st[tz][tx][ty] == false)
            {
                // cout << tx << " " << ty << " " << tz << endl;
                q.push({tz, tx, ty});
                st[tz][tx][ty] = true;
                dist[tz][tx][ty] = dist[t.z][t.x][t.y] + 1;
            }

        }

    }

}

int main()
{

    while(cin >> l >> n >> m && n, m, l )
    {

        flag = 0;

        memset(st, false, sizeof st);
        memset(dist, 0, sizeof st);

        for(int i = 0; i < l; i ++ )
        {
            for(int j = 0; j < n; j ++ )
                scanf("%s", g[i][j]);
        }


        for(int i = 0; i < l; i ++ )
            for(int j = 0; j < n; j ++ )
                for(int k = 0; k < m; k ++ )
                    if(g[i][j][k] == 'S')
                    {
                        a.z = i;
                        a.x = j;
                        a.y = k;
                    }
                    else if(g[i][j][k] == 'E')
                    {
                        b.z = i;
                        b.x = j;
                        b.y = k;
                    }

        bfs();

        if(flag == 0)
            cout << "Trapped!" << endl;

    }

    return 0;

}