2018腾讯秋招笔试题
题目来源:牛客网
1. 翻转数列
解题思路:
这道题目非常简单,可以设置一个flag变量,用来控制符号的编号,然后循环累计就可以得到结果。
AC代码:
#include <stdio.h>
int main(){
int n, m;
scanf("%d %d", &n, &m);
long long sum = 0;
int flag = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
sum += (flag * i);
flag *= -1;
}
printf("%lld\n", sum);
return 0;
}
2. 纸牌游戏
解题思路:
贪心算法,每个人每次都是抽当前数字最大的纸牌,因此只需要将数组进行排序,然后模拟两个人依次抽纸牌,将第二个人抽的纸牌数字乘上-1,进行累加即可得到结果。
AC代码:
#include <stdio.h>
#include<algorithm>
using namespace std;
bool compare1(int a, int b){return a > b;}
int main(){
int n;
scanf("%d", &n);
int card[n];
for(int i = 0; i < n; i++){
scanf("%d", &card[i]);
}
sort(card, card + n, compare1);
int flag = -1, sum = 0;
for(int i = 0; i < n; i++){
flag *= -1;
sum += card[i] * flag;
}
printf("%d\n", sum);
return 0;
}
3.贪吃的小Q
解题思路:
二分查找,需要注意的是,第二天吃的巧克力数量不少于第一天的一半,需要进行处理,否则前一天吃的巧克力是奇数的情况下会出现问题,比如前一天吃了19块巧克力,那么第二天至少吃10块巧克力,而不是19/2=9块巧克力。在程序中用了对2取余是否等于0来处理这种情况。
AC代码:
#include <stdio.h>
int sum(int mid, int n){
int sum = 0;
for(int i = 0; i < n ; i++){
sum += mid;
mid = mid % 2 == 0? mid / 2: mid / 2 + 1;
}
return sum;
}
int find(int n, int m){
int l = 1, h = m;
while(l <= h){
int mid = (l + h) / 2;
if(sum(mid, n) == m) return mid;
else if(sum(mid, n) > m) h = mid - 1;
else l = mid + 1;
}
return h;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
int ans = find(n, m);
printf("%d\n", ans);
return 0;
}
4.小Q的歌单
解题思路:
组合问题
AC代码:
include <stdio.h>
long long c[105][105];
int mod = 1000000007;
void init(){
c[0][0] = 1;
for(int i = 1; i <= 100; i++){
c[i][0] = 1;
for(int j = 1; j <= 100; j++){
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
}
}
}
int main(){
int k;
scanf("%d", &k);
int a, x, b, y;
scanf("%d %d %d %d", &a, &x, &b, &y);
long long ans = 0;
init();
for(int i = 0; i <= x; i++){
if(i*a <= k && (k-i*a)%b == 0 && (k-i*a)/b <= y){
ans = (ans + (c[x][i] * c[y][(k - i * a) / b]) % mod) % mod;
}
}
printf("%lld\n", ans);
return 0;
}