美团 CodeM 资格赛 Round A 题解

初赛A轮题目在线练习地址

https://www.nowcoder.com/test/5523985/summary

身体训练

根据期望的线性性质，枚举第 i 个人是第 j 个轮到的，每个事件的概率都是 1/n。相当于计算:

暴力计算即可。
代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
const int N = 1005;
int n;
double v, u, c[N], d[N];
int main(){
    scanf("%d%lf%lf",&n,&v,&u);
    rep(i,1,n) scanf("%lf",c+i);
    rep(i,1,n) scanf("%lf",d+i);
    double ans = 0;
    rep(i,1,n) rep(j,1,n) ans+=1.0/(c[i]-(j-1)*d[i]-v);
    ans*=u;
    printf("%.3lf\n",ans);
}

合并回文子串

考虑 c 中的回文子串，既然是子串，就一定可以拆成 a, b 两串的两个子串的 combine。不妨设是 a[i, j]与 b[k, l]的 combine，则可以考虑动态规划的状态 f[i][j][k][l]表示 a[i, j]与 b[k, l]的 combine 能否组成回文子串。则可以匹配第一个字符和最后一个字符来转移，根据第一个字符和最后一个字符分别来自 a 还是 b 共有四种转移:

图片标题

边界情况：
1. 当 j – i + 1 + l – k + 1 = 0 时答案是 true
2. 当 j – i + 1 + l – k + 1 = 1 时答案是 true。
代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int T;
int n,m;
char a[55],b[55];
bool f[55][55][55][55];
int main()
{
  for(scanf("%d",&T);T--;)
  {
    scanf("%s",a+1);n=strlen(a+1);
    scanf("%s",b+1);m=strlen(b+1);
    int ans=0;
    for(int d1=0;d1<=n;d1++)
      for(int d2=0;d2<=m;d2++)
        for(int i=1,j=d1;j<=n;i++,j++)
          for(int k=1,l=d2;l<=m;k++,l++)
          {
            if(d1+d2<=1)f[i][j][k][l]=1;
            else
            {
              f[i][j][k][l]=0;
              if(d1>1&&a[i]==a[j])f[i][j][k][l]|=f[i+1][j-1][k][l];
              if(d1&&d2&&a[i]==b[l])f[i][j][k][l]|=f[i+1][j][k][l-1];
              if(d1&&d2&&b[k]==a[j])f[i][j][k][l]|=f[i][j-1][k+1][l];
              if(d2>1&&b[k]==b[l])f[i][j][k][l]|=f[i][j][k+1][l-1];
            }
            if(f[i][j][k][l])ans=max(ans,d1+d2);
          }
    printf("%d\n",ans);
  }
  return 0;
}

倒水

大致分三种情况讨论:

T 大于所有 ti:由于要求温度最大，当然是把所有水都倒完。
T 小于等于所有 ti:因为倒水只会把水的温度往 T 靠拢，所以找一个最小的 ti，把其他所
有 tj 都倒水变成 ti。
存在 ti < T 且存在 tj > T:显然无解。
代码:

#include<bits/stdc++.h>
#define int64 long long
#define sqr(x) (x)*(x)
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define VI vector<int>
#define VI64 vector<int64>
#define VS vector<string>
#define PII pair<int,int>
#define PDD pair<double,double>
#define VPII vector< PII >
#define SZ(x) ((int)(x).size())
#define N 120000
using namespace std;
int n,t[N],c[N];
int T,C;
void P(double x){
	printf("Possible\n");
	printf("%.4lf\n",x);
	exit(0);
}
void fail(){
	printf("Impossible\n");
	exit(0);
}
int main(int argv,char **argc){
freopen(argc[1],"r",stdin);
freopen(argc[2],"w",stdout);
	scanf("%d",&n);
	scanf("%d%d",&T,&C);
	cerr<<C<<endl;
	bool f1=0,f2=0;
	rep(i,1,n){
		scanf("%d%d",&t[i],&c[i]);
		if(t[i]<T)f1=1;
		if(t[i]>T)f2=1;
	}
	if(f1 && f2)fail();
	if(!f1 && !f2)P(T);
	if(f1){
		T*=-1;
		rep(i,1,n)t[i]*=-1;
	}
	int minnT=1e9;
	int64 cc=0;
	rep(i,1,n)minnT=min(minnT,t[i]);
	if(minnT==T)fail();
	rep(i,1,n)cc+=(minnT*c[i]-c[i]*t[i]);
	if(T-minnT>0 && cc>(int64)C*(T-minnT))fail();
	if(T-minnT<0 && cc<(int64)C*(T-minnT))fail();
	cerr<<"lucky"<<endl;
	if(f1){
		double f1=0,f2=0;
		f1=(double)T*C;
		f2=C;
		rep(i,1,n)f1+=t[i]*c[i],f2+=c[i];
		P(-f1/f2);
	}else P(minnT*(f1?-1:1));
	return 0;
}

