头像

Wou


访客:585

离线:3小时前


活动打卡代码 AcWing 1078. 旅游规划

Wou
1天前
#include <iostream>
#include <cstdio>
#include <vector> 
using namespace std;
const int N = 2e5 + 5;

vector<int> G[N];
int f[N][3], dis[N], maxDis; 

void dfs1(int u, int father)
{
    int one = 0, two = 0;
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if (v == father) 
            continue;
        dfs1(v, u);
        int tmp = f[v][0] + 1;
        if (tmp >= one)
        {
            two = one;
            one = tmp;
        }
        else
            two = two > tmp ? two : tmp;
    }
    f[u][0] = one, f[u][1] = two;
}

void dfs2(int u, int father)
{
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if (v == father)
            continue;
        //f[v][2]
        if (f[v][0] + 1 == f[u][0])
            f[v][2] = max(f[u][1], f[u][2]) + 1;
        else
            f[v][2] = max(f[u][0], f[u][2]) + 1;
        dis[v] = max(f[v][1], f[v][2]) + f[v][0];
        maxDis = maxDis > dis[v] ? maxDis : dis[v];
        dfs2(v, u);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int root = 0;
    dfs1(root, -1);
    dfs2(root, -1);

    dis[root] = f[root][0] + f[root][1];
    for (int i = 0; i < n; ++i)
    {
        if (dis[i] == maxDis)
            printf("%d\n", i);
    }
    return 0;
} 



Wou
1天前
#include <iostream>
#include <cstdio>
#include <vector> 
using namespace std;
const int N = 2e5 + 5;

vector<int> G[N];
int f[N][3], dis[N], maxDis; 

void dfs1(int u, int father)
{
    int one = 0, two = 0;
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if (v == father) 
            continue;
        dfs1(v, u);
        int tmp = f[v][0] + 1;
        if (tmp >= one)
        {
            two = one;
            one = tmp;
        }
        else
            two = two > tmp ? two : tmp;
    }
    f[u][0] = one, f[u][1] = two;
}

void dfs2(int u, int father)
{
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if (v == father)
            continue;
        //f[v][2]
        if (f[v][0] + 1 == f[u][0])
            f[v][2] = max(f[u][1], f[u][2]) + 1;
        else
            f[v][2] = max(f[u][0], f[u][2]) + 1;
        dis[v] = max(f[v][1], f[v][2]) + f[v][0];
        maxDis = maxDis > dis[v] ? maxDis : dis[v];
        dfs2(v, u);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int root = 0;
    dfs1(root, -1);
    dfs2(root, -1);

    dis[root] = f[root][0] + f[root][1];
    for (int i = 0; i < n; ++i)
    {
        if (dis[i] == maxDis)
            printf("%d\n", i);
    }
    return 0;
} 


活动打卡代码 AcWing 1226. 包子凑数

Wou
2天前
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 105; 
const int M = 1e4 + 5;

int arr[N], f[M];

int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    return gcd(b, a%b);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    int tmp = arr[0];
    for (int i = 1; i < n; ++i)
        tmp = gcd(tmp, arr[i]);
    if (tmp != 1)
    {
        puts("INF");
        return 0;
    }
    f[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = arr[i]; j < M; ++j)
        {
            f[j] = max(f[j], f[j-arr[i]]);
        }
    }

    int res = 0;
    for (int i = 1; i < M; ++i)
    {
        if (!f[i])
            res++; 
    }
    printf("%d", res);
    return 0;
}



Wou
2天前
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 105; 
const int M = 1e4 + 5;

int arr[N], f[M];

int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    return gcd(b, a%b);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    int tmp = arr[0];
    for (int i = 1; i < n; ++i)
        tmp = gcd(tmp, arr[i]);
    if (tmp != 1)
    {
        puts("INF");
        return 0;
    }
    f[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = arr[i]; j < M; ++j)
        {
            f[j] = max(f[j], f[j-arr[i]]);
        }
    }

    int res = 0;
    for (int i = 1; i < M; ++i)
    {
        if (!f[i])
            res++; 
    }
    printf("%d", res);
    return 0;
}



Wou
2天前
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

struct Matrix{
    LL mat[4][4];
}answer;

void show(Matrix a)
{
    for (int i = 1; i <= 3; ++i)
    {
        for (int j = 1; j <= 3; ++j)
            cout << a.mat[i][j] << " ";
        cout << endl;
    }
}

Matrix Multiple(Matrix a, Matrix b, int c)
{
    Matrix res;
    memset(res.mat, 0, sizeof(res.mat));
    for (int i = 1; i <= 3; ++i)
    {
        for (int j = 1; j <= 3; ++j)
        {
            for (int k = 1; k <= 3; ++k)
            {
                LL tmp = a.mat[i][k] * b.mat[k][j] % c;
                res.mat[i][j] = (res.mat[i][j] + tmp) % c;
            }
        }
    }
    return res;
}

