直接上接期中考游记,从 Day -1 开始写。

Day -1

出了一场水题赛,背了高精和背包的板子。

希望今天背的明天都不要考到。

Day 1

直接来呗。

第一次参加线下 OI 比赛,不免有些激动。

$7:50$ 到考场,发现大家都到了,我已经是最后几个了(

进考场前看到 xj(学校信奥老师),让我细心点。rp++。

$8:00$ 被一个老师像赶牛一样赶到了考场。

机器是 win7 的,配有虚拟机,还有教程。不过因为没找到 Guide 没用。

$8:10$ 打完了 $4$ 题的模板,又打了个快排热热手。

$8:30$ 时间到了,但是老师说密码没来,让我们耐心等候。

$8:40$ 密码来了,但是没人能解压,老师说他们来解压,让我们耐心等候。

$8:43$ 解压完的文件来了,开题。

T1:???优秀的拆分?好像是一道黑题。。。

/jk/jk/jk

T2:???NOI 2130?看上去不难,再说了。

T3:???什么又臭又长的题面?不管了,先看 T4。

T4:???????????????????????

然后做题。

$8:50$ T1 样例 + 自造数据全过

$9:00$ T2 想到正解,一次性样例全过

T2 直接想到 $O(600n)$ 的正解了,根本没想快排暴力。

T3 不会。

$9:30$ T4 20pts 暴力完成,思路是简单 dfs。小样例可过。

$10:10$ T4 40pts $O(n^3m)$ 完成。思路是 dp 算每一个格子的最大值。自造数据发现极限在 $n=m=170$ 左右。

$10:20$ 思维貌似有些停滞,上了个厕所,心情舒畅。

$10:50$ T4 70pts $O(n^2m)$ 完成,思路是一些些前缀和优化降了一层循环。极限数据为 $n=m=460$ 可过。

接下来的时间里,我干嘛了呢?

  1. 把 T3 样例 $3$ 复制下来,肉眼找 x780 x80 x134 x913 等。
  2. 闭目养神。
  3. 吃了个饼干。
  4. 检查了 $5$ 遍文件夹及各题小样例。

没错我整场考试 T3 基本没看。事实证明我很幸运,因为它不在我的能力范围内。

估分 $100+100+0+70/80$,不算太好……

Day 2

考场代码发下来,回来更新。

先把考场代码贴出来:(未做任何改动)

T1 power

#include <bits/stdc++.h>
using namespace std;
int n;
bool a[30];
int pow(int x,int y) //x^y
{
    int ret=1;
    for (int i=1; i<=y; i++) ret*=x;
    return ret;
}
int main()
{
    freopen("power.in","r",stdin);
    freopen("power.out","w",stdout);
    cin>>n;
    if (n%2==1)
    {
        cout<<-1;
        return 0;
    }
    for (int i=30; i>=1; i--)
    {
        int now=pow(2,i);
        if (n>=now)
        {
            n-=now;
            a[i]=1;
        }
    }
    for (int i=30; i>=1; i--)
    {
        if (a[i]) cout<<pow(2,i)<<" ";
    }
    return 0;
}

T2 live

#include <bits/stdc++.h>
using namespace std;
int n,w,a[100001],t[601]={0};
int main()
{
    freopen("live.in","r",stdin);
    freopen("live.out","w",stdout);
    cin>>n>>w;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
        //t[a[i]]++;
    }
    for (int i=1; i<=n; i++)
    {
        t[a[i]]++;
        int now=i*w/100,cnt=0;
        now=max(1,now);
        for (int j=600; j>=0; j--)
        {
            cnt+=t[j];
            if (cnt>=now)
            {
                cout<<j<<" ";
                break;
            }
        }
    }
    return 0;
}

T3 expr

#include <bits/stdc++.h>
using namespace std;
string s;
int n,q;
bool a[100001];
int c[100001];
int main()
{
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    getline(cin,s);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i];
    cin>>q;
    for (int i=1; i<=q; i++) cin>>c[i];
    for (int i=1; i<=q; i++) cout<<0<<endl;
    return 0;
}

T4 number

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1001][1001],c[1001];
long long dp[1001][1001];
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++) cin>>a[i][j];
    }
    dp[1][1]=a[1][1];
    for (int i=2; i<=n; i++) dp[i][1]=dp[i-1][1]+a[i][1];
    for (int i=2; i<=m; i++) //this loop only focuses on the i-th colomn
    {
        c[1]=a[1][i];
        for (int j=2; j<=n; j++) c[j]=c[j-1]+a[j][i];
        for (int j=1; j<=n; j++) //now searching a[j][i]
        {
            if (i==m && j!=n) continue;
            dp[j][i]=-2147483647;
            int tmp=c[j];
            for (int k=1; k<=n; k++) //depth
            {
                if (k!=1)
                {
                    if (k<=j) tmp-=a[k-1][i];
                    if (k>j) tmp+=a[k][i];
                }
                dp[j][i]=max(dp[j][i],dp[k][i-1]+tmp);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

具体原理啥的就不写了。

oitiku 估分:

洛谷估分:

$100+100+0+70$(其中第三题暂无数据)

然而看到难度是 橙+橙+?+黄,感觉是不是 $300+$ 才能 1= 啊 /fad/fad

总之,总结一下本次考试的经验和教训。

  1. 开考前一定要把所有题都看一遍,看一下难度和自己是否有思路。如果连最简单的部分分都没有思路,就先完全放弃,只有剩下几题全 A 了或者确定自己不可能再得分了,再回来想这道题。
  2. 考试时一定要检查 freopen 的正确性,具体方法是:把样例放到一个 xxx.in 的文件里(用原来样例的那个文件也行),然后输出到自己建立的 xxx.out 文件中,再与答案 xxx.ans 比对。这样既测了样例,又验了 freopen。
  3. 考试时去上个厕所真的很重要,我的 T4 第 $3$ 个部分分就是一回来马上想到并一次性码对的。
  4. 考场还是建议使用 bits/stdc++.h 以防万一,但自己调试的时候如果心烦意乱就先不要用 bits,因为 bits 编译慢。
  5. 提交代码前一定要多次检查自己的代码、文件输入输出和文件夹,我检查了 $5$ 遍。
  6. 考试的时候如果认为你写的是正解,一定要算极限数据的时间复杂度,如果很危险或者根本过不去,不要太自信,赶紧想正解 / 优化。

这就是今年的 CSP-J2 了。

明天期中考就要出分了 /fad

【upd1】11.08.13:00

洛谷的 $4$ 题数据都有了。第 $3$ 题全输 $0$ 居然有 $3$ 个点,因此洛谷估分 $100+100+15+70=285$。

这样我自己估分 $100+100+10/15+70/75=280-290$。

希望能捞一个 1=,拿个绿钩钩(

明年还会继续,冲提高组。

希望还有更多的小伙伴们陪我走下去。

【upd2】11.17.22:00

官方分数出来了。 $100+100+5+70=275$。

所以 CCF 数据最毒瘤(确信

@楼楼223 说我 1= 稳了。那先恭喜我自己咯(

今天英语考炸了,有点难过,借此安慰自己。

希望明天数学脑子不要抽(

目标:班级 rk $(90-avg)$( $avg$ 指年级均分)