头像

DHF


访客:492

离线:6天前



DHF
7天前

题目描述

给定一颗树,树中包含n个结点(编号1~n)和n-1条无向边。

请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式

第一行包含整数n,表示树的结点数。

接下来n-1行,每行包含两个整数a和b,表示点a和点b之间存在一条边。
输出格式

输出一个整数m,表示重心的所有的子树中最大的子树的结点数目。
数据范围

1≤n≤105

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例:

4

算法1

(两遍dfs,第一遍求每个节点子树的结点个数,第二遍dfs假定删除当前点,与其联通的子树的最大结点个数) $O(n)$

C++ 代码

#include<iostream>
#include<cstring>
#include<limits.h>
#include<map>
#include<vector>
#define N 100010
#include<cstdio>
using namespace std;
vector<vector<int>>mp;
int cnt[N];
bool vis[N];
int n;
int re=INT_MAX;
int dfs(int node){
    cnt[node]=1;
    int sum=0;
    vis[node]=true;
    for(int i=0;i<mp[node].size();i++){
        if(!vis[mp[node][i]])
        sum+=dfs(mp[node][i]);
    }
    cnt[node]+=sum;
    vis[node]=false;
    return cnt[node];
}
void _dfs(int node,int k){
    int c=k;
    vis[node]=true;
    for(int i=0;i<mp[node].size();i++){
        if(!vis[mp[node][i]]){
          c=max(cnt[mp[node][i]],c);
          _dfs(mp[node][i],n-cnt[mp[node][i]]);
        }
    }
    vis[node]=false;
    re=min(re,c);
}
int main(){
    scanf("%d",&n);
    mp.resize(n+5);
    int a,b;
    for(int i=0;i<n-1;i++){
        scanf("%d %d",&a,&b);
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    dfs(1);
    _dfs(1,0);
    printf("%d",re);
    return 0;   
}



DHF
8天前

马走日爆搜版

题目描述

马在中国象棋以日字形规则移动。

请编写一段程序,给定 n∗m
大小的棋盘,以及马的初始位置 (x,y)

,要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点。
输入格式

第一行为整数 T

,表示测试数据组数。

每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标 n,m,x,y

样例

1
5 4 0 0

输出:32

可能是C++的语言特性,爆搜稳过。。。

算法1

(dfs)

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={-2,-1,1,2,2,1,-1,-2};
bool vis[10][10];
int n,m,re=0,sx,sy;
void dfs(int x,int y,int cnt){
if(cnt==n*m){
re;
return ;
}
vis[x][y]=true;
for(int i=0;i<8;i
){
int a=dx[i]+x,b=dy[i]+y;
if(a>=0&&a[HTML_REMOVED]=0&&b<m&&!vis[a][b]){
dfs(a,b,cnt+1);
}
}
vis[x][y]=false;

}
int main(){
int t;
cin>>t;
while(t–){
re=0;
cin>>n>>m>>sx>>sy;
dfs(sx,sy,1);
cout<<re<<endl;
}
return 0;
}



活动打卡代码 AcWing 1223. 最大比例

DHF
12天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N = 110;

int n;
LL a[N], b[N], x[N];

LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}

LL gcd_sub(LL a, LL b)
{
if (a < b) swap(a, b);
if (b == 1) return a;
return gcd_sub(b, a / b);
}

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

sort(x, x + n);
int cnt = 0;
for (int i = 1; i < n; i ++ )
    if (x[i] != x[i - 1])
    {
        LL d = gcd(x[i], x[0]);
        a[cnt] = x[i] / d;
        b[cnt] = x[0] / d;
        cnt ++ ;
    }

LL up = a[0], down = b[0];
for (int i = 1; i < cnt; i ++ )
{
    up = gcd_sub(up, a[i]);
    down = gcd_sub(down, b[i]);
}

cout << up << '/' << down << endl;

return 0;

}




DHF
19天前
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
int n,m;
void mul(ll a[],ll c[][3]){
    ll temp[3]={0};
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            temp[i]=(temp[i]+1ll*a[j]*c[j][i])%m;
        }
    }
    memcpy(a,temp,sizeof temp);
}
void mulm(ll A[][3]){
    ll temp[3][3]={0};
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                temp[i][j]=(temp[i][j]+A[i][k]*1ll*A[k][j])%m;
            }
        }
    }
    memcpy(A,temp,sizeof temp);
}

int main(){
    cin>>n>>m;
    ll a[3]={1,1,1};
    ll A[3][3]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    n--;
    while(n){
        if(n&1)mul(a,A);
        n>>=1;
        mulm(A);
    }
    printf("%lld",a[2]);
    return 0;
}


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

