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

1001 hzy和zsl的生存挑战

**【题意】**zsl 和hzy 来到了臭臭城堡，打算挑战臭臭城堡的大魔王hyz，大魔王hyz设置了这样的一个挑战：

1. zsl 和hzy两个人各自来到一间密室，期间两人无法以任何形式交流
2. 大魔王hyz会随机在两个人的脑海里各发送一个数字，0或者是1
3. zsl 和 hzy 需要猜对这俩个数字才算通关，但是大魔王hyz觉得人生不能过于无敌，因此降低难度，只要两个人中有一个人答对就算是通关

现在大魔王hyz 给出的数字可能的情况有 00， 01， 10， 11 四种，请按上述枚举的顺序，计算所有情况下zsl 和hzy 通关的几率。（假设zsl 和 hzy 两个人都足够机智，能够选择出最优决策）

【题解】 zsl和hzy被上帝给一个数，然后zsl后面跟上相反的数，hzy跟上相同的数
00: zsl:01 hzy:00
01: zsl:01 hzy:11
10: zsl:10 hzy:00
11: zsl:10 hzy:11

**【收获】**虽然比赛的时候第二发就其实是对的（虽然思路不是对的），还是要注意输出格式啊，一定要看清楚

---

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

**【题意】**例如下图，螺旋线每划过一个方格，都转过了四分之一圈。如果我们以四分之一圈为单位，那么我们用类似带分数的形式表示螺旋线转动的起点和终点。例如，0+0 到 0 + 1 意即从第一个方格转到第二个方格，划过了前两个方格，他们的面积之和为2（1+1）。同理，0+0 到 1+0 划过了前五个方格，他们的面积之和为40（1+1+4+9+25）。
【题解】

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

typedef long long ll;
ll f[40500],summ[40500];
int main()
{
	ll q,a,b,c,d;
	ll aa,bb,sum=0,maxx,minn;
	const ll modd=192600817;
	f[0]=1,f[1]=1;
	
	summ[0]=1,summ[1]=2;
	for(int i=2;i<40500;i++){
		f[i]=(f[i-1]%modd+f[i-2]%modd)%modd;
		summ[i]=(summ[i-1]%modd+(f[i]%modd)*(f[i]%modd))%modd;
	}
//cout<<summ[2]<<endl;
	while(~scanf("%lld",&q)){
		for(int i=0;i<q;i++){
			scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
			aa=a*4+b;
			bb=c*4+d;
			maxx=max(aa,bb);
			minn=min(aa,bb);
			//printf("%lld\n",((summ[maxx]-summ[minn]+f[minn]*f[minn])%modd+modd)%modd);
			cout<<((summ[maxx]-summ[minn]+f[minn]*f[minn])%modd+modd)%modd<<endl;
		}
	}
	
	
	return 0;
}

**【收获】**1.大数组一定要开在外面；
2.要先打表啊，先打表不是f[i]而是sum[i]这样再计算的时候就不会T了；
3.注意取模和减法上的细节

---

1007 简单数学题

**【题意】**已知F(n)=∑i=1n(i×∑j=inCij)求 F(n) mod 1000000007
【题解】还要用一下快速幂的模板

代码。。。

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

typedef long long ll;
const int fn=1000000007;
ll poww(ll a,ll b)
{
	ll ans=1;
	ll base=a;
	while(b){
		if(b&1){
			ans*=base%fn;
			ans=ans%fn;
		}
		base*=base%fn;
		base=base%fn;
		b>>=1;
	}
	return (ans%fn);
}
int main()
{
	ll n,e=1,a,sum=0,b;
	
	while(~scanf("%lld",&n)){
		e=poww(2,n);
		//cout<<e<<endl;  
		a=(e*((n-1)%fn+fn)%fn)%fn+1;
		printf("%lld\n",a%fn);
		e=1;
	}
	

	return 0;
}

**【收获】**1.这是一道数学题，要进行数学的推理，比如组合数的一些性质和定理要熟悉
2.有一些常用的组合数性质
请来这位大佬的blog看吧

---

---

愉快的结束线~~小尾巴，本人菜鸡一个，关于算法还在学习，所以blog中的内容大部分是总结各位大佬的，如果有侵权要求删除或者出处注明不全的，非常抱歉，欢迎站内私信啊。。。