电协招新第二次面试题基础部分答案

感谢大家参加了本次电协招新二面的线上OJ测试，因大家强烈期待，现予公布二面基本题答案，希望大家从答案当中有所收获！

EASY-1 斐波那契之梦

print("9227464")

EASY-2 PID算法

#include <bits/stdc++.h>
using namespace std;

int s, t;
double Kp, Ki, Kd;

int main(){
	
	double res, lerr = 0, err, serr = 0;
	scanf("%lf%lf%lf%d%d", &Kp, &Ki, &Kd, &s, &t);
	res = s;
	
	for(int i = 1; i <= 200; i++){
		err = t - res;
		serr += err;
		
		res += Kp * (err + Ki * serr + Kd * (err - lerr));
		
		if(i % 10 == 0) 
			printf("%0.3lf\n",res);
		lerr = err;
	}
	return 0;
}

EASY-3 两面包夹芝士

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define caseT int t; cin >> t; while(t--)
#define endl '\n'
 
void solve(){
    caseT{
        int b,c,h;
        cin >> b >> c >> h;
        cout << (((b - 1 < c + h ? b - 1 : c + h) << 1) | 1) << endl;
    }
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    time_t START_TIME = clock();
#endif
    IOS
    solve();
#ifndef ONLINE_JUDGE
    time_t END_TIME = clock();
    cout << "Time: " << double(END_TIME - START_TIME) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

EASY-4 两面包夹芝士

#include<iostream>
using namespace std;
int a,b,n;
int main()
{
	cin>>n>>a>>b;
	int ans=1e9;
	for(int i=0;i<=n/a;i++)
	{
		for(int j=0;j<=n/b;j++)
		{
			if(i*a+b*j<=n)
				ans=min(ans,n-i*a-b*j);
		}
	}
	cout<<ans;
	return 0;
}

EASY-5 恶魔果实

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e5+5;

pair<int, int>p[N];
int n, m;

int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> p[i].second  >> p[i].first;
	}	
	sort(p + 1, p + 1 + m);
	long long ans = 0, sum = 0;
	for(int i = 1; i <= m; i++){
		if(sum + p[i].second <= n){
			sum += p[i].second;
			ans += (long long)p[i].first * p[i].second; 
		}
		else{
			int temp = n - sum;
			ans += temp * p[i].first;
			break;
		}
	}
	cout << ans;
	return 0;
}

EASY-6 花果山

#include<bits/stdc++.h>
using namespace std;
int n, k, a, b;
void yes() {
	cout << "YES\n";
} 
void no() {
	cout << "NO\n";
}

int main() {
	cin >> n >> k >> a >> b;
	if (abs(a - b) > k || a == b)yes();
	else {
		if (b > a) {
			if (b + k < n || a - k >= 2 || (b - k > 1 && a + k < n))yes();
			else no();
		} else {
			if (a + k < n || b - k >= 2 || (a - k > 1 && b + k < n))yes();
			else no();
		}
	}
	return 0;
}

EASY-7 文明6

def find_best_location(map_data, rows_count, cols_count):
    data_record = [[0 for _ in range(cols_count)] for _ in range(rows_count)]

    max_pro = 0

    for i in range(rows_count):
        for j in range(cols_count):
            if map_data[i][j] != 0:
                production_of_this_city = 0
                for i1 in range(max(i - 1, 0), min(i + 2, rows_count)):
                    for j1 in range(max(j - 1, 0), min(j + 2, cols_count)):
                        production_of_this_city += map_data[i1][j1]

                data_record[i][j] = production_of_this_city
                if production_of_this_city > max_pro:
                    max_pro = production_of_this_city

    count = 0
    for index in data_record:
        for num in index:
            if num == max_pro:
                count += 1

    return max_pro, count


if __name__ == "__main__":
    rows = int(input())
    cols = int(input())

    civi_map = []

    for i in range(rows):
        row_str = input()
        row_nums = [int(x) for x in row_str.split()]
        if len(row_nums) == cols:
            civi_map.append(row_nums)

    max_production, count = find_best_location(civi_map, rows, cols)
    print(max_production, count)

EASY-8 拉练

#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define dep(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
const int N = 1005;
int n;
double v,u,c[N],d[N];
int main(){
    scanf("%d%lf%lf",&n,&v,&u);
    rep(i,1,n) scanf("%lf",c+i);
    rep(i,1,n) scanf("%lf",d+i);
    double ans = 0;
    rep(i,1,n) rep(j,1,n) ans+=1.0/(c[i]-(j-1)*d[i]-v);
    ans*=u;
    printf("%.3f\n",ans);
}

