技巧整理

Believe_in_dreams · 2025-11-30 14:58:57 · 算法·理论

考试技巧总结

注意事项

详细内容见 警示自己 。

考试策略

:::info[更固定化的策略 - 推荐程度⭐] 本策略应用于 4 小时、 4 道题的 CSP-S/NOIP 难度考试。

Part1 - 预处理

Part2 - 稳分必得

Part3 - 得分突破

Part4 - 整合检查

• :::

:::info[更随机应变的策略 - 推荐程度⭐⭐] 前 15min 读下题，写好模板和对拍。

后 5min 检查文件名和 freopen() 。

中间 2h40min 自由发挥，注意：优先性价比高、想周全再写、要争部分分、要构造检验特例、要对拍。 :::

:::info[跟大佬学的策略 - 推荐程度⭐⭐⭐] 做题分四步：想思路，写框架，写代码，调代码。

大佬说，

• 每一道题先用 $system1$ 随心想 $10min$ 。 如果想不出来就列举思考方向用 $BFS$ 的思路发散思考。 思考时可以有 从特殊往一般推广、猜想结论并验证 等等思路。 要写注释记录思路！要想周全！要构造反例验证！ 觉得思路周全后写代码框架，一定要具体。 # 未完工
• \color{green}{写代码，调代码}

  先写注释大框架，然后填充代码。

  以时间为第一关键字、得分为第二关键字排序写代码的先后顺序。

  如果有卡住则果断跳过。

• 检验代码调试、`freopen()` 、代码版本等注意事项。 :::

思维技巧总结

汇总了一些值得记录的题目，供二刷使用。

每一个板块的题目都按照时间排列。

标题是 出处 名称 ，标 Problem 的题目是找不到名字的题。

数据结构

::::info[Problem] 给定 n 个在二维平面上的横纵坐标互不相同的点。

求一个正方形能框住的点构成的集合的个数。

转移时间复杂度太高。

打表/数学归纳法/线性基知识，都可以发现一个关键性质：对于所有 u，SG(u) 一定是 0 或者 2 的非负整数次幂。

于是转移优化为 O(n\log n)，就做完了。 ::: ::::

::::info[P6599 「EZEC-2」异或] 给定 n,m ，构造 n 个值域 \in[1,m] 的数，使其两两异或之和最大。

输出最大值取模 10^9+7 。

重排 a 使得得到的 f_n 最大。

则输出最大数。

• 如果能找到上述数字

  则输出该数字+最大数。

算法正确性证明

• 如果序列只有非负数。

  显然 0 没有任何作用。

  性质： 最大数一定放在第一个是最优的。

  证明：

  因为所有数字都为正数，所以从 f_2 起所有数不被计入贡献。

  所以只能选择一个数字，最大数一定最优，得证。

• 如果序列只有非正数。

  显然 0 没有任何作用。

  性质： 最大数一定放在第一个是最优的。

  证明：

  因为所有数字都为负数，所以从 f_2 起所有数不被计入贡献。

  所以必须选择一个数字，最大数一定最优，得证。

• 如果序列有正有负。

  我们规定 “ x 被使用” 指的是在计算 f 的过程中到达 x 时，x 与 f_{i-1} 异正负，进入函数判定的第二个部分并对 f_i 给出贡献。

  • 性质： 所有使用的数字在合法情况下交换顺序不改变结果。

  • 性质： 一定至少有一个负数被使用。

  • 性质： 最优排列一定存在 f_i<0~(i\ge 1)

  证明：

  因为所有使用的数字在合法情况下交换顺序不改变结果。

  又因为一定至少有一个负数被使用。

  而将该数提前到最初使用一定合法，并且如此会导致 f_1<0 ，所以得证。

  • 性质： 最优排列中最后一个使用的数一定是正数。

  证明：

  考虑反证，显然 0 在此处不会造成任何影响。

  • 如果最后一个使用的数是负数。

    因为最优排列中一定存在 f_i<0~(i\ge 1) ，所以把最后一个数放在上述 i 之后一定合法且更优，与“最优”矛盾。

  故得证。

  • 性质： 最优排列中最后一个使用的数一定是最大的正数。

  证明：

  • 如果最优排列没有使用最大正数。

    则将最大正数替换掉排列中最后一个使用的正数，一定更优，与前提“最优”矛盾。

  • 如果使用了最大正数且不在最后

    则最大正数与最后一个使用的数交换，一定不劣。

  故得证。

  • 性质： 一定存在一种去除最大数的排列经过 f 计算的最后结果等于使用任意 非最大数 凑出的 “最大的小于 0 的数”。

  证明：

  考虑反证。

  • 如果 f 在某时 >0 且应使用的数中只剩下 >0 的数

    则所有使用的数的总和 >0 ，即凑出的数 >0 ，与假设“凑出的数 <0”矛盾。

  • 如果 f 在某时 <0 且应使用的数中只剩下 <0 的数

    则不使用这些剩余的数字一定使得凑出的数 <0 且更接近 0 ，与“最接近 0”的假设矛盾。

  于是不存在如上两种情况，则该排列一定存在，故得证。

