因为语文太差弃赛，第一个追及问题看不懂我就弃赛了。打进复赛确实挺难的，补一下题，锻炼下就行了。

身体训练

时间限制：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.42272.865 126.767 202.680 106.102 99.516 134.418 167.952 173.646 120.210 136.5712.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 
           
            #include 
            
             #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("%.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

输入例子:

310 220 125 130 1

输出例子:

Possible20.0000

这个题是混合，类似于求平均值之类的，可以分成三种情况啊。

1.T 大于所有 ti：由于要求温度最大，当然是把所有水都倒完。

2.T 小于等于所有 ti：因为倒水只会把水的温度往 T 靠拢，所以找一个最小的 ti，把其他所 有 tj 都倒水变成 ti。

3.存在 ti < T 且存在 tj > T：显然无解。

然后分情况讨论就好了，当时看了一眼这个题但是也没做

记录下这些元素的最大值最小值讨论下就可以了

 

#include
                
                 #define int64 long long#define rep(i,x,y) for(int i=(x);i<=(y);++i)#define N 120000using 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(){    scanf("%d",&n);    scanf("%d%d",&T,&C);    bool f1=0,f2=0;    rep(i,1,n){        scanf("%d%d",&t[i],&c[i]);        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)||T-minnT<0&&cc<(int64)C*(T-minnT))fail();    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;}
                 
                

合并回文子串

时间限制：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的价值。

输入例子:

2aabbaaaaabcaa

输出例子:

45

作者：张晴川 loj.ac

链接：

来源：牛客网

合并回文子串

• 考虑 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
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     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标准输入输出

题目类型：传统评测方式：文本比较

上传者： 

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

2

样例输出

35

数据范围与提示

n≤1e7

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

#include 
                     
                      using namespace std;const int N=1e7+1,MD=1e9+7;int n,fac[N],inv[N],F[N],ans;int po(int x,int y){    int t=1;    for(; y; y>>=1,x=1LL*x*x%MD)        if(y&1)t=1LL*t*x%MD;    return t;}int main(){    scanf("%d",&n);    fac[0]=1,fac[1]=1,F[0]=1,F[1]=2;    for(int i=2; i<=n; i++)    {        fac[i]=1LL*fac[i-1]*i%MD;        F[i]=(1LL*F[i-1]*(i+i)-1LL*(i-1)*(i-1)%MD*F[i-2])%MD;    }    inv[n]=po(fac[n],MD-2);    for (int i=n; i; i--)        inv[i-1]=1LL*inv[i]*i%MD;    for(int i=0; i<=n; i++)        ans=(ans+1LL*(i&1?-1:1)*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 0;}