CSP2020游记 + 半退役感想

今年 $\text{ln}$ 省初赛分数线极低, $\text{S}$ 和 $\text{J}$ 都很低,然后像我一样的蒟蒻就纷纷莫名其妙进了复赛给 $\text{dalao}$ 们送菜, $\text{mqy}$ 最开始 $\text{J}$ 组进了但是 $\text{S}$ 没进,结果因为有人没报名结果多余名额自由报名了,于是 $\text{mqy}$ 又进了复赛,我突然感觉我相对于 $\text{mqy}$ 初赛成绩的优势已经没有了,有点气啊。

但反正我们俩都是炮灰,本是同根生,相煎何太急啊!


早上是 $\text{J}$ 组,复赛的题还好,第一题难度有点像 $\text{14}$ 年的题目第一题,但是我分析了一下数据, $1 \le n \le 1 \times 10^7$ , $\text{Soga}$ !果断打表!

#include <bits/stdc++.h>
using namespace std;

int n;
long long pow2[24] = {0, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2};
int main()
{
  cin >> n;
  if(n % 2 == 1)
  {
    cout << -1 << endl;
    return 0;
  }
  for(int i = 1; i <= 23; i = i + 1)
    if(n >= pow2[i])
    {
        n = n - pow2[i];
      cout << pow2[i] << " ";
    }
  return 0;
}
// freopen我比赛写了,但是这里我就懒得写了,别打我
// 滑稽滑稽

这一波在洛谷评测了一下,满分过了,非常好啊,很有精神!


写完了之后去看了一眼第二题,第二题看起来很厉害的样子,但是其实一般,仔细分析了一下条件,然后就把代码写好了:

#include <bits/stdc++.h>
using namespace std;

int n, w;
int a[100010];

bool cmp(int p, int q)
{
    return p > q;
}
int main()
{
    cin >> n >> w;
    for(int i = 1; i <= n; i = i + 1)
    {
        cin >> a[i];
        sort(a + 1, a + 1 + i, cmp);
        if(i == 1)
            cout << a[1] << " ";
        else
            cout << a[i * w / 100] << " ";
    }
    return 0;
}
// 按照上题“惯例”我又不写freopen了

然后测了一下,样例一过了,样例二输出了一串0,我心态一点不乱,心态一乱,这个题就绝对搞不出来了。

查了一下,发现在 $i == 1$ 的特判的地方出现问题了。

首先我得弄明白为什么要特判,因为有的时候向下取整可能会取 $0$ ,所以这个时候就要取第一位。

然而,不一定是只有一位的时候向下取整取到 $0$ ,所以只要向下取整取到 $0$ ,直接输出第一名就完事了。

#include <bits/stdc++.h>
using namespace std;

int n, w;
int a[100010];

bool cmp(int p, int q)
{
    return p > q;
}
int main()
{
    cin >> n >> w;
    for(int i = 1; i <= n; i = i + 1)
    {
        cin >> a[i];
        sort(a + 1, a + 1 + i, cmp);
        int u = i * w / 100;
        if(u == 0)
            cout << a[1] << " ";
        else
            cout << a[u] << " ";
    }
    return 0;
}

然后本来想去测试样例三的,但是那个东西太长了, $\text{NOI Linux}$ 系统的 $\text{Guide}$ 我不会复制( $\text{mqy}$ :那你还写 $\text{freopen}$ 你怎么不会用啊!),那么一大长串一个一个敲不太容易,所以自己去分析了一下数据和我的代码的复杂度:

$\text{sort}$ 是 $\text{STL}$ 函数库自带的排序函数,本质好像是堆排序,复杂度是 $O(n \log n)$ ,如果乘上输入的 $n$ 的话我的算法时间复杂度是 $O(n^2 \log n)$ ,前 $50\%$ 的数据没什么问题,但是后面的 $50\% $大概率是炸了,想用桶排序试一试,结果最后不知道哪里出问题了样例都没过,而且当时第四题心态有点炸了(当时是做完了第四题回来看的第二题分析的复杂度,第四题出了点状况,下面会提到),然后不得已放弃了桶排序,还是选择 $\text{sort}$ 排序,加上了一个玄学优化,刚才在你谷测评姬上测了一下,是前 $50\%$ 都对了,但是后面全炸掉了,玄学优化没起任何作用。

