五一省选真题分享


五一|省选真题分享五一|省选真题分享

P4071 – SDOI2016 – D2T1 – 排列计数

题目信息

难度:提高+/省选-

算法:数学递推、逆元

题目描述

求有多少种 $1$ 到 $n$ 的排列 $a$,满足序列恰好有 $m$ 个位置 $i$,使得 $a_i=i$.

答案对 $10^9+7$ 取模,多组询问,询问次数为 $T$.

测试点编号$T=$$n, m\leq$测试点编号$T=$$n, m\leq$
$1 \sim 3$$10^3$$8$$10 \sim 12$$10^3$$10^3$
$4 \sim 6$$10^3$$12$$13 \sim 14$$5\times 10^5$$10^3$
$7 \sim 9$$10^3$$100$$15 \sim 20$$5\times 10^5$$10^6$

对于 $100\%$ 的数据,$0\leq m\leq 10^6$.

$\rm{Subtask}$ $\rm{1}$

$T=10^3$,$n, m\leq 8$.

对于每次询问,暴力枚举所有排列,时间复杂度 $\mathcal{O}(T\times n!)$,期望得分 $\rm{15pts}$.

$\rm{Subtask}$ $\rm{2}$

想到错排之后,正解非常自然。

根据小学排列组合知识,我们从数列中任意取 $n$ 个数,让它们满足 $a_i=i$,情况数为 $C_{n}^{m}$.

又因为 $n$ 个数的排列中,有 $m$ 个位置满足 $a_i=i$,对于剩下的 $n-m$ 个位置需要满足 $a_i\neq i$.

这样的情况数是 $n-m$ 的错排数,也就是 $D_{n-m}$.

由于乘法原理,最终的答案就是 $C_{n}^m\times D_{n-m}$.

对于多组询问,我们需要 $\mathcal{O}(n)$ 预处理组合数和错排数。

错排

概念

对于一个 $n$ 个元素的排列,若一个排列中所有的元素都不在自己的位置上,这样的一个排列称为一个错排。

一般将 $n$ 个元素的错排数量记作 $D_n$.

通过递推,可以在 $\mathcal{O}(n)$ 的复杂度内处理出 $D_1,D_2\cdots, D_n$.

递推式

推导过程不唯一。

第一步,在 $[1, n-1]$ 中任取一个元素 $i$,将 $n$ 连向 $i$,方法数量为 $(n-1)$.

第二步,确定 $i$ 连向哪个元素,分类讨论:

  1. $i$ 连向 $n$.此时剩下的 $n-2$ 个元素要满足错排,对答案贡献为 $(n-1)\times D_{n-2}$.

  1. $i$ 不连向 $n$.此时,相当于有 $n-1$ 个元素需要满足错排,对答案贡献为 $(n-1)\times D_{n-1}$.根据加法原理,得到递推式:
$$
\begin{align}
D_{n}=(n-1)\times(D_{n-1}+D_{n-2})\tag{n>2}
\end{align}
$$

特殊地,$D_1=0$,$D_2=1$.

求逆元 & 组合数

扩展欧几里得

概述

扩展欧几里得算法是用来在已知 $a,b$ 的情况下求解一组 $x,y$,使满足 $ax+by=gcd(a,\,b)=d$.

$\gcd(a, b)$ 为 $a, b$ 的最大公因数,方程一定有整数解

特解

要计算 $\gcd(a,\,b)$,并求出满足条件的 $x,y$.

将下一个状态 $b$ 和 $(a\%b)$ 表示为:$b\cdot x_1+(a\%b)\cdot y_1=d$

则:

$$
\begin{align}
\because b\cdot x_1+(a\%b)\cdot y_1=d,\\
\text{又}\because a\%b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b\\
\end{align}
$$
$$
\begin{aligned}\therefore gcd(a,\,b)=d&=b\cdot x_1+(a-\left\lfloor\frac{a}{b}\right\rfloor\times b)\cdot y_1\\
&=b\cdot x_1+a\cdot y_1-\left\lfloor\frac{a}{b}\right\rfloor\times b\times y_1\\
&=a\times y1+b\times(x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1)
\end{aligned}
$$

 

所以满足条件的 $x=y_1,\,y=x_1-\left\lfloor\frac{a}{b}\right\rfloor\times y_1$.

int exgcd(int a, int b, int &x, int &y) {//函数返回值为gcd(a,b)
    if(b == 0) {
        x = 1;//gcd(a,b) = a = 1a+0b
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);//先递归
    int t = x;//再计算x,y
    x = y;
    y = t - a / b * y;
    return r;
}

