【游记】2019国庆清北刷题营

图论

图论部分转载于Shu_Yu_Mo の blog

2-SAT

SomeThing
  • 又名2-SAT-2
  • 判断有无解
  • 确定变量
  • 确定关系表达式
  • 变量的取值有两种
  • %d - SAT 表达式有多少个变量
  • SAT - %d 每个变量的情况个数
加边规则

在这里插入图片描述

如果x−−>yx−−>yx−−>yx−−>yx --> yx−−>y，表示确定x即可确定y。
(当某个点必须为某个值的时候，自身连边，例：当必须为true时，就false连向true)

例题
  • POJ2446
  • HDU3622
  • UVA1514 Piece it together
  • UVA1086 The Ministers’ Major Mess
  • HDU4306

二分图

SomeThing

  • 此图是树 => 此图是二分图

  • 此图是二分图 => 此图是树

  • 二分图两边的点数量为n,m，匹配值是x，最大独立集数量为n+m-x

例题

给出一张图，删一条边，使之成为二分图（CF 19E Fairy

最大团

SomeThing
  • 给一张图，求最大团 —> NPC。
  • 所以很多问题中，求最大团的图有很多特殊性质。
  • 求最大团的方法 （wait）。
  • 补图 —> 把图之前的图上的边全都删掉，没有的边全都加上。
  • 原图的反图中的最大独立集就是最大团
例题
  • 【HEOI2012】朋友圈

最大独立集

  • 原图的反图就是最大团。
  • 在二分图中，独立集的个数为，n+m−x

independent

CSP-Algorithm

图论

  • Tarjan
  • 二分图
  • 2-SAT
  • 最小生成树
  • 最短路

模拟

  • 灭鼠计划
  • 猪国杀
  • 立体图
  • 操作系统
  • 靶形数独
  • [THUPC2018]组合数问题

SomeThing

动态规划

DP的三种方法

  1. 记忆化搜索
  2. 用自己算别人
  3. 用别人算自己

排列类dp

  1. 把数字从小到大or从大到小一个一个插入
  2. 一个序列的前缀也是一个前缀
  3. 在1~k的排列中加入i，可以将大于等于i的数字全部加1，然后再插入i。

例题

例题1：求在一颗无限大的满二叉树上取n个点取到第k层的方案数。一个非根节点只有当它的父亲节点被选择是才可以被选。

思路：把根拆掉变成两颗更小的树。

ans=f[n][n]−f[n][k−1]ans = f[n][n] - f[n][k-1]

例题2：

在这里插入图片描述

状态：f[i][j][k]f[i][j][k] 用了j个i-1，i，i+1与k个i，i+1，i+2的方案，枚举l个i+1，i+2，i+3。

在这里插入图片描述

题目链接：https://www.luogu.org/problem/CF1110D

例题3：

在这里插入图片描述

一般思路：维护前i轮下来逆序对的和。但是不知道转移时交换的两个数的大小关系。很显然，这样不行。

提示：期望的和=和的期望 -> 所有方案的逆序对数=枚举两个位置交换，在所有方案中有多少种方案会形成逆序对。

f[i][j][k]f[i][j][k]表示在i轮之后i,j小于i,k的方案数。 求有多少j>k但i,j小于i,k。

我们考虑暴力枚举i，j来统计逆序对数，那么∑逆序对数=∑方案(∑i∗∑j)sum 逆序对数 = sum 方案(sum i *sum j)。

l是用来枚举位置j交换后会对增加/减少多少逆序对。

在这里插入图片描述

在这里插入图片描述

题目来源：

在这里插入图片描述

At coder Inversion Sun 030D(大概是这个)

写题

流程

  1. 想思路
  2. 翻译成代码
  3. 调试

调试技巧

对拍
  • 工具
  1. 你的程序
  2. 暴力程序
  3. 数据生成器
  4. 对拍程序

  • 结果

    • 一样：
    1. 都对了
    2. 错到一块了qwq
    • 不一样：
    1. 至少一个错的
    2. 帮你找到调试用的数据

  • 用处： 帮你找到一组错误的数据

  • 效率：

在这里插入图片描述

写错了 -> 一般很快就出问题

  • 对拍程序：

在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
    while(true)
	{
    	system("data.exe");
    	system("std.exe");
    	system("brute.exe");
    	if(system("fc std.out brute.out")) break;
	}
}
  • 产生1~n的排列

在这里插入图片描述

  • windows产生rand(rand()自身最大值很小)：

在这里插入图片描述

  • 树的生产方法
  1. 纯随机
    在这里插入图片描述
  2. 扫把图：
    在这里插入图片描述
  • 生成图
    • 直接生产
    • 用map or set把重边去掉
    • 连通图：先生成一颗树，再随机加边
    • DAG：i -> j 当且仅当i < j
  • 强制在线：把暴力写入数据生成器中。可以直接生产离线数据，方便对拍，拍完了把代码改成强制在线。

数论

exgcd

用法：求ax+by=gcd(a,b)ax+by=gcd(a,b)的一组整数解，或者判断ax+by=kax+by=k是否有解

