2020美团杯

2020年“美团杯”程序设计挑战赛

第一次正经的acm赛,和真正acm选手噶、噶的队友jiedai组队的,队名是”那咋办嘛“

开场看到E题面有计数就先看,冷静了10min就会了,然后噶过了A

然后看了看B ,剩下就一直在自闭,一会做G,一会看I,写了些35(B、I),但基本是碌碌无为,最终战绩是rk57(rose、xgc、lhf的cf红名rk54,而我队平均分2100)

总的来说好像得奖区分题都是新题型

UPD:中奖了可还行

JLS的视频题解

OI好题:K(114514)、D(版本答案)


当时看过的题:

B 图片解密

请先思考后再展开

small的文件巨大,“大局观”直觉是缩小,浮点数只有01所以变成01,得到JZ4WC3TPIFYGK

large看到边界一列86400即一天天数,结合提示搜索,然后我并不会画钟,上网找了半天资料并不会

最后还是jiedai救场,然后他考虑的是相近的数字变成同一种颜色(甚至不转时间),得到LZYYJFQHJZJT

赛后看别人画的钟,才明白确实挺有道理的,就是你看得清一个东西,大概率是他背景比较清晰,所以估计会比较接近,是挺妙的一种替代方案(虽然我估计他是直觉,但我当时可能被86400冲昏了头脑)

UPD:听讲题,这个base32好像就是针对肉眼识别的

D 版本答案

请先思考后再展开

