The 10th SWJTU ACM Online Tutorial

时间:2023-01-14 18:23:53

小记:

这次校预赛,基友拿Java敲了4题,我用C++敲了4题,Python敲了1题(一个美丽的错误)。

题目都比较基础,有些数据太水,比如E的裸DP未优化AC,再如F的网络流竟然AC(我自己都惊呆了T^T)。

题外话:

昨天CodeJam打了满分,好高兴,毕竟我是半年没碰过C++的伪新手,嗯嗯~心态好才是真的好~

小伙伴们,加油啊~

相信代码相信爱~

 

Problem A: SRTP

求和比较。

 

Problem B: 2048

以R指令为例(L、U、D可通过旋转转化):

每行单独处理,移动规则为尽可能靠右,合并规则为优先合并右侧的两个。

可合并两组的特殊情况如:2 2 1 1合并后为0 0 4 2。

 

Problem C: What's Her Name?

统计某个逗比名字中各个字母的个数,再根据水桶效应,取最小值。

对于单个名字出现2次且不能顶针的n,需要把个数除以2后,再与其他比较。

 

Problem D: Skip Classes

统计:类型1的天数记为a,类型2的天数记为b=b1(早上)+b2(下午)。

答案为min[max(a+b1-m,0)+max(b2-k,0)]。

 

Problem E: Sequence

用d[i][j]表示以j结尾的长度为i的序列,DP状态转移方程:d[i][j]=d[i-1][p](p为j的因子,预处理得到所有的因子表)。

答案为Sum(d[n][1~k])。

 

Problem F: Share Candies

没有想到贪心方法,使用网络流的最大流最小费侥幸AC。

定义比平均值大的点为富足点,反之为贫穷点。对于每个富足点与贫穷点,建边,容量为富足点多余的糖果数,花费为富足点与贫穷点在环上的圆缺距离。超级源点与所有富足点连接,所有贫穷点与超级汇点连接。

答案为源点到汇点的最小费。

 

Problem G: Fibonacci Prime

预处理前80个Fibonacci数,根据互素原则,得到前20个Fibonacci Prime。

 

Problem H: A + B Again

抽象小数模型为:a.b(c),其中a、b、c位数不定,tb、tc表示10的(b、c部分对应长度)次幂。

引理:x=0.(c),tc*x=c.(c)=c+x,得到x=c/(tc-1)。

答案为(a*tb+b+c/(tc-1))/tb=((a*tb+b)*(tc-1)+c*tb)/(tb*(tc-1))。

 

Problem I: Digits' Sum

模拟后各位求和。