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

一：翻转数列

题目描述
小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