线性筛

筛素数核心思想：一个数大于1的倍数一定是合数。

欧拉筛分：一个数，一定能被质因数分解。

x=p1k1∗p2k2∗......∗pnknx=p1^k1*p2^k2*......*pn^kn

x=p1∗p1k1−1∗p2k2∗......∗pnknx=p1*p1^{k1-1}*p2^k2*......*pn^kn

欧拉函数

phi(i)表示小于等于i的数里面与i互素的数的个数

phi(x)=x(1−1/p1)(1−1/p2)...(1−1/pn)phi(x)=x(1-1/p1)(1-1/p2)...(1-1/pn)

求一个数的phi <==> 求这个数的质因数分解

性质：

  1. phi(1)=1phi(1)=1(唯一和1互质的数就是1本身)
  2. 若nn是素数，则phi(n)=n−1phi(n)=n-1
  3. 若nn是合数，则phi(n)<n−1phi(n)<n-1
  4. 当nn为奇数时，则phi(2n)=phi(n)phi(2n) = phi(n)
  5. 若aa、bb互质，则phi(a∗b)=phi(a)∗phi(b)phi(a*b)=phi(a)*phi(b)

组合数

在这里插入图片描述

####　逆元

在这里插入图片描述

欧拉定理&feim

在这里插入图片描述

在这里插入图片描述

Lucas定理

Lucas(n,m,p)=C(n%p,m%p)∗Lucas(n/p,m/p,p)Lucas(n,m,p)=C(n\%p,m\%p)*Lucas(n/p,m/p,p)

中国剩余定理(crt)

在这里插入图片描述

在这里插入图片描述

  1. 先将P分解质因数，得到其质因子

  2. 用Lucas定理求C(n,m)=Xi(mod pi)C(n,m)=X_i(mod pi)

  3. 合并两个相邻的同余方程，要求gcd(p1,p2) = 1

    1. C(n,m)=x1(mod p1)

      C(n,m)=x2(mod p2)

    2. C(n,m)=p1*k1+x1=p2*k2+x2 ==> exgcd

      p1*k1 - p2*k2 = x2 - x1

    3. 用exgcd求出一组整数解(k1,k2)

      C(n,m) = p1 * k1 + x1 (mod p1 * p2)

高斯消元

【HNOI2013】游走

在这里插入图片描述

在这里插入图片描述

大步小步算法(BSGS)

给定a，y，p，求最小的非负整数x，使得ax=y(mod p)a^x=y(mod p)

在这里插入图片描述

Bzoj2242：[SDOI2011]计算器

在这里插入图片描述

例题

在这里插入图片描述

在这里插入图片描述

CSP-S会涉及到的数学相关的知识

  1. 快速幂
  2. 矩阵乘法
  3. GCD/exGCD
  4. 筛素数/素数判断
  5. 欧拉函数
  6. 逆元
  7. 组合数取模/卢卡斯定理
  8. 中国剩余定理
  9. 高斯消元

模拟

例题

  • 时间复杂度
  • P3585 [POI2015]PIE
  • P3492 [POI2009]TAB-Arrays

贪心

例题

  1. P3419[POI2005]SAM-Toy Cars

    贪心策略：优先替换下一次出现时间晚的玩具，因为下一次出现得越晚，它闲置的时间最长，可以少占用地板的空间。

  2. [CF898D]Alarm Clock

    贪心策略：优先删每一段时间靠后的闹钟

  3. P3545[POI2012]HUR-Warehouse Store

  4. [CF954E] Water Taps

  5. P3457 [POI2007]POW-The Flood

  6. P3566 [POI2014]KLO-Bricks

考试策略

  1. 开考前把考试前最终需要检查的东西写一下。

  2. 前10~15分钟读题：读懂题，知道题在干什么，知道样例是怎么算的。

  3. 5分钟选择做题顺序，这时候还没有想出来题还没有怎么做，凭直觉把题目安装难度排序。

  4. 约1.5h写完每个题目的暴力，理想暴力分数：T1 100分，T2 60分，T3 30分。

  5. 接下来按照平时做题的方法去写一百分/更多部分分的做法。
    Alarm Clock

    贪心策略：优先删每一段时间靠后的闹钟

  6. P3545[POI2012]HUR-Warehouse Store

  7. [CF954E] Water Taps

  8. P3457 [POI2007]POW-The Flood

  9. P3566 [POI2014]KLO-Bricks

考试策略

  1. 开考前把考试前最终需要检查的东西写一下。
  2. 前10~15分钟读题：读懂题，知道题在干什么，知道样例是怎么算的。
  3. 5分钟选择做题顺序，这时候还没有想出来题还没有怎么做，凭直觉把题目安装难度排序。
  4. 约1.5h写完每个题目的暴力，理想暴力分数：T1 100分，T2 60分，T3 30分。
  5. 接下来按照平时做题的方法去写一百分/更多部分分的做法。
  6. 最后10到15分钟停止虐键盘，检查文件，编译，调试信息，数组大小，初始化等等。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/aurorapolaris/p/13449108.html