2024CCPC郑州邀请赛暨河南省赛(A,B,C,D,F,G,H,J,K,L,M)

2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest

2024 年中国大学生程序设计竞赛全国邀请赛(郑州)暨第六届 CCPC 河南省大学生程序设计竞赛

比赛链接

这场的题说实话难度其实都不大(除了 E E E I I I),但是做法很固定,考思维,想到了一拍脑袋就出,想不到就寄,因此很多强队都翻车了。这场 13 13 13 题其中的 11 11 11 题我觉得都可以赛时出。

是时候祭出这张图了:
在这里插入图片描述


Problem A. Once In My Life

题意:

对于小 A A A 而言,数位包含 1 ∼ 9 1 ∼ 9 19,并且至少两个数位是 d ( 1 ≤ d ≤ 9 ) d(1 ≤ d ≤ 9) d1d9十进制正整数都是幸运数。

d = 3 d = 3 d=3 时,显然 1234567890123 1234567890123 1234567890123 是小 A A A 的幸运数,但 987654321 987654321 987654321 因为数位 3 3 3 仅出现了一次而不是幸运数, 998244353 998244353 998244353 因为缺少数位 1 , 6 , 7 1, 6, 7 1,6,7 而不是幸运数。

现在小 A A A 有一个正整数 n n n,并给出正整数 d d d。他想找到正整数 k k k 使得二者的乘积 n ⋅ k n · k nk 是幸运数。

你能用计算机辅助他的计算吗?

输出保证 k ≤ 2 ∗ 1 0 10 k\le 2*10^{10} k21010

思路:

本质是个构造题,需要一点点数论知识。

我们想要 n k nk nk 得到的数里有 123456789 123456789 123456789 和额外的一个 d d d,那么我们就构造出来,假设结果是 123456789 d 123456789d 123456789d,构造得到的数不一定是 n n n 的倍数,但是我们可以加一些数让它成为倍数,不过这就破坏了这十个位置上的数字。

考虑到当 k k k 乘以 10 10 10 的时候, 123456789 d 123456789d 123456789d 也会乘以 10 10 10,相当于整体向左移动一位,低位就空出来了,这时我们给低位增加一些数字的时候,就不会影响到高处的十个位置了。最简单的想法就是反正 n ≤ 1 0 8 n\le10^8 n108,所以我们只要低八位空出来就行了,这时就会得到 123456789 d 00000000   m o d   n = x 123456789d00000000\bmod n=x 123456789d00000000modn=x,我们再加上 ( n − x )   m o d   n (n-x)\bmod n (nx)modn 就是乘积,除以 n n n 就是 k k k 了。

不过题目要求 k ≤ 2 ∗ 1 0 10 k\le 2*10^{10} k21010,当 n ≤ 1 0 7 n\le 10^7 n107 时,上面构造出来的数铁定 > 2 ∗ 1 0 10 \gt 2*10^{10} >21010。考虑到我们没必要低位留 8 8 8 位,比如 n n n 只有一位数的时候,我们低位就只留一位就行了,如果 n n n t t t 位数,那么我们低位就只留 t t t 位就可以了,这样构造出来的数 k k k 就是一个小于 2 ∗ 1 0 10 + t − 1 2*10^{10+t-1} 21010+t1 的数,除以一个大于 1 0 t − 1 10^{t-1} 10t1 的数,得到的数肯定小于 2 ∗ 1 0 10 2*10^{10} 21010

code:

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

int T;
ll n,d;
ll pw[20];

int main(){
	cin.tie(0)->sync_with_stdio(false);
	
	pw[0]=1;
	for(int i=1;i<=18;i++)pw[i]=pw[i-1]*10;
	
	cin>>T;
	while(T--){
		cin>>n>>d;
		int i=0;
		while(pw[i]<n)i++;
		ll ans=123456789ll*pw[i+1]+d*pw[i];
		ll x=(pw[i]-ans%n)%pw[i];
		cout<<(ans+x)/n<<'\n';
	}
	return 0;
}

Problem B. 扫雷 1

题意:

T0xel 喜欢玩扫雷,但是他玩的扫雷游戏有名为 “地雷探测器” 的特殊道具。

具体来说,T0xel 会进行 n n n 轮扫雷。每轮扫雷开始之前,T0xel 会获得 1 1 1 枚扫雷币。扫雷币在每轮扫雷结束后不会回收,可以保留至下一轮扫雷。T0xel 知道,在第 i i i ( 1 ≤ i ≤ n ) (1 ≤ i ≤ n) 1in扫雷中,花费 c i c_i ci 枚扫雷币可以购买一个地雷探测器,清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。

现在 T0xel 想知道,在这 n n n 轮扫雷中最多能购买多少个地雷探测器呢?

思路:

签到,是个贪心。因为我们在一轮中某个探测器可以买任意次,所以如果后面的轮中如果有一个很便宜的探测器,那么我们直接留着钱只买这个就行了,能买多少就买多少。如果后面有一个稍贵的探测器,因为我们不能买前面轮次的探测器,所以我们也有可能买这个探测器。

这种如果有一个 o i oi oi 比你强还比你年轻(这个题里就是探测器既便宜又靠后),那么你就没用了的思想,就很单调栈。所以用一个单调栈模拟一下,然后从前到后贪心买探测器即可。

或者可以按探测器价格排序,然后按顺序枚举,升序地选择购买探测器

如果把 ( i , c i ) (i,c_i) (i,ci) 看成一个点,其实相当于一个下凸壳,所以求下凸壳的思想也可以做。

code1:

单调栈

#include <iostream>
#include <cstdio>
#include <vector>
#define pii pair<int,int>
using namespace std;

int n;
vector<pii> sta;

int main(){
	cin>>n;
	for(int i=1,c;i<=n;i++){
		cin>>c;
		while(!sta.empty() && sta.back().first>=c)sta.pop_back();
		sta.push_back({c,i});
	}
	int p=0,rm=0,ans=0;
	for(auto [c,i]:sta){
		rm+=i-p;
		p=i;
		ans+=rm/c;
		rm-=rm/c*c;
	}
	cout<<ans<<endl;
	return 0;
}

code2:

队友赛时代码,排序后升序选点。

#include<bits/stdc++.h>
using namespace std;
int a[200005];
typedef pair<int,int> PII;
int main(){
	int n;
	cin>>n;
	vector<PII> pos;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		pos.push_back({a[i],i});
	}
	sort(pos.begin(),pos.end());
	int p = 1;
	int ans = 0;
	int was = 0;
	for(PII pii : pos){
		if(pii.second < p) continue;
		int le = pii.second - was;
		int t = le/pii.first;
		ans += t;
		was += t * pii.first;
		p = pii.second;
	}
	cout<<ans;
	
	return 0;
}

Problem C. 中二病也要打比赛

题意:

在被中二病彻底占领的世界中,存在着一个被称为 “现实” 的神秘领域。在这个领域中,小鸟游六花,一位坚信自己拥有着非凡力量的中二病少女,发现了一串神秘的数字序列 A A A。这个序列包含了 n n n 个元素,每个元素 A i A_i Ai 1 1 1 n n n 之间的整数。据说,只有当这个序列满足单调不降的性质时,隐藏在其中的超自然力量才会觉醒。

