头像

lxkk...




离线:7小时前


活动打卡代码 AcWing 1518. 团伙头目

lxkk...
4个月前
#include <bits/stdc++.h>
using namespace std;

int n, k;
unordered_map<string, vector<pair<string, int>>> g;
unordered_map<string, int> total;
unordered_map<string, bool> st;

int dfs(string ver, vector<string> &nodes)
{
    st[ver] = true;
    nodes.push_back(ver);

    int sum =0;
    for(auto edge : g[ver])
    {
        sum += edge.second;
        string cur = edge.first;
        if(!st[cur]) sum += dfs(cur, nodes);
    }

    return sum;
}

int main()
{
    cin >> n >> k;
    while(n --)
    {
        string a,b;
        int t;
        cin >> a >> b >> t;
        g[a].push_back({b, t});
        g[b].push_back({a, t});
        total[a] += t;
        total[b] += t;
    }

    vector<pair<string, int>> res;
    for(auto item : total)
    {
        string ver = item.first;
        vector<string> nodes;
        int sum = dfs(ver, nodes) / 2;

        if(nodes.size() > 2 && sum > k)
        {
            string boss = nodes[0];
            for(string node : nodes)
                if(total[boss] < total[node])
                    boss = node;
            res.push_back({boss, nodes.size()});
        }
    }

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

    cout << res.size() << endl;
    for(auto item : res) cout << item.first << ' ' << item.second << endl;
}


活动打卡代码 AcWing 1507. 旅行计划

lxkk...
4个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int d[N][N], cnt[N], w[N][N], dist[N], sum[N], pre[N], n, m, S, T;
bool st[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    memset(sum, 0x3f, sizeof sum);

    dist[S] = 0, sum[S] = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;

        for(int j = 0; j < n; j ++)
        {
            if(dist[j] > dist[t] + d[t][j])
            {
                dist[j] = dist[t] + d[t][j];
                sum[j] = sum[t] + w[t][j];
                pre[j] = t;
            }
            else if(dist[j] == dist[t] + d[t][j])
            {
                if(sum[j] > sum[t] + w[t][j])
                {
                    dist[j] = dist[t] + d[t][j];
                    sum[j] = min(sum[j], sum[t] + w[t][j]);
                    pre[j] = t;
                }
            }
        }
    }

}

int main()
{
    cin >> n >> m >> S >> T;

    memset(d, 0x3f, sizeof d);
    memset(w, 0x3f, sizeof w);
    for(int i = 0; i < m; i ++)
    {
        int a, b, c, e;
        cin >> a >> b >> c >> e;
        d[a][b] = d[b][a] = min(d[a][b], c);
        w[a][b] = w[b][a] = min(w[a][b], e);
    }

    dijkstra();

    vector<int> path;
    for(int i = T; i != S; i = pre[i]) path.push_back(i);

    cout << S;
    for(int i = path.size() - 1; i >= 0; i --) cout << ' ' << path[i];

    cout << ' ' << dist[T] << ' ' << sum[T] << endl;
}


活动打卡代码 AcWing 1477. 拼写正确

lxkk...
4个月前
#include <iostream>
#include <cmath>
using namespace std;
string s;
string a[11] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
int b[11];
int main()
{
    cin>>s;
    int sum = 0,len = (int)s.size();

    for (int i = 0; i<len; i++) {
        sum += (s[i] - '0');
    }
    int t = 0;
    while (sum/10 > 0) {
        int wei = sum % 10;
        b[t++] = wei;
        sum /= 10;
    }
    b[t] = sum;
    int flag = 0;
    for (int i = t; i>=0; i--) {
        if(flag == 0)
        {
            cout<<a[b[i]];
            flag = 1;
        }
        else
            cout<<" "<<a[b[i]];
    }
    cout<<endl;
    return 0;
}



lxkk...
7个月前
class Solution {
public:
    bool containsPattern(vector<int>& a, int m, int k) {
        int len = a.size();
        for(int i = 0; i + m * k <= len; i ++)
        {
            bool flag = true;
            for(int j = i; j < i + m * k; j ++)
            {
                if(a[j] != a[i + (j - i) % m])
                {
                    flag = false;
                    break;
                }
            }

            if(flag) return true;
        }

        return false;
    }
};


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

lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << 20;
int n, f[M][N], w[N][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 < M; 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;
}


活动打卡代码 AcWing 90. 64位整数乘法

lxkk...
8个月前
#include <iostream>
using namespace std;

int main()
{
    long long a, b, p;
    cin >> a >> b >> p;
    long long res = 0;
    while(b)
    {
        if(b & 1) res = (long long)(res + a) % p;
        a = (long long)(a + a) % p;
        b >>= 1;
    }

    cout <<  res << endl;
}



lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010, M = 200010, INF = 0x3f3f3f3f;
int n, m, S, T, h[N], e[M], ne[M], idx, f[M], d[N], cur[N], q[N];

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


//宽搜1、有没有增广路; 2、建立分层图
bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if(d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }

    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if(!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }

    return flow;
}

int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = find(S, INF)) r += flow;
    return r;
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);

    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    cout << dinic() << endl;
}


活动打卡代码 AcWing 486. 等价表达式

lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <map>
#include <stack>

using namespace std;
const int P = 13331;
map<char, int>priority;
stack<char> op;
stack<int> num;

void eval()
{
    char c = op.top(); op.pop();
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();

    if(c == '+') num.push((a + b) % P);
    else if(c == '-') num.push(((a - b) % P + P) % P);
    else if(c == '*') num.push(a * b % P);
    else
    {
        int t = 1;
        while(b --) t = t * a % P;
        num.push(t);
    }
}

int calc(string expr, int a)
{
    op = stack<char>();
    num = stack<int>();

    for(int i = 0; i < expr.size(); i ++)
    {
        if(expr[i] == ' ') continue;
        if(expr[i] >= '0' && expr[i] <= '9')
        {
            int j = i, number = 0;
            while(j < expr.size() && expr[j] >= '0' && expr[j] <= '9')
            {
                number = number * 10 + expr[j] - '0';
                j ++;
            }
            i = j - 1;
            num.push(number);
        }
        else if (expr[i] == 'a') num.push(a);
        else
        {
            char c = expr[i];
            if(c == '(') op.push(c);
            else if(c == ')')
            {
                while(op.top() != '(') eval();
                op.pop();
            }
            else
            {
                while(op.size() && priority[op.top()] >= priority[c]) eval();
                op.push(c);
            }
        }
    }

    while(op.size()) eval();

    return num.top();
}

bool check(string expr1, string expr2)
{
    for(int i = 0; i < 1000; i ++)
        if(calc(expr1, i) != calc(expr2, i))
            return false;

    return true;
}

int main()
{
    char ops[] = "(+-*^";
    for(int i = 0; i < 5; i ++) priority[ops[i]] = i;

    string expr, line;
    getline(cin, expr);
    int n; cin >> n; getchar();
    //getline(cin, line);

    for(int i = 0; i < n; i ++)
    {
        getline(cin, line);
        if(check(expr, line)) printf("%c", 'A' + i);
    }
}


活动打卡代码 AcWing 485. 篝火晚会

lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10;

int n, cir[N], e[N][2], sum[N];
bool st[N];

bool build()
{
    cir[1] = 1; 
    st[1] = true;
    for(int i = 2, last = 1, cur = e[1][0]; i <= n; i ++)
    {
        cir[i] = cur;
        st[cur] = true;
        int a = e[cur][0], b = e[cur][1];
        if(a != last && b != last) return false;
        if(a == last) last = cur, cur = b;
        else last = cur, cur = a;
    }

    for(int i = 1; i <= n; i ++)
        if(!st[i])
            return false;

    return true;
}

int work()
{
    reverse(cir + 1, cir + n + 1);
    memset(sum, 0, sizeof sum);

    for(int i = 1; i <= n; i ++)
        if(cir[i] >= i) sum[cir[i] - i] ++;
        else sum[cir[i] + n - i] ++;

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

    return res;
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> e[i][0] >> e[i][1];

    if(!build()) puts("-1");
    else 
    {

        cout << n - max(work(), work()) << endl;
    }
}


活动打卡代码 AcWing 484. 过河

lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 10010, M = 110;
int m, w[N], stones[M], S, T, L, f[N];

using namespace std;

int main()
{
    cin >> L >> S >> T >> m;

    for(int i = 1; i <= m; i ++) cin >> stones[i];

    if(S == T)
    {
        int res = 0;
        for(int i = 1; i <= m; i ++)
            if(stones[i] % S == 0)
                res ++;

        cout << res << endl;
    }
    else
    {
        sort(stones + 1, stones + m + 1);
        for(int i = 1, last = 0, offset = 0; i <= m; i ++)
        {
            if(stones[i] - last > 100)
            {
                offset += stones[i] - last - 100;
            }
            last = stones[i];
            stones[i] -= offset;
        }

        for(int i = 1; i <= m; i ++) w[stones[i]] = 1;

        L = stones[m] + 10;
        for(int i = 1; i <= L; i ++)
        {
            f[i] = M;
            for(int j = S; j <= T; j ++)
                if(i - j >= 0)
                    f[i] = min(f[i], f[i - j] + w[i]);
        }

        cout << f[L] << endl;
    }
}