头像

贺谦

NPU


访客:10779

离线:3小时前



贺谦
18小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 12, M = 1 << N;

int n, m;
long long f[N][M];
bool st[M];

int main()
{
    while (cin >> n >> m, n || m)
    {
        memset(f, 0, sizeof f);

        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j ++ )
            {
                if (i >> j & 1)
                {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt ++;
            }

            if (cnt & 1) st[i] = false;
        }

        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (int k = 0; k < 1 << n; k ++ )
                    if (!(j & k) && st[j | k])
                        f[i][j] += f[i - 1][k];

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

    }

    return 0;
}



活动打卡代码 AcWing 91. 最短Hamilton路径

贺谦
20小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
        {
            if (i >> j & 1)
            {
                for (int k = 0; k < n; k ++ )
                    if ((i - (1 << j)) >> k & 1)
                    {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                    }
            }
        }

    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}



贺谦
10天前
#include <iostream>
#include <queue>

using namespace std;

const int N = 100010, M = 100010;

int n, m;
vector<int> e[M], res;
int indegree[N];
queue<int> q;

bool bfs()
{
    for (int i = 1; i <= n; i++)
        if (indegree[i] == 0)
            q.push(i);

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        res.push_back(t);
        for (auto x : e[t])
        {
            indegree[x] --;
            if (indegree[x] == 0) q.push(x);
        }
    }

    return res.size() == n;
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        indegree[y] ++;
    }

    if (!bfs()) cout << -1 << endl;
    else
    {
        for (auto x : res) cout << x << ' ';
        cout << endl;
    }

    return 0;
}



贺谦
11天前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int match[N];
bool st[N];
vector<int> e[N];

bool find(int boy)
{
    for (auto girl : e[boy])
    {
        if (!st[girl])
        {
            st[girl] = true;
            if (match[girl] == 0 || find(match[girl]))
            {
                match[girl] = boy;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    while (m --)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }

    int res = 0;
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);
        if (find(i)) res ++;
    }

    cout << res << endl;

    return 0;
}



贺谦
11天前
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010, M = 200010;

typedef pair<int, pair<int, int>> PII;

int n, m;
int father[N];
vector<PII> q;

int find(int x)
{
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        q.push_back({ w, {u, v} });
    }

    sort(q.begin(), q.end());

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

    int cnt = 0, res = 0;
    for (auto item : q)
    {
        int w = item.first, a = item.second.first, b = item.second.second;

        int fa = find(a), fb = find(b);
        if (fa != fb)
        {
            cnt++;
            res += w;
            father[fa] = fb;
        }
    }

    if (cnt == n - 1) cout << res << endl;
    else cout << "impossible" << endl;

    return 0;
}



贺谦
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

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


int prim()
{
    int res = 0;

    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;

        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);

        st[t] = true;
    }

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while (m --)
    {
        int a, b, w;
        cin >> a >> b >> w;

        g[a][b] = g[b][a] = min(w, g[a][b]);
    }

    int res = prim();

    if (res == INF) puts("impossible");
    else cout << res << endl;

    return 0;
}


活动打卡代码 LeetCode 7. 整数反转

贺谦
17天前
class Solution {
public:
    int reverse(int x) {
        long long res = 0;

        while(x)
        {
            res = res * 10 + x % 10;
            x /= 10;
        }

        if(res < INT_MIN || res > INT_MAX) return 0;
        return res;
    }
};


活动打卡代码 LeetCode 6. Z 字形变换

贺谦
17天前
class Solution {
public:
    string convert(string s, int numRows) {
        int x = numRows, n = s.size();
        if(x == 1) return s;
        string str;

        for(int i = 0; i < x; i ++)
        {
            if(i == 0 || i == x - 1)
            {
                for(int j = i; j < n; j += (x - 1) * 2)
                    str += s[j];
            }
            else
            {
                for(int j = i, k = 2 * x - i - 2; j < n || k < n;
                        j += (x - 1) * 2, k += (x - 1) * 2)
                {
                    if(j < n) str += s[j];
                    if(k < n) str += s[k];
                }
            }
        }

        return str;
    }
};


活动打卡代码 LeetCode 5. 最长回文子串

贺谦
17天前
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        if (!s.size()) return res;
        int n = s.size();
        for (int i = 0; i < n; i ++)
        {
            int l = i - 1, r = i + 1;
            while(l >= 0 && r < n && s[l] == s[r]) l --, r ++;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);

            l = i, r = i + 1;
            while(l >= 0 && r < n && s[l] == s[r]) l --, r ++;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
        }

        return res;
    }
};



贺谦
18天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *tail = dummy;

        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                tail->next = l1;
                tail = tail->next;
                l1 = l1->next;
            }
            else
            {
                tail->next = l2;
                tail = tail->next;
                l2 = l2->next;
            }
        }

        if(l1) tail->next = l1;
        if(l2) tail->next = l2;

        return dummy->next;
    }
};