六花相信,通过解开这个序列的秘密,她可以进一步证明自己的 “邪王真眼” 的力量。然而,她很快就意识到,要驯服这个序列,需要一种特殊的魔法——一个能将 A A A 转化为另一个序列的函数 f f f,其定义域与值域均为 [ 1 , n ] ∩ Z [1, n] ∩ Z [1,n]Z。使用这个魔法后, A A A 会变成 B B B,其中 B i = f ( A i ) B_i = f(A_i) Bi=f(Ai)。但是,这个魔法的使用是有代价的,其成本由 [ 1 , n ] ∩ Z [1, n] ∩ Z [1,n]Z f ( x ) ≠ x f(x) \not= x f(x)=x x x x 数量决定。在这个充斥着中二病的世界中,六花必须以最小的代价激发序列中隐藏的力量。

现在,作为六花的冒险伙伴,你的任务是帮助她找到那个神奇的函数 f f f,将 A A A 转化为单调不降序列,并以最小的代价揭示序列中隐藏的超自然力量。

思路:

我们队出的最后一题,赛时我想到了前半缩点部分,猜测后边做法可能是个带懒节点的线段树优化 d p dp dp(不过并不是),因为时间不太够了,简单讲完后我直接上手写了(写了个缩点部分和带懒节点线段树),之后队友讨论出了后半做法是个最长上升子序列,接着我的部分写完,一遍 A C AC AC,这就是我们热血沸腾的组合技啊!

10
1 10 2 6 10 8 9 6 4 5

比如上面的一个样例,我们可以发现被两个 10 10 10 包含起来的这段区间一定只能同时等于一个值, 10 10 10 的区间内部有一个 6 6 6,而外部也有一个 6 6 6,因为内部的 6 6 6 被固定住了,那么外部的 6 6 6 也会随之固定,这两个 6 6 6 之间的部分也被迫同时等于 10 10 10 包含区间的值,同理其他数。

既然它们都等于一个值,那么我们就可以把它们看成一个点或者一个块。一个块内所有数都会转化成一个相同的数。我们上面缩块的过程就保证了一种数字只有可能出现在一个块内,否则的话,两个块肯定在缩块的时候就被缩在一起了。因此对序列 A A A 中出现过的某种数字 x x x,它在且仅在一个块内。

不难发现,如果一个块内出现了 s z sz sz 个不同的数,那么如果这个块等于块内含有的某个值,代价是 s z − 1 sz-1 sz1,否则如果变成块内没有出现过的其他值的话,代价就是 s z sz sz。因为上面推出过每种出现过的数在且仅在一个块内的结论,因此若原本出现过 t o t tot tot 种数,那么所有块的 s z sz sz 之和就是 t o t tot tot,也就是 ∑ s z = t o t \sum sz=tot sz=tot。假设有 t t t 个块选择等于块内含有的某个值,这时候代价就是 t o t − t tot-t tott。我们求最小代价,就是求最多能有几个块可以选择等于块内含有的某个值。

这样问题就转化为了:若干个位置上,每个位置上可以取一些值的一个,求最长上升子序列长度。

code:

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <set>
using namespace std;
const int maxn=2e5+5;

int n;
int a[maxn],tt[maxn],nxt[maxn];
int ans = 1;
int dp[maxn];
int main(){
	cin.tie(0)->sync_with_stdio(false);
	set<int> aa;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],tt[a[i]]=i;//ai出现的最后位置
	for(int i = 1;i<=n;i++)aa.insert(a[i]);
	for(int i=1;i<=n;i++)nxt[i]=tt[a[i]];
	for(int i = 1;i<=n;i++) dp[i] = 0x3f3f3f3f;
	vector<set<int> > block;
	block.push_back(set<int>());
	for(int l=1,r;l<=n;){//缩块
		r=l;
		block.push_back(set<int>());
		while(l<=r){
			r=max(r,nxt[l]);
			block.back().insert(a[l++]);
		}
	} 
	int sz = block.size() - 1;
	dp[1] = (*block[1].begin());
	for(int i = 2;i<=sz;i++){
		auto & st=block[i];
		vector<pair<int,int> > ope;
		for(auto p : st){
			if(p >= dp[ans]) ope.push_back({ans+1,p});
			else {
				int t = lower_bound(dp+1,dp+ans+1,p) - dp;
				ope.push_back({t,p});
			}
		}
		for(auto pi : ope){
			dp[pi.first] = min(dp[pi.first],pi.second);
			ans = max(ans,pi.first);
		}
	}
	cout<<aa.size() - ans<<endl;
	
	return 0;
}

Problem D. 距离之比

题意:

对于 R 2 \mathbb{R}^2 R2 平面上的两个点 P ( x P , y P ) P(x_P, y_P) P(xP,yP) Q ( x Q , y Q ) Q(x_Q, y_Q) Q(xQ,yQ) P Q PQ PQ 之间的曼哈顿距离定义为 ∥ P Q ∥ 1 = ∣ x P − x Q ∣ + ∣ y P − y Q ∣ ∥P Q∥_1 = |x_P − x_Q| + |y_P − y_Q| PQ1=xPxQ+yPyQ P Q PQ PQ 之间的欧几里得距离定义为 ∥ P Q ∥ 2 = ( x P − x Q ) 2 + ( y P − y Q ) 2 ∥P Q∥_2 =\sqrt{(x_P − x_Q)^2 + (y_P − y_Q)^2} PQ2=(xPxQ)2+(yPyQ)2

现在给出平面上互不重合的 n n n 个点 P 1 , P 2 , . . . , P n P_1, P_2, . . . , P_n P1,P2,...,Pn,请求出
max ⁡ 1 ≤ i < j ≤ n ∥ P i P j ∥ 1 ∥ P i P j ∥ 2 \max\limits_{1≤i<j≤n}\dfrac{∥P_iP_j∥_1}{∥P_iP_j∥_2} 1i<jnmaxPiPj2PiPj1

思路:

直觉上感觉只要直线 P Q PQ PQ 越靠近直线 y = x y=x y=x 或直线 y = − x y=-x y=x ,这个值就越大,证明:

假设斜线是 P Q PQ PQ(不妨假设靠下的就是 P P P 点,靠上的就是 Q Q Q 点),过点 P P P 作一条水平线,过点 Q Q Q 作一条竖直线,交于点 M M M,如下图。设 ∠ P = θ \angle P=\theta P=θ ∣ P Q ∣ = x |PQ|=x PQ=x,则 ∣ P M ∣ = x ∣ cos ⁡ θ ∣ , ∣ Q M ∣ = x ∣ sin ⁡ θ ∣ |PM|=x|\cos\theta|,|QM|=x|\sin\theta| PM=xcosθ,QM=xsinθ

在这里插入图片描述
因此 ∥ P Q ∥ 1 ∥ P Q ∥ 2 = x ∣ sin ⁡ θ ∣ + x ∣ cos ⁡ θ ∣ x = ∣ sin ⁡ θ ∣ + ∣ cos ⁡ θ ∣ \dfrac{∥PQ∥_1}{∥PQ∥_2}=\dfrac{x|\sin\theta|+x|\cos\theta|}{x}=|\sin\theta|+|\cos\theta| PQ2PQ1=xxsinθ+xcosθ=sinθ+cosθ


