2019~2020学年度上OI总结

花$30$分钟切了$T1$和$T2$
$T1$:吸取前车之鉴，没有用$getchar()$,之前有用$getchar$然后$100pts->2pts$的经历（感谢@C20211711刘君实1亲身测试能用$getchar$）

---

$T2$：读题时、没注意

票价不超过地铁票价的公交车

于是花了$5$分钟调+手算然后又看了一遍样例解释才注意到。
于是这句话使我的$queue$变成了$vector$重做了一遍，并且还花了$2$分钟想到$erase$与$j—$(差点没打$j—$的我和的确没打$j—$的@C2022汪冠宇)结合加速(不加会$T$掉$50$分)。

---

$T3:$按照经验，$T4$比$T3$简单，所以我先瞟了两眼，第一眼:完全背包，第二眼:贪心，就这么与正解擦肩而过，先打了$10\%T=1$的情况进$T4$

---

$T4:$看到这道题我分析出$Yes$=有一条从$a$到$1$的长$L$的路径，反之$No$即为没有。。。然后就不知道怎么做了，于是打了一个$dfs$骗分，嫌不够再（没事找事）加了个记忆化。
然后:数组$[10000][100]$,并且我忘了$bool$的$false$转$int$为$0$
所以一开始写成这个亚子:

int mem[10000][100]
bool dfs(int a,int l)
{
    if(mem[a][l]) return mem[a][l];
    if(l==0) 
    {
        if(a==1) return true;
        else return false;
    }
    bool re=false;
    for(int i=0;i<G[a].size();i++) re|=dfs(G[a][i],l-1);
    return mem[a][l]=re;
}

第三行在$mem[a][l]=false$时是根本没用的，该$T$还是会$T$(跟朴素的dfs一个分，测出来还很五颜六色)
然后我们改成这个亚子:

mem[100000][1000]
bool dfs(int a,int l)
{
    if(mem[a][l]) return mem[a][l]==-1?0:1;
    if(l==0) 
    {
        if(a==1) return true;
        else return false;
    }
    bool re=false;
    for(int i=0;i<G[a].size();i++) re|=dfs(G[a][i],l-1);
    mem[a][l]=(re==0?-1:1);
    return re;
}

它就有了$75pts$

死了，还是不该偷懒不算数组大小然后开小了。然后再动动脑子把$mem=0$的情况改一改，多了$40pts$

---

$T3:$骗分，预计得分$25-40$,实际得分:$15$···
先打了两次贪心，自己出的数据都挂掉了，看时间不多开始骗分.骗的时候都没想到$T=2$的简单情况直接性价比贪心，无脑枚举···

---

总的来说，我们得到了如下宝贵经验:
$1.getchar()$除了快读和吞回车基本不要打(尽量吞回车都不要用)
$2.$仔细读题，勾画重点
$3.$各种想到的算法都试一试
$4.$骗分也要骗得有技术含量，不要犯低级错误
$5.$数组一定要算大小

---

事后:发现$T4$的$Yes$和$No$打错了···自闭了$2=AFO$

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1275881998@qq.com