时间复杂度为:$\mathcal{O}(\min(\log a, \log b))$,即 $\mathcal{O}(\log n)$ 级别。

通解

假设特解为 $(x_0,y_0)$,满足 $ax_0+by_0=gcd(a,\,b)=d$,

则有:

$$
a(x_0+k\frac{b}{d})+b(y_0-k\frac{a}{d})=d\tag{k为整数}
$$

所以方程的通解为:

$$
x=x_0+k\frac{b}{d}\\y=y_0-k\frac{a}{d}
$$

对于其它二元一次不定方程$ax+by=c$($c$为任意正整数)只有当 $d\mid c$ 时才有整数解,通解形式:

$$
x=\frac{c}{d}x_0+k\frac{b}{d}\\y=\frac{c}{d}y_0-k\frac{a}{d}
$$

同余方程(模方程)

概述

指形如 $ax\equiv b\pmod c$ 的一种方程。其中 $a,b,c$ 是参数,$a,c$ 是正整数,$b$ 是小于 $c$ 的非负整数,$ x$ 是未知数。

解同余方程

根据同余定义,$ax\equiv b\pmod c$ 可化为 $xa+kc=b$. 其中 $a,b,c$ 已知,$x,k$ 未知,所以能用扩展欧几里得解同余方程

通解

如果 $b\nmid gcd(a,c)$,方程无整数解.

否则同扩展欧几里得酸法,求得通解:

$$
x=\frac{b}{d}x_0+k\frac{c}{d}\\k=\frac{b}{d}p_0-k\frac{a}{d}
$$

其中 $k\in \Bbb{Z}$.

最小非负整数解

因为 $x=\frac{b}{d}x_0+k\frac{c}{d}$,其中 $x_0$ 是方程 $xa+kc=gcd(a,\,c)$ 的特解, $\frac{b}{d}x_0$ 是原同余方程的特解,

若 $x>0$,则有 $x\equiv \frac{b}{d}x_0 \pmod{ \frac{c}{d}} $。最小非负整数解为 $\frac{b}{d}x_0\,\%\,\frac{c}{d}$.

若 $x<0$,同理,最小非负整数解为 $(\frac{b}{d}x_0\bmod \frac{c}{d}+\frac{c}{d} )\bmod\frac{c}{d}$.

综上,最小非负整数解为:

$$
x=(\frac{b}{d}x_0\bmod\frac{c}{d}+\frac{c}{d})\bmod \frac{c}{d}
$$

乘法逆元

概述

给定两个整数 $a$ 和 $p$,假设存在 $x$ 使得 $ax\equiv 1\pmod p)$,称 $x$ 为 $a$ 关于 $p$ 的乘法逆元

$a$ 关于 $p$ 的逆元存在的充分必要条件是 $\gcd(a,p)=1$.

在模意义下,乘一个数 $x$ 的逆元,可以理解为除以 $x$.

求一个数的逆元

将上面式子变形,变成 $ax+kp=1$,用扩展欧几里得能够求出一个 $x$.

如果 $p$ 是质数,有另一种方法求 $a$ 关于 $p$ 的逆元(费马小定理)

$$
a^{p-1}\bmod p=(a^{p-2}\times a)\bmod p=(x\times a)\bmod p=1
$$

所以 $a$ 关于 $p$ 的逆元是 $a^{b-2}\bmod b$ 的值,用快速幂优化。

时间复杂度:均为 $\mathcal{O}(\log n)$ 级别。

线性预处理逆元

在 $\mathcal{O}(n)$ 的时间复杂度内,求出任意 $n$ 个数的逆元,一般用于处理 $1\sim n$ 的逆元。

设我们要处理出 $a_1, a_2\cdots, a_n$ 的逆元。

第一步,预处理出前缀积数组 $\operatorname{pre}_i=\prod_{j=1}^ia_i$.

第二步,求出 $\operatorname{pre}_n$ 的逆元 $\operatorname{pre\_inv}_n$,复杂度 $\mathcal{O}(\log n)$.

第三步,通过 $\operatorname{pre\_inv}_i$,求出 $\operatorname{pre\_inv}_{i-1}$.

在模意义下,$\operatorname{pre\_inv}_i=\frac{1}{a_1\times a_{2}\times \cdots \times a_{i}}$,$\operatorname{pre\_inv}_{i-1}=\frac{1}{a_1\times a_2\times\cdots\times a_{i-1}}=\operatorname{pre\_inv}_{i}\times a_i$.

