算法中级班期中赛（02）期中

· · 个人记录

疫苗日期

思路

题目的意思还是很明确的，所以我们要考虑每个月的日期，这里的日期是和闰年相关的，因为2月在闰年有29天。

考察

分类讨论思想和ifelse分支结构用法

代码

这里给出ygc同学的代码，简洁高效！

我们考虑利用数组存下每个月的日期，然后考虑是不是闰年，由于只有14天，跨度最多一个月，后面考虑再那个月即可！

int md[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
char a,b;
int y,m,d;
int main(){
    cin>>y>>a>>m>>b>>d;
    d+=14;
    if(y%400==0||(y%4==0&&y%100!=0)) md[2]++;
    if(md[m]<d) d-=md[m],m++;
    if(m>12) m=1,y++;
    cout<<y<<'-'<<m<<'-'<<d;

二叉树游戏

思路

就是二叉树上考虑树的深度和宽度，深度可以直接通过dfs深入即可，那么宽度呢？

其实也很简单，假设我们现在进来的是深度为3的点，那么我们再开一个数组w，然后w[3]++即可，这样我们就求出深度和宽度了！

这里同学们可以再考虑一下。

考察

dfs+树+思维

代码

这里用了dby的代码，一个dfs做了两个事情，非常简洁

void dfs(int x,int fa)
{
    if(maxn<a[x]) maxn=a[x];
    s[a[x]]++;
    for(int i=0;i<g[x].size();i++)
    {
        int to=g[x][i];
        if(to!=fa)
        {
            a[to]=a[x]+1;
            dfs(to,x);
        }
    }
}

二叉树的思考

思路

本题考察利用递归建二叉树的能力，通过后序，可以找到二叉树的每个阶段的根，直接输出树根即可。

递归有两个功能，利用中序，分解字符串左右子树的大小，利用后序，可以分治出后续里面的当前的树根。

考察

递归的理解+字符串的处理+分治的思想

代码

void fis(int l1,int r1,int l2,int r2){
    if(l1>r1) 
        return;
    int p=a.find(b[r2]);//找到中间位置 
    cout<<a[p];
    fis(l1,p-1,l2,l2+p-1-l1);
   fis(p+1,r1,r2-r1+p,r2-1);
}

士兵

思路

考虑O(1)的查询和删除，我们可以用数组模拟下链表即可

考察

链表，数组

代码

void Init(int n){
    for(int i=1;i<=n;i++){
        a[i].pre=i-1;
        a[i].nxt=i+1;
    }
    a[n].nxt=0;
    return;
}
int main(){
    n=read();m=read();
    Init(n);
    for(int i=1;i<=m;i++){
        int x=read();
        if(a[x].pre==0) printf("* ");
        else printf("%d ",a[x].pre);
        if(a[x].nxt==0) printf("*\n");
        else printf("%d\n",a[x].nxt);
        a[a[x].nxt].pre=a[x].pre;
        a[a[x].pre].nxt=a[x].nxt;
    }
    return 0;
}

分成两组

思路

我们01dfs暴力去枚举所有的分组情况即可

考察

01dfs+剪枝

代码

void dfs(LL step,LL S)
{
    if(step==n+1)
    {
        ans=min(ans,abs(S*2-s));
        return;
    }
    dfs(step+1,S+a[step]);
    dfs(step+1,S);
}

这里要注意s的范围，建议用longlong

这里其实还可以剪枝，本题虽然没考察，但是我们可以做一个最优解剪枝，就是剩下的数都给它，都不能比之前的最小差更小，那么我们直接范围。

建议先sort从大到小排序后这么操作！

友好匹配

考察

因为是树上的最短路径，那么我们可以用lca来实现，考虑友好匹配的时候，是看

考点

有很多种做法
bfs+组合数
dij最短路+组合数
dfs+lca+组合数也是可以的
这里面我们用lca+组合数来实现：我们考虑第一遍用dfs进行预处理，记录父节点f[]的信息，利用w[N][3]数组，记录从根出发的余数为0的，为1，为2的数量，类似树的距离。
然后用lca求出路径上每个类型的人的数量。 因为是两两匹配，所以是C（k,2），就是k个人里面选2个，所以(k-1)*k/2；

代码

本题考察深度还是可以的，有绿题左右水平！

#include<bits/stdc++.h>
using namespace std;
const int N=101000;
vector<int> G[N];  
int n,ww,w[N][3],a[N],d[N],father[N],q;
void dfs(int root)
{
  if(G[root].size()==0)
    return;
  for(int i=0; i<G[root].size(); i++)
  {
    int x=G[root][i];
    father[x]=root;
    d[x]=d[root]+1;//处理深度 
    for(int i=0;i<3;i++)//处理前缀的余数 
        if(a[x]==i)         
            w[x][i]=w[root][i]+1;
        else
            w[x][i]=w[root][i];
    dfs(x);
  }
}
int lca(int a,int b){
    if(d[a]>d[b])
        swap(a,b);
    while(d[b]>d[a])
        b=father[b];
    while(a!=b){
        a=father[a];
        b=father[b];
    }
    return a;
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a[i]=x%3;
    }
    w[1][a[1]]=1,d[1]=1;
    dfs(1);
    cin>>q;
    for(int i=1;i<=q;i++){
        int x,y;
        long long ans=0;
        cin>>x>>y;
        int lf=lca(x,y);
        for(int i=0;i<3;i++){
            long long  z=w[x][i]+w[y][i]-w[lf][i]-w[father[lf]][i];
            ans+=z*(z-1)/2;
        }
        cout<<ans<<endl;
    }
    return 0;
}