C. 小 C 的爱情

题目描述

某天晚上，小C在操场中心完成了乐跑打卡，准备回寝室研究 $\text{BZOJ 1000}$ .这时（前方高能），他看到一个漂亮的mm正在绕着操场匀速率圆周运动（啥？匀速率你都能看出来，我去）。小C被mm深深的吸引。但是这个时候，他又想起了自己的 $\text{BZOJ}$ 还没有刷完。
于是他想了一个折中的办法：把自己交给命运，他以 $v$ 的速度追mm，但是只走 $N$ 米。如果追上，就问妹子要QQ，否则就回寝室。
现在我们假设操场是一个圆形，半径为 $r$ ，二者的速率不变，mm跑步的速率的 $v_1$ ,小C的速率是 $v_2$ ，他最多走 $N$ 米，并且在小C追mm的时候，二者和圆心始终在同一直线。
那么小C的命运如何呢？

输入

多组输入，mm的速率 $v_1$ ，小C的速率 $v_2$ ，操场半径 $r$ ,以及 $N$ .
所有的数据保证在double的范围以内。

输出

如果能够追上，输出：Yes
如果追不上，输出：No
样例输入
1 1 1 1
11904 41076 3561 3613
样例输出
No
Yes

分析

$\text{PHO}$ 的经典运动学问题。

如图，在自然坐标系下，将小C的速度 $\overrightarrow {v_1}$ 分解为径向的 $\overrightarrow {v_n}$ 和切向的 $\overrightarrow {v_t}$ 。由于小C和小姐姐的连线始终过圆心，故两者对于圆心的角速度相同，设 $\omega=\frac{v1}{r}$ 。设在 $t$ 时刻，小C到圆心的距离为 $x$ ，所以 $v_t=\omega x$ ， $v_n=\frac{dx}{dt}$ ，故 $v_2=\sqrt{v_n^2+v_t^2}=\sqrt{v_n^2+(\omega x)^2}$ ，即$v_n=\sqrt {v_2^2-\omega ^2x^2}=\sqrt {v_2^2-\frac{v_1^2x^2}{r^2}}=\frac{dx}{dt}$，即$dt = \frac{dx}{\sqrt{v_2^2-\frac{v_1^2 x^2}{r^2}}}$。两边积分$\displaystyle \int_0^tdt=\displaystyle{\int_0^r \frac{dx}{\sqrt{v_2^2-\frac{v_1^2 x^2}{r^2}}}}$，得到小C追上小姐姐的时间$t=\frac{r}{v_1}\arcsin \left(\frac{v_1}{v_2}\right)$，所以小C走的总路程$s=v_2t=\frac{v_2r}{v_1}\arcsin \left(\frac{v_1}{v_2}\right)$。比较 $s$ 和 $N$ 的大小即可。

代码

#include<iostream>
#include<cmath>
using namespace std;
long double v1,v2,r,n;//以防万一还是用long double
void solve()
{
	long double s=v2*r/v1*asin(v1/v2);
	if(s<=n) puts("Yes");
	else puts("No");
}
int main()
{
	while(cin>>v1>>v2>>r>>n) solve();
	return 0;
}

F. 小 C 的数学题

$\text{CUGOJ 2173}$

题目描述

已知某函数 $f(n)$ 的定义如下：

${\displaystyle f(n)={\begin{cases}1,&{n\le2}\\ f(n-1)+f(n-2)+\lfloor log_2n\rfloor,&{n\ge 3}\end{cases}}}$

求函数 $f(n)$ 的值，为了防止数据过大，你只需要输出答案对 $10^9+7$ 取模之后的结果。

输入

最多十行，每行一整数 $n$ ， $1\le n < 10^9$

输出

$f(n)$

样例输入

666
666666
666666666

样例输出

581824003
310868947
609519880

分析

乍一看是矩阵快速幂，但是随着 $n$ 的增大， $\lfloor log_2n\rfloor$ 也会随之改变。

${{\displaystyle {\begin{pmatrix}f_n\\f_{n-1}\\1\end{pmatrix}}}=\displaystyle {\begin{pmatrix}1&1&\lfloor log_2n\rfloor\\1&0&0\\0&0&1\end{pmatrix}}}{\displaystyle {\begin{pmatrix}f_{n-1}\\f_{n-2}\\1\end{pmatrix}}}$

