"蔚来杯"2022牛客暑期多校训练营1
| A | B | C | D | E | F | G | H | I | J | K | |
| 赛时过题 | O | O | O | ||||||||
| 赛后补题 |
赛后感悟：
1、无论当前榜单如何，最好所有题目都要看，以免歪榜导致可做题没做！（C题歪榜导致没人做）
2、开题时最好要模拟一下样例，把样例搞清楚的同时可能发现一些优秀的性质！（J题的性质通过模拟样例是可以猜到的）
3、不要陷入思维死胡同，一旦自己的思路长时间想不通一定要多和队友交流！（I题自己的做法碰壁后没和队友充分交流，而是钻死胡同了）
赛时排名情况：
5题末尾：56名
4题末尾：304名
G Lexicographical Maximum
题目难度：Check-in（签到）
题目大意：给定 n，求出 1, 2, . . . , n 对应的数字字符串 中字典序最大的那个字符串
数据范围：1 ≤ n ≤ 101000000
题目解析：
显然，为了让字典序最大，能放9就放9，直到最后一位
如果n除了最后一位都是9，那么最后一位也填上
否则为了保证字符串<=n，那么就不能填最后一位(如n=621时输出99而非990）
赛后总结：很快就发现了签到题并一发AC，干得不错！
参考代码：
查看代码
#include
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=1e6+1000;
char s[N];int len;
int check()
{
For(i,1,len-1) if (s[i]!='9') return 0;
return 1;
}
int main()
{
scanf("%s",s+1);len=strlen(s+1);
For(i,1,len-1) putchar('9');
if (check()) putchar(s[len]);
return 0;
} A Villages: Landlines
题目难度：Easy
题目大意：
数轴上有恰好一个发电站与 n ? 1 个建筑物
在数轴上放置一些电力塔使得所有建筑物通过电力塔与发电站连通
能源站位于 xs，能与距离 rs 内的电力塔直接连通
第 i 个建筑物位于 xi，能与距离 ri 内的电力塔直接连通
可以消耗 |xA ? xB| 长度的电线连通位于 xA 与 xB 的电力塔
最小化消耗的电线长度。
数据范围：1≤n≤2×105，?109≤xs?≤109, 1≤rs?≤109
题目解析：阅读理解题。题面很长，做法很简单。
等价于有 n 个区间 [xs ? rs, xs + rs], [xi ? ri, xi + ri]
先合并所有有交集的区间，形成大区间（可以在子区间中交集处放任意多电力塔，让这些子区间通过电力塔形成大区间）
最后填补大区间之间的空隙即可（即在大区间的边界处放电力塔，相邻大区间边界的电力塔再连电线）
赛后总结：丁老师和宇彬很快就做出来了，一发AC，good job!
参考代码：
查看代码
#include
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=2e5+1000;
int n;std::pair p[N];
int main()
{
scanf("%d",&n);
For(i,1,n)
{
int x,r;scanf("%d%d",&x,&r);
p[i]=std::make_pair(x-r,x+r);
}std::sort(p+1,p+1+n);
int max=p[1].first;
long long ans=0;
For(i,1,n)
{
if (p[i].first>max) ans+=p[i].first-max,max=p[i].second;
else max=std::max(max,p[i].second);
}
printf("%lld\n",ans);
return 0;
} D Mocha and Railgun
题目难度：Easy
题目大意：
T组数据
给定一个圆心在原点、半径为r的圆和严格位于圆内的一点 P(x,y)
Mocha 会从点 P 向任意角度发射一个长度为 2d 的电磁炮
电磁炮底边的中点为点 P 且保证无论怎么转两端一直位于圆内
询问单次发射能摧毁的最大圆弧长
数据范围：
1 ≤ T ≤ 1000, ?109 ≤ x, y ≤ 109, 1 ≤ r, d ≤ 109
标准解析：
无论当前的电磁炮旋转角度如何，我们可以固定电磁炮的方向，将点 Q 绕原点旋转，从而使得电磁炮方向竖直向上（即 y 轴正方向）。
那么我们可以将题目转化成为电磁炮的方向总是竖直向上的，点 Q 绕原点旋转一周的过程中可以摧毁的最长墙壁长度。
并且题目保证了 base segment 总是位于圆内部的，那么我们设点 Q 到原点距离是 dis，点 Q 绕原点旋转一周就可以转化成点 Q 在以 (?dis, 0) 和 (dis, 0) 为端点的线段上移动。
显然摧毁的墙壁是一段劣弧，那么长度的大小关系就可以映射到弦长的大小关系。
设电磁炮摧毁墙壁的端点为 PL 和 PR，则对应弦长长度为√((yPL ? yPR )2 + (2d)2)，其中 d 是给定的，那么显然两点纵坐标之差的绝对值最大时弦长最长。
对交点坐标求导不难看出当Q位于线段端点时差的绝对值最大，返回原题面，也就是 base segment 位于直线 QO 上时摧毁墙壁最长。（其实通过直观感知也能看出来）
赛时经历：（题目难点：卡精度）
（1）首先无论P在哪，根据圆的对称性都可以转到原点O的正上方
然后直观上认为电子炮向正上/下方发射，摧毁的圆弧最短
那么就是说在电磁炮在转的时候摧毁的圆弧长会先变长再变短
采用三分，由于精度损失WA了一发
（2）后来发现大部分数据在三分的时候都会电子炮以90°为最优（即向正左/右发射）
为了必变精度损失导致三分后的最终l,r错误，再交一发只取90°的做法，由于精度损失又WA了
ldouble c=acos(dot(px1,py1,px2,py2)/(dis(px1,py1)*dis(px2,py2)))（3）发现在算圆心角的时候如果采用点积直接计算，计算时涉及开根号、除法、反三角，误差较大
不如直接计算该线段相对于某个线段的圆心角，再一减就出来了。计算只涉及除法、反三角，减少误差。AC！
ldouble c=ABS(asin(py2/r)-asin(py1/r));参考代码：
查看代码
#include
#include
#include
#define ldouble long double
#define ABS(x) ((x)<0?-(x):(x))
const ldouble pi=acos(-1.0);
ldouble dis(ldouble x,ldouble y)
{
return sqrt(x*x+y*y);
}
ldouble getlen(ldouble x1,ldouble y1,ldouble b,ldouble r)
{
ldouble A=1;
ldouble B=2*x1*cos(b)+2*y1*sin(b);
ldouble C=x1*x1+y1*y1-r*r;
return (-B+sqrt(B*B-4*A*C))/(2*A);
}
ldouble dot(ldouble x1,ldouble y1,ldouble x2,ldouble y2)
{
return x1*x2+y1*y2;
}
ldouble calc(ldouble xq,ldouble yq,ldouble d,ldouble a,ldouble r)
{
ldouble x1=xq+d*cos(a);
ldouble y1=yq+d*sin(a);
ldouble x2=xq-d*cos(a);
ldouble y2=yq-d*sin(a);
ldouble b=a+pi/2;
ldouble len1=getlen(x1,y1,b,r);
ldouble len2=getlen(x2,y2,b,r);
ldouble px1=x1+len1*cos(b);
ldouble py1=y1+len1*sin(b);
ldouble px2=x2+len2*cos(b);
ldouble py2=y2+len2*sin(b);
// ldouble c=acos(dot(px1,py1,px2,py2)/(dis(px1,py1)*dis(px2,py2)));
ldouble c=ABS(asin(py2/r)-asin(py1/r));
printf("%.6Lf %.6Lf\n",a/pi*180,c*r);
return c*r;
}
ldouble calc2(ldouble xq,ldouble yq,ldouble d,ldouble a,ldouble r)
{
ldouble x1=xq;
ldouble y1=yq+d;
ldouble x2=xq;
ldouble y2=yq-d;
ldouble py1=y1;
ldouble px1=sqrt(r*r-py1*py1);
ldouble py2=y2;
ldouble px2=sqrt(r*r-py2*py2);
// ldouble b=a+pi/2;
// ldouble len1=getlen(x1,y1,b,r);
// ldouble len2=getlen(x2,y2,b,r);
// ldouble px1=x1+len1*cos(b);
// ldouble py1=y1+len1*sin(b);
// ldouble px2=x2+len2*cos(b);
// ldouble py2=y2+len2*sin(b);
ldouble c=ABS(asin(py2/r)-asin(py1/r));
// ldouble c=acos(dot(px1,py1,px2,py2)/(dis(px1,py1)*dis(px2,py2)));
return c*r;
}
int main()
{
int T;scanf("%d",&T);
while (T--)
{
ldouble sr,xq,yq,d;scanf("%Lf%Lf%Lf%Lf",&sr,&xq,&yq,&d);
yq=dis(xq,yq);xq=0;
// ldouble l=0,r=pi;
// while (r-l>1e-10)
// {
// ldouble lmid=l+(r-l)/3;
// ldouble rmid=r-(r-l)/3;
// if (calc(xq,yq,d,lmid,sr) I Chiitoitsu
题目难度：mediun-easy
题目大意：
一共有34种麻将牌，每种麻将牌一共有4张。
初始手牌有 13 张麻将牌，其中相同种类牌至多出现 2 张
每轮可以从牌堆摸牌：
①若达成七对子则自摸胡牌
②若不然则选择手牌中某张牌并丢弃之
给定初始手牌，求最优策略下达成七对子的期望轮数
多组数据，数据组数不超过 105 组
题目解析：题面较长，但做法不难。
设抽到了某一个手牌：
①如果这个手牌能和手里的某个单牌配对，就丢掉当前手牌中的某另外一个未配对单牌
②如果这个手牌不能和手里某个单牌配对，那就把这个新收到的单牌丢了
（因为一直保持老单牌，对于老单牌来说牌堆里一直有3个牌能和它配对）
（如果丢了老单牌，牌堆里最多有3个牌能和新单牌配对，如果一直随便乱丢牌堆里甚至都不到3个能和它配对）
通过DP求期望，令dp[i][j]表示当前牌堆里有i张牌，自己还有j个单牌（如果采用上述策略，牌堆里剩余的i张牌一定有j*3张的种类和当前手牌配对，其他都是要丢的，故无需记录）
需要注意的是如果新抽到的牌和当前手牌配对了，之后再抽到该种类牌就要丢弃了，即配对后把该种类牌当做i-j*3的那部分处理
dp[i][j]=1+(j*3/i)*dp[i-1][j-2]+((i-j*3)/i)*dp[i-1][j] (i>j*3)
dp[i][j]=1+dp[i-1][j-2] （i==j*3）由于牌数为奇数，某种类牌<=2，故单牌数一定也为奇数，故边界情况一定是只剩一张单牌，最后再抽一张牌和它配对（不可能开局即胜利）
dp[i][1]=1+(j*3/i)*0+((i-j*3)/i)*dp[i-1][1] (i>3)
dp[i][1]=1(i==3)赛后总结：
赛时一直往期望可加性去钻牛角尖。。。不要陷入思维死胡同，一旦自己的思路长时间想不通一定要多和队友交流！
1、为什么这个期望DP是对的呢？
每一个dp[i][j]其实相当于一个随机变量Xi,j
dp[i][j]=1+(j*3/i)*dp[i-1][j-2]+((i-j*3)/i)*dp[i-1][j] 实际上是数学期望的定义式，只不过dp[i-1][j-2]和dp[i-1][j]是待求项
2、同种类的牌会不会发生重复等问题？拿牌的顺序对答案是否有影响？
同种类的牌不会发生重复问题。如果当前该种类的牌可与当前牌配对，那就是(j*3/i)*dp[i-1][j-2];否则（已经配对成功/手牌中无该类别单牌）就是(i-j*3)/i)*dp[i-1][j-2]。
拿牌的顺序已经在DP过程中考虑了，实际上DP就是对拿牌过程的模拟。
比如当前有手牌1m：
先抽到1m再抽到1n：dp[i][j]->dp[i-1][j-2]->dp[i-2][j-2]
先抽到1n再抽到1m：dp[i][j]->dp[i-1][j]->dp[i-2][j-2]
3、到底什么是期望可加性？一些概率论的基本概念？
随机变量是个映射，将样本空间中的样本点映射到实数上。X=X(w)表示样本点w被映射为实数X上了。比如{X<=x}={w|X(w)<=x}就是是一个包含若干样本点的事件。
例题：给出一棵含n个白点的有根树,每次随机选择一个还没有被染黑的节点,将这个节点和这个节点子树中的所有点染黑。问期望操作多少次后所有点都被染黑？
做法：设总操作次数为随机变量X，某个点的操作次数为随机变量Yi，则X=sum(Yi)，则E(X)=E(sum(Yi))=sum(E(Yi))。（第二个等号为期望可加性）
又Yi=1，当前点到根节点这depth[i]个点中，当前点被第一个染黑(p=1/depth[i])
=0，当前点到根节点这depth[i]个点中，当前点不是第一个被染黑(p=1-1/depth[i])
故E(Yi)=depth[i]
注意到期望可加性满足的条件是随机变量X可表示为若干子随机变量Y之和，即子随机变量X和Y经历的操作过程是完全一致的，只是计算的对象不一样。
这道题的阉割版：设桶里有n个白球和m个黑球，每次随机从桶里抽出一个球，直到抽出某个黑球为止。要求取球次数的期望。
设某个白球的取球次数为X，则
X=1，该球在第一个黑球之前被取到，p=
0，该球在第一个黑球之后被取到
参考代码：
查看代码
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=34*13+500;
const long long mod=1e9+7;
long long dp[N][N];
char s[13*2+100];
long long power(long long x,long long y)
{
long long ans=1;
while (y)
{
if (y&1) ans=ans*x%mod;
y>>=1;x=x*x%mod;
}
return ans;
}
int main()
{
For(j,1,1) For(i,3*j,34*4-13)
{
if (i>3*j) dp[i][j]=(1+dp[i-1][j]*(i-j*3)%mod*power(i,mod-2)%mod)%mod;
else dp[i][j]=1;//dp[3][1]=1,抽一张牌后必胜
}
for(int j=3;j<=13;j++) For(i,j*3,34*4-13)//单牌一定是奇数，且最多13张即一开始全是单牌
{
if (i>3*j) dp[i][j]=(1+dp[i-1][j]*(i-j*3)%mod*power(i,mod-2)%mod+dp[i-1][j-2]*(j*3)%mod*power(i,mod-2)%mod)%mod;
else dp[i][j]=(1+dp[i-1][j-2])%mod;//必中
}
int TAT;scanf("%d",&TAT);
For(T,1,TAT)
{
scanf("%s",s+1);
int temp=0;
For(i,1,13)
{
int flag=0;
For(j,1,i-1) if (s[(j-1)*2+1]==s[(i-1)*2+1]&&s[j*2]==s[i*2])
{
flag=1;break;
}
if (!flag) temp++;
else temp--;
}
printf("Case #%d: %lld\n",T,dp[34*4-13][temp]);
}
return 0;
}