4.26 腾讯笔试-数据分析与技术研究
时间有点久，题意记不清了...
第一题：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 1005
struct node{
int x,y,m;
node(){}
node(int xx,int yy,int mm):x(xx),y(yy),m(mm){}
bool operator < (const node a) const{
return y - x*1.0/m > a.y - a.x*1.0/m;
}
}a[MAXN];
double b[MAXN];
char s[MAXN];
bool vis[MAXN];
int n,m;
int ans,sum;
int main()
{
scanf("%d %d",&n, &m);
for(int i = 0 ; i < n ; i++){
scanf("%d %d", &a[i].x, &a[i].y);
a[i].m = m;
b[i] = a[i].y - a[i].x * 1.0 / m;
}
sort(a, a+n);
ans = 0;
sum = 0;
for(int i = 0 ; i < n ; i++){
if(a[i].y - a[i].x * 1.0 / m <= 0)
break;
ans += a[i].y;
sum += a[i].x;
}
if(sum % m)
sum = sum / m + 1;
else sum = sum / m;
ans -= sum;
printf("%d\n",ans);
return 0;
} 第二题：求抛物线与直线之间的面积。微积分忘光了，搬一份别人的代码...
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int T, A, B, C;
double get(double y)
{
return y * y/2/B - (1.0*C)/B * y - y*y*y/6/A;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d %d %d", &A, &B, &C);
int delta = 4 * A * A - 8 * A * B * C;
if (delta <= 0)
{
printf("0\n");
continue;
}
double a = (2 * A + sqrt((double)delta)) / 2.0 / B;
double b = (2 * A - sqrt((double)delta)) / 2.0 / B;
printf("%.6f\n", get(a) - get(b));
}
return 0;
}
第三题：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int mod = 100003;
#define MAXN 1005
ll n,m;
ll ans, sum;
ll powmod(ll x, ll n, int mod){
ll res = 1;
while(n > 0){
if(n&1LL)
res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main()
{
scanf("%lld %lld",&m, &n);
ans = powmod(m, n, mod);
sum = powmod(m-1, n-1, mod);
sum = sum * m % mod;
ans = (ans + mod - sum)%mod;
printf("%lld\n",ans);
return 0;
}
第四题：求互补数组。
先已第一个数为基准处理数组，将2 11 21变成0 9 19这种。然后排序，前后两个指针向中间移动找互补的。注意有多个0 0 0的数组可以互相互补。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100005
struct node{
int id;
vector<int> a;
bool operator < (const node p) const{
for(int i = 0 ; i < a.size() ; i++){
if(a[i] != p.a[i])
return a[i] < p.a[i];
}
return id < p.id;
}
}a[MAXN];
int n,m;
ll ans;
bool equ(int p, int q){
for(int i = 0 ; i < m ; i++){
if(a[p].a[i] != a[q].a[i])
return false;
}
return true;
}
int ok(int p, int q){
for(int i = 0 ; i < m ; i++){
if(a[p].a[i] + a[q].a[i] < 0)
return -1;
if(a[p].a[i] + a[q].a[i] > 0)
return 1;
}
return 0;
}
int main()
{
scanf("%d %d",&n, &m);
for(int i = 0 ; i < n ; i++){
int p, q;
scanf("%d", &p);
a[i].id = i;
a[i].a.clear();
a[i].a.push_back(0);
for(int j = 1 ; j < m ; j++){
scanf("%d", &q);
a[i].a.push_back(q - p);
}
}
sort(a, a+n);
int l = 0, r = n-1;
ans = 0;
while(l < r){
int l_num = 1;
int r_num = 1;
while(l+l_num < r && equ(l, l+l_num)){
l_num++;
}
while(r-r_num > l && equ(r, r-r_num)){
r_num++;
}
int t = ok(l,r);
if(t == 0){
if(equ(l, r)){ //多个0 0 0
ans += 1LL * (r - l + 1) * (r - l) / 2;
}
else ans += 1LL * l_num * r_num;
l += l_num;
r -= r_num;
}
else if(t < 0){
l += l_num;
}
else if(t > 0){
r -= r_num;
}
}
printf("%lld\n",ans);
return 0;
}
第五题：先离散化，然后用bfs搜联通块。没想到用并查集...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100005
struct node{
int x,y;
node(){}
node(int xx,int yy):x(xx),y(yy){}
bool operator < (const node a) const{
if(x == a.x) return y < a.y;
return x < a.x;
}
};
vector<int> a[MAXN * 2];
int b[MAXN][2];
int c[MAXN * 2];
char s[MAXN];
bool vis[MAXN * 2];
int n,m;
int ans;
int main()
{
int tt,ca = 1;
int p,q;
scanf("%d",&tt);
while(tt--){
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
for(int i = 0 ; i < n ; i++){
scanf("%d %d", &b[i][0], &b[i][1]);
c[i*2] = b[i][0];
c[i*2+1] = b[i][1];
}
sort(c,c+2*n);
int nn = unique(c,c+2*n)-c;
for(int i = 0 ; i < nn ; i++)
a[i].clear();
for(int i = 0 ; i < n ; i++){
p = b[i][0];
q = b[i][1];
int pp = lower_bound(c,c+nn,p)-c;
int qq = lower_bound(c,c+nn,q)-c;
a[pp].push_back(qq);
a[qq].push_back(pp);
}
ans = 0;
for(int i = 0 ; i < nn; i++){
if(vis[i])
continue;
vis[i] = true;
queue<int> que;
que.push(i);
int sum = 1;
while(!que.empty()){
int t = que.front();
que.pop();
for(int i = 0 ; i < a[t].size() ; i++){
int q = a[t][i];
if(vis[q])
continue;
vis[q] = true;
sum++;
que.push(q);
}
}
ans = max(ans, sum);
}
printf("%d\n",ans);
}
return 0;
} 
投递小米集团等公司10个岗位 >
