题解2023牛客寒假算法基础集训营3

不断减损的时间

https://ac.nowcoder.com/acm/contest/46811/A

A 不断减损的时间

简单题，直接贪心，对于正整数那便是能除就除。负数不操作就行。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
ll sum;
int main() {
	int n = read();
	for(int i = 1;i <= n;i++) {
		int a = read();
		if(a <= 0) sum += a;
		else {
			while(!(a & 1)) a >>= 1;
			sum += a;
		}
		
	}
	cout << sum << endl;
}

B 勉强拼凑的记忆

中档题，关键在于如何构造。alt

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	int T = read();
	while(T--) {
		ll n = read();
		if(n == 1) {
			cout << "1" << endl;
		}
		else if(n == 2) {
			cout << "-1" << endl;
		}
		else {
			ll ans = (n + (n + 1) / 2 * 2) / 3;
			cout << ans << endl;
		}
	}
}

C 忽远忽近的距离

中档题，我的出发点是类似数学归纳，对长度为 4,5,64,5,6 进行归纳，找出这3种长度的解决方法，然后就可以拓展到长度 nn 了，这个见代码。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	int n = read();
	if(n <= 3) {
		cout << "-1" << endl;
		return 0;
	}
	else if(n % 2 == 0) {
		if(n % 4 == 0) {
			for(int i = 1;i <= n / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}			
		}
		else {
			int m = n - 6;
			for(int i = 1;i <= m / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}	
			printf("%d %d %d %d %d %d\n",n - 2,n - 1,n,n - 5,n - 4,n - 3);
		}
	}
	else {
		int m = n - 5;
		if(m == 2) {
			cout << "-1" << endl;	
			return 0;	
		}
		else if(m % 4 == 0) {
			for(int i = 1;i <= m / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}			
		}
		else {
			int mm = m - 6;
			for(int i = 1;i <= mm / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}	
			printf("%d %d %d %d %d %d ",m - 2,m - 1,m,m - 5,m - 4,m - 3);
		}
		printf("%d %d %d %d %d\n",n - 1,n,n - 4,n - 3,n - 2);
	}
}

D 宿命之间的对决

简单题，我们假设偶数有先手必胜，那么我就执行必胜方法。那么偶数先手必输，那我就取 22 则还是偶数，出现矛盾，那么其实偶数就一定先手必胜。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	ll n = read();
	if(n % 2 == 0) {
		cout << "kou" << endl;
	}
	else cout << "yukari" << endl;
}

E 公平守望的灯塔

简单题，可以考虑旋转坐标，注意精度问题，用向量表达。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const long double pi = acos(-1);
ll xa,ya,xb,yb;
int main() {
	cin >> xa >> ya >> xb >> yb;
	long double vecx = (xb - xa) / sqrt(2);
	long double vecy = (yb - ya) / sqrt(2);
	long double x = cos(pi/4) * vecx + sin(pi/4) * vecy + xa;
	long double y = -sin(pi/4) * vecx + cos(pi/4) * vecy + ya;
//	cout << "x :: " << x << " y:: " << y << endl;
	ll ansx = (x + 0.5);
	ll ansy = (y + 0.5);
	if((ansx-xa)*(ansx-xa) - (ansy-yb)*(ansy-yb) == (ansx-xb)*(ansx-xb) - (ansy-ya)*(ansy-ya)) {
		cout << ansx << " " << ansy << endl;
		return 0;
	}
	x = cos(-pi/4) * vecx + sin(-pi/4) * vecy + xa;
	y = -sin(-pi/4) * vecx + cos(-pi/4) * vecy + ya;
	ansx = (x + 0.5);
	ansy = (y + 0.5);
	if((ansx-xa)*(ansx-xa) - (ansy-yb)*(ansy-yb) == (ansx-xb)*(ansx-xb) - (ansy-ya)*(ansy-ya)) {
		cout << ansx << " " << ansy << endl;
		return 0;
	}
	cout << "No Answer!" << endl;	
}

F 迎接终结的寂灭

签到题。输出 4242 就可以。

G 严肃古板的秩序