0 ≤ θ < π 2 0\le\theta\lt \dfrac{\pi}{2} 0θ<2π 时,有 原式 = sin ⁡ θ + cos ⁡ θ = 2 ( sin ⁡ θ cos ⁡ π 4 + cos ⁡ θ sin ⁡ π 4 ) = 2 sin ⁡ ( θ + π 4 ) 原式=\sin\theta+\cos\theta=\sqrt{2}(\sin\theta\cos\dfrac{\pi}{4}+\cos\theta\sin\dfrac{\pi}{4})=\sqrt{2}\sin(\theta+\dfrac{\pi}{4}) 原式=sinθ+cosθ=2 (sinθcos4π+cosθsin4π)=2 sin(θ+4π)根据三角函数的知识,显然当 θ = π 4 \theta=\dfrac{\pi}{4} θ=4π 时, 原式 = 2 原式=\sqrt{2} 原式=2 取得最大值, 原式 = 1 原式=1 原式=1 取得最小值。当 θ ∈ [ 0 , π 4 ) \theta\in[0,\dfrac{\pi}{4}) θ[0,4π) 时,原式随 θ \theta θ 增大而增大,当 θ ∈ [ π 4 , π 2 ) \theta\in[\dfrac{\pi}{4},\dfrac{\pi}{2}) θ[4π,2π) 时,原式随 θ \theta θ 增大而减小。通俗点讲就是角度越靠近 45 45 45 度角,值就越大。


同理当 π 2 ≤ θ < π \dfrac{\pi}{2}\le\theta\lt \pi 2πθ<π 时,有 原式 = sin ⁡ θ − cos ⁡ θ = 2 ( sin ⁡ θ cos ⁡ π 4 − cos ⁡ θ sin ⁡ π 4 ) = 2 sin ⁡ ( θ − π 4 ) 原式=\sin\theta-\cos\theta=\sqrt{2}(\sin\theta\cos\dfrac{\pi}{4}-\cos\theta\sin\dfrac{\pi}{4})=\sqrt{2}\sin(\theta-\dfrac{\pi}{4}) 原式=sinθcosθ=2 (sinθcos4πcosθsin4π)=2 sin(θ4π)显然当 θ = 3 π 4 \theta=\dfrac{3\pi}{4} θ=43π 时, 原式 = 2 原式=\sqrt{2} 原式=2 取得最大值, 原式 = 1 原式=1 原式=1 取得最小值。当 θ ∈ [ π 2 , 3 π 4 ) \theta\in[\dfrac{\pi}{2},\dfrac{3\pi}{4}) θ[2π,43π) 时,原式随 θ \theta θ 增大而增大,当 θ ∈ [ 3 π 4 , π ) \theta\in[\dfrac{3\pi}{4},\pi) θ[43π,π) 时,原式随 θ \theta θ 增大而减小。通俗点讲就是角度越靠近 135 135 135 度角,值就越大。

之后再旋转直线,就会和前面重复,所以我们就不需要向下讨论了。


先看直线的角度靠近 45 45 45 度角的情况,其实也就是如果直线越贴和直线 y = x y=x y=x,值就越大。但是斜着看很难受,我们不妨将整个坐标系关于原点逆时针旋转 45 45 45 度,这样只要直线越贴近 y y y 轴(也就是角度越靠近 90 90 90 度),值就越大了。

这时会发现一个很强的性质,就是答案只会出现在横坐标相邻的点对上

证明:假设坐标系上横坐标按顺序有三个点 A , B , C A,B,C A,B,C,如果 B B B 点在直线 A C AC AC 上方,显然直线 A B AB AB 更陡,角度更靠近 90 90 90 度,答案更大。如果 B B B 点在直线 A C AC AC 下方,显然直线 B C BC BC 更陡,角度更靠近 90 90 90 度,答案更大。发现对任意三个点,最优答案总是出现在横坐标相邻的点上,而不会出现在直线 A C AC AC 这种线上。

在这里插入图片描述
因此我们按横坐标排序后 O ( n ) O(n) O(n) 算一遍相邻点的答案,取最大值即可。不过注意我们排序是按旋转后的横坐标排序,但是计算还是用原坐标来计算。

一个点关于原点逆时针旋转 θ \theta θ 角度,根据计算几何的知识,它的旋转矩阵为
[ cos ⁡ θ − sin ⁡ θ sin ⁡ θ cos ⁡ θ ] \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} [cosθsinθsinθcosθ]
一个点 ( x , y ) (x,y) (x,y) 旋转 45 45 45 度也就是 π 4 \dfrac{\pi}{4} 4π 后的坐标为:
[ x y ] ⋅ [ cos ⁡ π 4 − sin ⁡ π 4 sin ⁡ π 4 cos ⁡ π 4 ] = [ x + y − x + y ] \begin{bmatrix} x\\y \end{bmatrix}\cdot\begin{bmatrix} \cos\dfrac{\pi}{4} & -\sin\dfrac{\pi}{4} \\ \sin\dfrac{\pi}{4} & \cos\dfrac{\pi}{4} \end{bmatrix}=\begin{bmatrix} x+y\\-x+y \end{bmatrix} [xy] cos4πsin4πsin4πcos4π =[x+yx+y]

沿旋转 45 45 45 度后的横坐标排序就是按 x + y x+y x+y 排序。

同理 [ x y ] ⋅ [ cos ⁡ 3 π 4 − sin ⁡ 3 π 4 sin ⁡ 3 π 4 cos ⁡ 3 π 4 ] = [ x − y x + y ] \begin{bmatrix} x\\y \end{bmatrix}\cdot\begin{bmatrix} \cos\dfrac{3\pi}{4} & -\sin\dfrac{3\pi}{4} \\ \sin\dfrac{3\pi}{4} & \cos\dfrac{3\pi}{4} \end{bmatrix}=\begin{bmatrix} x-y\\x+y \end{bmatrix} [xy] cos43πsin43πsin43πcos43π =[xyx+y]沿旋转 135 135 135 度后的横坐标排序就是按 x − y x-y xy 排序。

code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;

ll T,n;
pll a[maxn];

double calc(pll a,pll b){
	auto [x1,y1]=a;
	auto [x2,y2]=b;
	return (abs(x1-x2)+abs(y1-y2))/sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++){
			auto &[x,y]=a[i];
			cin>>x>>y;
		}
		sort(a+1,a+n+1,[](pll a,pll b){
			return a.first+a.second<b.first+b.second;
		});
		
		double maxx=1;
		for(int i=2;i<=n;i++)
			maxx=max(maxx,calc(a[i-1],a[i]));
		
		sort(a+1,a+n+1,[](pll a,pll b){
			return a.first-a.second<b.first-b.second;
		});
		
		for(int i=2;i<=n;i++)
			maxx=max(maxx,calc(a[i-1],a[i]));
		
		cout<<setiosflags(ios::fixed)<<setprecision(12)<<maxx<<endl;
	}
	return 0;
}

Problem F. 优秀字符串

题意:

A A A 认为,一个字符串 S S S 是优秀字符串,当且仅当:

  • S S S 的长度 ∣ S ∣ |S| S 恰好为 5 5 5
  • S S S 的第三个字符与第五个字符相同;
  • S S S 的前四个字符互不相同。

例如 henan 是优秀字符串,但 queryproblemqueue 不是,因为:

  • query 的第三个字符为 e e e,而第五个字符为 y y y
  • problem 的长度不为 5 5 5
  • queue 的前四个字符中 u u u 出现了两次。