DHF
20天前
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<limits.h>
#define N 100005
#define ll long long
using namespace std;
ll node[N];
int cnt[N];//出度表
int vis[N];
int n;
ll max(ll a,ll b){
    return a>b?a:b;
}
map<int,vector<int>>mp;//mps为逆向关系表
int main(){
      scanf("%d",&n);
      for(int i=1;i<=n;i++){
          scanf("%lld",&node[i]);
      }
      for(int i=0;i<n-1;i++){
        int u,v;         
          scanf("%d %d",&u,&v);
          mp[u].push_back(v);
          mp[v].push_back(u);
          cnt[u]++;
          cnt[v]++;

      }
      queue<int>q;

      for(int i=1;i<=n;i++){
           if(cnt[i]==1){
            //  printf("%d ",i);
               q.push(i);
            }
      }

      while(!q.empty()){
          int p=q.front();
          q.pop();
          vis[p]=1;
            for(auto e:mp[p]){
                if(vis[e])continue;
             if(node[p]>=0) node[e]+=node[p];
              cnt[e]--;
              if(cnt[e]==1)q.push(e);
            }

      }
      ll re=INT_MIN;
      for(int i=1;i<=n;i++){
          re=max(re,node[i]);
      }
      printf("%lld",re);
    return 0;
}


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

DHF
20天前
#include<cstdio>
#include<cstring>

using namespace std;
int f[1005][1005];
int main(){
    char s[1005];
    scanf("%s",s);
    int n=strlen(s);

    for(int i=1;i<=n;i++){
        for(int j=0;j+i-1<n;j++){
               int l=j,r=j+i-1;
               if(l==r){
                   f[l][r]=1;
                   continue;
               }
                if(s[l]==s[r]){
                    f[l][r]=f[l+1][r-1]+2;
                }

                if (f[l][r - 1] > f[l][r]) f[l][r] = f[l][r - 1];
                if (f[l + 1][r] > f[l][r]) f[l][r] = f[l + 1][r];

        }
    }

    printf("%d\n",n-f[0][n-1]);
    return 0;
}


活动打卡代码 AcWing 1047. 糖果

DHF
20天前
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int f[104][105];
int main(){
        int n,k;
        cin>>n>>k;
        memset(f,-0x3f,sizeof f);
        f[0][0]=0;
        for(int i=1;i<=n;i++){
            int w;
            scanf("%d",&w);
            for(int j=0;j<k;j++){
                f[i][j]=max(f[i-1][j],f[i-1][(j+k-w%k)%k]+w);
            }
        }
        cout<<f[n][0];
    return 0;
}


活动打卡代码 AcWing 1234. 倍数问题

DHF
22天前
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n, m;
vector<int> a[N];
int f[4][N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        a[x % m].push_back(x);
    }

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i < m; i ++ )
    {
        sort(a[i].begin(), a[i].end());
        reverse(a[i].begin(), a[i].end());

        for (int u = 0; u < 3 && u < a[i].size(); u ++ )
        {
            int x = a[i][u];
            for (int j = 3; j >= 1; j -- )
                for (int k = 0; k < m; k ++ )
                    f[j][k] = max(f[j][k], f[j - 1][(k - x % m + m) % m] + x);
        }
    }

    printf("%d\n", f[3][0]);

    return 0;
}



活动打卡代码 AcWing 1242. 修改数组

DHF
24天前
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
using namespace std;
int a[N];
int vis[N];
int fa[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){
        fa[fy]=fx;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<N-1;i++){
        fa[i]=i;
    }
    for(int i=0;i<n;i++){
        if(!vis[a[i]]){
            vis[a[i]]=1;
            if(vis[a[i]-1]==1){
                merge(a[i],a[i]-1);
            }
            if(vis[a[i]+1]==1){
                merge(a[i]+1,a[i]);
            }
            continue;
        }
        int fi=find(a[i]);
        vis[fi+1]=1;
        merge(fi+1,fi); 
        if(vis[fi+2]==1){
            merge(fi+2,fi+1);
        }
        a[i]=fi+1;
    }
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}


活动打卡代码 AcWing 1246. 等差数列

DHF
25天前
#include<bits/stdc++.h>
//#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n],ma=-1,mi=INT_MAX;
    for(int i=0;i<n;i++){
        cin>>a[i];
        mi=min(mi,a[i]);
        ma=max(ma,a[i]);
    }
    if(ma-mi==0){
        cout<<n;
        return 0;
    }
    sort(a,a+n);
    vector<int>b;
    for(int i=0;i+1<n;i++)b.push_back(a[i+1]-a[i]);
    int s=b.size();
    int re=__gcd(b[0],b[1]);
    for(int i=0;i<s;i++){

        re=__gcd(re,b[i]);
    }
    cout<<(ma-mi)/re+1;
    return 0;
}