中档题，比较简单的搜索，可以小剪枝，考虑到每一个数字最多也只能增加该数字这么多，因为取模一定小于他。所以用后缀和剪枝，爆搜即可。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
ll a[100],b[100],c[100],tot,top;
ll ksm(ll x,ll mod) {
	ll ans = 1,a = x % mod;
	for(;x;x >>= 1,a = a * 1ll * a % mod) {
		if(x & 1) ans = ans * 1ll * a % mod;
	}return ans;
}
bool dfs(int u,ll sum) {
//	cout << u << " " << sum <<" "<< ksm(sum,a[u]) << endl;
	if(u == top + 1) {
		if(sum == tot) return 1;
		else return 0;
	}
	if(sum + c[u] < tot) return 0;
	if(sum > 0 && a[u] > 0)  {
		b[u - 1] = 3;
		if(dfs(u + 1,ksm(sum,a[u]))) return 1;
		b[u - 1] = 0;
	}	
	b[u - 1] = 2;if(dfs(u + 1,sum - a[u])) return 1;b[u - 1] = 0;	
	b[u - 1] = 1;if(dfs(u + 1,sum + a[u])) return 1;b[u - 1] = 0;
	return 0;
}
int main() {
	char ch = getchar();
	while(1) {
		ll x = 0;
		while(isdigit(ch)) {x = x * 10ll + ch - '0';ch = getchar();}
//		cout <<x<<" ? : " << ch << endl;
		a[++top] = x;		
		if(ch == '=') break;
		ch = getchar();
	}
	tot = read();
//	for(int i = 1;i <= top;i++) cout << a[i] << endl;
//	cout << tot << endl;
	
	for(int i = top;i >= 1;i--) c[i] = c[i + 1] + a[i];
	if(dfs(2,a[1])) {
		for(int i = 1;i < top;i++) {
			cout << a[i];
			if(b[i]==1)cout<<'+';
			if(b[i]==2)cout<<'-';
			if(b[i]==3)cout<<'#';
		}
		cout<<a[top]<<"="<<tot<<endl;
	}
	else cout << "-1";
}

H 穿越万年的轮回

留坑。

I 灵魂碎片的收集

中档题，考虑偶数 xx ，由于 x−1x-1 ， x−3x-3 中有一个是素数。所以对于 x−1x-1 我们构造 (x−1)2(x-1)^2 ，对于 x−3x-3 构造 2(x−3)2(x-3) 。那么奇数，我们减去一个因数 11 。考虑到哥德巴赫猜想，所以存在 P1,P2P_1,P_2 使得 x−1=P1+P2x-1=P_1+P_2 ，那么构造 P1×P2P_1\times P_2 即可。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 4e6 + 10;
const ll M = 2e6;
ll a[N],tot,vis[N],p[N];
int main() {
	int T = read();
	vis[1] = 1;
	for(int i = 2;i <= M;i++) {
		if(!vis[i]) {
			p[++tot] = i;
//			cout << i << " ";
		}
		for(int j = 1;j <= tot && p[j] * 1ll * i <= M;j++) {
			vis[p[j] * i] = 1;
			if(i % p[j] == 0) break;
		}
	}
	while(T--) {
		ll x = read();
		if(x == 1) {
			cout << "3" << endl;
			continue;
		}
		if(x == 3) {
			cout << "4" << endl;
			continue;
		}
		if(x == 5 || x == 2) {
			cout << "-1" << endl;
			continue;
		} 
		if(x == 6) {
			cout << "6" << endl;
			continue;
		}
		if(x == 7) {
			cout << "8" << endl;
			continue;
		}
		if(!(x & 1)) {
			if(!vis[x - 1]) {
				printf("%lld\n",(x - 1) * 1ll * (x - 1));
				continue;
			}
			if(!vis[x - 3]) {
				printf("%lld\n",(x - 3) * 2ll);
				continue;
			}
			cout << "-1" << endl;
		}
		else {
			int f = 0;
			for(int i = 2;i <= tot;i++) {
				if((x - 1 > p[i]) && (vis[x - p[i] - 1] == 0) && (x - 1 - p[i] != p[i])) {
					printf("%lld\n",p[i] * 1ll * (x - p[i] - 1));
					f = 1;
					break;
				}
			}
			if(!f) {
				cout << "-1" << endl;
			}
		}
	}
	return 0;
}

J 无法磨灭的悔恨

不会。

K 永恒守候的爱恋

中档题，我们贪心的构造，由于 f(n)=(a1+1)(a2+1)...(ak+1),n=p1a1p2a2...pkakf(n)=(a_1+1)(a_2+1)...(a_k+1),n=p_1^{a_1}p_2^{a_2}...p_k^{a_k} 所以，如果我们从后往前删的话，我们希望删去最大的 aia_i 。如果 f(n)=xf_(n)=x 而每删去一个 aia_i 就会减少 x×aiai+1x\times \frac{a_i}{a_i+1} 。那我们对相同的 aia_i 开一个桶记录，然后等比数列求和即可。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 4e6 + 10;
const int M = 200000;
const int mod = 1e9 + 7;