第四步,通过 $\operatorname{pre\_inv}_i$,求出 $\operatorname{inv}_i$.

在模意义下,$\operatorname{inv}_i=\operatorname{pre}_{i-1}\times \operatorname{pre\_inv}_{i}$.

在上面的步骤中,$\operatorname{pre\_inv}_i$ 即为 $i$ 的阶乘的逆元,在处理组合数时常用。

有另一种方法也可以处理逆元,时间复杂度相同,但不好记,而且证明麻烦,不需要掌握。

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

预处理组合数

预处理后,$\mathcal{O}(1)$ 地求解 $[1, n]$ 范围内的组合数,对大质数取模的结果。

记 $\operatorname{fac}_n=n!$,根据组合数的定义式:

$$
C_n^m=\frac{n!}{m!(n-m)!}=\frac{\operatorname{fac}_n}{\operatorname{fac}_m\times \operatorname{fac}_{n-m}}
$$

可以得到:

$$
C_n^m \bmod p = \operatorname{fac}_n (\operatorname{fac}_m)^{-1}(\operatorname{fac}_{n-m})^{-1}
$$

所以预处理出 $[1, n]$ 的阶乘,以及阶乘的逆元,每次即可 $\mathcal{O}(1)$ 求组合数。

int fac[], inv_fac[];
fac[0] = 1;
for(int i = 1; i <= n; i++)
	fac[i] = fac[i - 1] * i % p;
inv_fac[n] = power(fac[n], p - 1);
for(int i = n - 1; i >= 0; i--)
	inv_fac[i] = inv_fac[i + 1] * (i + 1) % p;

P4343 – SHOI2015 – 自动刷题机

题目信息

难度:提高+/省选-

算法:二分答案

题目描述

每秒,自动刷题机的代码生成模块会有两种可能的结果:

  1. 写了 $x$ 行代码
  2. 删除之前写的 $y$ 行代码。(如果 $y$ 大于当前代码长度则相当于全部删除。)

对于一个 OJ,每道题都需要且仅需要 $n$ 行代码。一旦在某秒结束时,其积累了大于等于 $n$ 行的代码,刷题机会在瞬间提交代码并新建一个文件。

题目给定 $l$ 关于写代码的日志信息,每条日志信息包含一个正整数 $x_i$,表示第 $i$ 秒时添加的代码行数。若 $x$ 为负数,则代表删除了代码。

自动刷题机一共切了 $k$ 道题,希望你计算 $n$ 可能的最小值和最大值。

$1\leq l\leq 10^5, -10^9\leq x_i\leq 10^9$.

题解

二分。

int check(int x) {
	int sum1 = 0, sum2 = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] > 0) sum1 += a[i];
		else if(sum1 + a[i] < 0) sum1 = 0;
		else sum1 += a[i];
		if(sum1 >= x) {
			sum1 = 0; sum2++;
		}
	}
	return sum2;
}

P4092 – HEOI2016/TJOI2016 – 树

题目信息

难度:提高+/省选-

算法:DFS序、线段树

题目描述

给定一颗有根树,根为 $1$ ,有以下两种操作:

  1. 标记操作:对某个结点打上标记。(在最开始,只有结点 $1$ 有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)
  2. 询问操作:询问某个结点最近的一个打了标记的祖先。(这个结点本身也算自己的祖先)

$1\leq n\leq 10^5, 1\leq q\leq 10^5$.

题解

预处理这棵树的DFS序,所有点权值初始为 $0$.

对 $x$ 点操作时,将 $x$ 点的权值赋为 $\operatorname{dfn}_{x}$

对 $x$ 点询问时,答案就是根结点 $1$ 到 $x$ 的路径上的最大值。

这个可以树剖+线段树维护,也可以只用线段树维护。

线段树做法

用线段树维护区间最大值。

由于子树内的所有节点 dfs 序相邻,每次操作时,在线段树区间修改 $x$ 的子树,取最大值即可。

每次询问时,在线段树上查询 $x$ 点在线段树上的权值即可。

