考试报告-1

· · 个人记录

我的主页

P1378 油滴扩展

涉及算法/考点：

全排列

解题思路：

全排列枚举所有顺序，计算。n很小，全排列复杂度并不会超时，不需要优化

解题关键点：

摆放油滴不同的顺序会产生不同的结果，需要列举出全部可能性再逐一比较

易错点/出现的错误总结：

  1. 计算半径时，可能出现负数，要赋值为 0
  3. 摆放的第i个油滴的下标并不是[i]

    通用技巧总结：

  5. ### 类比题目： 全排列

P1069 [NOIP2009 普及组] 细胞分裂

涉及算法/考点：

整除

解题思路：

一个数可以拆分成p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\cdots p_i^{e_i}的形式
如果 b 是 a 的倍数
那么 b 的所有 e_i 大于 a 的对应的 e_i
所以对于每一个 s_i 只需要计算出 anss_i=max(\lceil \frac{m.e_i}{s_i.e_i}\rceil)就可以啦
最终答案： ans=max(anss_i)

解题关键点：

把整除转换一下

易错点/出现的错误总结：

  1. 当 m1=1 时直接输出1
  2. 当 m1 或 s_i 是质数时要把他自己放进去

通用技巧总结：

把整除转换一下
自信即巅峰

P1970 [NOIP2013 提高组] 花匠

涉及算法/考点：

解题思路：

dp

假设 dp_{i,0/1} 为结尾是 i 的最长序列且其结尾为上升/下降
那么

dp_{i,1} = \left\{ \begin{array}{cc} dp_{i-1,0}+1 & h_i>h_{i-1}\\ dp_{i-1,1} & else \end{array} \right. dp_{i,0} = \left\{ \begin{array}{cc} dp_{i-1,1}+1 & h_i<h_{i-1}\\ dp_{i-1,0} & else \end{array} \right.

结果就是 \max(dp_{n,0},dp_{n,1})
初始值： dp_{1,0}=1,dp_{1,1}=1

解题关键点：

分类讨论

易错点/出现的错误总结：

搞混/搞错/搞反两种情况QwQ

通用技巧总结：

分类讨论：让“不可能”成为现实
看起来很离谱违反直觉的东西可能是正确的

P3405 [USACO16DEC]Cities and States S

就是地图

涉及算法/考点：

哈希

解题思路：

把城市名称的前两位转换成一个数
具体方法：num=s_0\times256+s_1
如果几个城市的省会和名称的前两位都一样，那为什么还要一个一个算呢
优化方法：对于每个城市，进行以下操作：
anss[a[i].fst][a[i].sec]++
统计答案： 

for(int i=0;i<n;i++){
    if(a[i].fst==a[i].sec)continue;
    ans+=anss[a[i].sec][a[i].fst];
}

解题关键点：

易错点/出现的错误总结：

通用技巧总结：

好好读题

代码

#include<bits/stdc++.h>
using namespace std;
int anss[750][750];
long long ans;
int n;
struct node{
    int fst,sec;
};
char fc[20],sc[10];
node a[200010];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s%s",fc,sc);
        a[i]={(fc[0]-'A')*26+fc[1]-'A',(sc[0]-'A')*26+sc[1]-'A'};
        ++anss[a[i].fst][a[i].sec];
    }
    for(int i=0;i<n;++i){
        if(a[i].fst==a[i].sec)continue;
        ans+=anss[a[i].sec][a[i].fst];
    }
    cout<<(ans>>1);
}

P5683 [CSP-J2019 江西] 道路拆除

就是道路拆除

涉及算法/考点：

最短路（ Dijkstra 或者 BFS ）

解题思路：

从点 1 ，点 s1 和点 s2 各自跑一遍最短路，分别记为 d0 d1 d2
枚举一个点 P ，当 d0_P+d1_P\le t1 且 d0_P+d2_P \le t2 时，求出 ans=min(d0_P+d1_P+d2_P)
答案就是 m-ans

那么求出的最短路之和不是可能会有重复计算吗
就是这样

在这里 边 (2,P) 被重复计算了（在 d1_P 和 d2_P 中）
但是别忘了我们会枚举所有的点做中转点
在这里（点 P ）重复了，在其他点（ 2 号点）就不会重复了！
而且因为边权都是 1 ，重复的一定会大于不重复的，所以在取 min 的时候就不会取到它，对答案没有影响

解题关键点：

把问题转化成三个最短路

易错点/出现的错误总结：

把小于等于打成小于
把1-n的循环写成0-n-1

通用技巧总结：

多次（正向+反向）最短路

P5682 [CSP-J2019 江西] 次大值

涉及算法/考点：

还是整除

解题思路：

我们只需要取出 a 中的前三个不同的数
最大值一定是 a_2
因为最大的模数是 a_1 ，所以不可能有大于等于 a_1 的结果
也不可能有大于等于 a_2 的结果 因为没有比 a_2 更大的被除数

也可能是 $a_3$ ，因为 $a_3$ $mod$ $a_2$ 或者 $a_3$ 因为 $a_3$ $mod$ $a_1$ 都等于 $a_3

解题关键点：

发现有好多好多个没有意义的 a_i

易错点/出现的错误总结：

用样例就可以测出来

通用技巧总结：

分类讨论

P1314 [NOIP2011 提高组] 聪明的质监员

涉及算法/考点：

解题思路：

二分枚举 W 的值
对于每次二分出来的 W 求一遍前缀和
设 qzh1_i 为在 i 之前的合格的 w_i 的个数
设 qzh2_i 为在 i 之前的合格的 w_i 的 v_i 之和
在对每个区间 [l,r] 进行计算 求和
再和s比较

解题关键点：

易错点/出现的错误总结：

通用技巧总结：

P5018 [NOIP2018 普及组] 对称二叉树

涉及算法/考点：

深搜

解题思路：

从每个节点出发
搞一个 dfs(l,r) 表示左右子树分别是 l 和 r
当 l 和 r 都是空子树 返回 1
如果 v_l\neq v_2 时返回 0
如果 当 l 和 r 有一个是空子树 返回 0
如果 dfs(l_l,r_r)=0 返回 0
如果 dfs(l_r,r_l)=0 返回 0
如果前面都不成立 返回 1
再跑一遍计算子树大小 取最大值

解题关键点：

每个 dfs 函数递归几层就可以得出结果
因为如果要让他递归很多次就要让树接近一个满二叉树或者一条链
满二叉树最多有 logn 层
链的话只要递归几层就可以判断出来他不是对称的
所以看起来 O(n^2) ，会超时，但是实际上差不多 O(nlogn) ，不超时

易错点/出现的错误总结：

为什么我没想到可以同时跑两边QwQ

通用技巧总结：

自信即巅峰
暴力出奇迹

P1077 [NOIP2012 普及组] 摆花

涉及算法/考点：

dp

类似于背包

解题思路：

dp[0][0]=1;
for(int i=1;i<=n;i++){
    for(int j=0;j<=m;j++){
        for(int k=0;k<=j&&k<=a[i];k++){
            dp[i][j]+=dp[i-1][j-k];
            dp[i][j]%=ms;
        }
    }
}

解题关键点：

把本题转换成“背包”

通用技巧总结：

把不熟悉的问题转换成熟悉的问题