综上证毕。

给出代码辅助理解。

const int W=2e6,N=2005;
int n,a[N],mx=0,id,flg;
bitset<2*W+5>dp;
signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        if(a[i]>mx)
            mx=a[i],id=i;
    }
    dp[W]=1;
    for(int i=1;i<=n;++i){
        if(i==id)
            continue;
        if(dp[W-a[i]]){
            /*
            如果最后0能被凑出来，
            这里单独特判的原因是我们初始默认0能被凑出来(f[0]=0)才可以转移。
            */
            flg=1;break;
        }
        //转移 dp[x]|=dp[x-a[i]]
        if(a[i]<0)dp|=dp>>(-a[i]);
        else dp|=dp<<a[i];
    }
    if(!flg)
        for(int i=W-1;i>=1;--i)
            if(dp[i]){
                write(i-W+mx);//如果能凑出负数，则选择合法的最大的负数再给最大数冲上去
                return 0;
            }
    write(mx);//如果凑不出负数则只能选择一个正数计入贡献，肯定选最大的；如果能凑出0则让最大数直接从0冲上去
    return 0;
}

:::: :::::

图论

::::info[P8191 [USACO22FEB] Moo Network G] 有 n 个点二维平面上的点（坐标为整数），两点的距离为欧几里德距离的平方，求它们的最小生成树。

感性理解，对于贡献是正的元素，先来要求低的。

推一下 b_i<0 的情况，设有 b_1,b_2<0,t_1,t_2,f 。

把 (t_1,b_1) 放前面：f>t_1,f+b_1>t_2 ，即 f>max(t_1,t_2-b_1)。

把 (t_2,b_2) 放前面：f>t_2,f+b_2>t_1 ，即 f>max(t_2,t_1-b_2)。

如果把 (t_1,b_1) 放前面更好，则 max(t_1,t_2-b_1)<max(t_2,t_1-b_2) 。

考虑分类讨论拆掉 max 。

• $\text{原式}\Rightarrow t_1<t_1-b_2$ ，恒成立。
• $\text{原式}\Rightarrow t_2-b_1<t_2$ ，恒矛盾。

综上，如果把 (t_1,b_1) 放前面更好，则 t_1+b_1>t_2 ，缩放得 t_1+b_1>t_2+b_2。

同理，如果把 (t_2,b_2) 放前面更好，则 t_2+b_2>t_1 ，缩放得 t_2+b_2>t_1+b_1 。

于是对于负数部分按照 t_i+b_i 从大到小排序即可。

给出代码。

struct node{int a,x;};
bool cmp1(node a,node b){return a.a<b.a;}
bool cmp2(node a,node b){return a.a+a.x>b.a+b.x;}
vector<node> s1,s2;
bool solve(){
    n=read(),t=read();
    s1.clear(),s2.clear();
    for(int i=1;i<=n;++i){
        int x=read(),y=read();
        if(y>=0)s1.push_back({x,y});
        else s2.push_back({x,y});
    }
    sort(s1.begin(),s1.end(),cmp1);
    sort(s2.begin(),s2.end(),cmp2);
    if(t<=0)return 0;
    for(auto x:s1){
        if(t<=x.a)return 0;
        t+=x.x;
    }
    for(auto x:s2){
        if(t<=x.a)return 0;
        t+=x.x;
        if(t<=0)return 0;
    }
    return 1;
}

::: ::::

未完工！

::::info[P4597 序列 sequence] 给定一个序列，每次操作把某个数 +1 或 −1。

把序列变成非降数列，求最少操作次数。

对于第二种分类情况，对答案贡献 1 。

给出代码。

#define int long long
int n,t,s[100005],ans=1;
signed main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        s[i]=x+y*t;
    }
    for(int i=n-1;i>=1;i--)
        if(s[i]>=s[i+1])s[i]=s[i+1];
        else ans++;
    cout<<ans;
    return 0;
}

::: ::::

其他