Nowcoder Girl初赛重现赛 补题

Nowcoder Girl初赛重现赛

---

感想：
第一次打nowcoder girl ,比赛体验感还是很好的，
（虽然有些题目没有A掉自闭了挺久的）
题目好像不是很难
但是因为不能翻博客，看书，然后差点连裸的背包都挂掉了
-果然诚如高中化学老师箴言：基础不牢，地动山摇。
比赛的时候好像只写了三四道 --好像还有写假的成分QAQ
但是能出现在那个榜上面超级开心，???? 希望自己被抽中QAQ
希望面试顺利，瑟瑟发抖。

---

A 牛妹爱整除
B 吃桃
C 背包问题
D 泡面
E 伪直径
F 最大最小差 --！！！未补

1.数学题

在B进制下的每个位数之和%k =0;
原来的数%k = 0
-3的倍数的十进制数上每一位的和也是三的倍数
转化一下就是以上 等号取到的情况就是左右两边都对p取余 —也就是B%k ==1

所有就是进制数=倍数+1
//比赛时候瞎蒙3k+1 longlong 过

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin>>x;
    cout<<x+1<<endl;
}

2.dfs

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,k;
int r[N],nt[N];
vector<int>v[N];
void dfs(int x,int fa)
{
	for(int i=0;i<v[x].size();i++)
	{
		if(fa==v[x][i]) continue;//因为是一棵树所以要只要考虑的是下一个节点不要再会到原来节点形成死循环
		dfs(v[x][i],x);
		if(r[x]<r[v[x][i]]+1)
		{
			r[x]=r[v[x][i]]+1;
			nt[x]=v[x][i];
		}else if(v[x][i]<nt[x]&&r[x]==r[v[x][i]]+1)
		{
			nt[x]=v[x][i];
		}
	}
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int a,b;scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(k,0);
	while(k)
	{
		cout<<k<<endl;
		k=nt[k];
	}
} 

比赛时候的超级暴力的dfs，debug 成功后的版本

#include<bits/stdc++.h>
using namespace std;
vector<int>v[200010];
int vis[200010];
int p[200010];
int jg[200010];int maxx;
void dfs(int x,int cnt)
{
        if(maxx<cnt)
        {
            maxx=cnt;
            for(int i=1;i<=cnt;i++)
            {
                jg[i]=p[i];
            }
        }else if(maxx==cnt)
         {
            int ok=0;
            for(int i=1;i<=cnt;i++)
            {
                if(jg[i]>p[i])
                {
                    ok=i;
                    break;
                 }
                 if(jg[i]<p[i]) break;//QAQ
             }
             if(ok)
             {
                for(int i=ok;i<=cnt;i++) jg[i]=p[i];
             }
         }
    for(int i=0;i<v[x].size();i++)
    {
        if(vis[v[x][i]]==0)
        {
            vis[v[x][i]]=1;
            p[cnt+1]=v[x][i];
            dfs(v[x][i],cnt+1);
            vis[v[x][i]]=0;
        }
    }
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n-1;i++)
    {
        int a,b;scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vis[k]=1;p[1]=k,jg[1]=k;
    dfs(k,1);
    //cout<<maxx<<endl;
    for(int i=1;i<=maxx;i++) printf("%d\n",jg[i]);
}

3.01背包

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N];
int w[N],V[N]; 
int main()
{
   int n,v;
   cin>>n>>v;
   int s=0;
   for(int i=1;i<=n;i++)
   {
   	cin>>w[i]>>V[i];//体积，价值 
   	s+=V[i];
   }
   for(int i=1;i<=n;i++)
   {
   	for(int j=s;j>=V[i];j--)
   	{
   		dp[j]=max(dp[j],dp[j-V[i]]+w[i]);
	}
   }
   for(int i=1;i<=s;i++)
   {
   	if(dp[i]>=v)
   	{
   		printf("%d\n",i);
   		return 0;
	}
   }
}
}

4 .priority_queue 在时间都符合的情况下，把这些元素都存到小根堆里面。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll ans[N];
struct node
{
	int id;ll tt;
};
int cmp(node x,node y)
{
	if(x.tt==y.tt) return x.id<y.id;
	return x.tt<y.tt; 
}
struct  cmp1//维护小根堆 
{
    bool operator ()(node x,node y)
    {
    		return x.id>y.id ;
	}
 } ;
int main()
{
	int n,p;cin>>n>>p;
	priority_queue<node,vector<node>,cmp1> q;
	vector<node>v; 
	for(int i=1;i<=n;i++)
	{
		ll tt;cin>>tt;
	    v.push_back(node{i,tt});
	}
	sort(v.begin(),v.end(),cmp);//时间早优先 
	int st=0;int tot=n;ll now=0ll;//tot倒完水的人 
	while(tot)
	{
		if(q.empty()&&st<n) 
		{
			q.push(v[st]);
			now=v[st].tt;
			st++;
		}
		node k=q.top();now+=1ll*p;
		ans[k.id ]=now ;q.pop();tot--;
		while(st<n)
		{
			if(v[st].tt>now)
			{
				break;
			}
			q.push(v[st]);
			st++;
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}

5.解法类似2 --转化为求树的直径-1

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,k;
int r[N];
vector<int>v[N];
int ans;
void dfs(int x,int fa)
{
	for(int i=0;i<v[x].size();i++)
	{
		if(fa==v[x][i]) continue;
		dfs(v[x][i],x);
		ans=max(ans,r[v[x][i]]+r[x]+1);//求最大的直径
		if(r[x]<r[v[x][i]]+1)
		{
			r[x]=r[v[x][i]]+1;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b;scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,0);
	cout<<ans-1<<endl;
}