现在,小 A A A n n n 个仅包含英文字母与数字的字符串 S 1 , S 2 , . . . , S n S_1, S_2, . . . , S_n S1,S2,...,Sn,请你帮小 A A A 求出这些字符串中优秀字符串的数量。

思路:

签到

code:

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if (s.size() == 5 && (s[2] == s[4])) {
			set<char> ss;
			for (int i = 0; i < s.size() - 1; i++) {
				ss.insert(s[i]);
			}
			ans += (ss.size() == 4);
		}
	}
	cout << ans;
	return 0;
}

Problem G. 扫雷 2

题意:

T0xel 喜欢玩扫雷,但是他不喜欢数字 2 2 2

他想构造一个 n × n n × n n×n 的扫雷的地图,其中有 m m m 个雷,并且没有一个空地周围恰有 2 2 2 个雷。
也就是说,他想构造一个 01 01 01 方阵,使得不存在一个 0 0 0 周围 8 8 8 格中恰有 2 2 2 1 1 1。特别地,边上的 0 0 0 周围 5 5 5 个格不能恰有 2 2 2 1 1 1,角落上的 0 0 0 周围 3 3 3 个格不能恰有 2 2 2 1 1 1

思路:

还好赛时我放弃写这个题了,不然怕是罚时吃饱然后 G G GG GG 了。这个题看着人畜无害,实际上特殊情况超级多,需要善于调试,写代码把所有情况枚举一遍然后找错,再考虑加特判。

大概思路如下,假设左上角格子的坐标为 ( 1 , 1 ) (1,1) (1,1)。左上黄色蛇形部分包含了两个相邻紫色对角线上的所有格子,假设外侧对角线第一行的格子的坐标为 ( 1 , i ) (1,i) (1,i),那么这个蛇形部分就占据了 2 i − 1 2i-1 2i1 个格子。右下蓝色填充部分包含了后 x x x 行和列的所有格子和额外的两个格子,其中第 i i i 行和第 i i i 列包含 2 i − 1 2i-1 2i1 个格子。绿色格子可填可不填。
在这里插入图片描述
如果我们最多可以填完后 x + 1 x+1 x+1 行和列,第 x x x 行和列没有足够的格子填充,那么我们就剩下少于 2 x − 1 2x-1 2x1 个格子,我们先给出那两个额外的蓝色格子,因为蛇形只能凑 2 i − 1 2i-1 2i1 个格子,所以如果剩余了偶数个格子,我们就再拿出一个填充到绿色位置。

因为剩余的格子少于 2 x − 1 2x-1 2x1,我们还拿出了至少 2 2 2 个格子,因此剩余的格子少于 2 x − 3 2x-3 2x3,蛇形需要 2 i − 1 2i-1 2i1 个格子,就可以保证 i < x − 1 i<x-1 i<x1,这样黄色和蓝色区域正好不会冲突。

不过剩余的格子如果少于 2 2 2 个,我们甚至根本拿不出两个额外的蓝色格子,因此我们退一行列,剩余的格子个数就增加 2 x + 1 2x+1 2x+1,再减去两个额外的蓝色格子,剩余的格子 < 2 x + 1 <2x+1 <2x+1,正好可以保证 i < x + 1 i<x+1 i<x+1(因为蓝色退了一行列,所以额外蓝色格子填在点 ( 1 , x + 1 ) , ( x + 1 , 1 ) (1,x+1),(x+1,1) (1,x+1),(x+1,1) 上),正好也不冲突。这时形状大概如下:
请添加图片描述


这时我们大概的逻辑就出来了,然后就是无数的特殊情况:

一:

当黄色蛇形部分和蓝色额外块之间隔一个块的时候,就会出现 b u g bug bug
在这里插入图片描述
解决方法:删掉两个蓝色额外块,蛇形部分向外移动一格。

在这里插入图片描述

二:

当空间逐渐变小,两个蓝色额外块,黄色块,绿色块会靠的越来越近。当 ( 2 , 2 ) (2,2) (2,2) 被黄色覆盖, ( 4 , 4 ) (4,4) (4,4) 被绿色覆盖,黄色和绿色会靠的足够近,就会出现一个特色 b u g bug bug
在这里插入图片描述
解决方法:当 ( 2 , 2 ) , ( 4 , 4 ) (2,2),(4,4) (2,2),(4,4) 同时被填充,将 ( 4 , 4 ) (4,4) (4,4) 换到 ( 1 , 1 ) (1,1) (1,1) 去。
在这里插入图片描述

三:

m = n 2 − 7 m=n^2-7 m=n27 时,两个蓝色额外块会靠的足够近,导致 b u g bug bug

在这里插入图片描述

解决方法:从 ( n , n ) (n,n) (n,n) 移植一个格子到 ( 3 , 3 ) (3,3) (3,3)

在这里插入图片描述

四:

m ≥ n 2 − 4 m\ge n^2-4 mn24 的时候,特判吧。

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

五:

n = 5 , m = 10 n=5,m=10 n=5,m=10 的时候。不需要垫脚就会出现类似特判二的情况。

在这里插入图片描述

解决方法:反正就这一个,随便构造。

在这里插入图片描述

讨论结束后就可以 A C AC AC 力!其实 m = 0 m=0 m=0 也要特判,不过题目保证 m > 0 m>0 m>0,所以无所谓了。

code:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1005;

int T,n,m;
bool mp[maxn][maxn];
void print(){
	for(int i=1;i<=n;i++,puts(""))
		for(int j=1;j<=n;j++)
			cout<<(mp[i][j]?"1":"0");
}

int main(){
//	cout<<1000<<endl;
//	for(int i=0;i<=25;i++)cout<<5<<" "<<i<<endl; 
	cin>>T;
	while(T--){
		cin>>n>>m;
		puts("Yes");
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				mp[i][j]=false;
		
		if(n==5){
			if(m==10){
				cout<<"11110\n11100\n11000\n10000\n00000\n";
				continue;
			}
		}
		if(m==n*n-7){
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					mp[i][j]=true;
			mp[n][n]=mp[1][1]=mp[1][2]=mp[2][1]=mp[2][2]=mp[2][3]=mp[3][2]=false;
			print();
			continue;
		}
		if(m==n*n-4){
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					mp[i][j]=true;
			mp[1][1]=mp[1][2]=mp[2][1]=mp[n][n]=false;
			print();
			continue;
		}
		if(m==n*n-3){
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					mp[i][j]=true;
			mp[1][1]=mp[1][2]=mp[2][1]=false;
			print();
			continue;
		}
		if(m==n*n-2){
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					mp[i][j]=true;
			mp[1][1]=mp[n][n]=false;
			print();
			continue;
		}
		if(m==n*n-1){
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					mp[i][j]=true;
			mp[1][1]=false;
			print();
			continue;
		}
		if(m==n*n){
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					mp[i][j]=true;
			print();
			continue;
		}
		
		int i1=n,i2;
		while(m>=2*i1-1){
			m-=2*i1-1;
			i1--;
		}
		
		if(i1<n && m<2){
			i1++;
			m+=2*i1-1;
		}
		for(int i=i1+1;i<=n;i++)
			for(int j=1;j<=n;j++)
				mp[i][j]=mp[j][i]=true;
		if(m==2){//m>=2
			mp[i1][1]=mp[1][i1]=true;
			print();
			continue;
		}
		if(~m&1){//m>2
			mp[i1][i1]=true;
			m--;
		}
		
		//m为奇数 
		if(2*(i1-1)-1==m){
			i2=(m+1)/2;
			for(int i=1;i<=i2;i++)
				mp[i][i2-i+1]=true;
			for(int i=1;i<i2;i++)
				mp[i][i2-i]=true;
		}
		else {
			if(i1<n){
				mp[i1][1]=mp[1][i1]=true;
				m-=2;
			}
			i2=(m+1)/2;
			for(int i=1;i<=i2;i++)
				mp[i][i2-i+1]=true;
			for(int i=1;i<i2;i++)
				mp[i][i2-i]=true;
		}
		
		if(mp[2][2]==true && mp[4][4]==true){
			mp[1][1]=true;
			mp[4][4]=false;
		}
		print();
	}
	return 0;
}

