登录后台

还没有账号?注册一个吧(>ω・*)ノ

页面导航

2021/7/20模拟 题解&总结

噔 噔 咚

A - 粒子

如果一道题过程像最短路,思想像最短路,实现像最短路,那么它大部分情况下就是最短路。

写了一个 map<int,set<pii> > 并使用 priority_queue 模拟 $Dijkstra$ 的做法,难写难调,最后还挂了95pts,非常没有性价比。

事实上,考虑把一个点拆成1个中心点和4个触发点,对于坐标相同的触发点连边,最短路即可。

也可以对每个点记一下最早可能被四个方向上的哪个点触发,貌似简洁一些。

B - 游戏

做完A已经只剩两个小时多一点了。

瞄了一眼,有个思路,然后因为题面很像博弈决定去做更憨的C,C做完D有个思路然而没写出来,所以这题暴力30分滚粗了。

吃完饭回来仔细看了一遍,一分钟后发现有一个 $O(n^2)$ 的dp,考虑优化。

哦数据范围5000啊那没事了(

首先把不相邻的情况全部最先做,先删一定更优,这样只剩下一些连续区间。

然后发现长为 $L$ 的区间可以枚举断点拆成 $x$ 和 $L-1-x$ 的两段,直接转移即可。

按mzx说法这题可以出到1e5然后打表(

C - 白色相簿

首先可以证明最后剩下至多两个连通块,连通块内为完全子图,连通块间互相讨厌。

那么我们求出所有满足二分图性质的连通块,假设有 $cnt$ 个。

那么每个这样的连通块可以选择放最终大连通块中任一个,答案即为 $2^{cnt-1}$。

下面分享史诗级憨批错误:

bool dfs(int u,int f){
    for(int v:g[u]){
        if(v==f)continue;
        if(co[v]==co[u])return 1;
        else if(co[v])continue;//没写这行
        co[v]=-co[u];
        if(dfs(v,u))return 1;
    }
    return 0;
}

本来想说什么的,但是真的无语了...

只要有 $sz \ge 4$ 的偶环就可以把我杀了,居然只扣了25pts...

D - 密码

因为只想搏一手AC所以没有写思路和正解类似顺手就能过的部分分...

考虑建出01 Trie,然后在上面dp。

$dp[u][v]$ 表示第一种方法转移到 $u$ 点,第二种方法转移到 $v$ 点的最小长度。

如果当前点是endpos可以转移回根节点,并且每次转移优先考虑字典序更小的方法,用bfs转移再记录一下转移方案即可。

呃貌似直接这么爆搜有50分来着,为啥没有写呢?我也不知道。

还因此送掉了B...

吐槽

暴力都没打满,联赛难度还没之前省选难度的发挥好(指该拿的分拿完)。

用的什么憨批考试策略啊,联赛难度总是想跳不求稳活该挂分。

从去年到现在都没怎么吃痛,不要在NOIP上才长教训啊...

总结

  1. A题考试时做的操作本身没做错,下次要再简化思维别绕进去了。
  2. 大部分情况下B题难度就是B题难度,不要被题面骗了,Emiya家今天的饭那次也是。
  3. 不要犯nt错误时在脑子里一闪而过『这么写是不是会挂』然后当懒狗忽略。
  4. 考试状态真的会降低,不要总是贪正解,暴力分也很香。
  5. 考试策略安排要更合理,只有4个小时不能总是挥霍,脑子和手还要更快。
  6. 不要好高骛远,不然联赛考不好省选考不高等于啥都没学(
  7. 想想自己的眼前和背后,继续加油吧。

版权属于:Crab_Dave

转载时须注明出处及本声明