美团CodeM初赛B轮题解
题目练习链接: https://www.nowcoder.com/test/5599304/summary
黑白树
思路
“每次操作选择的点必须是白色”这个条件其实是可以无视的，因为这可以通过自顶向 下选择来避免。
通过观察发现最底层的叶子必须选择，选完之后无视变黑的点，剩下的叶子也必须通过 选择其子树中某个节点来使自己变黑，因此贪心选择能染层数最深(最上面被染到的点最接 近根)的点+模拟即可。复杂度为线性。
参考代码
#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;
const double pi=acos(-1);
VI E[N];
int dep[N],fa[N],ans,n,f[N],k[N],p[N];
void dfs(int x){
f[x]=dep[x]-k[x]+1;
p[x]=1e9;
for(int i=0;i<E[x].size();++i){
dep[E[x][i]]=dep[x]+1;
dfs(E[x][i]);
f[x]=min(f[x],f[E[x][i]]);
p[x]=min(p[x],p[E[x][i]]);
}
if(p[x]>dep[x]){
ans++;
p[x]=f[x];
}
}
int main(int argv,char **argc){
// freopen("in","r",stdin);
// freopen("out","w",stdout);
freopen(argc[1],"r",stdin);
freopen(argc[2],"w",stdout);
scanf("%d",&n);
rep(i,2,n){
scanf("%d",&fa[i]);
E[fa[i]].pb(i);
}
dep[1]=1;
rep(i,1,n)scanf("%d",&k[i]);
dfs(1);
cerr<<ans<<endl;
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
送外卖 2
思路
3^q 状压每个货物的(未领、已领、已到)状态，对于每层状态，保存现在在点 i 的最 早到达时间，每一层用 dijkstra 暴力更新最早时间 O(n^2+m)。
复杂度 O(3^q(n^2+m))
如果将图缩减为一个不超过 2q 个点的完全图(只留下订单涉及的点)，两点之间的边长 为原图最短路，复杂度可以优化为 O(q(n^2+m) + 3^q q^2)。
参考代码
#include <stdio.h>
#include <stdlib.h>
#define inf 1000000005
using namespace std;
int n,m,q,Q,i,j,k,u,v,c,ans;
int s[15],t[15],l[15],r[15],w[15],p[15];
int son[25],Next[405],ed[405],cost[405],tot;
int f[60005][25];
bool vis[25];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(;m;--m)
{
scanf("%d%d%d",&u,&v,&c);
++tot;Next[tot]=son[u];son[u]=tot;ed[tot]=v;cost[tot]=c;
}
for(i=Q=1;i<=q;++i,Q*=3)scanf("%d%d%d%d",&s[i],&t[i],&l[i],&r[i]),p[i]=Q;
for(i=0;i<Q;++i)
for(j=1;j<=n;++j)
f[i][j]=inf;
f[0][1]=0;
for(i=0;i<Q;++i)
{
for(j=1;j<=n;++j)vis[j]=false;
for(j=1;j<=n;++j)
{
for(u=0,k=1;k<=n;++k)if(!vis[k]&&(!u||f[i][k]<f[i][u]))u=k;
for(k=son[u],vis[u]=true;k;k=Next[k])if(f[i][u]+cost[k]<f[i][ed[k]])f[i][ed[k]]=f[i][u]+cost[k];
}
for(j=1,k=i;j<=q;++j,k/=3)w[j]=k%3;
for(v=0,j=1;j<=q;++j)
{
if(w[j]==0&&f[i][s[j]]<inf)
{
if(f[i][s[j]]>l[j])u=f[i][s[j]];else u=l[j];
if(u<f[i+p[j]][s[j]])f[i+p[j]][s[j]]=u;
}
if(w[j]==1&&f[i][t[j]]<=r[j])
{
u=f[i][t[j]];
if(u<f[i+p[j]][t[j]])f[i+p[j]][t[j]]=u;
}
if(w[j]==2)++v;
}
for(j=1;j<=n;++j)if(f[i][j]<inf&&v>ans)ans=v;
}
printf("%d\n",ans);
}
模
思路
参考代码
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
int T;
LL a,b,c,k;
LL gcd(LL a,LL b)
{return b?gcd(b,a%b):a;}
int main()
{
for(scanf("%d",&T);T--;)
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
if(c%gcd(b,gcd(a,k-1))==0)
puts("Yes");
else
puts("No");
}
return 0;
}
合并字符串的价值
思路
参考代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=500005;
int CtI[256],T;
int n,m,a[maxn],b[maxn];
char str[maxn];
int cnt[maxn][4],pos[4][maxn];
struct node
{
int s[16];
node *lc,*rc;
int Max(int l,int r,const int &a,const int &b,const int &mask)
{
if(l>=a&&r<=b)return s[mask];
int mid=l+r>>1;
if(b<=mid)return lc->Max(l,mid,a,b,mask);
if(a>mid)return rc->Max(mid+1,r,a,b,mask);
return max(lc->Max(l,mid,a,b,mask),rc->Max(mid+1,r,a,b,mask));
}
}ndl[maxn*2],*ns,*root;
node* build(int l,int r)
{
node *x=++ns;
if(l==r)
{
for(int mask=0;mask<16;mask++)
{
x->s[mask]=0;
for(int c=0;c<4;c++)
x->s[mask]+=(mask>>c&1)?cnt[l][c]:-cnt[l][c];
}
}
else
{
int mid=l+r>>1;
x->lc=build(l,mid);
x->rc=build(mid+1,r);
for(int mask=0;mask<16;mask++)
x->s[mask]=max(x->lc->s[mask],x->rc->s[mask]);
}
return x;
}
void init()
{
CtI['A']=0,CtI['C']=1,CtI['G']=2,CtI['T']=3;
scanf("%s",str+1);n=strlen(str+1);
for(int i=1;i<=n;i++)a[i]=CtI[str[i]];
scanf("%s",str+1);m=strlen(str+1);
for(int i=1;i<=m;i++)b[i]=CtI[str[i]];
for(int i=1;i<=n;i++)
{
memcpy(cnt[i],cnt[i-1],sizeof(cnt[0]));
cnt[i][a[i]]++;
pos[a[i]][cnt[i][a[i]]]=i;
}
ns=ndl;
root=build(0,n);
}
void work()
{
int bA[4],bL[4];
memset(bA,0,sizeof(bA));
memset(bL,0,sizeof(bL));
for(int i=1;i<=m;i++)
bA[b[i]]++;
int ans=0,sl[6],cu[6];
for(int l,r,d,k,mask,i=0;i<=m;i++)
{
if(i)bL[b[i]]++;
for(int c=0;c<4;c++)
{
k=bA[c]-bL[c]-bL[c]+cnt[n][c];
if(k<0)k=(k-1)/2;
else k/=2;
k++;
if(k<=0)k=-1;
else if(k>cnt[n][c])k=n;
else k=pos[c][k]-1;
sl[c]=cu[c]=k;
}
sort(sl,sl+4);
sl[5]=n;
for(int j=0;j<=4;j++)
{
if(j==0)l=0;
else l=sl[j-1]+1;
r=sl[j];
l=max(l,0),r=min(r,n);
if(l<=r)
{
d=mask=0;
for(int c=0;c<4;c++)
if(r<=cu[c])d+=bL[c],mask|=1<<c;
else d+=bA[c]-bL[c]+cnt[n][c];
ans=max(ans,d+root->Max(0,n,l,r,mask));
}
}
}
printf("%d\n",ans);
}
int main()
{
freopen("2.in","r",stdin);
freopen("2.out","w",stdout);
for(scanf("%d",&T);T--;)
{
init();
work();
}
return 0;
}
子串
思路
本题是一道简单的模拟题。直接对于 15 种可能的 k 枚举，每种情况下直接使用 KMP 算 法进行匹配即可，时间复杂度是 O(n log n + |t|), 其中|t|是 t 的长度。
可以进行一些简单的优化，例如 t 中出现数字 i 的话必然进制 k > i。这样可以常数优化。
实际上通过对 t 的结构进行研究也许可以获得更好的结果(判断断点)，但是对于本题 的范围没有必要。
参考代码
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int maxn = 50000 + 10;
const int maxt = 1000000 + 1;
const char alphabet[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
char tmp[20];
string itoa(int n, int k) {
int c;
for (c = 0; n; c ++) tmp[c] = alphabet[n % k], n /= k;
tmp[c] = 0;
for (int i = 0; i < c / 2; ++ i) swap(tmp[i], tmp[c-1-i]);
string str (tmp);
return str;
}
string seq(int n, int k) {
string str = "";
for (int i = 1; i <= n; i ++)
str = str + itoa(i, k);
return str;
}
string s, t;
int nx[maxt];
int main() {
int n;
cin >> n;
cin >> t;
nx[0] = 0;
for (int i = 0; i < t.length() - 1; i ++) {
int j = nx[i];
while (j && t[i + 1] != t[j]) j = nx[j - 1];
nx[i + 1] = (t[i + 1] == t[j]) ? j + 1 : 0;
}
for (int k = 2; k <= 16; k ++) {
s = seq(n, k);
int j = 0;
bool matched = false;
for (int i = 0; i < s.length(); i ++ ) {
while (j && s[i] != t[j]) j = nx[j - 1];
j = (s[i] == t[j]) ? j + 1 : 0;
if (j == t.length()) {
matched = true;
break;
}
}
if (matched) {
cout << "yes\n";
return 0;
}
}
cout << "no\n";
return 0;
}
景区路线规划
思路
参考代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 105
#define eps 0.00000001
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Dor(i,r,l) for(int i=r;i>=l;i--)
int n,m,K;
int pt[maxn],h1[maxn],h2[maxn];
int son[maxn],Next[maxn*maxn/2],ed[maxn*maxn/2],wt[maxn*maxn/2],cnt;
double f[60*8+5][maxn];
double Doit(int *h){
double result=0;
For(t,0,K) For(now,1,n) f[t][now]=0;
For(now,1,n) f[pt[now]][now]=1.0/n;
For(t,0,K){
For(now,1,n) result+=f[t][now]*h[now];
For(now,1,n){
int num=0;
for(int i=son[now];i;i=Next[i])
if(K-t>=wt[i]+pt[ed[i]]) num++;
if(num==0) continue;
for(int i=son[now];i;i=Next[i])
if(K-t>=wt[i]+pt[ed[i]])
f[t+wt[i]+pt[ed[i]]][ed[i]] += f[t][now]/num;
}
}
return result;
}
int main(){
cin >> n >> m >> K;
For(i,1,n) cin >> pt[i] >> h1[i] >> h2[i];
For(i,1,m){
int x, y, t;
cin >> x >> y >> t;
Next[++cnt]=son[x]; son[x]=cnt; ed[cnt]=y; wt[cnt]=t;
Next[++cnt]=son[y]; son[y]=cnt; ed[cnt]=x; wt[cnt]=t;
}
printf("%.5lf %.5lf\n",Doit(h1),Doit(h2));
}
题目练习链接: https://www.nowcoder.com/test/5599304/summary
#美团#
