欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

腾讯2018春招技术类编程题汇总

程序员文章站 2022-06-18 19:41:27
一:翻转数列题目描述小Q定义了一种数列称为翻转数列:给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4…, 每隔m个符号翻转一次, 最初符号为’-’;。例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.而n = 4, m = 1, 数列就是: -1, +2, -3, + 4.小Q现在希望你能帮他算算前n项和为多少。样例输入例子1:8 2输出例子1:8思路&...

一:翻转数列

题目描述
小Q定义了一种数列称为翻转数列:
给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4…, 每隔m个符号翻转一次, 最初符号为’-’;。
例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.
而n = 4, m = 1, 数列就是: -1, +2, -3, + 4.
小Q现在希望你能帮他算算前n项和为多少。

样例

输入例子1:
8 2

输出例子1:
8

思路
    从第一个数字开始,每 2m 个数字之和为 m^2,总共有 n / 2m 个这样的组合,因此和为 m * n / 2

代码

#include <iostream>

using namespace std;
typedef long long ll;
ll n, m;

int main()
{
	scanf("%lld%lld", &n, &m);
	printf("%lld\n", n * m / 2);
	return 0;
 } 

二:纸牌游戏

题目描述

    牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。
    牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。
他们的得分等于他们抽到的纸牌数字总和。
    现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。

思路
    从大到小排序, 牛牛先选, 然后羊羊选, 就是奇数加在牛牛上, 偶数加在羊羊上,最后输出他们的差

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int a[N];
int n;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	int cow = 0, sheep = 0;
	for(int i = 1; i <= n; i++)
	{
		if(i & 1) cow += a[i];
		else sheep += a[i];
	}
	cout << cow - sheep << endl;
	return 0;
 } 

三:贪吃的小Q

题目描述
    小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有巧克力吃,请问他第一天最多能吃多少块巧克力

样例

输入例子1:
3 7

输出例子1:
4

思路
    二分答案, 注意实数二分的特殊性。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 100010;

int n, day;

bool check(int num)//判断第一天吃掉num块巧克力是否可以
{
	int c = n;
	int d = day;
	int div = num;
	while(d) 
	{
		c -= div;
		d--;
		div = ceil((double)div / 2);
		if(c < 0)
			return false; //不可以
	}
	return true;//可以
}

int main()
{
	cin >> day >> n;
	int l = 1, r = n;
	while(l < r) //二分枚举
	{
		int mid = (l + r + 1) >> 1;
		if(!check(mid)) r = mid - 1;
		else l = mid;
	}
	cout << l << endl;
	return 0;
 } 

四:小Q的歌单

题目描述
    小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌,现在小Q想用这些歌组成一个总长度正好为K的歌单,每首歌最多只能在歌单中出现一次,在不考虑歌单内歌曲的先后顺序的情况下,请问有多少种组成歌单的方法。

样例

输入例子1:
5
2 3 3 3

输出例子1:
9

思路
    01背包求方案数裸题, 将所有的歌的长度都存到a数组中, 遍历a数组,一重循环遍历物品, 二重循环遍历空间

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 10010,mod = 1000000007;

int k, A, X, B, Y;

long long f[N];
int a[N];


int main()
{
	cin >> k >> A >> X >> B >> Y;
	int n = X + Y;
	for(int i = 1; i <= X; i++)
		a[i] = A;
	for(int i = X + 1; i <= n; i++)
		a[i] = B;
	f[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j = k; j >= a[i]; j--)
		{
			f[j] += f[j - a[i]];
			f[j] %= mod;
		}
	}
	cout << f[k] <<endl;
	return 0;
 } 

本文地址:https://blog.csdn.net/qq_45432665/article/details/107878685

相关标签: 面试题汇总