Matrix expMod(Matrix a, int b, int c)
{
    Matrix res;
    memset(res.mat, 0, sizeof(res.mat));
    res.mat[1][1] = res.mat[2][2] = res.mat[3][3] = 1;
    while (b)
    {
        if (b & 1)
            res = Multiple(res, a, c);
        a = Multiple(a, a, c);
        b >>= 1;
    }
    return res;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    answer.mat[1][2] = answer.mat[1][3] = 1;
    answer.mat[2][1] = answer.mat[2][2] = answer.mat[2][3] = 1;
    answer.mat[3][3] = 1;
//  show(answer);
//  show(Multiple(answer, answer, 1000));
    answer = expMod(answer, n-2, m);
    LL ans = 0;
    for (int i = 1; i <= 2; ++i)
        ans = (ans + answer.mat[i][3]) % m;
    ans = (ans + answer.mat[3][3]*2%m) % m;
    printf("%lld", ans);
//  show(answer);
    return 0;
}



Wou
2天前
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

struct Matrix{
    LL mat[4][4];
}answer;

void show(Matrix a)
{
    for (int i = 1; i <= 3; ++i)
    {
        for (int j = 1; j <= 3; ++j)
            cout << a.mat[i][j] << " ";
        cout << endl;
    }
}

Matrix Multiple(Matrix a, Matrix b, int c)
{
    Matrix res;
    memset(res.mat, 0, sizeof(res.mat));
    for (int i = 1; i <= 3; ++i)
    {
        for (int j = 1; j <= 3; ++j)
        {
            for (int k = 1; k <= 3; ++k)
            {
                LL tmp = a.mat[i][k] * b.mat[k][j] % c;
                res.mat[i][j] = (res.mat[i][j] + tmp) % c;
            }
        }
    }
    return res;
}

Matrix expMod(Matrix a, int b, int c)
{
    Matrix res;
    memset(res.mat, 0, sizeof(res.mat));
    res.mat[1][1] = res.mat[2][2] = res.mat[3][3] = 1;
    while (b)
    {
        if (b & 1)
            res = Multiple(res, a, c);
        a = Multiple(a, a, c);
        b >>= 1;
    }
    return res;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    answer.mat[1][2] = answer.mat[1][3] = 1;
    answer.mat[2][1] = answer.mat[2][2] = answer.mat[2][3] = 1;
    answer.mat[3][3] = 1;
//  show(answer);
//  show(Multiple(answer, answer, 1000));
    answer = expMod(answer, n-2, m);
    LL ans = 0;
    for (int i = 1; i <= 2; ++i)
        ans = (ans + answer.mat[i][3]) % m;
    ans = (ans + answer.mat[3][3]*2%m) % m;
    printf("%lld", ans);
//  show(answer);
    return 0;
}


活动打卡代码 AcWing 1220. 生命之树

Wou
2天前
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;

vector<int> G[N];
int w[N];

LL dfs(int u, int father)
{
    LL res = w[u];
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if (v == father) 
            continue;
        LL tmp = dfs(v, u);
        if (tmp > 0)
            res += tmp;
    }
    return res;
}

int main()
{
    int n, root = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &w[i]);
        if (w[root] < w[i])
            root = i;
    }
    for (int i = 0; i < n-1; ++i)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    printf("%lld", dfs(root, -1));
    return 0;
}



Wou
2天前
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;

vector<int> G[N];
int w[N];

LL dfs(int u, int father)
{
    LL res = w[u];
    for (int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if (v == father) 
            continue;
        LL tmp = dfs(v, u);
        if (tmp > 0)
            res += tmp;
    }
    return res;
}

int main()
{
    int n, root = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &w[i]);
        if (w[root] < w[i])
            root = i;
    }
    for (int i = 0; i < n-1; ++i)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    printf("%lld", dfs(root, -1));
    return 0;
}


活动打卡代码 AcWing 1222. 密码脱落

Wou
2天前
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e3 + 5;

int f[N][N];
string str;

int dfs(int l, int r)
{
    if (f[l][r]) 
        return f[l][r];
    if (l >= r)
        return 0;
    int res;
    if (str[l] != str[r])
        res = min(dfs(l, r-1)+1, dfs(l+1, r)+1);
    else
        res = dfs(l+1, r-1);
    return f[l][r] = res;
}

int main()
{
    cin >> str;
    cout << dfs(0, str.size()-1);
    return 0;
} 



Wou
2天前
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e3 + 5;

int f[N][N];
string str;

int dfs(int l, int r)
{
    if (f[l][r]) 
        return f[l][r];
    if (l >= r)
        return 0;
    int res;
    if (str[l] != str[r])
        res = min(dfs(l, r-1)+1, dfs(l+1, r)+1);
    else
        res = dfs(l+1, r-1);
    return f[l][r] = res;
}

int main()
{
    cin >> str;
    cout << dfs(0, str.size()-1);
    return 0;
}