Problem H. 随机栈

题意:

Toxel 获得了一个随机的 “栈”。这个栈可被视为一个多重集 S S S,从一个非空的随机栈 S S S 中取出一个元素时,有可能从中取出任何一个元素,其中每个元素被取出的概率是相等的。取出该元素后,该元素会从集合中删除。以 { 1 , 2 , 2 } \{1, 2, 2\} {1,2,2} 为例,有 1 3 \frac13 31 的概率取出 1 1 1,使得集合变为 { 2 , 2 } \{2, 2\} {2,2},有 2 3 \frac23 32 的概率取出 2 2 2,使得集合变为 { 1 , 2 } \{1, 2\} {1,2}。每次取出元素的事件相互独立。

Toxel 正在对这个集合做一些操作。集合初始时为空,它总共进行了 2 n 2n 2n 次操作,其中 n n n 次操作为插入, n n n 次操作为取出。现在,Toxel 告诉了你它操作的顺序以及每次插入的数,且保证每次取出时,集合非空。Toxel 想知道,如果把每次取出的数排成一个序列,那么这个序列递增的概率是多少?这里,递增的严格定义是:取出数列的每一项(除最后一项)小于等于它的后一项。

由于答案可能不是整数,为了方便计算,你只需要求出这个值对 998   244   353 998\ 244\ 353 998 244 353 取模的结果。

思路:

这个题虽然看起来像概率论,但是实际上就是个算数,很签到。

因为我们得到的序列是单调不降的,所以我们每次从多重集中选出来的数一定是最小的数。我们模拟一下这个多重集加数和取数的过程,每次取数的时候累乘一下 最小数的个数和多重集的个数的比值,最后得到的就是答案。

不过我们有可能加数取数的过程本身就会造成无解的情况,也就是在给定的操作序列里,我们一定会取出一个较大数,然后才加入一个较小数,这样是一定无解的。所以我们记录一下前面取出的最小数,如果一次加数比前面最小数还小,就无解。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int qpow(int x,int n){
	int ans = 1;
	while(n){
		if(n & 1) ans = ans * x % mod;
		x = x * x % mod ;
		n >>= 1;
	}
	return ans;
}
int inv(int x){
	return qpow(x,mod -2);
}
int ope[400005];
signed main(){
	int n;
	cin>>n;
	int sz = 0;
	map<int,int> mp;
	int mx = -1;
	int ans = 1;
	for(int i = 1;i<=2*n;i++)cin>>ope[i];
	for(int i = 1;i<=2*n;i++){
		int num = ope[i];
		if(num != -1){
			if(mx > num){
				cout<<0<<'\n';return 0;}
				mp[num]++;sz ++ ;
		}else{
			
			ans = ans * (*mp.begin()).second %mod;
			ans = ans * inv(sz) % mod;
			sz --;
			mx = max(mx,(*mp.begin()).first);
			(*mp.begin()).second--;
			if((*mp.begin()).second == 0) mp.erase(mp.begin());
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Problem J. 排列与合数

题意:

A A A 2023 2023 2023 年河南省 C C P C CCPC CCPC 大学生程序设计竞赛的赛场上遇到了一道名为 “排列与质数” 的题目。与大多数选手一样,小 A A A 并没能在赛场上解决这个棘手的题目。比赛结束后,小 A A A 想到了一个与之相关的题目:排列与合数,可是小 A A A 仍然没有能力解决。这个名为 “排列与合数” 的题目是这样的:

给定一个有且仅有 5 5 5 位,且各个数位互不相同的十进制正整数 n n n。你可以重新排列 n n n 的各个数位,但需要保证重新排列得到的整数 n ′ n' n 没有前导零。请问重新排列数位得到的 n ′ n' n 能否为合数?若能为合数,请求出一个满足条件的 n ′ n' n

例如,当 n = 12345 n = 12345 n=12345 时,任意排列得到的 n ′ n' n 均是合数,因此可以任意取 n ′ n' n。当 n = 13579 n = 13579 n=13579 时,可以重新排列数位得到合数 n ′ = 97531 = 7 × 13933 n' = 97531 = 7 × 13933 n=97531=7×13933

一个正整数是合数,当且仅当它可以分解为两个不小于 2 2 2 的整数的乘积。

现在,小 A A A 带着他的题目来到赛场上求助。你能帮助小 A A A 解决这个题目吗?

思路:

签到,如果五个数位上有一个偶数,那么把它放在最低位上,这样就是一个非 2 2 2 偶数,一定是合数。如果全是奇数,因为各个数位的数各不相同,因此这五个奇数一定是 1 , 3 , 5 , 7 , 9 1,3,5,7,9 1,3,5,7,9,直接输出 97531 97531 97531 即可。

注意如果有零的情况,不能出现前导零。

code:

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int p = -1;
		for (int j = 0; j < 5; j++) {
			if ((s[j] - '0') % 2 == 0) {
				p = j;
			}
		}
		if (p == -1) {
			cout << "97531\n";
			continue;
		}
		else {
			for (int j = 0; j < 5; j++) {
				if (p == j) continue;
				cout << s[j];
			} 
			cout << s[p];
		}
		cout << "\n";
	}
	
	return 0;
}

Problem K. 树上问题

题意:

378QAQ 有一棵由 n n n 个节点组成的无根树,节点编号从 1 1 1 n n n,每个节点有一个正整数点权。

378QAQ 认为一个节点是美丽节点,当且仅当该节点作为根时,对于除根节点以外的所有节点,其
点权都不小于其父亲节点的点权的 1 2 \frac12 21

请你计算出有多少个节点是美丽节点。

思路1(换根DP):

相当于 儿子节点值的二倍大于等于父节点的值。当我们认定了一个根节点后,其下的所有边都会满足这样一种情况。

一个边的这个满足关系只和它两端的点有关系,而且是有向的(即远离根的一端的点的值的二倍大于等于靠近根的一端的点的值)。所以当我们的根向旁边一个点移动的时候,除了这两个点之间的边有可能会发生转变(也就是原先有贡献,结果变成没有贡献,或者反过来),其他的边则不会受到影响。

因此考虑换根DP。不妨设 1 1 1 号点是根节点,设 c n t [ i ] cnt[i] cnt[i] 为以点 i i i 为根节点的子树的不合法边的个数,我们去计算以每个点为整个树的根节点时不合法边的个数,统计一下有几个点的答案为 0 0 0 即可。显然 1 1 1 号点我们已经计算好了,我们计算好点 u u u 的答案,需要去计算儿子节点 v v v 的答案。

在这里插入图片描述
可以发现分别以 u , v u,v u,v 为根时,红色区域和蓝色区域的边的方向都没变,所以它们对答案的贡献是相同的,只有 u , v u,v u,v 这条边发生了改变,因此我们给 a n s u ans_u ansu 减去 v → u v\rightarrow u vu 的贡献,再加上 u → v u\rightarrow v uv 的贡献就得到了 a n s v ans_v ansv

code:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;

int T,n,a[maxn];

int head[maxn],ent;
struct edge{
	int v,nxt;
}e[maxn<<1];
void add(int u,int v){
	e[++ent]={v,head[u]};
	head[u]=ent;
}

int cnt[maxn];//以u为根的子树不合法边的个数 
void dfs1(int u,int fa){
//	cout<<"^^^"<<u<<" "<<fa<<endl;
	int ans=0;
	for(int i=head[u],v;i;i=e[i].nxt){
		v=e[i].v;
		if(v==fa)continue;
		dfs1(v,u);
		ans+=cnt[v]+(a[v]*2<a[u]);
	}
	cnt[u]=ans;
	return;
}

int ans[maxn];
void dfs2(int u,int fa){
//	cout<<u<<" "<<val<<endl;
	for(int i=head[u],v;i;i=e[i].nxt){
		v=e[i].v;
		if(v==fa)continue;
		ans[v]=ans[u]-(a[v]*2<a[u])+(a[u]*2<a[v]);
		dfs2(v,u);
	}
	return;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		ent=0;
		for(int i=1;i<=n;i++)head[i]=0;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1,u,v;i<n;i++){
			cin>>u>>v;
			add(u,v);
			add(v,u);
		}
		dfs1(1,-1);
//		for(int i=1;i<=n;i++)cout<<cnt[i]<<" \n"[i==n];
		
		ans[1]=cnt[1];
		dfs2(1,-1);
		
		int t=0;
		for(int i=1;i<=n;i++)t+=(ans[i]==0);
		cout<<t<<endl;
	}
	return 0;
}

