1. 题目

T1 一

题目描述

问题描述

你是能看到第一题的 friends 呢。
——hja

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
给定字符串 $s$，并且令 $x=1,y=0$。你需要根据字符串给出的字母来进行操作，具体如下：

如果字符串该位为 $\tt A$，则令 $x=2\times x+y$。
如果字符串该位为 $\tt B$，则令 $x=2\times y+x$。
如果字符串该位为 $\tt C$，则令 $x=y=x+y$。
若为其他字符，则不作任何操作。

所有操作结束后，输出 $x+y$ 的值，答案对 $10^9+7$ 取模。

输入格式
一行一个字符串 $s$。

输出格式
一行一个整数代表 $x+y$ 对 $10^9+7$ 取模之后的结果。

样例输入

ABCD

样例输出

数据规模与约定

对于 $30\%$ 的数据，字符串长度不超过 $10$。
对于 $60\%$ 的数据，字符串长度不超过 $100$。
对于 $100\%$ 的数据，字符串长度不超过 $10^5$ 且全部由大写字母组成。

Sol

送分的，Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MOD=1e9+7;
typedef long long ll; // 注意开 long long
string str;
ll x=1,y=0;
int main()
{
	cin>>str; int len=str.length();
	for (int i=0;i<len;i++) 
	{
		if (str[i]=='A') x=2*x%MOD+y;
		else if (str[i]=='B') y=2*y%MOD+x;
		else if (str[i]=='C') x=y=(x+y)%MOD;
	} printf("%lld",(x+y)%MOD);
	return 0;
}

T2 二

题目描述

问题描述

你是能看到第二题的 friends 呢。
——aoao

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
给定一个 $01$ 字符串 $s$，你可以将其中的某个 $1$ 换为 $0$ 或者某个 $0$ 换为 $1$，每次替换视为一次操作。现在我们希望通过尽量少的操作次数，使得其变为一个 $k$ 段的字符串，其中奇数段为 $1$；偶数段为 $0$。比如，$100101$ 为一个 $5$ 段的字符串。

输入格式
第一行一个整数 $k$。
第二行一个 $01$ 字符串。

输出格式
一行一个整数代表最小的操作次数。

样例输入

3
010

样例输出

数据规模与约定
本题一共 $10$ 组测试数据，对于第 $i$ 组测试数据，$k=i$，字符串长度为 $3^i$。

Sol

爆搜是 $O(n2^n)$ 的，可以获得 40pts。

考虑 dp。

设 $dp_{i,j}$ 表示 $[1,i]$ 已经确定，$i$ 在第 $j$ 段的最小方案。则转移为：

\[dp_{i,j}=\min\{dp_{i-1,j},dp_{i-1,j-1}\}+[s_i\neq j \bmod 2] \]

其中 $[x]=\begin{cases}1&\textbf{true}\\0&\textbf{false}\end{cases}$，$s$ 是原字符串的数字表示.

因为奇数段为 $1$，所以 $j$ 为奇数时目前为 $1$，否则为 $0$，所以后面是 $[s_i\neq j \bmod 2]$ .

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=60005,K=15;
typedef long long ll;
ll dp[N][K];
int k; string str;
int main()
{
	memset(dp,0x3f,sizeof dp);
	scanf("%d",&k); cin>>str; int len=str.length();
	if (str[0]=='1') dp[1][1]=0;
	else dp[1][1]=1;
	for (int i=2;i<=k;i++) dp[1][i]=len+1;
	for (int i=2;i<=len;i++)
		for (int j=1;j<=k;j++)
			dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+(str[i-1]-'0'!=(j&1));
	printf("%lld",dp[len][k]);
	return 0;
}

T3 三

题目描述

问题描述

你是能看到第三题的friends呢。
——laekov

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
给定平面上 $N$ 个圆，你可以过原点画一条直线，如果这条直线必须经过某个圆的圆心，问这条直线最多经过多少个圆？

输入格式
第一行一个数 $N$ 代表圆的个数。
接下来 $N$ 行每行三个数 $x,y,r$，代表圆心为 $(x,y)$ 半径为 $r$。

输出格式
输出一行一个整数代表答案。

样例输入

2
1 1 1
-1 -1 1

样例输出

数据规模与约定

本题一共 $10$ 组测试数据，对于第 $i$ 组测试数据，$N=i^2$。所有给定的圆一定不包含原点，如果直线只经过圆的边界仍然算经过该圆。

[前置] 向量点积 & 叉积

