CSP/J 集训 Day 3 模拟赛总结

今天在图灵打了国庆模拟赛 Day3,赛后总结一下。


T1:自动生产线

每 3 天一个周期,总产量 s = a + b + c。先算完整周期数 full = (n-1)/s,天数 days = full*3,剩余 rem = n - full*s,再逐天判断 rem 在第几天达到。

结果:AC,100 分。

反思:这题是签到题,公式推对了就没问题。


T2:距离之和

暴力 O(n²) 能过 n ≤ 10000,但正解是排序后算贡献:第 i 个数左边有 i 个比它小,右边有 n-1-i 个比它大,贡献为 a[i]*(i) - a[i]*(n-1-i)。

结果:AC,100 分。

反思:暴力能过这题,但正解更优雅,下次可以试试排序做法。


T3:追忆

判断是否能重排为回文串(最多一个字符出现奇数次)和循环串(最小周期 < 长度且能整除)。

我自测完忘改 freopen 里的文件名了,导致 0 分。

问题:freopen 写的是 recall.in,但自测时改成了别的名字,交上去之前没改回来。

正解:回文串判断奇偶,循环串用 KMP 求最小周期。

结果:0 分


T4:位序列

区间异或、或、与。暴力每次 O(n) 查询,n,m ≤ 5×10^5 会 TLE。

正解:按位拆解,每一位维护前缀和,查询时 O(21) 算答案。

结果:0 分(自测完忘改 freopen)。

反思:自测完一定要把 freopen 改回来! 这种低级错误太亏了。


T5:梦境

每根木材长度 x,锯成两根 x/2,奇数额外产生一个 1。问处理完第几根木材后能得到至少 k 个 1。

我写的是 k/2 或 k/2+1,完全不对。

正解:模拟锯木材的过程,统计每根木材产生的 1 的个数,前缀和 + 二分查找。

结果:20 分(骗了部分分)。

反思:这题需要模拟 + 二分。


成绩表

题目 文件名 结果 得分 备注
T1 自动生产线 auto AC 100 签到题,公式正确
T2 距离之和 volume 暴力能过
T3 追忆 recall 0 前缀
T4 位序列 bit freopen 忘改
T5 梦境 dream 20 骗分
总分 220

总结

T1、T2 是签到题,必须拿满,我做到了。

T4 是 freopen 忘改导致 0 分,太亏了。

T5 是模拟 + 二分,我公式错了,骗了 20 分。

经验教训

  1. 自测完一定要把 freopen 改回来! 这是今天最大的教训。
  2. 看到变换题,先想数学性质,别急着模拟。
  3. 能骗分就骗分,但骗分代码也要符合题意。
  4. 数组大小按数据范围开,别开小也别开太大。
  5. 贪心、模拟要保证逻辑正确,不能想当然。
  6. 别急着堆屎山代码,代码越简洁越不容易出错。
  7. 不放过任何得分机会,哪怕感觉没希望也试试。

这次成绩:auto 100,volume 100,recall 0,bit 0(freopen 忘改),dream 20。

下次一定要注意 freopen!

1 条评论

  • 1