2021CCPC新疆省赛题解BDEFGHIJK

K. chino with c language

题意

$memcpy()$不会检查源地址范围与目标地址范围是否重叠,它只从左往右复制每个字节;$memmove()$会检查源地址范围与目标地址范围是否重叠,若发生重叠,它会通过特殊处理使得目的地址填充上与源地址相同的数据.设两函数调用都需要三个参数$p_1,p_2,l$,分别表示源地址、目的地址、要复制的字节数是.如对下标从$1$开始的字符串"abcdefg"调用$memcpy(1,3,5)$将得到"ababab",而调用$memmove(1,3,5)$将得到"ababcde".

给定长度为$n(1\le n\le 1\mathrm{e}5)$的、只包含小写英文字母的字符串$s$,给定参数$p_1,p_2,l(1\le p_1,p_2,l\le n,1\le p_1+l-1,p_2+l-1\le n)$,分别输出调用$memcpy(p_1,p_2,l)$和$memmove(p_1,p_2,l)$的结果.

代码 -> 2021CCPC新疆省赛-K(模拟)

const int MAXN = 1e5 + 5;
int n;
char s[MAXN], t[MAXN];

void solve() {
	cin >> n >> s + 1;
	strcpy(t + 1, s + 1);
	int p1, p2, l; cin >> p1 >> p2 >> l;
	for (int i = 0; i < l; i++) t[p2 + i] = s[p1 + i];
	for (int i = 0; i < l; i++) s[p2 + i] = s[p1 + i];
	cout << s + 1 << endl << t + 1;
}

int main() {
	solve();
}

J. do NOT a=2b

题意

称一个序列是坏的,如果其中存在两个元素$a,bs.t.a=2b$.给定一个长度为$n(1\le n\le 1\mathrm{e}5)$的序列$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}6)$,删除尽量少的元素使得它不是坏的,输出最少要删除的元素的个数.

思路

$dp[a][0]$表示不删除值为$a$的元素,$dp[a][1]$表示删除所有值为$a$的元素.设值为$a$的元素个数为$cnt[a]$.