最长树链

枚举每个约数，保留对应的边，做一次最长路径。因为一个数的约数个数可以保证，所以复杂度符合要求。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n, l, c[100001], len, value[100001], visit[100001], V[100001];
bool b[100001];
map< int, vector<int> > factor;
struct node{
  node *next;
  int where;
} a[200001], *first[100001];
inline void makelist(int x, int y) {
  a[++l].where = y;
  a[l].next = first[x];
  first[x] = &a[l];
}
pair<int, int> bfs(int init, int v, int round) {
  c[1] = init; visit[init] = 1;
  int pos = 0, will = 0;
  int k = 1, l = 1;
  for (; l <= k; ++l)
  {
    int m = c[l];
    if (visit[m] > will)
      will = visit[m], pos = m;
    for (node *x = first[m]; x; x = x->next)
      if (!(value[x->where] % v) && !visit[x->where])
      {
        visit[x->where] = visit[m] + 1;
        c[++k] = x->where;
      }
  }
  if (round == 0) 
    for (int i = 1; i <= k; i++)
      visit[c[i]] = 0;
  return make_pair(pos, will);
}
int calc(int v) {
  vector<int> idx = factor[v];
  int will = 0;
  for (int i = 0; i < idx.size(); i++)
    if (!visit[idx[i]])
    {
      will = max(will, bfs(bfs(idx[i], v, 0).first, v, 1).second);
    }
  for (int i = 0; i < idx.size(); i++)
    visit[idx[i]] = 0;
  return will;
}
     
int main() {
  len = 0;
  memset(b, false, sizeof(b));
  for (int i = 2; i <= 100000; i++)
  {
    if (!b[i])
      c[++len] = i;
    for (int j = 1; j <= len; ++j)
      if (c[j] * i > 100000)
        break;
      else
      {
        b[c[j] * i] = true;
        if (!(i % c[j]))
          break;
      }
  }
  scanf("%d", &n);
  memset(first, 0, sizeof(first)); l = 0;
  for (int i = 1; i < n; i++)
  {
    int x, y;
    scanf("%d%d", &x, &y);
    makelist(x, y);
    makelist(y, x);
  }
  factor.clear();
  for (int i = 1; i <= n; i++)
  {
    int x;
    scanf("%d", &x);
    value[i] = x;
    for (int j = 1; c[j] * c[j] <= x; ++j)
      if (!(x % c[j]))
      {
        if (factor.find(c[j]) == factor.end())
          factor[c[j]].clear();
        factor[c[j]].push_back(i);
        for (; !(x % c[j]); )
          x /= c[j];
      }
    if (x != 1)
    {
      if (factor.find(x) == factor.end())
        factor[x].clear();
      factor[x].push_back(i);
    }
  }
  int ans = 0;
  memset(visit, 0, sizeof(visit));
  memset(V, 0, sizeof(V));
  for (map< int, vector<int> >::iterator itr = factor.begin(); itr != factor.end(); ++itr)
    ans = max(ans, calc(itr->first));
  printf("%d\n", ans);
}

数列互质

对于在整个序列中出现次数超过 sqrt(n)的数，最多只有 sqrt(n)种，那么对于这些数，很容易用一个数组做前缀和维护，可以在每次询问中直接求出它们的出现次数并 gcd 判断。剩下的数的出现次数不超过 sqrt(n)，那么可以对它出现恰好 w 次的区间左右端点写出一个范围约束，这样的约束只总共只有 nsqrt(n)对，把左端点和右端点看成笛卡尔坐标系上的 x,y坐标，约束就可以看成一个矩形，问题转化为求询问点被多少矩形覆盖到，可以用扫描线来离线对所有询问计算。
一个 trick case，k=1 是需要注意 gcd(1,0)=1 的问题。