思路2(并查集缩点):

我们队赛时的想法。

可以发现这个 儿子节点值的二倍大于等于父节点的值 的关系是“有向”的,如果一条边的两个端点分别是 u , v u,v u,v,由于这个图是个树,因此整个图会被这条边分成两个连通块(点 u u u 一侧和点 v v v 一侧)。

如果存在 2 a u ≥ a v , 2 a v < a u 2a_u\ge a_v,2a_v\lt a_u 2auav,2av<au 的关系的话,那么当点选在点 v v v 一侧的时候,是永远不可能成立的,我们不妨把这条边改成 u → v u\rightarrow v uv 的一条有向边,来表示这种有向关系。当然,当 2 a u ≥ a v , 2 a v ≥ a u 2a_u\ge a_v,2a_v\ge a_u 2auav,2avau 同时满足的话,则没有限制,连成普通的双向边即可。这时,当我们从新图的一个点出发,如果可以到达其他所有点的时候,就说明这个点是可行的一个根节点。

因为一部分树边被改成了有向边,因此修改后的图就含有若干个强连通块,强连通块内的所有点可以互相到达,因此我们把图中所有极大强连通块缩成一个点,这样整个图就变成了一个有向无环图。我们在这个图上找有没有一个点可以到达其他所有点。

因为原图就是一个树,因此缩点后的图仍然是一个树,因此满足条件的点就是树根,它有且只有一个,并且只有它入度为 0 0 0

我们可以用并查集将一个强连通块缩成一个点,还能同时记录一下块内有几个点,然后我们再通过有向边记录一下每个块的入度,最后检查一下是否存在只有一个块入度为 0 0 0 即可。

code2:

队友赛时代码,当时是 A C AC AC 了,但是在 C F CF CF 上重交就过不了了。局部变量开太多导致 M L E MLE MLE,视评测机优化还会变 R E RE RE 或者 W A WA WA。把一些局部变量改成全局变量就行了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int find(int x,vector<int> & fa){
	if(fa[x] == x) return x;
	int fx = find(fa[x],fa);
	fa[x] = fx;
	return fx;
}
void merge(int x,int y,vector<int> & fa,vector<int> & cnt){
	int fx = find(x,fa);
	int fy = find(y,fa);
	if(fx == fy) return ;
	fa[fx] = fy;
	cnt[fy] += cnt[fx];
	return ;
}
void solve(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	vector<int> a(n+5);
	vector<int> fa(n+5);
	vector<int> cnt(n+5);
	for(int i = 1;i<=n;i++) {
		cin>>a[i];
		fa[i] = i; cnt[i] = 1;
	}
	vector<int> edge[n+5];
	for(int i = 1;i<n;i++){
		int u,v;cin>>u>>v;
		if(a[u]*2>=a[v] && a[v]*2 >= a[u]){
			merge(u,v,fa,cnt);
		}else if(a[u]*2>=a[v]){
			edge[v].push_back(u);
		}else if(a[v]*2>=a[u]){
			edge[u].push_back(v);
		}
	}
	set<pair<int,int> > st;
	for(int i= 1;i<=n;i++){
		for(auto j : edge[i]){
			int u = i,v = j;
			int fu = find(u,fa);int fv = find(v,fa);
			if(fu == fv) continue;
			// if(fu > fv) swap(fu, fv);
			st.insert({fu,fv});
		}
	}
	vector<int> chu(n+5),ru(n+5);
	for(auto pii : st){
		chu[pii.first]++;ru[pii.second]++;
	}
	int sz = 0;
	int ans = 0;
	for(int i = 1;i<=n;i++){
		int fi = find(i,fa);
		if(i != fi) continue;
		if(ru[i] == 0){
			sz ++;
			ans = cnt[i];
		}
	}
	if(sz > 1)
		cout<<0<<'\n';
	else cout<<ans<<'\n';
	
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

Problem L. Toxel 与 PCPC II

题意:

Toxel 正在参加 PCPC(Pokémon Center Programming Contest)比赛。它写的一段代码中有不少
b u g bug bug,正在调试。这份代码总共有 n n n 行,而且经验丰富的 Toxel 已经知道了其中 m m m 行代码有 b u g bug bug,并锁定了这 m m m 行的具体位置。但是 Toxel 还需要进行一些调试以了解错误的具体细节并修复它们。

Toxel 会进行多次调试。每次调试时,Toxel 可以任选一个 i i i,使得程序从第 1 1 1 行开始,顺序运行完第 i i i 行后退出。Toxel 可以通过这 i i i 行代码运行的一些输出结果来进行 d e b u g debug debug。运行这 i i i 行代码总共需要 i i i 秒。接下来,Toxel 会一次性地 d e b u g debug debug i i i 行代码,并修复所有这 i i i 行中的所有 b u g bug bug b u g bug bug 数量越多,修复所需的时间也越多。设这 i i i 行代码中现存的 b u g bug bug 数量为 x x x,那么 Toxel 需要 x 4 x^4 x4 秒来 d e b u g debug debug 并完成修复。修复后,这 i i i 行代码中将不再存在任何 b u g bug bug

PCPC 的赛场争分夺秒。请你帮 Toxel 计算一下,它最短需要多少秒才能完成 d e b u g debug debug,修复整个代码中的所有漏洞?

思路:

很明显的 d p dp dp,朴素想法是设 d p [ i ] dp[i] dp[i] 表示 d e b u g debug debug i i i 行代码所需的最少时间,设 s j ∼ i s_{j\sim i} sji 表示第 j j j 行到第 i i i 行的 b u g bug bug 数量, d p [ 0 ] = 0 dp[0]=0 dp[0]=0,那么状态转移方程为 d p [ i ] = min ⁡ { d p [ j ] + i + s j + 1 ∼ i 4 } ( 0 ≤ j < i ) dp[i]=\min\{dp[j]+i+s_{j+1\sim i}^4\} \quad(0\le j\lt i) dp[i]=min{dp[j]+i+sj+1i4}(0j<i)

不过这是个 n 2 n^2 n2 递推,会 T T T

优化1:

因为运行一行代码也需要时间,我们要尽可能少地选取代码,因此我们每次选择的时候,选择的这一行一定有 b u g bug bug。不然如果这一行没 b u g bug bug 的话,我们不如选上一行,同理向上走,直到我们选中有 b u g bug bug 的一行。

因此我们枚举的时候只对 b u g bug bug 行枚举,时间优化为 O ( m 2 ) O(m^2) O(m2)

优化2:

因为 d e b u g debug debug 所需时间是 b u g bug bug 数量的四次方,非常夸张的增长速度,因此我们猜测其实每次 d e b u g debug debug 只会选取少量 b u g bug bug

考虑到我们多运行一次代码,花费也不会超过 2 ∗ 1 0 5 2*10^5 2105。而 3 8 4 − 3 7 4 = 210975 38^4-37^4=210975 384374=210975,已经超过 2 ∗ 1 0 5 2*10^5 2105 了,这意味着如果我们一次性选取了 38 38 38 b u g bug bug,那么我们不如先选一个 b u g bug bug,然后再选后面的 37 37 37 b u g bug bug,就算多运行一次也肯定划得来。

因此我们枚举 j j j 的时候,不必枚举所有的 b u g bug bug 行,我们只需要向上枚举四五十行就行了。如果枚举 50 50 50 行,时间复杂度就会优化为 O ( 50 m ) O(50m) O(50m)

code:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;

int n,m;
ll a[maxn],dp[maxn];

int main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i];
	for(int i=1;i<=m;i++)dp[i]=1e18;
	for(int i=1;i<=m;i++){
		for(int j=i-1;j>=max(0,i-50);j--){
			dp[i]=min(dp[i],dp[j]+a[i]+1ll*(i-j)*(i-j)*(i-j)*(i-j));
		}
	}
	cout<<dp[m];
	return 0;
}