#include <bits/stdc++.h>
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
	int ret = 0; char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch <= '9' && ch >= '0') {
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret;
}
int n, q;
struct Edge{
	int to, nxt;
}edge[MAXN << 1];
int head[MAXN], e_cnt = 0;
void add(int u, int v) {
	edge[++e_cnt].to = v;
	edge[e_cnt].nxt = head[u];
	head[u] = e_cnt;
}
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], rk[MAXN], top[MAXN], tot = 0;
void dfs1(int x, int father) {
	fa[x] = father;
	siz[x] = 1;
	for(int i = head[x]; i; i = edge[i].nxt) {
		int ne = edge[i].to; if(ne == father) continue;
		dfs1(ne, x);
		if(siz[ne] > siz[son[x]]) son[x] = ne;
		siz[x] += siz[ne];
	}
}
void dfs2(int x, int topf) {
	dfn[x] = ++tot; rk[tot] = x; top[x] = topf;
	if(!son[x]) return;
	dfs2(son[x], topf);
	for(int i = head[x]; i; i = edge[i].nxt) {
		int ne = edge[i].to;
		if(ne == fa[x]) continue;
		if(ne == son[x]) continue;
		dfs2(ne, ne);
	}
}
int c[MAXN << 2], lazy[MAXN << 2];
inline void push_up(int rt) {
	c[rt] = max(c[ls(rt)], c[rs(rt)]);
}
inline void build(int rt, int l, int r) {
	c[rt] = -1; lazy[rt] = -1;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(ls(rt), l, mid);
	build(rs(rt), mid + 1, r);
	push_up(rt);
}
void push_down(int rt, int l, int r) {
	if(lazy[rt] != -1) {
		lazy[ls(rt)] = max(lazy[ls(rt)], lazy[rt]);
		lazy[rs(rt)] = max(lazy[rs(rt)], lazy[rt]);
		c[ls(rt)] = max(c[ls(rt)], lazy[rt]);
		c[rs(rt)] = max(c[rs(rt)], lazy[rt]);
		lazy[rt] = -1;
	}
}
void update(int rt, int l, int r, int x, int y, int v) {
	if(x <= l && r <= y) {
		lazy[rt] = max(lazy[rt], v);
		c[rt] = max(c[rt], v);
		return;
	}
	int mid = (l + r) >> 1;
	push_down(rt, l, r);
	if(x <= mid) update(ls(rt), l, mid, x, y, v);
	if(y > mid) update(rs(rt), mid + 1, r, x, y, v);
	push_up(rt);
}
int query(int rt, int l, int r, int x, int y) {
	if(x <= l && r <= y) {
		return c[rt];
	}
	int mid = (l + r) >> 1;
	push_down(rt, l, r);
	int ret = -1;
	if(x <= mid) ret = max(ret, query(ls(rt), l, mid, x, y));
	if(y > mid) ret = max(ret, query(rs(rt), mid + 1, r, x, y));
	push_up(rt);
	return ret;
}
int main() {
	n = read(); q = read();
	for(int i = 2; i <= n; i++) {
		int u = read(), v = read();
		add(u, v); add(v, u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	build(1, 1, n);
	update(1, 1, n, 1, n, dfn[1]);
	while(q--) {
		char cmd; cin >> cmd; int num = read();
		if(cmd == 'Q') {
			printf("%d\n", rk[query(1, 1, n, dfn[num], dfn[num])]);
		} else {
			update(1, 1, n, dfn[num], dfn[num] + siz[num] - 1, dfn[num]);
		}
	}
	return 0;
}

 

P4588 – TJOI2018 – 数学计算

题目信息

难度:提高+/省选-

算法:线段树

题目描述

有一个数 $x$,初始值为 $1$,现在有 $Q$ 次操作,操作分为两种类型:

  1. 给定 $m$,将 $x$ 变为 $x\times m$,并输出 $x\bmod M$,
  2. 给定 $pos$,将 $x$ 变为 $x$ 除以第 $pos$ 次所乘的数(保证第 $pos$ 次操作一定为类型 $1$,对于每个类型 $1$ 的操作最多被除一次),并输出 $x\bmod M$.

$M$ 是题目给定的常数。

对于 $20\%$ 的数据,$1\leq q\leq 500$,

对于 $100\%$ 的数据,$1\leq q\leq 10^5, 1 < M\leq 10^9$.

$\rm{Subtask}$ $1$

对于 $1\leq q\leq 500$ 的数据。

记录第 $i$ 次操作输入的数 $m_i$,对这次操作是否被除掉作标记。

每次询问的时候,扫一遍 $m$ 数组,计算乘积,复杂度 $\mathcal{O}(q^2)$.

$\rm{Subtask}$ $2$

对于 $1\leq q\leq 10^5$ 的数据,不难发现,上面算法的时间复杂度瓶颈在于求 $q$ 个数的乘积。

直接把询问编号作为横坐标,作为线段树维护即可将复杂度降到 $\mathcal{O}(q\log q)$.

#include <bits/stdc++.h>
#define int long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
const int MAXN = 1e5 + 10;
int T, mod;
int c[MAXN << 2], lazy[MAXN << 2];
void push_up(int rt) {
	c[rt] = c[ls(rt)] * c[rs(rt)] % mod;
}
void build(int rt, int l, int r) {
	if(l == r) {
		c[rt] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(rt), l, mid);
	build(rs(rt), mid + 1, r);
	push_up(rt);
}
void update(int rt, int l, int r, int x, int v) {
	if(l == x && r == x) {
		c[rt] = v;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) update(ls(rt), l, mid, x, v);
	if(x > mid) update(rs(rt), mid + 1, r, x, v);
	push_up(rt);
}
signed main() {
	scanf("%lld", &T);
	while(T--) {
		int Q; scanf("%lld%lld", &Q, &mod);
		build(1, 1, Q);
		for(int i = 1; i <= Q; i++) {
			int opt, m; scanf("%lld%lld", &opt, &m);
			if(opt == 1) {
				update(1, 1, Q, i, m);
				printf("%lld\n", c[1]);
			} else {
				update(1, 1, Q, m, 1);
				printf("%lld\n", c[1]);
			}
		}
	}
	return 0;
}

P5677 – GZOI2017 – 配对统计

题目信息

难度:提高+/省选-

算法:数学、树状数组

题意

给定一个数列 $a_1, a_2, \cdots, a_n$.

定义在有序数对 $(x, y)$ 上的“好对”:对于 $a_x$,$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。

给定 $q\leq 3\times 10^5$ 组询问,每次询问一个区间 $[l, r]$ 中,有多少个好对。

题目求:每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和,即:

$$
\sum_{i=1}^{m}Ans_i\times i
$$

分析

关于匹配

任何一个好对 $(x, y)$,都满足 $|a_x-a_y|\leq |a_x-a_i|(i\neq x)$.

并且通过数据范围可以发现:$\forall i\neq j$ 都有 $a_i\neq a_j$,所以当 $x$ 固定时,确定 $y$ 的方法是非常自然的。

将 $a$ 数组排序,排序后的数组为 $b$,不妨设 $a_x$ 在 $b$ 中的下标为 $t$,那么 $a_y$ 在 $b$ 中的下标只可能为 $t-1$ 和 $t+1$.

具体地:

  • 如果 $|b_t-b_{t-1}|<|b_{t+1}-b_{t}|$,也就是 $b_{t-1}$ 距离 $b_t$ 更近,那么 $a_y$ 在 $b$ 中的下标为 $t-1$;
  • 如果 $|b_t-b_{t-1}|>|b_{t+1}-b_{t}|$,此时 $b_{t+1}$ 距离 $b_t$ 最近,$a_y$ 在 $b$ 中的下标为 $t+1$;
  • 如果 $|b_t-b_{t-1}|=|b_{t+1}-b_{t}|$,$a_y$ 在 $b$ 中的下标为 $t-1$ 或 $t+1$.

总之,我们可以非常容易地在 $O(n\log n)$ 复杂度内,对于每个 $x$,找到能与其构成好的配对的 $y$.

关于询问

思路

现在的问题是如何统计答案。

因为题目只要求输出所有询问的和,于是想到将询问离线下来。对于每个好对,统计有多少个询问完全覆盖了它。这个好对对于最终答案的贡献就是:所有覆盖它的询问的编号之和

对于这个问题,容易想到将所有询问排序,之后用树状数组维护,具体方法:

方法

从左到右枚举 $[1, n]$,假设枚举到了 $i$.

对于 $i$,我们已经计算过与其匹配的数,在 $a$ 中的下标 $y$,如果 $y > i$,那么所有左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问都能包含这个好对。

再考虑答案的形式 $\sum_{i=1}^{m}Ans_i\times i$,我们现在要求:左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问的编号和,使用树状数组维护。

于是考虑将询问按照左端点排序,在枚举到 $i$ 的时候,把所有左端点 $l\leq i$ 的询问加入到树状数组中,把树状数组的位置 $r$ 的权值加上这个询问的编号 $num$.

这样,$(i, y)$ 的贡献就等价于:树状数组中 $[y, n]$ 的区间和。

如果与 $i$ 匹配的 $y < i$,在上面的方法中并没有包含到。所以我们再反向枚举一遍 $i$,方法相同。将右端点 $r\geq i$ 的询问加入树状数组,每次的贡献为树状数组中 $[1, y]$ 的区间和。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int c[MAXN];
int n, m;
int lowbit(int x) {
	return x & (-x);
}
void update(int x, int k) {
	for(int i = x; i <= n; i += lowbit(i)) {
		c[i] += k;
	}
}
int query(int x) {
	int ret = 0;
	for(int i = x; i > 0; i -= lowbit(i)) {
		ret += c[i];
	}
	return ret;
}
int query2(int x) {
	return query(n) - query(x - 1);
}
int a[MAXN];
struct Node{int num, val;} b[MAXN];
bool cmp(Node A, Node B) {
	return A.val <= B.val;
}
struct Query{int val, l, r;} q[MAXN];
bool cmp2(Query A, Query B) {
	return A.r >= B.r;
}
bool cmp3(Query A, Query B) {
	return A.l <= B.l;
}
int rk[MAXN];
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		b[i].val = a[i]; b[i].num = i;
	}
	sort(b + 1, b + n + 1, cmp);
	for(int i = 1; i <= n; i++) {
		rk[b[i].num] = i;
	}
	for(int i = 1; i <= m; i++)  {
		q[i].val = i;
		scanf("%lld%lld", &q[i].l, &q[i].r);
	}
	sort(q + 1, q + m + 1, cmp2);
	int ans = 0;
	b[0].val = -inf; b[n + 1].val = inf;
	for(int i = n, j = 1; i >= 1; i--) {
		while(q[j].r >= i && j <= m) {
			update(q[j].l, q[j].val);
			j++;
		}
        //下面六行:判断 t-1 和 t+1,哪个距离 t 更近,能与 t 构成好的匹配。
		if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] - 1].num < i) ans += query(b[rk[i] - 1].num);
		}
		if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] + 1].num < i) ans += query(b[rk[i] + 1].num);
		}
	}
	sort(q + 1, q + m + 1, cmp3);
	memset(c, 0, sizeof(c));
	for(int i = 1, j = 1; i <= n; i++) {
		while(q[j].l <= i && j <= m) {
			update(q[j].r, q[j].val);
			j++;
		}
		if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] - 1].num > i) ans += query2(b[rk[i] - 1].num);
		}
		if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
			if(b[rk[i] + 1].num > i) ans += query2(b[rk[i] + 1].num);
		}
	}
	cout << ans << endl;
	return 0;
}