代码:

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
#define L 100
using namespace std;
int n,m,S,Sn,i,j,k,w,l,r,u,v,ul,vr,c;
int a[50005],sum[50000/L+5][50005],ans[50005],t[50005];
int ql[50005],qr[50005],qk[50005];
vector<int> V[100005];
vector<pair<int,int> > Ins[L+5][50005],Del[L+5][50005];
vector<int> query[50005];
int main()
{
  scanf("%d%d",&n,&m);S=min((int)sqrt(n),100);
  for(i=1;i<=n;++i)scanf("%d",&a[i]),V[a[i]].push_back(i);
  
  for(i=1;i<=n;++i)
  if(V[i].size()>=S)
  {
    ++Sn;
    for(k=V[i].size(),j=0;j<k;++j)++sum[Sn][V[i][j]];
    for(j=1;j<=n;++j)sum[Sn][j]+=sum[Sn][j-1];
  }
  else
  {
    c=V[i].size();
    for(j=0;j<c;++j)
    {
      u=V[i][j];
      if(j)ul=V[i][j-1]+1;else ul=1;
      for(k=j,l=1;k<c;++k,++l)
      {
        v=V[i][k];
        if(k<c-1)vr=V[i][k+1]-1;else vr=n;
        Ins[l][ul].push_back(make_pair(v,vr));
        Del[l][u].push_back(make_pair(v,vr));
      }
    }
  }
  
  for(i=1;i<=m;++i)
  {
    scanf("%d%d%d",&ql[i],&qr[i],&qk[i]);
    l=ql[i];r=qr[i];
    query[l].push_back(i);
    for(j=1;j<=Sn;++j)if(sum[j][r]-sum[j][l-1]>0&&__gcd(sum[j][r]-sum[j][l-1],qk[i])==1)++ans[i];
  }
  
  for(i=1;i<S;++i)
  for(j=1;j<=n;++j)
  {
    for(k=Ins[i][j].size()-1;k>=0;--k)
    {
      l=Ins[i][j][k].first;
      r=Ins[i][j][k].second;
      for(w=l;w<=n;w+=w&-w)++t[w];
      for(w=r+1;w<=n;w+=w&-w)--t[w];
    }
    for(k=query[j].size()-1;k>=0;--k)
    {
      l=query[j][k];
      u=qr[l];v=qk[l];
      if(__gcd(v,i)!=1)continue;
      for(w=u;w;w-=w&-w)ans[l]+=t[w];
    }
    for(k=Del[i][j].size()-1;k>=0;--k)
    {
      l=Del[i][j][k].first;
      r=Del[i][j][k].second;
      for(w=l;w<=n;w+=w&-w)--t[w];
      for(w=r+1;w<=n;w+=w&-w)++t[w];
    }
  }
  
  for(i=1;i<=m;++i)printf("%d\n",ans[i]);
}

二分图染色

完全二分图转棋盘模型，即 N ×N 棋盘上放黑白棋子，每个格子至多放一个，同行同列没有相同颜色的棋子。
用容斥原理，先假设每个格子可以放多个，再减去不合法的方案。如果每个格子可以放多个，一个不合法的格子所在的行和列都不会再摆放其他棋子，也没有两个不合法的格子同行同列。因此我们有计算式:
其中 AN−i 表示在 (N − i) × (N − i)的棋盘上放单色棋子，使得没有棋子同行同列的方案数。考虑从 (N − 1) ×(N − 1)棋盘递推到 N ×N 棋盘，我们有:
第一项是在第 N 行或者第 N 列上放一枚棋子或者不放的方案数，由于放两枚棋子的情况会
被统计两次，最后还需减去摆两枚棋子的方案数，即第三项。

代码:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
const int N = (int) 1e7;
const int mod = (int) 1e9 + 7;
using namespace std;
long long fac[N+10], inv[N+10], a[N+10];
int n;
long long ex(int x, int y, int w) {
    if ((w = (w + y) % y) % x == 0)
        return w / x;
    return ((ex(y % x, x, -w) * y) + w) / x;
}
long long c(int n, int m) {
    return (long long) fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i-1] * (long long) i % mod;
    inv[n] = ex(fac[n], mod, 1);
    for (int i = n; i >= 1; --i)
        inv[i-1] = (long long) inv[i] * i % mod;
    a[0] = 1;
    for (int i = 1; i <= n; ++i)
        a[i] = (2LL * i * a[i - 1] % mod - ((long long) (i-1) * (i-1)) % mod * a[i - 2] % mod + mod) % mod;
    long long ans = 0;
    for (int i = 0; i <= n; ++i)
        ans = (ans + ((i & 1 ? mod - 1LL : 1LL) * c(n, i) % mod * c(n, i) % mod * fac[i] % mod * a[n-i] % mod * a[n-i] % mod)) % mod;
    cout << ans << endl;
}