头像

zyk2507




离线:1小时前


最近来访(35)
用户头像
成影
用户头像
wakqd
用户头像
童心
用户头像
海尔达尔的木筏
用户头像
鉴新
用户头像
fduytfkuhj

活动打卡代码 AcWing 3. 完全背包问题

zyk2507
4天前

IMG_0FC7ACB28815-1.jpeg

未压缩版本

#include <bits/stdc++.h>
#define N 555
using namespace std;

int f[N][N], w[N], c[N];;

int main()
{
    int n, v; cin >> n >> v;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i] >> c[i];
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= v; j++)
        {
            if(j < w[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + c[i]);
        }
    }
    cout << f[n][v];
}

压缩版本

#include <bits/stdc++.h>
#define N 1111
using namespace std;

int f[N], w[N], c[N];;

int main()
{
    int n, v; cin >> n >> v;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i] >> c[i];
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = w[i]; j <= v; j++)
        {
            // if(j >= w[i]) 更改循环的起始条件以后就可以简化代码
            f[j] = max(f[j], f[j - w[i]] + c[i]);
        }
    }
    cout << f[v];
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

zyk2507
6天前

IMG_08089EDE16A3-1.jpeg

原版

#include <bits/stdc++.h>
#define N 2222
using namespace std;

int f[N][N];
int v[N], w[N];
int main()
{
    int nn, vv; cin >> nn >> vv;
    for(int i = 1; i <= nn; i++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1; i <= nn; i++)
    {
        for(int j = 1; j <= vv; j++)
        {
            if(j < v[i])
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[nn][vv];
    return 0;
}

往反方向读,以前的数据就不会被修改。

压缩内存版本

#include <bits/stdc++.h>
using namespace std;
#define N 1111
int nn, vv, f[N], w[N], v[N];

int main()
{
    cin >> nn >> vv;
    for(int i = 1; i <= nn; i++)
    {
        cin >> w[i] >> v[i];
    }
    for(int i = 1; i <= nn; i++)
    {
        for(int j = vv; j >= w[i]; j--)
        {
            // if(j >= w[i]) 更改循环起始位置以后就可以忽略条件判断 
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    cout << f[vv] << endl;
    return 0;
}



zyk2507
7天前
#include <bits/stdc++.h>
#define N 55555
#define INF 0x3f3f3f3f

using namespace std;


int dist[N], backup[N];

struct edge
{
    int a, b, w;
}tmp, edges[N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k; cin >> n >> m >> k;
    for(int i = 0; i < m; i++)
    {
        int a, b, w; cin >> a >> b >> w;
        tmp.a = a, tmp.b = b, tmp.w = w;
        edges[i] = tmp;
    }
    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; i++)
    {
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w); // 使其只能长一条边
        }
    }
    if(dist[n] > INF / 2) cout << "impossible";
    else cout << dist[n];
    return 0;
}



zyk2507
8天前
#include <bits/stdc++.h>
#define N 155555
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int, int>;

vector<pii> adj[N];
bool met[N];
int dis[N];
priority_queue<pii, vector<pii>, greater<pii> > q;

int main()
{
    int n, m; cin >> n >> m;
    while(m--)
    {
        int a, b, w; cin >> a >> b >> w;
        if(a == b) continue;
        adj[a].push_back({b, w});
    }

    memset(dis, INF, sizeof dis);
    dis[1] = 0;
    q.push({0, 1});
    while(!q.empty())
    {
        int a = q.top().second; q.pop();
        if(met[a]) continue;
        met[a] = 1;
        for(auto u : adj[a])
        {
            int b = u.first, w = u.second;
            if(dis[a] + w < dis[b])
            {
                dis[b] = dis[a] + w;
                q.push({dis[b], b}); // 在这里可以将距离存为负数,这样子就不需要专门声明q 为小根堆了
            }
        }
    }
    cout << (dis[n] == INF ? -1 : dis[n]) ;
    return 0;
}



zyk2507
8天前

堆优化的Dijkstra

#include <bits/stdc++.h>
#define N 555
#define INF 0x3f3f3f3f

using namespace std;


int dis[N], met[N], adj[N][N];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q;

int main()
{
    memset(dis, INF, sizeof dis);
    memset(adj, INF, sizeof adj);
    int n, m; cin >> n >> m;
    while(m--)
    {
        int a, b, w; cin >> a >> b >> w;
        if(a == b) continue;
        if(adj[a][b] == INF) adj[a][b] = w;
        else adj[a][b] = min(adj[a][b], w);
    }
    dis[1] = 0;
    q.push({0, 1});
    while(!q.empty())
    {
        int a = q.top().second; q.pop();
        if(!met[a])
        {
            for(int i = 1; i <= n; i++)
            {
                if(adj[a][i] == INF) continue;
                int b = i, w = adj[a][b];
                if(dis[a] + w < dis[b])
                {
                    dis[b] = dis[a] + w;
                    q.push({dis[b], b});
                }
            }
        }
    }
    cout << (dis[n] == INF ? -1 : dis[n]);
    return 0;
}



zyk2507
8天前

sets

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int main()
{
    indexed_set s;
    s.insert(2);
    s.insert(3);
    s.insert(7);
    s.insert(9);

    /* 给下标,出数字 */
    auto x = s.find_by_order(2);
    cout << *x << "\n";

    /* 给数字,出下标 */
    cout << s.order_of_key(2) << "\n";
    // 若该元素不存在,s.order_of_key(n) 返回的是传入的数字在s 里本该在的位置
    cout << "Not exists:\n";
    cout << s.order_of_key(6) << "\n";
    cout << s.order_of_key(8);
    return 0;
}

输出:

7
0
Not exists:
2
3



活动打卡代码 AcWing 846. 树的重心

zyk2507
9天前

TODO:重新复习一下这个知识点

IMG_916D1B2A4129-1.jpeg

#include <bits/stdc++.h>
#define N 1111111
using namespace std;

int h[N], e[N * 2 + 1], ne[N * 2 + 1], idx, n, ans = N;
bool met[N];

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

int dfs(int u)
{
    met[u] = 1;
    int res = 0, sum = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(!met[e[i]])
        {
            int sssize = dfs(e[i]);
            res = max(res, sssize);
            sum += sssize;
        }
    }
    res = max(res, n - sum);
    ans = min(res, ans);
    // cout << res << "  " << ans << endl;
    return sum;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++)
    {
        int a, b; cin >> a >> b;
        append(a, b), append(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

zyk2507
11天前
#include <bits/stdc++.h>
#define N 3333333
using namespace std;

int trie[N][2], a[N], idx;
bool end[N];

void insert(int n)
{
    int p = 0;
    for(int i = 30; ~i; i--)
    {
        int u = n >> i & 1;
        if(!trie[p][u])  trie[p][u] = ++idx;
        p = trie[p][u];
    }
}

int query(int n)
{
    int p = 0, res = 0;
    for(int i = 30; ~i; i--)
    {
        int u = n >> i & 1;
        if(trie[p][!u])
        {
            p = trie[p][!u];
            res = (res << 1) + !u;
        }
        else
        {
            p = trie[p][u];
            res = (res << 1) + u;
        }
    }
    return res;
}

int main()
{
    int n; cin >> n;
    int maxx = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        insert(a[i]);
        maxx = max(maxx, query(a[i]) ^ a[i]);
    }
    cout << maxx << endl;
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

zyk2507
11天前
#include <bits/stdc++.h>
#define N 222222
using namespace std;

string str;
int trie[N][26], cnt[N], idx;

void insert()
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - '0';
        if(!trie[p][u]) trie[p][u] = ++idx;
        p = trie[p][u];
    }
    cnt[p]++;
}