向量都知道罢，就是有向线段（好像一般写法是 $\overrightarrow v$），向量 $v$ 的长度是 $|v|$，叫 $v$ 的模长。

接下来的向量 $v(x,y)$ 均表示起点为 $(0,0)$，终点为 $(x,y)$ 的向量。

点积定义：对于向量 $v_1(x_1,y_2),v_2(x_2,y_2)$，其点积为 $v_1\cdot v_2=|v_1|\cdot|v_2|\cdot\cos \theta=x_1x_2+y_1y_2$ .
叉积定义：对于向量 $v_1(x_1,y_2),v_2(x_2,y_2)$，其叉积为 $v_1\times v_2=|v_1|\cdot|v_2|\cdot\cos \theta=x_1y_2+y_1x_2$ .

其中 $\theta$ 为 $v_1$ 与 $v_2$ 的夹角。

Sol

显然暴力枚举所有圆判断相交是 $O(N^2)$ 的，可以通过。

对于直线和圆判断相交的做法就是把这条直线到圆心的距离和半径比一比就好了。

关于直线 $OP$ 到点 $Q$ 的距离如下：

直接转成解析式可能会导致斜率为 $\infty$，所以只能用向量（点表示直线）

这里的 $v_1,v_2$ 很好求，就是 $v_1=P-O$，$v_2=Q-O$（变成原点出发）

显然这两点直接的距离 $d=v_2\sin \angle QOP$，由于叉积后面那段，所以 $d=\dfrac{v_1\times v_2}{|v_1|}=\dfrac{x_1y_2-y_1x_2}{\sqrt{x_1^2+y_1^2}}$ . 公式就出来了。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=105;
typedef double db;
int n,nans;
struct point // (0,0) -> (x,y) 的 向量 
{
	db x,y;
	point(db X=0,db Y=0){x=X; y=Y;}
	inline double len(){return sqrt(x*x+y*y);} // 模长 
	point operator+(const point& b){return point(x+b.x,y+b.y);}
	point operator-(const point& b){return point(x-b.x,y-b.y);}
	double operator*(const point& b){return x*b.y-y*b.x;} // 叉积 
}p[N];
double dis(point p1,point p2,point v1){point v2=p1-p2; return fabs(v1*v2)/v1.len();} // 点到直线距离 
const point zero(0,0); // 原点 
double r[N];
int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&r[i]);
	for (int i=0;i<n;i++)
	{
		point vec=p[i]-zero; int ans=0;
		for (int j=0;j<n;j++)
			if (dis(p[j],zero,vec)<=r[j]) ++ans;
		nans=max(nans,ans);
	}
	printf("%d",nans);
	return 0;
}

T4 四

题目描述

问题描述

你是能看到第三（？）题的 friends 呢。
——laekov

众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

给定一张 $N$ 个点 $M$ 条边的无向图，现在会有一条边的长度变为 $0$，每条边被选中的概率均为 $\dfrac{1}{M}$。问这种情况下的最小生成树的期望大小为多少？即你需要计算出 $M$ 种情况下的生成树大小，加起来再除以 $M$。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行每行三个数 $s,e,d$ 代表一条从 $s$ 到 $e$ 长度为 $d$ 的边。

输出格式

输出一行一个实数代表答案，保留六位小数。

样例输入

样例输出

1.333333

数据规模与约定

对于 $30\%$ 的数据，$N,M\le 100$ .
对于 $60\%$ 的数据，$N,M\le 10^3$ .
对于 $100\%$ 的数据，$1\le N\le10^5$，$1\le M\le2\times10^5$，$1\le s,e\le N$，$1\le d\le10^3$ .

[前置] 倍增 LCA

定义： LCA 指树上两点的的最近公共祖先（一个点到 root 的路径上所有点称作这个点的祖先，其本身和 root 也是）

显然可以暴力向上跳求 LCA：

/*
 dep : 节点深度
 fa  : 节点父亲
*/ 
inline void lca(int p1,int p2)
{
	while (p1!=p2){if (dep[p1]<dep[p2]) swap(p1,p2); p1=fa[p1];} // 让深度深的点暴力向上跳 
	return p1;
}

引理：对于任意 $n \in \mathbb N$，存在自然数序列 $a_1,a_2,\cdots,a_q$ 且 $a_1<a_2<\cdots<a_q$，使得

\[n=2^a_1+2^a_2+...+2^a_q \]

Proof：Q.E.D.

