头像

lxz




离线:12分钟前


活动打卡代码 AcWing 35. 反转链表

lxz
30天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head-> next) return head;
        ListNode *q = head, *p = head -> next;
        while (p)
        {
            ListNode *n = p -> next;
            p -> next = q;
            q = p;
            p = n;
        }
        head -> next = NULL;
        return q;
    }
};


活动打卡代码 AcWing 851. spfa求最短路

lxz
1个月前
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010, M = N;
int n, m;
int dis[N], vis[N];
int h[N], e[M], ne[M], w[M], idx;

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

int spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (int i = h[t] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[t] + w[i])
            {
                dis[j] = dis[t] + w[i];
                if (!vis[j]) q.push(j);
            }
        }
    }
    return dis[n] == 0x3f3f3f3f ? -1 : dis[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));
    while (m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int res = spfa();
    if (res == -1) puts("impossible");
    else cout << res;
    return 0;
}



lxz
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dis[N], backup[N];

struct Edge{
    int a, b, c;  
}edges[M];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 0 ; i < m ; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    for (int i = 0 ; i < k ; i ++)
    {
        memcpy(backup, dis, sizeof(dis));
        for (int j = 0 ; j < m ; j ++)
        {
            int a = edges[j].a, b = edges[j].b, c = edges[j].c;
            dis[b] = min(dis[b], backup[a] + c);
        }
    }
    if (dis[n] > 0x3f3f3f3f / 2) cout << "impossible";
    else cout << dis[n];
    return 0;
}



lxz
1个月前
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef pair<int, int> PII;

const int N = 150010, M = N;

int h[N], e[M], ne[M], W[M], idx;
int dis[N], vis[N];
int n, m;

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

int dijkstra()
{
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while (heap.size())
    {
        auto tt = heap.top();
        heap.pop();
        if (vis[tt.second]) continue;
        int dist = tt.first, ver = tt.second;
        vis[ver] = 1;
        for (int i = h[ver] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dist + W[i])
            {
                dis[j] = dist + W[i];
                heap.push({dis[j], j});
            }
        }
    }
    if (dis[n] == 0x3f3f3f3f) return -1;
    else return dis[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);

    while (m --)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
    }
    cout << dijkstra();
    return 0;
}  



lxz
1个月前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int g[N][N], vis[N];
int dis[N];
int n, m;

void Dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 0 ; i < n - 1 ; i ++)
    {
        int mini = -1;
        for (int j = 1 ; j <= n ; j ++)
        {
            if (!vis[j] && (mini == -1 || dis[mini] > dis[j]))
                mini = j;
        }

        for (int j = 1 ; j <= n ; j ++)
        {
            if (dis[j] > dis[mini] + g[mini][j]) dis[j] = dis[mini] + g[mini][j];
        }
        vis[mini] = 1;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for (int i = 0 ; i < m ; i ++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = min(g[a][b], w);
    }
    Dijkstra();
    if (dis[n] == 0x3f3f3f3f) cout << "-1";
    else cout << dis[n];
    return 0;
} 



lxz
1个月前
#include <iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++)
        scanf("%d", &a[i]);
    f[1] = a[1];
    int res = 1;
    for (int i = 1 ; i <= n ; i ++)
    {
        int l = 1, r = res;
        while (l < r) 
        {
            int mid = l + r + 1 >> 1;
            if (f[mid] >= a[i]) r = mid - 1;
            else l = mid;
        }
        if (f[l] < a[i])
        {
            f[l + 1] = a[i];
            if (l == res) res ++;
        }
        else f[l] = a[i];
    }
    cout << res;
    return 0;
}



lxz
1个月前
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int dp[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a, b);
    for (int i = 1 ; i <= n ; i ++)
    {
        for (int j = 1 ; j <= m ; j ++)
        {
            if (a[i - 1] == b [j - 1])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            else 
                dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]));
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}



lxz
1个月前
#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++) scanf("%d", &a[i]);
    int ri, res = 0;
    for (int i = 1 ; i <= n ; i ++)
    {
        f[i] = 1;
        for (int j = 1 ; j < i ; j ++)
        {
            if (a[j] < a[i]) 
            {
                if (f[i] < f[j] + 1)
                {
                    f[i] = f[j] + 1;
                    g[i] = j;
                    if (res < f[i])
                    {
                        res = f[i];
                        ri = i;
                    }
                }
            }
        }
    }
    /*
    for (int i = ri ; i != 0 ; i = g[i])
        printf("%d ", a[i]);
    puts("");
    */
    printf("%d", res);

    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

lxz
1个月前
#include <iostream>

using namespace std;

const int N = 510, M = 0x3f3f3f3f;

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

int main()
{
    scanf("%d", &n);
    int res = -M;
    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= i ; j ++)
            scanf("%d", &a[i][j]);
    dp[1][1] = a[1][1];
    for (int i = 2 ; i <= n ; i ++)
    {
        for (int j = 1 ; j <= i ; j ++)
        {
            if (j == i) dp[i][j] = dp[i - 1][j - 1] + a[i][j];
            else if (j == 1) dp[i][j] = dp[i - 1][j] + a[i][j];
            else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
        }
    }
    for (int i = 1 ; i <= n ; i ++)
        res = max(res, dp[n][i]);
    cout << res;
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

lxz
1个月前
#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int dp[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1 ; i <= n ; i ++)
    {
        scanf("%d", &s[i]);
        for (int j = 1 ; j <= s[i] ; j ++) scanf("%d%d", &v[i][j], &w[i][j]);
    }
    for (int i = 1 ; i <= n ; i ++)
    {
        for (int j = m ; j >= 0 ; j --)
        {
            for (int k = 1 ; k <= s[i] ; k ++)
            {
                if (j >= v[i][k]) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
            }
        }
    }
    printf("%d", dp[m]);
    return 0;
}