Problem M. 有效算法

题意:

给出长度为 n n n 的正整数序列 { a n } \{a_n\} {an} { b n } \{b_n\} {bn}。对于每个 a i ( 1 ≤ i ≤ n ) a_i(1 ≤ i ≤ n) ai1in,进行恰好一次以下操作:

  • a i a_i ai 变成满足 ∣ a i − x ∣ ≤ k × b i |a_i − x| ≤ k × b_i aixk×bi 的任意整数 x x x

请你求出最小的非负整数 k k k,使得存在至少一种方法使得操作后序列 { a n } \{a_n\} {an} 所有数都相等。

思路:

满足 ∣ a i − x ∣ ≤ k × b i |a_i − x| ≤ k × b_i aixk×bi,则 x ∈ [ k b i − a i , k b i + a i ] x\in [kb_i-a_i,kb_i+a_i] x[kbiai,kbi+ai]。当 k k k 增大的时候,这个区间会变得越来越大,就越有可能出现合法的 x x x。也就是说答案具有单调性。

因此考虑二分答案,对一个答案进行 O ( n ) O(n) O(n) 验证。验证可以求出 n n n 个取值区间,我们只要保证它们的交集不为空即可(我们可以取所有区间左端点的最大值和右端点的最小值,如果最大值小于最小值就说明交集不为空)。

code:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=3e5+5;
typedef long long ll;

int T,n;
ll a[maxn],b[maxn];

bool check(ll k){
	ll lmx=-1e18,rmi=1e18;
	for(int i=1;i<=n;i++){
		lmx=max(lmx,a[i]-k*b[i]);
		rmi=min(rmi,a[i]+k*b[i]);
	}
	return lmx<=rmi;
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		
		ll l=0,r=1e9,mid;
		while(l<r){
			mid=(l+r)>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		cout<<l<<"\n";
	}
	return 0;
}

END

本人的碎碎念,顺便记录一下2024年5月的这场ccpc。

作为本地土著还是庆幸是我轻来办比赛,而不是郑大,郑大不重视计院,尤其不重视acm。本来想锐评一下郑大,算了,郑大作为河南唯一一所211,面子工程做的那是相当到位,听不得一点杂音呢。陈述一下事实,郑大去年校赛浪潮杯不仅没给奖品,连出题人的出题费都不给,我算是开了眼了。比赛费用也不报销,与之相对的其他比赛都报销ppt大赛有啥含金量啊 ,来郑大打acm就好比去西伯利亚挖土豆。

郑轻办的这场感觉经验不足,正式赛当天日程就出了点问题,本来是八点四十开幕式,九点半比赛,结果晚点不仅禁止入会场,领导们叨叨到九点十分多还没结束。因为体育馆(音乐厅)位置不够所以有的队要去机房考(不过有补偿),过去要走一两里地,时间来不及,所以我们队直接半途直接润去机房了,之后也是临时调整时间。比赛结束后滚榜也不会滚,人都上去领奖了还在滚榜,领奖的人拿完牌子赶紧退场,之后发河南省奖的时候连榜也不滚了,直接念名字上去领奖。估计应该会被挂贴吧(好像并没)。

第二天郑轻老师居然亲自致歉
请添加图片描述
不过也能看出来我轻是努力想办好的。虽然出了一些岔子,但是并没有引起什么舆论风波,也侧面说明了大部分人对这场的体验还是不错的。参赛服发的是一件速干T恤,腋下到侧腹有散热设计,纯白,少乱七八糟的 l o g o logo logo,质感摸起来非常棒。设计用心了,是一件非常适合日常穿的衣服。训练赛当天发了午餐券和晚餐券,一张在食堂可以抵扣十五元,非常推荐卤肉饭金灿灿的麻布洗(就算不抵扣,直接买也很便宜,一碗卤肉饭半碗全是肉,才十二块,这才应该是大学的食堂) 。赛时午饭给的一整包火腿,酸奶和一个大奶油面包,是马斯卡彭,说是面包,其实是蛋糕胚+奶油,爽吃。在糖的加持下,我们队封榜时直接连出两题,这两天我吃的很开心,下次还想来。

我们河南 A C M e r ACMer ACMer 腰杆子直起来了!
请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/632258.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

24个AI写作网站汇总,免费ai工具,把AI用好工作效率真的能提高300%!

从去年到今年&#xff0c;可谓是AI爆发之年&#xff0c;各种AI工具也是层出不穷。随着openai的暴堆算力以及chatgpt人工智能算法的不断进步&#xff0c;ai正在大跨步的向前迈进。 ai可说是集中了全人类的智慧&#xff0c;未来ai的发展我是不敢想象的。不过在今天&#xff0c;如…

element select下拉框编辑时回显已经删除的数据