变化中蕴含着不变性，在区间 $n\in [2^{p},2^{p+1})$ 内， $\lfloor log_2n\rfloor$ 的值不变。因此我们只需要将 $n$ 分成若干个这样的区间，进行分段的矩阵快速幂即可。

代码

#include<iostream>  
#include<cmath>
#include<cstring>  
using namespace std;
typedef long long ll;
const int N=4;
const ll mod=1e9+7;
ll n;
struct matrix//定义矩阵
{
	ll m[N][N];
	matrix()//构造函数 
	{
		memset(m,0,sizeof(m));
	}
};
//定义矩阵乘法
matrix operator *(const matrix &x,const matrix &y)
{
	matrix res;
	int i,j,k;
	for(i=1;i<=3;i++)
	{
		for(j=1;j<=3;j++)
		{
			for(k=1;k<=3;k++)
			{
				res.m[i][j]+=x.m[i][k]*y.m[k][j];
				res.m[i][j]%=mod;
			}
		}
	}
	return res;
}
//矩阵快速幂
matrix quick_matrix_pow_mod(matrix a,ll b)
{
	matrix res;
	int i;
	for(i=1;i<=3;i++) res.m[i][i]=1;//单位矩阵 
	while(b)
	{
		if(b&1) res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
matrix t,f;
void solve()
{
	//t为系数矩阵
	t.m[1][1]=1;
	t.m[1][2]=1;
	t.m[2][1]=1;
	t.m[3][3]=1;
	f.m[1][1]=f.m[2][1]=f.m[3][1]=1;
	ll i;
	for(i=3;i<=n;)
	{
		ll l,r,now=(ll)(log((double)i)/log((double)2));
		l=i;
		r=min(n,(1LL<<(now+1))-1);//分段
		t.m[1][3]=now;//更改系数矩阵
		matrix temp=quick_matrix_pow_mod(t,r-l+1);
		f=temp*f;//得到新的f
		i=r+1;//进入下一段
	}
	printf("%lld\n",f.m[1][1]);//输出
}
int main()
{ 
	while(~scanf("%lld",&n)) solve();
	return 0;
}

I. 小 C 的趣味篮球赛

$\text{CUGOJ 2176}$

题目描述

比赛又开始了，这是一场激动人心的篮球赛，比赛场上的气氛十分的热烈。但是坐在一旁的小 C 却对场上的火拼。
不这么感兴趣，开始着迷于比赛分数的变化。看着比赛得分跌宕起伏，小 C 突然好奇一个问题：双方的得分到底能够出现多少次分数相同的情况。
注意每一回合必须有甲队进一球，或者乙队进一球。
以下是一个例子，假设比赛开始的得分是 0：0，下一次小 C 看到的得分是 3：2。
此时如果进球的顺序是甲进乙进依次循环，那么总比分的变化如下
0:0 1:0 1:1 2:1 2: 2 3:2
在上述若干次的变化中包含共有 3 次分数相同。
那么下面给出我们的问题，我们首先将给出一个整数 $n$ 代表小 C 看了几次分数牌，其后 $n$ 行代表小 C 每一次观察到的比分。求问在这场比赛中，双方分数最多相同了多少次。注意使用多组输入。

输入

$n$ $(1≤n≤10000)$ 代表小 C 观看的次数。
$a_i$ $b_i$ $(0≤a_i,b_i≤10^9)$ ,代表每次观看时，甲队和乙队的得分。

输出

请输入这场比赛中比赛分数相同的最大可能次数。

样例输入

3
2 0
3 1
3 4
3
0 0
0 0
0 0
1
5 4

样例输出

2
1
5

分析

前一次的比分，要变成后一次，最佳情况是先都变成前一次比较大的那一个，然后交替加一。直到变成第二次的小的。就比如1:3到7:4，就变成3:3，4:4，也就是后一次小的减前一次大的再加一，如果后一次小的比前一次大的还小，那就不可能比分相同了。然而还需要特判，如果前一次比分相同，就不需要加一了。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct node
{
	int l,r;
};
void solve()
{
	node temp;
	node last={0,0};
	int ans=1;
	while(n--)
	{
		cin>>temp.l>>temp.r;
		if(temp.l==last.l&&temp.r==last.r) continue;
		int res;
		res=min(temp.l,temp.r)-max(last.l,last.r)+/*特判*/(last.l!=last.r);
		if(res>0) ans+=res;
		last=temp;//记录前驱
	}
	cout<<ans<<endl;
}
int main()
{
	while(cin>>n) solve();
	return 0;
}

J. 小C找众数~

$\text{CUGOJ 2177}$

题目描述

所谓众数，就是在一个具有 $n$ 个数的序列中，出现次数最多的那个数。例如： $S={1,2,2,2,3,5}$ ，则 $S$ 的众数是 $2$ ，其次数为 $3$ 。现在小C的任务是：对于给定的由 $n$ 个自然数组成的数组 $S$ ，计算出 $S$ 的众数。
本题保证每组数据中必定存在一个众数。

输入

输入数据包含多个测试实例，每组样例占两行。首先输入的是 $n$ $(0<n<10000)$ ，其后一行将会输入一个数字 $a_i$ $(0\leq a_i\leq 10^9)$ .

输出

输出一个数字 $n$ 代表该组数据中的众数。

样例输入

5
1 2 2 3 4
10
5 5 1 2 2 3 3 3 3 4

样例输出

2
3

分析

找到数列中的众数，最朴素的思想是开一个 $cnt$ 数组，遍历$\{a_n\}$，每次执行cnt[a[i]]++，但是 $a_i$ 的规模很大，考虑用 $\text{map}$ 映射的方式进行离散化处理，也就是说对于没有出现的数字，就不需要统计。

代码

#include<map>
#include<iostream>
using namespace std;
int n;
void solve()
{
	//key为数字的值，value为数字的个数。
	map<int,int>cnt;
	//读取n个数字
	while(n--)
	{
		int temp;
		cin>>temp;
		cnt[temp]++;//统计个数
	}
	//迭代器访问
	auto it=cnt.begin();
	int ans=0;
	int times=-1;
	while(it!=cnt.end())
	{
		if(times<it->second)
		{
			//答案更新
			ans=it->first;
			//最大的出现次数更新
			times=it->second;
		}
		it++;
	}
	cout<<ans<<endl;
}
int main()
{
	while(cin>>n) solve();
	return 0;
}

K. 小C的 ACM/ICPC

过水已隐藏

题目描述

小 C 是 CUGACM 的一名队员，现在他告诉你 ACM 是什么：
ACM 国际大学生程序设计竞赛（英文全称：ACM International Collegiate Programming Contest（简称 ACM-ICPC或 ICPC））是由国际计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程。
序、分析和解决问题能力的年度竞赛。经过近 40 年的发展，ACM 国际大学生程序设计竞赛已经发展成为全球最具影响力的大学生程序设计竞赛。赛事目前由 IBM 公司赞助。
赛事由各大洲区域预赛和全球总决赛两个阶段组成。决赛安排在每年的 3-5 月举行，而区域预赛一般安排在上一年的 9-12 月举行。原则上一个大学在一站区域预赛最多可以有 3 支队伍，但只能有一支队伍参加全球总决赛。
入围世界总决赛名额（WF Slots）分为参与名额（Participation Slots）、奖牌名额（Medal Bonus Slots）和其他红利名额（Other Bonus Slots）三类。其中参与名额是从 ICPC 总部分配给各大洲区的参与名额（ParticipationSlots）中，由各大洲洲区主席确定并分配给洲子赛区的部分，其中各预赛区第一名自动获得参加全球总决赛的资格；奖牌名额是 ICPC 总部根据上一年度总决赛结果直接分配给获得奖牌的特定学校的名额；其他红利名额是各大洲区主席从 ICPC 总部争取到的额外奖励名额。
全球总决赛第一名将获得奖杯一座。另外，成绩靠前的参赛队伍也将获得金、银和铜牌。而解题数在中等以下的队伍会得到确认但不会进行排名。
那么问题来了，请输出“I LOVE ACM”这行字符串。
输入
无
输出
输出“I LOVE ACM”
样例输入
样例输出
I LOVE ACM

分析

哈皮题

代码

#include<stdio.h>
int main()
{
	printf("I LOVE ACM\n");
	return 0;
}