P5675 – GZOI2017 – 取石子游戏

题目信息

难度:提高+/省选-

算法:博弈论、动态规划

题目分析

显然,可以看出这个问题与Nim类游戏相关。Nim类游戏先手必胜,当且仅当每堆石子的数量的异或和不为 $0$

所以Alice先手必败仅有两种情况:

  1. 异或和为 $0$;
  2. 异或和不为 $0$,但Alice选择的第一堆石子无法使异或和变成0.

第一种情况容易处理,对于第二种情况,可以发现:只有指定选的第一堆石子数量,大于其他堆的异或和时,才能够做到:删去一堆棋子,异或和也不为 $0$.

综合两种情况,只要其他 $n-1$ 堆石子的异或和 $\geq $ 第一堆石子数量即可。

所以就可以枚举Alice先选择哪一堆 $i$,然后每次DP处理:有多少种选择方法使得异或和等于 $k$.

通过数学方法进行分析,容易得到上一段中的 $k\in[0, 256]$,于是直接二维 DP 即可。

DP状态:$f_{j, k}$ 表示,当固定一堆不选时,其余的前 $j$ 堆,异或和为 $k$ 的方案数量。

每次从上一行转移过来,具体看代码就行了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 208, MAXJ = 270, mod = 1e9 + 7; 
int n;
int a[MAXN];
int dp[MAXN][MAXJ]; //dp[j][k]表示,当固定一堆不选时,其余的前j堆,异或和为k的方案数量 
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	int ans = 0; dp[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int k = 0; k < 256; k++) {
				if(i == j) dp[j][k] = dp[j-1][k];
				else dp[j][k] = (dp[j - 1][k] + dp[j - 1][k ^ a[j]]) % mod;
			} 
		}
		for(int j = a[i]; j < 256; j++) {
			ans = (ans + dp[n][j]) % mod;
		}
	}
	cout << ans << endl;
	return 0;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();