MID-1 LED灯的游戏

#include <iostream>
#include <cmath> 
using namespace std;

double gold;

void solve(){
	double a, b;
	cin >> a >> b;
	if(a < b) swap(a, b); 
	if(b == floor((a-b)*gold)){
		cout << "Dpgg Wins!\n";
	}else cout << "Bgg Wins!\n";
}

int main(){
	gold = (sqrt(5) + 1) / 2;
	int n;
	cin >> n;
	while(n--)
		solve();
	
	return 0;
}

MID-2 咒术开发

#include <iostream>
using namespace std;
const int N = 1e5 + 5;

int n, a[N], b[N];

bool check(int mid){
	for(int i = 1; i <= n; i++){
		if(b[i] * mid > a[i])
			return false;	 
	}
	return true;
}


int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
	}
	int l = 1, r = 1e9;
	while(l < r){
		int mid = (l + r + 1) / 2;
		if(check(mid))
			l = mid;
		else 
			r = mid - 1; 
	}
	cout << l;
	
	
	return 0;
}

MID-3 大秘宝

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3+5;

pair<int, int>P[N];
int n, m;
int ans = -1;
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int a, b; cin >> a >> b; 
		P[i].first = b;
		P[i].second = a;
	}
	sort(P + 1, P + 1 + m);
	for(int i = 1; i <= m; i++){
		if(P[i].second == 1){
			ans = max(ans, n - P[i].first + 1);
			break;
		}
	}
	for(int i = m; i >= 1; i--){
		if(P[i].second == 2){
			ans = max(ans, P[i].first);
			break;
		}
	}
	cout << ans;
	return 0;
}

MID-4 电协码

def get_gray_code(n, m):
    # 计算格雷码的总数量
    total_codes = 2 ** n

    # 验证输入是否有效
    if m < 0 or m >= total_codes:
        return None

    # 将 m 转换为二进制数
    binary = bin(m)[2:].zfill(n)

    # 进行格雷码转换
    gray_code = [binary[0]]
    for i in range(1, n):
        gray_code.append(str(int(binary[i - 1]) ^ int(binary[i])))

    return ''.join(gray_code)


# 示例用法
n, m = map(int, input().split())

gray_code = get_gray_code(n, m)
if gray_code:
    print(gray_code)
else:
    pass

HARD-1 难以描述的梦境

import math

s = input()
s = s.split(' ')

n = int(s[0])
k = int(s[1])

f = [0, 0]
for i in range(2, n + 1):
    f.append(int(math.log2(i - 1)) + 1)

front = []
back = []
for i in range(n, 0, -1):
    if k - f[i] >= 0:
        front.append(i)
        k -= f[i]
    else:
        back.append(i)

back.reverse()
for it in front:
    print(f"{it} ", end="")
for it in back:
    print(f"{it} ", end="")

HARD-2 接水

#include <iostream>
#include <cmath> 
#include <string>
using namespace std;
const int N = 120;

int num[N], len;

int main(){
	string s;
	getline(cin, s);
	int temp = 0;
	for(int i = 0; i < (int)s.length(); i++){
		if(isdigit(s[i])){
			temp = temp * 10 + (s[i] - '0');
		}else{
			if(temp != 0){
				num[len++] = temp;
				temp = 0;
			}
		}
	}
	num[len++] = temp;
	int ans = 0;
	int l = 0, r = len - 1, lm = 0, rm = 0;
	while(l < r){
		lm = max(lm, num[l]);
		rm = max(rm, num[r]);
		if(lm > rm){
			ans += rm - num[r];
			r--;
		}
		else{
			ans += lm - num[l];
			l++;
		}
	}
	cout << ans;
	
	return 0;
}

HARD-3 A+B

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &x : v)
        is >> x;

    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    if (!v.empty()) {
        os << v.front();

        for (int i = 1; i < v.size(); ++i)
            os << ' ' << v[i];
    }

    return os;
}

char s[70];
int ways[20];
ll dp[70];

int main() {
#ifdef LBT
    freopen("test.in", "r", stdin);
    int nol_cl = clock();
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            ++ways[i + j];

    cin >> s;
    int l = strlen(s);
    dp[0] = 1;

    for (int i = 0; i < l; ++i) {
        dp[i + 1] += dp[i] * ways[s[i] - '0'];

        if (s[i] == '1' && i + 1 < l)
            dp[i + 2] += dp[i] * ways[10 + s[i + 1] - '0'];
    }

    cout << dp[l] << '\n';

#ifdef LBT
    LOG("Time: %dms\n", int ((clock()
                              - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
    return 0;
}