【OI 生涯起点】CSP-J2 游记

直接上接期中考游记，从 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 ```cpp #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 ```cpp #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 ```cpp #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 ```cpp #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$ 指年级均分）