“字节跳动-文远知行杯”——广东工业大学第十四届程序设计竞赛

补题补题：

A、hzy 和zsl 的生存挑战

题解：由于我们去考虑最优解，那么其中两人就应该是这样走法，一人选择相同数，另一人选择相反数，这样必会通关

#include <iostream>
using namespace std;

int main()
{
	cout<<"1.00"<<endl;
	cout<<"1.00"<<endl;
	cout<<"1.00"<<endl;
	cout<<"1.00"<<endl;
	return 0;
}

B、人类史上最大最好的希望事件

题解：预处理斐波那契数列的平方和。把a+b 和c+d 转化为整数s1、s2。求0+0到x+y的前缀和，找出s2,s1中较大的那个，再输出sum[s2]-sum[s1-1]（注意此时s2为较大值，s1为较小值）。注意这些数可能会非常大，所以最好不断地对题目给出的数进行取余。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long LL;

const int N = 40010; 

int p = 192600817;
LL S[N],sum[N],ans[N];//面积，总和，边长 

void init()
{
	ans[1] = ans[2] = 1;
    S[1] = S[2] = 1;
    for(int i = 3;i< N;i++)
    {
    	ans[i] = (ans[i - 1] + ans[i - 2])%p; //边长 
    	S[i] = ((ans[i]%p) * (ans[i]%p))%p; //面积 
    }
    sum[1] = 1;
	for(int i = 2;i < N;i++)
	{
		sum[i] = (sum[i - 1] + S[i]) % p;
	}
}


int solve(int a,int b,int c,int d)
{	
    int s1 = a*4 + b + 1; //初始 
    int s2 = c*4 + d + 1; //终止 
    
    if(s1>s2) swap(s1,s2);

    return (sum[s2] % p - sum[s1 - 1] % p + p) % p;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T; 
	init();
	while(cin>>T)
	{
		while(T--)
		{
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			cout<<solve(a,b,c,d)<<endl;
		}
	}
	return 0;
}

C、超级无敌简单题

题解1：直接预处理150000个鸽子数，处理的时候，用bool数组记录是否用过。

题解2：对于非鸽子数，发现循环节里的第一个数都是4，其余暴力判断即可。

下面用到的是题解1

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 150000, M = 1e7 + 10;
int a[N + 5];
bool st[M]; //判断 这个数是否存在 

int is_gz(int n)
{
	if (n != 1 && n != 7 && n < 10) return false;

	int sum = 0;
	while (n)
	{
		int t = n % 10;
		sum += t * t;
		n /= 10;
	}
	if (st[sum]) return true;
	else return is_gz(sum);
}

void solve()
{
	st[1] = 1;
	a[1] = true;
	for (int i = 2, j = 2; j <= N; i++)
	{
		if (is_gz(i)) {
			st[i] = true;
			a[j++] = i;
		}
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	solve();
	while (T--)
	{
		int n;
		scanf("%d", &n);
		cout << a[n] << endl;
	}

	return 0;
}

D、免费送气球

E、水题

F、清一色

G、简单数学题

题目公式化简得：

题解：暴力求解上面化简公式

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

const int P = 1e9 + 7;
const int MAX = P;

int solve(LL a,LL b)
{
	LL ans = 1;
	a %= P; //取余
	while (b)
	{
		if (b & 1) ans = a * ans % P;
		a = a * a % P;
		b >>= 1;
	}
	return ans % P;
}

int main()
{
	LL n, ans;
	while (scanf("%lld", &n)!=EOF)
	{
		
		ans = (((n - 1) % P) * (solve(2, n) % P) + 1) % P;
		printf("%lld\n", ans);
	}
	return 0;
}

H、zyb的面试

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int solve()
{
	int n, k;
	int ans = 1;
	scanf("%d%d", &n, &k);
	while (k>1)
	{
		if (ans * 10 <= n)
		{
			ans *= 10; //相当于往前走
			k--;
		}
		else {
			if (ans + 1 <= n){
				//比如1009--因为1000已经算过--下一位是101((x/10)然后再加一)--下一位1010
				while (ans % 10 == 9) ans /= 10; //往右边走
				ans++;
				k--;
			}
			else {
				ans /= 10;
				while (ans % 10 == 9) ans /= 10; //往右边走
				ans++;
				k--;
			}
		}
	}
	return ans;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		cout << solve() << endl;
	}
}