<el-form-item label"是否激活" prop"activationId"><el-selectv-model"formParams.activationId"style"width: 140px"clearableplaceholder"请选择"><el-optionv-for"item in activationList":ke…

CentOS7使用Docker安装Redis图文教程

1.拉取Redis镜像 这里制定了版本&#xff0c;不指定默认latest最新版 docker pull redis:6.0.8提示信息如下即为下载成功 2.上传配置文件 官方配置文件&#xff08;找自己对应的版本&#xff09;&#xff1a;reids.conf 或者将如下配置文件命名为redis.conf&#xff0c;上…

Kubernetes的Service类型详解

1. Service详解 1.1 Service介绍 在Kubernetes中&#xff0c;Service资源解决了Pod IP地址不固定的问题&#xff0c;提供了一种更稳定和可靠的服务访问方式。以下是Service的一些关键特性和工作原理&#xff1a; Service的稳定性&#xff1a;由于Pod可能会因为故障、重启或扩…

文件批量改名神器:轻松实现导入文件筛选与批量重命名,提升文件管理效率新体验!

电脑中的文件堆积如山&#xff0c;你是否曾为寻找某个特定文件而头疼不已&#xff1f;是否曾因为文件命名不规范而错失重要信息&#xff1f;别担心&#xff0c;现在有了这款文件批量改名神器&#xff0c;一切问题都将迎刃而解&#xff01; 第一步&#xff0c;我们打开需要改名文…

【ONE·基础算法 || 队列(宽搜运用) 优先级队列(堆运用) 】

总言 主要内容&#xff1a;编程题举例&#xff0c;熟悉理解宽搜类题型&#xff0c;队列、堆此类STL容器使用。       文章目录 总言1、 宽搜2、N 叉树的层序遍历&#xff08;medium&#xff09;2.1、题解 3、二叉树的锯齿形层序遍历&#xff08;medium&#xff09;3.1、题解…

【永洪BI】精确不同值计数

一、功能演示 二、使用说明 1、 功能简介 精确不同值计数&#xff0c;即统计所有数据行中不同数据值的总数量&#xff0c;数据值相同时只计算一次&#xff0c;如果存在维度字段&#xff0c;会按照不同类别分别计数。 2、 应用场景 想要统计数据中不同值出现的次数时可以使用…

Metasploit基本命令

1. 开启控制台 命令&#xff1a; msfconsole2. 搜索模块 命令&#xff1a; search ms17-010 # 模块名这里以搜索 ms17-010 为例&#xff0c; auxiliary 开头的为测试模块&#xff0c;也就是 POC&#xff0c;看看存不存在漏洞&#xff0c; exploit 开头的为攻击模块 3. 调…

DCMM(数据管理能力成熟度模型)对企业的价值

随着大数据时代的来临&#xff0c;数据已成为企业发展的重要驱动力。为了有效地管理和利用数据&#xff0c;企业需要建立一套完善的数据管理体系&#xff0c;而DCMM&#xff08;数据管理能力成熟度模型&#xff09;正是这样一个帮助企业构建和优化数据管理能力的框架。 DCMM结构…

芯片固定环氧胶有什么优点?

芯片固定环氧胶有什么优点&#xff1f; 芯片固定环氧胶在电子封装和芯片固定应用中具有多种显著优点&#xff0c;以下是其中的一些关键优势&#xff1a; 高粘接强度&#xff1a;环氧胶能够牢固地粘合芯片和基板&#xff0c;提供出色的粘接强度&#xff0c;确保芯片在各种环境条…

webpack优化构建速度示例-IgnorePlugin:

IgnorePlugin是webpack的一个内置插件&#xff0c;允许你忽略某些特定的模块或文件 webpack.config.jsconst config {entry: ./src/index.js,output: {filename: main.js},mode: development, }module.exports config;src/index.js import moment from moment console.log(mo…

剑指Offer打卡day34——AcWing 66. 两个链表的第一个公共结点

AcWing 66. 两个链表的第一个公共结点 暴力做法&#xff0c;两层for循环 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/ class Solutio…

LeetCode109:组合总和Ⅳ

题目描述 给你一个由 不同 整数组成的数组 nums &#xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 解题思想 使用完全背包 代码 /*dp[i]&#xff1a;表示装满容量为i的背包有dp[i]种方…

OpenHarmony上移植memtester

1. 下载源码&#xff1a; wget https://pyropus.ca./software/memtester/old-versions/memtester-4.6.0.tar.gz 2. 解压并指定交叉编译方式 解压 tar -xvf memtester-4.6.0.tar.gz 修改conf-cc和conf-ld&#xff0c;指定交叉编译方式 conf-cc conf-ld 3. 编译 直接运行m…

【问题实操】银河高级服务器操作系统实例分享,三台服务器宕机解决方式

1.服务器环境以及配置 物理机/虚拟机/云/容器 物理机 外网/私有网络/无网络 私有网络 处理器&#xff1a; Hygon C86 7265 24-core Processor 2 of 2 CPU sockets populated, 24 cores/48 threads per CPU 48 total cores, 96 total threads 内存&#xff1a; 768 GiB …

1W、2W 3KVAC隔离 宽电压输入 交直两用AC/DC 电源模块 ——TP01(02)AZ 系列

TP01(02)AZ为客户提供一款超小体积模块式开关电源&#xff0c;该系列模块电源输出功率为1W、2W&#xff0c;具有极低的空载损耗&#xff0c;低漏电流仅0.1mA&#xff0c;小体积&#xff0c;隔离耐压高达3KV等特点。产品安全可靠&#xff0c;EMC 性能好&#xff0c;EMC 及安全规…

哪个品牌的开放式耳机性价比高?五大高口碑优质爆款直入

最近几年来耳机音频市场上的质量问题层出不穷&#xff0c;就连最近火爆的开放式耳机也未能幸免。这是由于很多企业过分强调智能化、注重外形设计等&#xff0c;而忽视了作为一款开放式耳机最基本的音质和舒适性。很多品牌使用劣质材料制作开放式耳机产品&#xff0c;从而存在着…

英睿达硬盘数据恢复方法:从丢失到找回的详细指南

在数字化时代&#xff0c;硬盘作为我们存储重要数据的关键设备&#xff0c;承载着大量的个人、工作甚至商业信息。然而&#xff0c;无论是由于意外删除、格式化、病毒感染还是硬件故障&#xff0c;硬盘数据丢失的情况时有发生。英睿达硬盘作为市场上的知名品牌&#xff0c;其数…

基于yolov8+flask搭建一个web版本的网页模型预测系统

测试环境&#xff1a; anaconda3python3.8 torch1.9.0cu111 ultralytics8.2.2 首先我们将训练好的权重放在weights目录下面 并将名字改成yolov8n.pt&#xff0c;如果不想改可以在代码app.py都把路径改过来即可。然后我们打开 python app.py之后看到 我们点击选择文件支持图…

在PDF中使用Paragraph进行文本段落的处理

上一篇文章中我们使用itxtpdf库中的方法&#xff0c;绘制了一个固定表格与一个动态表格。如果你想在PDF中加入文字该怎么办呢。可以使用本文推荐的Paragraph这个类去实现&#xff0c;效果如下&#xff1a; 我在PDF中插入了一个工作流的审批流程。具体实现呢还是使用itextpdf库中…