退役划水(24)/2022 MetaCamp程序设计大赛线上初赛2
2022/8/12 1:29:10
本文主要是介绍退役划水(24)/2022 MetaCamp程序设计大赛线上初赛2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
引流封面图（？）
差点忘了。写到后边才想起来，于是回来补上
上一次的密码似乎并没有人去破译，于是就把解答附上吧
（其实不算是密码学？）
（我连负号都没删，一堆负数给人的感觉不就是…）
（为什么删了逗号？因为我把字符串输入再输出的时候，输出格式忘加逗号和空格了就直接连起来了，还懒得改了）
烦
昨晚打Metabit的比赛，打了第14名
获得了参加线下赛的资格
线下赛可以去北京玩，包吃住，交通报销
打比赛进前14有奖金（虽然跟我没啥关系）。但主要是有好玩的
而且我也想捞一捞各个企业的HR微信，指不定以后有点啥用
所以本来21-23号没什么事，打算参与的（虽然不可能拿奖）
结果科三挂了。从明天开始算起，10天后才能再次预约考试
时间完美的撞上了
结果好端端的机会就没了
从这里开始的部分是0：00之后写的，所以“今天”“明天”等的定义可能与上文不同
科三考试要排队领号。于是早上8点去了，倒数第三（165号）
怎么这也能这么卷啊
除了VIP能保前三四十号，
剩下的人什么凌晨三四点去取号就六十多号了
六点多去就一百多了
这都啥啊
于是不出预料的，考试就等到了傍晚
然后在下班点各种社会车辆开始乱窜
打死也想不到居然是在掉头挂的。
掉头的时候对面来了仨社会车辆嗖嗖得就过了
我刚想踩刹车停下等他们都过去
结果安全员估计是看到下半晚高峰的社会车辆自己也着急下班了，比我先踩的
挂了
就很无语
当初为啥报的C1，这不活活受罪
一起学车的4个人无一例外的都挂科了
然而C1的科二都过了，科三不过感觉亏得慌
（为啥都说科二难啊？我看今天科三通过率也就百分之二三十，科二也没这么低啊）
DC一如既往的倒霉
练车练到一半，考试规则（车型）改了
于是练车4天里，第一天教灯光
一换车又乱了套了
手动挡科三我是真不觉得简单，练4天就能过也太强了
心情很烂
本来之前终于搞定了博客园传视频的问题了
想往博客上再传一点打歌
今天科三裂开了，直接反向紫菜
最开始是打算录一个唱打Testify挂博客遗臭万年的（当然只能打PRS，剩下的打不动）
结果打歌的时候经常跟不上英文单词的速度，说得不够流利
本来就唱歌不好听，更离谱的是一晚上了也没全连
如果有人有兴趣的话，今天我可以再试试（什么不良癖好）
中午也是，打pgr的nhelv打了俩小时，一直失误
3good - 2good1miss - 2g2m - 1g2m - 6g - 6g - 5g - 1g1m
绷不住了，不打了
是干啥啥不行的一天
这么说就不对了，本来就是干啥啥不行一人
/kk
前天打metabit的比赛，前后有一些小事
skyh打了第一轮，但是寄了，于是也要打第二轮
（每轮前25名能获得资格。要去掉非在读大学生。第一轮获得名额的人不占第二轮名额）
我也打算打第二轮。但当时因为疫情原因在犹豫要不要去
skyh当天有事，说我不去就帮他打，但我寻思着没啥事就去，于是就自己打自己的（skyh似乎另找了别人）
然后开考之前cbx，哦不，xbc跑出来
然后就开打了
我5分钟A题，7分钟B题。这时以17的罚时排在第4
然后就变成菜狗了，C题不会
看排行榜，没人过
又想了想C题，不会
看排行榜，没人过
开始看并思考D题，不会
看排行榜，没人过
开始看并思考E题，不会
看排行榜，没人过
这时候cbx，啊，xbc冒出来
这时间点也太奇怪了，第24分钟问A题
后来发现他是先WA了一发A然后去搞B，B在24分钟过的
然后A在25分钟过的
我觉得C题没什么希望。于是开始认真地思考D题
想了半天终于有思路了，于是开写
开写之前瞥了一眼榜，C题突然过了一万个人，D题有零星一两个
然后在49分钟的时候把D过掉了。中间磕磕绊绊的
调了好久。最后是因为做浮点数除法的时候俩参数都是int给我取整了
暗骂自己是沙白
这时候过了D题但我的排名还是已经掉到两位数了
然后开始冥思苦想C，但是一直差点思路
然后我就开始写记搜
在比赛过了大半的时候我调出来了暴力过了样例
？最开始说好的颓题解上升的有点快
（主要是因为打比赛的网站和我们学校程设相关课程网站一直。有查重，怕被ban）
（我们学校用，所以我们是实名。在一堆乱七八糟的现起ID里看起来就像傻憨憨）
记一下这句话，后面要考（
经典/st甩头。看着这一堆磨磨唧唧的变量就知道为啥他想要代码了
然后突然他茅塞顿开
回收封面（
后来我把代码局部重构了，把记搜改成了滚动数组dp
（什么垃圾网站内存就给128M…滚动我还调了半天）
然后终于过了。开始思考E
当时我正在认真思考问题，没有意识到事情的严重性
这就要上AC代码了
然而主要问题是，我在VSCode上直接把C题的代码覆盖了去写E了
我又懒得去翻网站，我心想就一个记忆化改滚动数组自己写也没啥问题
也不知道他那里到底发生了啥，但看时间似乎还差不多，我就先跑去E了
然后就开始使劲搞E题。有了个大体思路
交上去尝试了一下，爆了一发
在离比赛结束还有不到十分钟的时候有了个百分百对的思路
但是来不及写了，于是摆烂了
闲来无事翻翻排行榜，自己在14名
xbc掉的有点多，而且有个离谱的事情
C题他狂暴爆10发没整出来。我也不知道到底是啥问题
反正xbc大神赛后就不鸟我了，555
skyh大神，或者这场比赛里叫做e大神，找的代打似乎不够大神，打到了34名
这只是初步去重。由于非在校本科生的存在，第一轮的第29名也收到邀请了
所以去重31还是很有戏的
而且应该像我这样不去的人也有，那往前挤挤就进去了
（不会只有我是沙白吧）
反正他们就在北京上学，离北京近
秦皇岛人在杭州上学，到哪都是卑微
怎么省选寄了一次高考寄了一次后续破事没完没了的啊
今天下午（考科三之前）metabit的人给我打电话，问我的意愿，我说应该想去
他说让我填问卷。截至时间是8/10 23:59
嗯，然后考完了科三，在截止日期的时间点，我在写这篇博客
事实上还想报的，但是时间一耽误的话，如果下次科三还没过，那么就要等寒假了
我现在对我的水平可是充分不自信
今天都不行。那这10天驾校不组织练车，之后再考估计也很可能不行
更甭提再多等一个学期寒假再考了。忘干净了都
不如在家背背科四的东西。希望这个假期能把本搞下来…唉，真费劲
哈哈，就假装是我忘了回复问卷吧
北京是一个会让我留下遗憾的地方，过去是，现在是，将来也会是
所以，现在，前天的意义，就只是单纯的打了一场没有任何用的个人赛
为了留下点什么，来写个题解吧
无聊的A题
无聊的B题
没什么意思的C题
无聊的D题
一般般的E题
题解区：
A.按下注排序，拿个变量维护当前排名最高的是谁，模拟，没了
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,p[100005],w[100005];
4 long long ans[100005];
5 struct pe{
6 int p,w,id;
7 friend bool operator<(pe x,pe y){return x.w>y.w;}
8 }P[100005];
9 int main(){
10 cin>>n;
11 for(int i=1;i<=n;++i) scanf("%d",&P[i].p),P[i].id=i;
12 for(int i=1;i<=n;++i) scanf("%d",&P[i].w);
13 sort(P+1,P+1+n);
14 int mx=1;
15 for(int i=1;i<=n;++i){
16 if(P[i].p<P[mx].p)mx=i;
17 ans[P[mx].id]+=i*1ll*(P[i].w-P[i+1].w);
18 }
19 for(int i=1;i<=n;++i) printf("%lld ",ans[i]);
20 }
View Code
B 猜的结论，不会证，但感觉很对。应该是先造出一个全能的，然后让这一个全能的扩展到全部
造出一个全能的需要的步数是 最小的出现所有技能的子区间长度-1， 扩展到全部是n-1
求这个子区间就维护一个set里存着每种能力上次出现的下标，每次用当前枚举的右端点减去set里的最小值就完事了
不过这个结论有谁能证吗？
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m,l[300005],ans;
4 multiset<int>s;
5 int main(){
6 cin>>n>>m;
7 ans=n;
8 for(int i=1;i<=m;++i) s.insert(l[i]=-n);
9 for(int i=1,x;i<=n;++i){
10 scanf("%d",&x);
11 s.erase(s.find(l[x]));
12 s.insert(l[x]=i);
13 ans=min(ans,i-*s.begin());
14 }
15 cout<<ans+n-1;
16 }
View Code
C 倒着dp。dp[d][T][0/1][0/1]表示第d天还剩T块钱，且当前A B分别有没有付过打车钱，这种情况下最大期望满意度
转移方式可以参考我给cbx的暴力代码。把记搜改成滚动数组优化就行了
这个题为什么想了那么久啊？为什么啊？最开始甚至没想到后两维状态，这也太菜了吧
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,T,a[2333],b[2333],c[2333],d[2333],e[2333],p[2333],nw,nx;
4 long double ans;
5 double dp[2][10002][4];
6 inline long double dfs(int T,int s){
7 //cerr<<nx<<'!'<<' ' <<s<<endl;
8 if(T<0) return -1e18;
9 return dp[nx][T][s];
10 }
11 int main(){
12 cin>>n>>T;
13 for(int i=1;i<=n;++i) cin>>a[i]>>b[i]>>c[i]>>d[i]>>e[i]>>p[i];
14 for(int i=n;i;--i){
15 nw=i&1; nx=nw^1; int t=i;
16 memset(dp[nw],0,sizeof dp[nw]);
17 cerr<<i<<endl;
18 for(int j=0;j<=T;++j) for(int s=0;s<4;++s)
19 //cerr<<i<<' '<<j<<' '<<s<<' '<<endl,
20 dp[nw][j][s]=max(
21 a[t]+dfs(j-b[t],s|1)*p[t]/100+dfs(j-b[t],s|2)*(100-p[t])/100,
22 c[t]+(s==3?dfs(j-d[t]-e[t],0):dfs(j-d[t],s|1)*p[t]/100+dfs(j-d[t],s|2)*(100-p[t])/100)
23 );
24 }
25 printf("%.9lf",max(dp[1][T][0],-1.));
26 }
View Code
D 普通的期望题。利用期望的线性性，对于每一对同色的，消除它们的期望得分是(它们的距离+1)/2。
每一对乘上它们这对存在于最终方案的概率即可（概率是$\frac{1}{k-1}$）
因为随机选择，所以介于这一对之间的每个球都有一半的概率在此前被消掉，一半的概率没消掉。
那么只要把距离改为 右侧的下标 - 左侧的下标，然后对每一个球分别统计他作为左侧和右侧的次数，就做完了
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m;long double ans;
4 vector<int>v[100005];
5 int main(){
6 cin>>n>>m;
7 for(int i=1,x;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
8 for(int i=1;i<=m;++i){
9 int s=v[i].size();
10 long double p=1.L/(s-1);
11 for(int j=0;j<s;++j) ans+=p*(1-s+j+j)*v[i][j];//,cout<<1-s+j+j<<' '<<v[i][j]<<endl;
12 //cout<<ans<<endl;
13 }
14 printf("%.9Lf",(n/2+ans)/2);
15 }
View Code
E 考虑你是怎么求所有子段的最大子段和的。简单dp，srr[l][r]=max(srr[l][r-1],srr[l+1][r],sum[l...r])
也就是如果说srr被sum更新了，那么sum就等于srr，否则sum小于等于srr
sum拆成前缀和形式变成$S_r-S_{l-1}$，那么就是经典的差分约束，有若干个$S_a-S_b \leq srr$或者 $S_a-S_b = srr$
小于等于就建单向边，否则双向。最后输出一组方案就完了。
代码并没有时间写，所以或许正确性可能也有问题，欢迎指正。
我好菜啊我好菜啊我好菜啊
学车和竞赛样样不精通
还是摆烂睡大觉吧
（怎么感觉总是这么结尾的，表达不出今天的坏心情）
算了，表达出来也不见得是什么好事
我都说不藏了你还看这个干啥
这篇关于退役划水(24)/2022 MetaCamp程序设计大赛线上初赛2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-04-16软路由代理问题， tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本，并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本，并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口，如果关闭，则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量，由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享
- 2024-04-14shell 正则判断字符串内是否含有th-icode9专业技术文章分享