插一句不想干的题外话,上学之后 $\text{mqy}$ 来问我第二题的事情,结果他才发现他的复杂度也过不去,当场炸了……


第三题……嗯……不会……再见……

倒不是我懒得读题, $\text{mqy}$ 这个题是用栈做,其实我也想这么干的,结果临时想不起来怎么读取输入的一整行,我就记得是个 $\text{getline}$ ,但是具体怎么写不知道了,最后心态突然就乱了,然后,再见……

但因为这个题要求输出 $\text{1}$ 和 $\text{0}$ ,所以我灵机一动玄学随机数想骗点分,然后写了个随机数,就保存了……


说第四题之前,先插个题外话:

考试之前 $\text{mqy}$ 开玩笑地问我今年 $\text{CSP}$ 可能出什么题目,我也开玩笑的回答说:“今年可能出原题。”

我俩人一笑而过。

谁知一语成谶。


第四题,方格取数,对于这个题我也是熟悉的不得了了,每天一看洛谷题库,放在第五题就叫方格取数,题意也差不多。

但很难受,我没做过。

盲猜是 $\text{DP}$ ,但是后来转移方程写错了,写完了才查出来,因为第三题的缘故,心态就已经炸掉了,于是草草了事,骗了点分。

洛谷自测貌似是 $\text{35}$ ???

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int a[1005][1005], dp[1005][1005];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i = i + 1)
        for(int j = 1; j <= m; j = j + 1)
        {
            cin >> a[i][j];
            dp[i][j] = a[i][j];
        }
    for(int i = 1; i <= n; i = i + 1)
    {
        for(int j = 1; j <= m; j = j + 1)
        {
            if(i != 1 && j != 1)
                dp[i][j] = max(dp[i][j] + dp[i - 1][j], dp[i][j] + dp[i][j - 1]);
            else if(i == 1)
                dp[i][j] = dp[i][j] + dp[i][j - 1];
            else
                dp[i][j] = dp[i][j] + dp[i - 1][j];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

考场的时候也没给只向右或下走的情况,于是我也不知道具体多少分,当时洛谷自测是民间数据,所以真正分数我也不确定。

估分: $100$ + $50$ + $0$ + $35$ = $185$

这个分在 $\text{LN}$ 是不低的分了,我还算满意了吧。

至少比去年好一点,大概估分只有 $155$ ,最后还因为没写 $\text{freopen}$ 爆 $0$ 了,那心态不就炸了吗。

算了,听天由命吧,我其实今后学不学都不一定了,桑……

因为 $\text{CCF}$ 今年推迟比赛导致两个省竞赛生还未开始就出局这种情况,再加上一个物理竞赛的学长告诉我竞赛有很多黑幕,我最后被迫暂时退役。

如果初三的时候成绩够好能考上本地著名的的 $24$ 中学,还有机会继续学下去,但是就以我现在的语文成绩,我看有点悬。

也许三年之后,我彻底退役了,再不会有人记得我, $\text{JS}$ 小学(本人母校)也不会记得我的传说,以及 $\text{JS-OI}$ 初代( $\text{JS}$ 小学首先参加信息学竞赛的四个人的组合,我, $\text{mqy}$ , $\text{hjz}$ 和 $\text{yzh}$ 四个人, $\text{hjz}$ 和 $\text{yzh}$ 彻底退役,我半退役,仅有 $\text{mqy}$ 目前仍在役)当年大闹信息课的事件。

但我仍然希望,能够在退役前(或许是永远退役了),留下属于自己的荣耀。

$\text{mqy}$ 和 $\text{prdn}$ 还会坚持的,也许他们,能够继续走下去,带着我们的希望,和荣耀。

不知道为什么就偏题了,但是还是因为要退役了,所以很感慨,就多说了两句。( $\text{mqy}$ :你管这叫两句???)

好了朋友们,山高路远,我们江湖再见。


发表于 2020-11-07 19:07:58 in 感想