头像

Pr


访客:5715

离线:6天前



Pr
6天前
#include<bits/stdc++.h>
using namespace std;
const int N=6e3+10;
int h[N],e[N],ne[N],idx;
int H[N];
bool has_fa[N];
int n;
int f[N][2];
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u)
{
    f[u][1]=H[u];
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][0],f[j][1]);
    }
}
int main()
{
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
    scanf("%d",&H[i]);
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(b,a);
        has_fa[a]=true;
    }
    int root;
    for(int i=1;i<=n;i++)
    if(!has_fa[i]) root=i;
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
    return 0;
}



Pr
7天前
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
    int n=nums.size();
    vector<vector<int>> f(n,vector<int>(n,0));
    for(int i=1;i<n;i++) f[i][i]=nums[i];
    for(int len=2;len<=n;len++)
        for(int i=0;i+len-1<n;i++)
         {
             int l=i,r=i+len-1;
             f[l][r]=max(-f[l+1][r]+nums[l],-f[l][r-1]+nums[r]);
         }
    return f[0][n-1]>=0;
    }
};


活动打卡代码 AcWing 1075. 数字转换

Pr
7天前
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n;
int h[N],e[N],ne[N],idx;
int sum[N];
bool st[N];
int ans=0;
void init()
{
    memset(h,-1,sizeof(h));
    memset(st,false,sizeof(st));
    idx=0;
}
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u)
{
    int d1=0,d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        int d=dfs(j)+1;
        if(d>=d1) d2=d1,d1=d;
        else if(d>d2) d2=d;
    }
    ans=max(ans,d1+d2);
    return d1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
      for(int j=2;j<=n/i;j++)
        sum[i*j]+=i;
    init();
    for(int i=2;i<=n;i++)
    {
        if(i>sum[i])
        {
            add(sum[i],i);
            st[i]=true;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            dfs(i);
            st[i]=true;
        }
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1073. 树的中心

Pr
7天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2*N;
const int INF=0x3f3f3f3f;
int h[N],e[M],w[M],ne[M],idx;
int n;
int d1[N],d2[N],dp1[N],dp2[N],up[N];
int res=INF;
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs_down(int u,int fa)
{
    d1[u]=d2[u]=-INF;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        int d=dfs_down(j,u)+w[i];
        if(d>d1[u])
        {
            d2[u]=d1[u];
            d1[u]=d;
            dp2[u]=dp1[u];
            dp1[u]=j;
        }
        else if(d>d2[u]) 
        {
            d2[u]=d;
            dp2[u]=j;
        }
    }
     if(d1[u]==-INF) d1[u]=d2[u]=0;
     return d1[u];
}
void dfs_up(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        if(dp1[u]==j) up[j]=max(up[u],d2[u])+w[i];
        else up[j]=max(up[u],d1[u])+w[i];
        dfs_up(j,u);
    }
}
int main()
{
    scanf("%d",&n);
    init();
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs_down(1,-1);
    dfs_up(1,-1);
    for(int i=1;i<=n;i++)
    {
        res=min(res,max(up[i],d1[i]));
    }
    cout<<res<<endl;
    return 0;
}



Pr
8天前
class Solution {
public:
    int minCut(string s) {
    int n=s.size();
    s=" "+s;
    vector<vector<bool>> g(n+1,vector<bool>(n+1));
    vector<int> f(n+1,1e8);
    f[0]=0;
    for(int j=1;j<=n;j++)
        for(int i=1;i<=j;i++)
         {
             if(i==j) g[i][j]=true;
             if(s[i]==s[j])
             {
                 if(i+1>j-1||g[i+1][j-1]) g[i][j]=true;
             }
         }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(g[j][i]) f[i]=min(f[i],f[j-1]+1);
        }
    }
    return f[n]-1;
    }
};


活动打卡代码 LeetCode 125. 验证回文串

Pr
8天前
class Solution {
public:
    bool check(char c)
    {
        return c>='a'&&c<='z'||c>='0'&&c<='9'||c>='A'&&c<='Z';
    }
    bool isPalindrome(string s) {
    for(int i=0,j=s.size()-1;i<j;i++,j--)
    {
        while(i<j&&!check(s[i])) i++;
        while(i<j&&!check(s[j])) j--;
        if(i<j&&tolower(s[i])!=tolower(s[j])) return false;
    }
    return true;
    }
};




Pr
8天前
class Solution {
public:
    int numDistinct(string s, string t) {
    int n=s.size(),m=t.size();
    s=" "+s;
    t=" "+t;
    vector<vector<long>> f(n+1,vector<long>(m+1,0));
    for(int i=0;i<=n;i++) f[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          {
              f[i][j]+=f[i-1][j];
              if(s[i]==t[j]) f[i][j]+=f[i-1][j-1];
          }
    return f[n][m];
    }
};


活动打卡代码 LeetCode 264. Ugly Number II

Pr
8天前
class Solution {
public:
    int nthUglyNumber(int n) {
    vector<int> q;
    q.push_back(1);
    int i=0,j=0,k=0;
    while(--n)
    {
      int t=min(q[i]*2,min(q[j]*3,q[k]*5));
      q.push_back(t);
      if(q[i]*2==t) i++;
      if(q[j]*3==t) j++;
      if(q[k]*5==t) k++;
    }
    return q.back();
    }
};


活动打卡代码 LeetCode 91. Decode Ways

Pr
8天前
class Solution {
public:
    int numDecodings(string s) {
    int n=s.size();
    vector<int> f(n+1,0);
    s=' '+s;
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]>='1'&&s[i]<='9') f[i]+=f[i-1];
        if(i>1)
        {
            int t=(s[i-1]-'0')*10+s[i]-'0';
            if(t>=10&&t<=26) f[i]+=f[i-2];
        }
    }
    return f[n];
    }
};



Pr
9天前
class Solution {
public:
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    int mod=1e9+7;
    int findPaths(int n, int m, int N, int x, int y) {
        if(N==0) return 0;
    vector<vector<vector<int>>> f(N,vector<vector<int>>(n,vector<int>(m,0)));
    for(int i=0;i<n;i++ )
    {
        f[0][i][0]++;
        f[0][i][m-1]++;
    }
    for(int i=0;i<m;i++)
    {
        f[0][0][i]++;
        f[0][n-1][i]++;
    }
    for(int t=1;t<N;t++)
      for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
            {
                for(int p=0;p<4;p++)
                {
                    int a=i+dx[p];
                    int b=j+dy[p];
                    if(a<0||a>=n||b<0||b>=m) continue;
                   f[t][i][j]=( f[t][i][j]+f[t-1][a][b])%mod;
                }
            }
    int res=0;
    for(int i=0;i<N;i++)
    res=(f[i][x][y]+res)%mod;
    return res;
    }

};