倍增 lca 就是每次按 $2$ 的次幂往上跳，因为引理所以一定能跳到。

先让这两个点跳到同一深度，然后再一起往上跳即可。
维护 $f_{i,j}$ 为从第 $i$ 个点往上跳 $2^j$ 步到达的点，显然跳 $2^j$ 步就是跳两次 $2^{j-1}$ 步，所以转移为 $f_{i,j}=f_{f_{i,j-1},j-1}$。

求 $f_{i,j}$ 的代码如下：

inline void dfs(int now)
{
	for (p is now's son) // 可以根据自己喜欢的写法写这里
	{
		f[p][0]=now;
		for (int i=1;i<=18;i++)        // 18 是 logN
			f[p][i]=f[f[p][i-1]][i-1]; // 跳 2^j 步就是跳两次 2^(j-1) 步
		dfs(p);
	}
}

求了 $f_{i,j}$，倍增 lca 就好做了，注意跳的时候从大到小，不然都跳 $2^0=1$ 步就和暴力一样了= =
Code:

inline void lca(int p1,int p2)
{
	if (dep[p1]<dep[p2]) swap(p1,p2); // 使得 p1 深度最小 
	for (int i=18;i>=0;a--)           // 把 p1 和 p2 跳到一样深 
		if (dep[f[p1][i]]>=dep[p2]) p1=f[p1][i]; // 如果跳不过（跳过后比 p2 深度低），就跳 
	if (p1==p2) return p2;                       // 特判特殊情况（因为后面会让 lca 再往上一步） 
	for (int a=18;a>=0;a--)                              // 跳到 lca 下面 
		if (f[p1][i]!=f[p2][i]) p1=f[p1][i],p2=f[p2][i]; // 还没重合，也就是还没到 lca 
	return f[p1][0];                                     // 最后走一步 
}

Sol

* MST 指最小生成树

显然暴力的复杂度是 $O(M\times \text{MST 的复杂度})$ 的，用 kruskal 法是 $O(M^2\log M)$ 的，可以获得 60pts。

正解是先算一棵原图的 MST，然后考虑将边权变为 $0$ 对 MST 的贡献。

先将边分类：

有 $n-1$ 条在 MST 上的边，我们称之为「树边」；
有 $m-n+1$ 条不在 MST 上的边，我们称之为「非树边」；

设目前 MST 大小为 $S$，分类讨论：

将一「树边」的权值 $v$ 变为 $0$，显然 MST 不会受影响，则当前树大小为 $S-v$ .
将一「非树边」的权值 $v$ 变为 $0$，众所周知图中每个点都在 MST 上，所以找条边用 $0$ 替下来就好了，根据贪心思想，取一条最大边即可，这样既不破坏这棵树的性质，有能让其大小最小。若此边为 $p_1\to p_2$，则询问 $p_1 \to p_2$ MST 上简单路径边权最大值（设其长度为 $u$），则目前树大小为 $S-u+0=S-u$ .

这个 $u$ 可以用暴力向上跳求，单次期望 $O(\log n)$，最坏 $O(n)$，在随机数据下可以通过，但是如果被毒瘤出题人卡了就死了。

在倍增 LCA 的时候维护一个 $g_{i,j}$ 表示第 $i$ 点向上跳 $2^j$ 步的路径中最大的边权是多少。

显然 $g_{i,0}$ 就是 $\operatorname{len}(i \to \text{fa}(i))$ （$\text{fa}(i)$ 是 $i$ 的父亲）

同理，将第 $i$ 点向上跳 $2^j$ 步的最大值分成两段，取 $\max$ 即可。转移为：

\[g_{i,j}=\max(g_{i,j-1},g_{f_{p,a-1},a-1}) \]

MST 上简单路径边权最大值 Code：

inline void dfs(int now)
{
	for (p is now's son) // 可以根据自己喜欢的写法写这里
	{
		f[p][0]=now; g[p][0]=len(now-->p); // 可以根据自己喜欢的写法写这里
		for (int i=1;i<=18;i++)
		{
			f[p][i]=f[f[p][i-1]][i-1];
			g[p][i]=max(g[p][i-1],g[f[p][i-1]][i-1]); // 前半段很显然，后半段还得先到点 f[p][a-1] 再转移 
		}
		dfs(p);
	}
}
inline int lca(int p1,int p2)
{
	int ans=0;
	if (dep[p1]<dep[p2]) swap(p1,p2);
	for (int i=18;i>=0;i--) 
		if (dep[f[p1][i]]>=dep[p2]) ans=max(ans,g[p1][i]),p1=f[p1][i]; // 跳的时候加上答案统计 
	if (p1==p2) return p2;
	for (int i=18;i>=0;i--)
		if (f[p1][i]!=f[p2][i]) ans=max(ans,max(g[p1][i],g[p2][i])),p1=f[p1][i],p2=f[p2][i]; // 跳的时候加上答案统计 
	return max(ans,max(g[p1][0],g[p2][0])); // 统计 
}

2. 算法 -- 搜索

最优解问题（最优化）
e.g. 给定 $N$ 个数 $a_{1\dots N}$，在其中选 $M$ 个数，求这 $M $ 个数之和的最大/小值
解数量问题（计数）
e.g. 给定 $N,M$ ，求从一个大小为 $N\times M$ 的矩阵内从左下走到右上，且每次只能向上或向右的方案数
解方案问题（构造）

BFS 条件：代价为 $1$ & 最优解问题
e.g. 走迷宫最优解

优化：

剪枝：
1. 可行性剪枝
  e.g. 给定 $N$ 个数 $a_{1\dots N}$，在其中选 $M$ 个数，求这 $M $ 个数之和的最大值
  如果怎么选也选不够 $M$ 个了，那么就直接返回
2. 最优性剪枝
  e.g. 给定 $N$ 个数 $a_{1\dots N}>0$，在其中选 $M$ 个数，求这 $M $ 个数之和的最小值
  如果目前已经比最优解差了就直接返回
3. 对称性剪枝
  e.g. 在 $n\times n$ 的棋盘上放 $n$ 个皇后（Queen），使其互不攻击，求方案数
  方案完全对称，直接搜一半即可
改变搜索顺序
e.g. 给定 $N$ 个数 $a_{1\dots N}>0$，在其中选 $M$ 个数，求这 $M $ 个数之和的最小值
排个序，加上最优性剪枝，第一次就搜到最优解，后面的全被最优性剪枝给剪了
卡时
TLE 显然是 0pts，掐个表在 $1s$ 以内要 TLE 的时候直接输出，也是有一定概率 AC 的（分值由 $0$ 到 $\ge 0$）
注意不要卡的太紧，输出和退出也是要用时间的。

#include<ctime>
#include<cstdlib>
#include<iostream>

// clock() 函数，程序运行了多少时间：
//    Windows 系统：单位为毫秒（ms）
//    Linux   系统：单位为微秒（μs） 
// 也可以直接乘上 CLOCKS_PER_SEC 变成秒（s）单位 

void dfs()
{
	if (colck()>=900){Output; exit(0);}
	// dfs
}

Problem 1：靶形数独（NOIp提高组 2009；洛谷 P1074；loj 2591）

最优性剪枝：都填 $9$ 还比最优解小就返回
可行性剪枝：某个格子填不了数了就返回
改变搜索顺序：
1. 从上到下按行搜（原顺序，被卡/kel）
2. 从下到上按行搜
3. 从右到左按列搜
4. 随机打乱搜玄学pts（随机打乱是 random_shuffle）
5. 从中间往外搜（很科学）加上最优性剪枝，先填大的
6. 从外往中间搜（很科学 too）加上最优性剪枝，先填小的
7. 先填可能性小的

Problem 2：八数码问题（洛谷 P1379）

因为代价为 1 & 最优解问题，所以用 bfs

判重：把空位置变成 $0$，然后九进制直接丢进桶里，或者十进制直接丢掉个位（个位可以算出来），当然也可以 Cantor 展开。

优化：双向 BFS ：
vis 变成 0,1,2（未遍历，起点遍历，终点遍历）
如果相交，那么结束

Problem 3：USACO1.5 八皇后 Checker Challenge（洛谷 P1219）

位运算优化

对角线：

对角线编号
位运算优化

位运算优化：
攻击皇后现状：

7 6 5 4 3 2 1 0
      1
	1 1 1
  1 1 1 1 1
a = 00010000 下    =>  a   = a
b = 00010000 左下  =>  b <<= 1
c = 00010000 右下  =>  c >>= 1

a|b|c 就是不能放皇后的的位置

清北学堂 2020 国庆J2考前综合强化 Day1

1. 题目

T1 一

题目描述

Sol

T2 二

题目描述

Sol

T3 三

题目描述

[前置] 向量点积 & 叉积

Sol

T4 四

题目描述

[前置] 倍增 LCA

Sol

2. 算法 -- 搜索