CodeM美团点评编程大赛初赛A轮

时间：2023-03-09 14:44:35
CodeM美团点评编程大赛初赛A轮
因为语文太差弃赛，第一个追及问题看不懂我就弃赛了。打进复赛确实挺难的，补一下题，锻炼下就行了。
身体训练

时间限制：1秒

空间限制：32768K

美团外卖的配送员用变速跑的方式进行身体训练。
他们训练的方式是：n个人排成一列跑步，前后两人之间相隔 u 米，每个人正常速度均为 v 米/秒。
当某个配送员排在最后的时候，他需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v 米/秒。每个人最初的最高速度为c[i] 米/秒，每轮衰减d[i] 米/秒，也就是说，如果i是第j个跑的，那么他的速度就是c[i]-(j-1)*d[i] 米/秒。
n个人初始以随机的顺序排列，每种顺序的概率完全相等，跑完一轮（每个人都追到排头一次，序列恢复原样）的期望需要的时间是多少？
输入描述:
第一行整数n（<=1000）, 实数v(<=100) , 实数u(<=10)

第二行n个实数每个人的速度c[i](<=50000)

第三行n个实数值每个人衰减量d[i](<=10)

输入数据保证每个人的速度不会衰减到<=v
输出描述:
答案保留3位小数。
输入例子:
10 37.618 0.422

72.865 126.767 202.680 106.102 99.516 134.418 167.952 173.646 120.210 136.571

2.941 3.664 7.363 4.161 0.246 8.046 5.521 7.473 7.178 5.649
输出例子:
0.815
这个追及问题的题意不太友好啊，但是看着他们一个一个过了还是有点后悔弃赛太早了。其实题目的意思就是有个人要从最后到前面的u米追及问题，速度差是c[i]-(j-1)*d[i]-v，需要追及的路程是nu。然后求下所有队列的期望
然后枚举下公式。使用rep压行感觉好爽啊，虽然不好看了，但是代码量减少不少
#include <stdio.h>

#include <bits/stdc++.h>

#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 = ;

int n;

double v,u,c[N],d[N];

int main(){

    scanf("%d%lf%lf",&n,&v,&u);

    rep(i,,n) scanf("%lf",c+i);

    rep(i,,n) scanf("%lf",d+i);

    double ans = ;

    rep(i,,n) rep(j,,n) ans+=1.0/(c[i]-(j-)*d[i]-v);

    ans*=u;

    printf("%.3f\n",ans);

}
倒水

时间限制：1秒

空间限制：32768K

有一个大水缸，里面水的温度为T单位，体积为C升。另有n杯水（假设每个杯子的容量是无限的），每杯水的温度为t[i]单位，体积为c[i]升。
现在要把大水缸的水倒入n杯水中，使得n杯水的温度相同，请问这可能吗？并求出可行的最高温度，保留4位小数。
注意：一杯温度为t1单位、体积为c1升的水与另一杯温度为t2单位、体积为c2升的水混合后，温度变为(t1*c1+t2*c2)/(c1+c2)，体积变为c1+c2。
输入描述:
第一行一个整数n, 1 ≤ n ≤ 10^5

第二行两个整数T，C,其中0 ≤ T ≤ 10^4, 0 ≤ C ≤ 10^9

接下来n行每行两个整数t[i]，c[i]

0 ≤ t[i], c[i] ≤ 10^4
输出描述:
如果非法，输出“Impossible”（不带引号)否则第一行输出“Possible"（不带引号），第二行输出一个保留4位小数的实数表示答案。

样例解释：往第二杯水中倒0.5升水

往第三杯水中到1升水

三杯水的温度都变成了20
输入例子:
3

10 2

20 1

25 1

30 1
输出例子:
Possible

20.0000
这个题是混合，类似于求平均值之类的，可以分成三种情况啊。
1.T 大于所有 ti：由于要求温度最大，当然是把所有水都倒完。
2.T 小于等于所有 ti：因为倒水只会把水的温度往 T 靠拢，所以找一个最小的 ti，把其他所 有 tj 都倒水变成 ti。
3.存在 ti < T 且存在 tj > T：显然无解。
然后分情况讨论就好了，当时看了一眼这个题但是也没做
记录下这些元素的最大值最小值讨论下就可以了
#include<bits/stdc++.h>

#define int64 long long

#define rep(i,x,y) for(int i=(x);i<=(y);++i)

#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();

}

void fail(){

    printf("Impossible\n");

    exit();

}

int main(){

    scanf("%d",&n);

    scanf("%d%d",&T,&C);

    bool f1=,f2=;

    rep(i,,n){

        scanf("%d%d",&t[i],&c[i]);

        if(t[i]<T)f1=;

        if(t[i]>T)f2=;

    }

    if(f1 && f2)fail();

    if(!f1 && !f2)P(T);

    if(f1){

        T*=-;

        rep(i,,n)t[i]*=-;

    }

    int minnT=1e9;

    int64 cc=;

    rep(i,,n)minnT=min(minnT,t[i]);

    if(minnT==T)fail();

    rep(i,,n)cc+=(minnT*c[i]-c[i]*t[i]);

    if(T-minnT>&&cc>(int64)C*(T-minnT)||T-minnT<&&cc<(int64)C*(T-minnT))fail();

    if(f1){

        double f1=,f2=;

        f1=(double)T*C;

        f2=C;

        rep(i,,n)f1+=t[i]*c[i],f2+=c[i];

        P(-f1/f2);

    }else P(minnT*(f1?-:));

    return ;

}
合并回文子串

时间限制：2秒

空间限制：262144K

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
输入描述:
第一行一个整数T(T ≤ 50)。

接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。
输出描述:
对于每组数据输出一行一个整数表示价值最大的C的价值。
输入例子:
2

aa

bb

a

aaaabcaa
输出例子:
4

5

作者：张晴川 loj.ac
链接：https://www.nowcoder.com/discuss/28582
来源：牛客网

合并回文子串

  • 考虑 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 共有四种转移:

CodeM美团点评编程大赛初赛A轮

  • 边界情况：
    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;

}

二分图染色

内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： zcysky

题目描述

给定一个完全二分图，图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数，并对109+710^{9}+710​9​​+7取模。

输入格式

二分图单边的顶点数目 nnn。

输出格式

输出一个整数，即所求的答案。

样例

样例输入

2

样例输出

35

数据范围与提示

n≤1e7

CodeM美团点评编程大赛初赛A轮

按照题解做就好了，这个题本来我还真的找不到这个组合数

#include <bits/stdc++.h>

using namespace std;

const int N=1e7+,MD=1e9+;

int n,fac[N],inv[N],F[N],ans;

int po(int x,int y)

{

    int t=;

    for(; y; y>>=,x=1LL*x*x%MD)

        if(y&)t=1LL*t*x%MD;

    return t;

}

int main()

{

    scanf("%d",&n);

    fac[]=,fac[]=,F[]=,F[]=;

    for(int i=; i<=n; i++)

    {

        fac[i]=1LL*fac[i-]*i%MD;

        F[i]=(1LL*F[i-]*(i+i)-1LL*(i-)*(i-)%MD*F[i-])%MD;

    }

    inv[n]=po(fac[n],MD-);

    for (int i=n; i; i--)

        inv[i-]=1LL*inv[i]*i%MD;

    for(int i=; i<=n; i++)

        ans=(ans+1LL*(i&?-:)*fac[n]*fac[n]%MD*inv[i]%MD*inv[n-i]%MD*inv[n-i]%MD*F[n-i]%MD*F[n-i])%MD;

    printf("%d\n",(ans+MD)%MD);

    return ;

}

相关文章