注意到$a$只能是偶数,状态转移方程: { a 为奇数 { d p [ a ] [ 0 ] = 0 , 因为 a 2 不是一个整数 d p [ a ] [ 1 ] = c n t [ a ] , 即要删除所有值为 a 的元素 a 为偶数 { d p [ a ] [ 0 ] = d p [ b ] [ 1 ] , 即不删 a 就要删除所有值为 b = a 2 的元素 d p [ a ] [ 1 ] = min ⁡ { d p [ b ] [ 0 ] , d p [ b ] [ 1 ] } + c n t [ a ] , 删除 a 后 b 可删可不删 \begin{cases}a为奇数\begin{cases}dp[a][0]=0,因为\dfrac{a}{2}不是一个整数 \\ dp[a][1]=cnt[a],即要删除所有值为a的元素\end{cases} \\ a为偶数\begin{cases}dp[a][0]=dp[b][1],即不删a就要删除所有值为b=\dfrac{a}{2}的元素 \\ dp[a][1]=\min\{dp[b][0],dp[b][1]\}+cnt[a],删除a后b可删可不删\end{cases}\end{cases} ⎩ ⎨ ⎧​a为奇数{dp[a][0]=0,因为2a​不是一个整数dp[a][1]=cnt[a],即要删除所有值为a的元素​a为偶数{dp[a][0]=dp[b][1],即不删a就要删除所有值为b=2a​的元素dp[a][1]=min{dp[b][0],dp[b][1]}+cnt[a],删除a后b可删可不删​​.

注意到每个$dp[a]$都包含了$dp[b]$的最优解,故只需对所有$2a>1\mathrm{e}6$的$a$统计答案即可.

代码 -> 2021CCPC新疆省赛-J(线性DP)

const int MAXN = 1e6 + 5;
int n;
map<int, int> cnt;  // cnt[b]表示值为b的元素个数
int dp[MAXN][2];  // dp[a][0]表示不删除值为b的元素,dp[a][1]表示删除所有值为b的元素

void solve() {
	cin >> n;
	while (n--) {
		int a; cin >> a;
		cnt[a]++;
	}

	for (int a = 1; a <= 1e6; a++) {
		if (a & 1) {
			dp[a][0] = 0;  // b/2不是整数
			dp[a][1] = cnt[a];  // 删除所有值为b的元素
		}
		else {
			dp[a][0] = dp[a / 2][1];  // 不删a就要删除所有值为b=a/2的元素
			dp[a][1] = min(dp[a / 2][0], dp[a / 2][1]) + cnt[a];  // 删除a后b可删可不删
		}
	}

	int ans = 0;
	for (int a = 5e5 + 1; a <= 1e6; a++)  // 对所有2a>1e6的a统计答案
		ans += min(dp[a][0], dp[a][1]);
	cout << ans;
}

int main() {
	solve();
}

E. is the order a rabbit ??

题意

兔子交易市场有规则:①市场只在上午和下午开放,每天的上午、下午的兔子交易价格可能不同;②每天至多只能买一只兔子,每只兔子只能买一次;③每天只能卖一只兔子.某人到该交易市场经营$n$天,设他有足够的钱可用于购买兔子,第一天前和最后一天后他都没有兔子,问他最多能赚多少钱.

第一行输入一个整数$n(1\le n\le 1\mathrm{e}5)$.接下来$n$行每行输入两个整数$a,b(1\le a,b\le 1\mathrm{e}9)$,分别表示该天上午和下午兔子的价格.

思路

从最后一天往前推,维护当前的最高价格$maxprice$.

设某天上午和下午的价格分别是$u,v$.

(1)若 m a x p r i c e ≥ max ⁡ { u , v } maxprice\geq \max\{u,v\} maxprice≥max{u,v},则以当天的最低价格 min ⁡ { u , v } \min\{u,v\} min{u,v}买入,以$maxprice$卖出,利润 m a x p r i c e − min ⁡ { u , v } maxprice-\min\{u,v\} maxprice−min{u,v}.

(2)若 m a x p r i c e < max ⁡ { u , v } maxprice<\max\{u,v\} maxprice<max{u,v}:

​ ①若$u<v$,则当天上午买入,下午卖出,利润$v-u$.

​ ②若$u\ge v$且$maxprice>v$,则以$maxprice$买入,当天下午卖出,利润$maxprice-v$.

代码 -> 2021CCPC新疆省赛-E(思维)

const int MAXN = 1e5 + 5;
int n;
pii prices[MAXN];

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> prices[i].first >> prices[i].second;

	int maxprice = 0;  // 当前的最高价格
	ll ans = 0;
	for (int i = n; i >= 1; i--) {
		auto [u, v] = prices[i];
		if (maxprice >= max(u, v)) ans += maxprice - min(u, v);
		else {
			if (u < v) ans += v - u;
			else if (maxprice > v) ans += maxprice - v;
			
			maxprice = max(u, v);  // 更新最高价格
		}
	}
	cout << ans;
}

int main() {
	solve();
}

G. cocktail with snake

题意

某游戏界面可视为一个$n\times m$的网格.初始时玩家在点$(1,1)$处,先向右走到$(n,1)$,再向上走到$(n,2)$,再向左走到$(1,2)$,再向上走到$(1,3),\cdots$,重复该过程直至走到终点.每一步玩家可按路线移动$1$个单位长度,求移动$k$步后到达的点与起点的Manhattan距离.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入三个整数 n , m , k    ( 1 ≤ n , m ≤ 1 e 18 , 0 ≤ k ≤ min ⁡ { n m − 1 , 1 e 18 } ) n,m,k\ \ (1\leq n,m\leq 1\mathrm{e}18,0\leq k\leq \min\{nm-1,1\mathrm{e}18\}) n,m,k  (1≤n,m≤1e18,0≤k≤min{nm−1,1e18}).

思路

如上图,将$(1,1)\to (3,1)\to (3,2)$视为一段,将$(3,2)\to (1,2)\to (1,3)$视为一段.显然移动$k$步后在第$k^{\prime }=\lfloor \frac{k}{n}\rfloor$段,且$k^{\prime }$为奇数时向右走,为偶数时向左走.显然向上走的距离$\Delta y=k^{\prime }$,$\Delta x$只需考察$k\%n$和行进方向即可.

代码 -> 2021CCPC新疆省赛-G(思维)

void solve() {
	ll n, m, k; cin >> n >> m >> k;

	ll r = k % n;
	k/=n;

	ll ans = k;  // Δy
	if (k & 1) ans += (n - r - 1);
	else ans += r;
	cout << ans << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}

I. chino with mates

题意

给定一个长度为$n(1\le n\le 1\mathrm{e}5)$的序列$a_1,\cdots ,a_n(-1\mathrm{e}9\le a_i\le 1\mathrm{e}9)$和一个长度为$m(1\le m\le 1\mathrm{e}5)$的序列$b_1,\cdots ,b_n(-1\mathrm{e}9\le b_i\le 1\mathrm{e}9)$.称数对$(a_i,b_j)$是好的,如果$a_i{b}_j\in [l,r](1\le i\le n,1\le j\le m,-1\mathrm{e}9\le l\le r\le 1\mathrm{e}9)$.问有几个好的数对$(a,b)$.

思路

先将$b[]$升序排列.对每个$a_i$,若$a_i{b}_j\in [l,r]$,则$b_j$在$\frac{l}{a_i}$和$\frac{r}{a_i}$之间.

令$left=\min \left\{\frac{l}{a_i},\frac{r}{a_i}\right\},right=\max \left\{\frac{l}{a_i},\frac{r}{a_i}\right\}$,在$b[]$上二分出第一个$\ge left$的位置$po{s}_1$和第一个$>right$的位置$po{s}_2$,

​ 则$a_i$对答案的贡献为$po{s}_2-po{s}_1$.

代码 -> 2021CCPC新疆省赛-I(思维)

void solve() {
	int n, m; cin >> n >> m;
	vi a(n), b(m);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	int l, r; cin >> l >> r;

	sort(all(b));

	ll ans = 0.;
	for (int i = 0; i < n; i++) {
		double left = (double)l / a[i], right = (double)r / a[i];
		if (cmp(left, right) > 0) swap(left, right);

		int pos1 = lower_bound(all(b), left) - b.begin();
		int pos2 = upper_bound(all(b), right) - b.begin();
		ans += pos2 - pos1;
	}
	cout << ans;
}

int main() {
	solve();
}

F. chino with ball

题意

$x$轴上有编号$1\sim n$的$n$个球,其中第$i(1\le i\le n)$个球的初位置坐标为$p_i$,初速度为$v_i$(以向右为$x$轴正方向).球的体积忽略不计,且两球碰撞时会交换速度.求$k$秒后每个球的位置.

第一行输入两个整数$n,k(1\le n\le 1\mathrm{e}5,0\le k\le 1\mathrm{e}9)$.接下来$n$行每行输入两个整数 p i , v i    ( − 1 e 9 ≤ p i ≤ 1 e 9 , v i ∈ { − 1 , 0 , 1 } ) p_i,v_i\ \ (-1\mathrm{e}9\leq p_i\leq 1\mathrm{e}9,v_i\in\{-1,0,1\}) pi​,vi​  (−1e9≤pi​≤1e9,vi​∈{−1,0,1}).数据保证所有球的初位置不同.

输出$n$个整数,其中第$i(1\le i\le n)$个数表示编号为$i$的球$k$秒后的位置.

思路

注意到两球交换速度可视为互相穿过了对方,故球$k$秒后的位置即$p_i+k{v}_i$.但题目要求按原编号输出球$k$秒后的位置,互相穿过后继续向前的球未必是原来的球,可将所有初位置和末位置都升序排列,这时顺序一一对应.

代码 -> 2021CCPC新疆省赛-F(思维)

void solve() {
	int n, k; cin >> n >> k;
	vii start(n + 1);  // 初位置
	vi end(n + 1);  // 末位置
	for (int i = 1; i <= n; i++) {
		int p, v; cin >> p >> v;
		start[i] = { p,i };
		end[i] = p + k * v;
	}

	sort(start.begin() + 1, start.end());
	sort(end.begin() + 1, end.end());

	vi ans(n + 1);
	for (int i = 1; i <= n; i++) ans[start[i].second] = end[i];
	for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}

int main() {
	solve();
}

B. cocktail with hearthstone

题意

某游戏的规则:①每个玩家的战绩用数对$(a,b)$表示,其中$a$表示胜利场数,$b$表示失败场数.初始时战绩为$(0,0)$;②每轮胜利的玩家$a++$,失败的玩家$b++$,没有平局;③每轮对战的两个人的战绩相同,设为$(a,b)$,则该轮结束后会产生一个$(a+1,b)$和一个$(a,b+1)$;④若有玩家胜利$n$次或失败$m$次,他将自动退出游戏.

现安排了$2^{n+m}$个玩家,保证所有玩家在退出游戏前都能找到对手.现有$q$个询问,每个询问给定$a,b$,设战绩$(a,b)$符合退出游戏的要求,问有多少个人以战绩$(a,b)$退出游戏,答案对$1\mathrm{e}9+7$取模.

第一行输入三个整数$n,m,q(1\le m<n\le 2\mathrm{e}5,1\le q\le 2\mathrm{e}5)$.接下来$q$行每行输入两个整数$a,b(0\le a\le n,0\le b\le m)$,数据保证$a=n$或$b=m$.

对每个询问,输出以战绩$(a,b)$退出游戏的人数,答案对$1\mathrm{e}9+7$取模.

思路

游戏过程:$(0,0)\{\begin{array}{l}(1,0)\{\begin{array}{l}(2,0)\{\begin{array}{l}(3,0)\\ (2,1)\end{array}\\ (1,1)\{\begin{array}{l}(2,1)\\ (1,2)\end{array}\end{array}\\ (0,1)\{\begin{array}{l}(1,1)\{\begin{array}{l}(2,1)\\ (1,2)\end{array}\\ (0,2)\{\begin{array}{l}(1,2)\\ (0,3)\end{array}\end{array}\end{array}$.

第$0$层:$(0,0)$有$1$个.

第$1$层:$(1,0)$有$1$个、$(0,1)$有$1$个.

第$2$层:$(2,0)$有$1$个、$(1,1)$有$2$个、$(0,2)$有$1$个.

第$3$层:$(3,0)$有$1$个、$(2,1)$有$3$个、$(1,2)$有$3$个、$(0,3)$有$1$个.

显然个数的规律为杨辉三角.

考察$a=n$的情况.显然$(a,b)$在第$(a+b)$层,且在该层数量占比$\frac{C_{a+b}^a}{2^{a+b}}$.但注意到$a=n$时,到达$(a,b)$前$(a,b-1),(a,b-2),\cdots$早已退出游戏,故能转移到$(a,b)$的合法状态只有$(a-1,b)$,故占比应取$\frac{C_{a+b-1}^{a-1}}{2^{a+b}}$.总人数$2^{n+m}$,故$ans=2^{n+m-a-b}\cdot C_{a+b-1}^{a-1}$.同理$b=m$时,$ans=2^{n+m-a-b}\cdot C_{a+b-1}^{b-1}$.

注意特判$(a,b)=(n,m)$的情况,因无任何合法状态能转移到$(n,m)$,故$ans=0$.

代码 -> 2021CCPC新疆省赛-B(组合计数)

const int MAXN = 4e5 + 5;
const int MOD = 1e9 + 7;
int fac[MAXN], ifac[MAXN];

void init() {  // 预处理阶乘及其逆元
	fac[0] = 1;
	for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;

	ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2, MOD);
	for (int i = MAXN - 1; i; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;
}

int C(int n, int m) {  // 组合数C(n,m)
	return (ll)fac[n] * ifac[m] % MOD* ifac[n - m] % MOD;
}

void solve() {
	init();

	int n, m; cin >> n >> m;
	CaseT{
		int a,b; cin >> a >> b;
		
		if (a == n && b == m) {
			cout << 0 << endl;
			continue;
		}

		int ans = 0;
		if (a == n) ans = qpow(2, n + m - a - b, MOD) * C(a + b - 1, a - 1) % MOD;
		else ans = qpow(2, n + m - a - b, MOD) * C(a + b - 1, b - 1) % MOD;
		cout << ans << endl;
	}
}

int main() {
	solve();
}

H. cocktail with pony

题意

$x$轴的线段$[1,n]$上A在追B,其中A初位置为$x_1$,每次走$v_1$步;B初位置为$x_2$,每次走$v_2$步.B与A交替移动,B先移动,即B在奇数轮移动,A在偶数轮移动,且两人的移动都不能超出线段边界.若有某一瞬间A和B在同一位置,则A抓住B.B想尽量晚被抓住,A想尽快抓住B,两人都采取最优策略,问几轮后A能抓住B.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入五个整数$n,v_1,v_2,x1,x_2(2\le n\le 1000,1\le v_1,v_2\le 1\mathrm{e}9,1\le x_1,x_2\le n,x_1\ne x_2)$.

思路

若初始时$x_1<x_2$,令$x_1=n-x_1+1,x_2=n-x_2+1$,统一为两人都往左走.

模拟.注意为保证B尽量晚被抓住,其位置应尽量靠左,则B移动到边界$x=1$处时若还有多余的步数会左右横跳,最终停在$x=1$或$x=2$处.

代码 -> 2021CCPC新疆省赛-H(思维+模拟)

void solve() {
	int n, v1, v2, x1, x2; cin >> n >> v1 >> v2 >> x1 >> x2;
	
	if (x1 < x2) x1 = n - x1 + 1, x2 = n - x2 + 1;  // 保证两人都往左走

	int ans = 1;
	while (true) {
		if (ans & 1) {  // B走
			if (x2 == 1 && x1 == 2) break;  // B的路被堵死
			
			if (x2 - v2 >= 1) x2 -= v2;  // B完整地向左走
			else if (v2 - x2 & 1) x2 = 1;  // B在边界附近左右横跳,最终停在x=1
			else x2 = 2;  // B在边界附近左右横跳,最终停在x=2
		}
		else {  // A走
			if (x1 - x2 <= v1) break;  // 下一步抓到

			x1 -= v1;  // A完整地向左走
		}

		ans++;
	}
	cout << ans << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}

D. cocktail with swap

题意

给定一个长度为$n$的字符串$s$,下标从$1$开始.现有操作:选择下标$i,j\in [1,n]s.t.l\le |i-j|\le r$,交换$s_i$和$s_j$.求若干次(可能为零次)操作后能得到的字典序最小的字符串.

第一行输入三个整数$n,l,r(2\le n\le 1\mathrm{e}5,1\le l\le r<n)$.

思路I

①$l=r$时,只能跳着排序.

②$l\le \lfloor \frac{n}{2}\rfloor$时,显然能做到交换相邻元素,则能得到的字典序最小的字符串即原串升序排列的结果.

③$l>\lfloor \frac{n}{2}\rfloor$时,分为两段$[1,n-l],[l+1,n]$.

对情况①和③,预处理出所有能动的字符,对它们排序后放回原串即可.

代码I -> 2021CCPC新疆省赛-D(思维+模拟)

const int MAXN = 1e5 + 5;
char s[MAXN], tmp[MAXN];  // 原串、临时串

void solve() {
	int n, l, r; cin >> n >> l >> r >> s;

	if (l == r) {
		for (int i = 0; i < l; i++) {
			// 预处理出能动的字符
			int m = 0, j = i;
			while (j < n) tmp[m++] = s[j], j += l;
			sort(tmp, tmp + m);

			// 结果放回原串
			m = 0, j = i;
			while (j < n) s[j] = tmp[m++], j += l;
		}
	}
	else if (l <= n / 2) sort(s, s + n);
	else {
		// 预处理出能动的字符
		int m = 0;
		for (int i = 0; i < n - l; i++) tmp[m++] = s[i];
		for (int i = l; i < n; i++) tmp[m++] = s[i];
		sort(tmp, tmp + m);

		// 结果放回原串
		m = 0;
		for (int i = 0; i < n - l; i++) s[i] = tmp[m++];
		for (int i = l; i < n; i++) s[i] = tmp[m++];
	}
	cout << s;
}

int main() {
	solve();
}

思路II

用一个并查集$dsu2$维护每个起点开始的区间中能动的下标,枚举每个起点$i$,将以其开始的区间中能动的下标$j$对应的集合合并.朴素做法时间复杂度$O(n^2)$,会TLE.

考虑优化,注意到可用另一个并查集$dsu1$维护指针$j$下一步跳到的位置,保证每次$j$跳到下一段的开头,时间复杂度$O(n)$.

代码II -> 2021CCPC新疆省赛-D(思维+并查集)

const int MAXN = 1e5 + 5;
int n, l, r; 
string s;

struct DSU {
	int n;  // 元素个数
	int fa[MAXN];  // fa[]数组
	int siz[MAXN];  // 集合大小

	void init() {  // 初始化fa[]、siz[]
		for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
	}

	int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

	bool merge(int x, int y) {  // 返回合并是否成功,即初始时是否不在同一集合中
		x = find(x), y = find(y);
		if (x != y) {
			if (siz[x] > siz[y]) swap(x, y);  // 保证x所在的集合小

			fa[x] = y;
			siz[y] += siz[x];
			return true;
		}
		else return false;
	}
}dsu1, dsu2;

void solve() {
	cin >> n >> l >> r >> s;

	dsu1.n = n; dsu1.init();  // 维护维护j跳的位置
	dsu2.n = n; dsu2.init();  // 维护每个起点开始的区间中能动的下标

	vb vis(n);
	for (int i = 0; i < n; i++) {  // 枚举起点
		for (int j = i + l; j <= i + r && j < n; j = dsu1.find(j) + 1) {  // j跳到下一段的开头
			dsu2.fa[dsu2.find(j)] = dsu2.fa[dsu2.find(i)];
			vis[j] = true;

			if (vis[j - 1]) dsu1.fa[dsu1.find(j - 1)] = dsu1.fa[dsu1.find(j)];
		}
	}

	// 预处理每个起点开始的区间中出能动的字符的下标
	vector<vi> son(n);
	for (int i = 0; i < n; i++) son[dsu2.find(i)].push_back(i);

	for (int i = 0; i < n; i++) {
		if (son[i].size()) {
			// 预处理出能动的字符
			string t;
			for (auto j : son[i]) t.push_back(s[j]);
			sort(all(t));

			// 结果放回原串
			int idx = 0;
			for (auto j : son[i]) s[j] = t[idx++];
		}
	}
	cout << s;
}

int main() {
	solve();
}