void query()
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - '0';
        if(!trie[p][u])
        {
            cout << "0\n";
            return;
        }else
        {
            p = trie[p][u];
        }
    }
    cout << cnt[p] << '\n';

}

int main()
{
    int n; cin >> n;
    while(n--)
    {
        string op; cin >> op >> str;
        if(op == "I") insert();
        if(op == "Q") query();
    }
    return 0;
}


活动打卡代码 AcWing 3302. 表达式求值

zyk2507
11天前
#include <bits/stdc++.h>

using namespace std;

stack<int> nums;
stack<char> op;

unordered_map<char, int> pri = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void eval()
{
    int b = nums.top();
    nums.pop();
    int a = nums.top();
    nums.pop();
    int res;
    if(op.top() == '+') res = a + b;
    if(op.top() == '-') res = a - b;
    if(op.top() == '*') res = a * b;
    if(op.top() == '/') res = a / b;
    op.pop();
    nums.push(res);
}


int main()
{
    string s; cin >> s;
    for(int i = 0; i < s.size(); i++)
    {
        if(isdigit(s[i]))
        {
            int j = i, x = 0;
            while(j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + (int)(s[j] - '0');
                j++;
            }
            nums.push(x);
            i = j - 1;
        }else if(s[i] == '(')
        {
            op.push('(');
        }else if(s[i] == ')')
        {
            while(op.size() && op.top() != '(') // 先把括号内的东西处理成一个值,再继续
                eval();
            op.pop();
        }else
        {
            while(op.size() && pri[op.top()] >= pri[s[i]]) // 如果检索到下一个符号的优先级小于当前栈顶的,先处理好之前的计算,然后再继续下面的计算
            {
                eval();
            }
            op.push(s[i]);
        }
    }
    while(op.size()) eval(); //处理最后剩下的数据
    cout << nums.top() << endl;
    return 0;
}