pty性质非常好:首先每方一定最多一个无圣盾,而且特判只有一只的情况后,在每轮进攻前防守方没圣盾那个一定是上次刚进攻完的(换句话说对面下次进攻的现在一定有圣盾,身为老炉石玩家,这些可以直接直觉

如果我们是防守方,如果存在一个无圣盾,经过本轮后一定变所以具体哪里不重要;

如果我们是进攻方,如果存在一个无圣盾,只要不是要进攻那个,经过本轮后一定补上了,所以具体哪里不重要;

因此进攻方始终只有「进攻的有圣盾1」、「进攻的无圣盾0」两种情况,防守方始终只有「都有圣盾1」、「一个无圣盾0」两种情况(分别记为A、B)

其实不需要列表格的,但担心有人看不懂,就写一下吧:
$$
\begin{aligned}
设f(i,j,0/1,0/1)&表示准备进攻,进攻方i个,防守方j个,然后是进攻方和防守方各自状态
\\
(i,j,11):\frac{1}{j}打下个进攻 &\to (j,i,00), \frac{j-1}{j} 打其他 \to (j,i,10)
\\
(i,j,01):\frac{1}{j}打下个进攻 &\to (j,i-1,01), \frac{j-1}{j} 打其他 \to (j,i-1,11)
\\
(i,j,10):\frac{1}{j}打无圣盾 &\to (j-1,i,10),\frac{1}{j}打下个进攻 \to (j,i,00), \frac{j-2}{j} 打其他 \to (j,i,10)
\\
(i,j,00):\frac{1}{j}打无圣盾 &\to (j-1,i-1,11),\frac{1}{j}打下个进攻 \to (j,i-1,01), \frac{j-2}{j} 打其他 \to (j,i-1,11)
\end{aligned}
$$
特判A=1且B=0,对于$i \ne j$,此时$(i,j)与(j,i)$相互转移,此时就是解个二元一次方程;否则是个自环

剩下的,将i+j看做一层,则层数单调,同层的除去自环后,二进制状态一定变小,所以是个DAG,可以直接dp转移,$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
ll dp[N][N][2][2];//00->攻击无盾,防守存在无盾
ll h(int i,int j){return ((dp[j-1][i][1][0]+dp[j][i][0][0])*Inv[j]+1)%MOD;}
void main()
{
int n=qread(),m=qread();MOD=qread();if(n<m) swap(n,m);PRE();
fo(sum,2,n+m) fo(A,0,1) fo(B,0,1) fo(i,1,sum-1)
{
int j=sum-i;if(i>n or j>n) continue;
if(i==1){ dp[i][j][A][B]=(A==0 or (j==1 and B==0)?1:2);continue; }
if(j==1){ dp[i][j][A][B]=(B==0?1:2);continue; }
if(B==1) dp[i][j][A][1]=(1+Inv[j]*dp[j][i-(A^1)][0][A^1]+(j-1)*Inv[j]%MOD*dp[j][i-(A^1)][1][A^1])%MOD;
else
{
ll jj=(j-2)*Inv[j]%MOD;
if(A==0) dp[i][j][0][0]=(1+Inv[j]*dp[j-1][i-1][1][1]+Inv[j]*dp[j][i-1][0][1]+jj*dp[j][i-1][1][1])%MOD;
else//下面都是 10
{
if(i==j) dp[i][j][1][0]=Inv[2]*(h(i,j))%MOD*j%MOD;
else if(i>j)
{
dp[i][j][1][0]=(h(i,j)+jj*dp[j][i][1][0])%MOD;
assert( dp[j][i][1][0]==(h(j,i)+(i-2)*Inv[i]%MOD*dp[i][j][1][0])%MOD );
}
else
{
//dp[i][j][1][0]=(h(i,j)+h(j,i)*jj+jj+1)%MOD*invm( mm(1+MOD-(i-2)*Inv[i]%MOD*jj%MOD) )%MOD;
dp[i][j][1][0]=(h(i,j)+h(j,i)*jj)%MOD*(i*j)%MOD*Inv[i*2+j*2-4]%MOD;
}
}
}
}write(dp[n][m][1][1]);
}

E 半前缀计数

请思考后点击展开

考虑怎么判断一个字符串是否是半前缀,那就是优先从最前面开始走,得到最长前缀,发现走不动了了判断后面是否存在该子串。

因此想到每个字符串在其匹配到的最长前缀那里唯一计数,而$[1,i]+[j,k]$是计数点的充要条件明显是$s_{i+1} \ne s_j$。

枚举前缀,那么我们需要的其实就是后面部分中,第一个字符不等于该前缀的下一个字符,的本质不同字符串个数,sam即可(然而因为写法问题被卡了半天常数),code

G 平行四边形

请先思考后再展开

结论是$P_i=g^{i-1} \bmod (n+1)$

证明倒不太难,已知$a \ge b,c \ge d,a-b=c-d,b \ne d,g^a-g^b=g^c-g^d$

$g^b(g^{a-b}-1)=g^d(g^{c-d}-1)$,得到矛盾

I 未来程序·改二

请先思考后再展开

small一开始没注意到1ll以为是自然溢出套998244353,觉得不可做,去医院做个眼睛手术后才发现不是,那么将每个函数的效果,表示为,传入x,传出ax+b

1
2
3
4
typedef unsigned long long ull;
pll F[N];pll operator * (pll a,pll b){ return { a.FR*b.FR%MOD,(a.SE*b.FR+b.SE)%MOD }; }
scanf("void f%d(){f%d();f%d();}\n",&z,&a,&b);F[i]=F[a]*F[b];
write(F[3000].SE);//466909359

large首先要注意到static,然后注意到看似随机其实只有位运算。那么用列向量存x和ans,在模2意义下做矩乘就好了

M 最长公共子序列

请先思考后再展开

签到,stable_sort即可(直接用sort会在较小的地方用插入排序),交换次数是nlogn的。然而我当时居然写了个二分……code


赛时完全没看过,现在补了的题目:

F 程序解密

请先思考后再展开

统计学,先跑一下单个字符稳一手,赌一手出现较多且的后面一个字符相同的三元组是int,一下破三个字符就大改变了,头文件再搞完,就没了(或者先得到换行符得到结构,然后得到大括号,然后是int main)

large不知道怎么说,看jls视频吧

K 114514

请先思考后再展开

很厉害的一道贪心题

1、2、3的结构中,2次是比较平衡的,所以从出现两次的4入手

如果我们知道每组的两次4的位置是ai和bi,从后往前处理每个属于b的4,与其前面第一个可用的1配对;然后从左往右跑一次114就好了,第i个5直接对应第i前的a中4。所以small很好做

问题变成怎么把4分为a和b,充要条件为,对于每个后缀中有x个1,y个4,一定是$|a| \ge x-y$。但同时我们的b要尽量靠后,所以在满足条件的情况下,优先分配为b;a和b间的配对,也直接用第i小的a和第i小的b配对就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
scanf("%s",str+1);int n=strlen(str+1),m=n/6;
for(int x=0,y=0,i=n;i>=1;i--)
{
if(str[i]=='1') x++;if(str[i]=='4') y++;
inB[i]=used[i]=0;ned[i]=x-y;
} fo(i,1,n-1) chmax(ned[i+1], ned[i]-(str[i]=='4') );
vc<int> a4,b4;fd(i,n,1) if(str[i]=='4'){ if(sz(a4)<ned[i] or sz(b4)==m) a4.PB(i); else b4.PB(i),inB[i]=1; }
sort(all(a4)),sort(all(b4));fo(i,0,sz(a4)-1) ans[i+1][3]=a4[i];fo(i,0,sz(b4)-1) rk[b4[i]]=i+1,ans[i+1][6]=b4[i];
stack<int> one;int c5=0,c1=0;fo(i,1,n) if(str[i]=='1') one.push(i); else if(str[i]=='5') ans[++c5][4]=i;
fd(i,n,1) if(inB[i]){
while(sz(one) and one.top()>i) one.pop();
assert(sz(one));int x=one.top();one.pop();used[x]=1,ans[rk[i]][5]=x;
}
fo(i,1,n) if(str[i]=='1' and !used[i]){ c1++;if(c1&1) ans[(c1+1)/2][1]=i; else ans[c1/2][2]=i; }
fo(i,1,m){ fo(j,1,6) write1(ans[i][j]);puts(""); } debug("\n");

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/95b4a9d.html
转载请注明出处,谢谢!