int n,a[N],b[N];
int ksm(int a,int b) {
	int x = 1;
	for(;b;b >>= 1,a = a * 1ll * a % mod) {
		if(b & 1) x = x * 1ll * a % mod;
	}return x;
}
int inv(int x) {
	return ksm(x,mod - 2);
}
int Sum(int q,int n) {
	int fac = (1 - ksm(q,n) + mod) % mod;
	int ifac = (1 - q + mod) % mod;
	return fac * 1ll * inv(ifac) % mod;
}
int res = 1,ans;
int main() {	
	n = read();
	for(int i = 1;i <= n;i++) {
		a[i] = read();
		res = (a[i] + 1) * 1ll * res % mod;
		b[a[i]]++; 
	}
	for(int i = M;i >= 1;i--) {
		if(b[i]) {
			ans = (ans + res * 1ll * Sum(inv(i + 1) * 1ll * i % mod,b[i]) % mod) % mod;
//			cout << res << endl;
//			res = res * 1ll * inv(i + 1) % mod * (i) % mod;				
			res = res * 1ll * ksm((inv(i + 1) * 1ll * i % mod),b[i]) % mod;
//			cout << res << endl;
			b[i - 1] += b[i];
			b[i] = 0;
		}
	}
	cout << ans << endl;
	return 0;
}
全部评论
加油啊 456的题解就靠你了
1 回复
分享
发布于 2023-01-23 17:47 福建

相关推荐

头像 头像
想顺利毕业的蚊不叮说我这儿没问题啊
昨天 10:41
已编辑
四川大学 电子信息类
点赞 评论 收藏
转发
头像
牛客818193220号
04-22 13:10
河北工业大学 计算机类
点赞 评论 收藏
转发
头像
mujinSong
03-01 20:18
腾讯_腾讯视频_后端
pdd🐂🍺
直接把人封了
投递拼多多等公司10个岗位
点赞 评论 收藏
转发
头像
今天墨鱼了吗
04-21 22:49
C++
记录一下国企IT岗位的工作内容
说是Java岗，其实要求的是全栈，但是基本能用就行，不用太刻意深究其原理。&nbsp;早上7点准时起床，绕着小区跑步，加上吃早餐、开大、洗澡的时间，大概7.50能出门。出行的方式主要为地铁+共享单车，8.30之前踩点进公司。从食堂随便拿点早餐，一边吃一边看需求书或者是待解决的业务问题。9点开始进入工作状态，优先解决业务的问题，然后开始写代码，主要的工作方式为ctrl+c或ctrl+v，偶尔需要自己写一些逻辑代码。这种状态要一直持续到12.00，期间要喝水两次，站立排泄2-3次。食堂随便吃个饭+坐地铁+共享单车回家睡觉，大概1点可以躺下，然后开始睡觉，1.35准时起床，地铁+共享单车去公司，喝水加站泄，...
投递58到家等公司10个岗位 >
点赞 评论 收藏
转发
8 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
337924次浏览 7098人参与
# 晒一晒我的offer #
2751876次浏览 49395人参与
# 华为求职进展汇总 #
431145次浏览 4329人参与
# 第一次面试 #
13046次浏览 201人参与
# 非技术岗薪资爆料 #
4102次浏览 94人参与
# 机械人怎么评价今年的华为 #
47439次浏览 379人参与
# 你更愿意参加线上面试还是线下面试？ #
3611次浏览 50人参与
# 海信求职进展汇总 #
6707次浏览 90人参与
# 来聊聊机械薪资天花板是哪家 #
17294次浏览 132人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
21799次浏览 208人参与
# 应届生应该先就业还是先择业 #
10457次浏览 103人参与
# 除了offer，现在你还缺点啥？ #
1838次浏览 43人参与
# 百度工作体验 #
18890次浏览 205人参与
# 为什么那么多公司毁约 #
31923次浏览 267人参与
# 通信硬件薪资爆料 #
133798次浏览 917人参与
# 实习工作，你找得还顺利吗？ #
4746次浏览 70人参与
# 讲讲我经历过的年终奖 #
5759次浏览 76人参与
# 软件开发薪资爆料 #
531214次浏览 9183人参与
# 通信硬件人笔面经互助 #
59859次浏览 1342人参与
# 如果校招重来我最想改变的是 #
69895次浏览 1376人参与
牛客网
牛客企业服务