校赛链接：济南大学第一届ACM校赛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/contest/58844#problems本人作为选手参加了这次比赛（混盗梦空间分数(bushi)）
讲一下每个题的做法：
A
简单的模拟题，注意题意：第四个月而非每四个月
用small，big数组表示当前月份的小兔子和大兔子数量，用num数组存放当前年份出生的小兔子数
维护这三个数组即可，答案是small[n]+big[n]
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int small[N],big[N],num[N];
int main(){
int n;
cin>>n;
small[1]=1;
num[1]=1;
for(int i=2;i<=n;i++){
int t=i-3;
if(t>=1)
{
big[i]=big[i-1]+num[t];
small[i]=small[i-1]-num[t];
}
else{
big[i]=big[i-1];
small[i]=small[i-1];
}
small[i]+=big[i];
num[i]=big[i];
}
cout<<small[n]+big[n];
}
B
给定1到n的一个排列，一次操作允许交换任意两数，求最小的交换次数使这个数列变为1，2，....，n
结论题，
设数x一开始在第y个位置，若x==y，则他在正确的位置上，不用动；否则交换第y个位置的数和第x个位置的数，这样这个数x 位置就正确了。然后再看此时第y个位置的数t，如果t==y,结束；否则将交换第t个数和第y个数，一直这样做下去，总有一个时刻，和第y个位置有关的所有数都回到了正确的位置上，且容易发现这样一定是最优的。
例如?
i? ?（下标）? ? ? ? ? ?1? ? 2? ? 3? ? 4? ? 5
一开始?? ? ? ? ? ? ? ? ?3? ? 2? ? 4? ? 5? ? 1
第一次? ? ? ? ? ? ? ? ? 4? ? 2? ? 3? ? 5? ? 1? （3位置正确）
第二次? ? ? ? ? ? ? ? ? 5?? ?2? ? 3? ? 4? ? 1? （4位置正确）
第三次? ? ? ? ? ? ? ? ? 1? ? 2? ? 3? ? 4? ? 5? （5位置正确）?
由于每一个错误的数，必定在这样的一个“圈”里，所以找出这样的圈的个数即可，
设有k个圈(单独一个数也看成一个圈），他们分别有个数，那么每个圈内要进行
次操作，因此总的次数为?
次
时间复杂度O（n）（因为每个数最多被交换一次）
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+500;
int a[N];
bool st[N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int res=0;
for(int i=1;i<=n;i++){
if(!st[i]){
++res;
while(1){
int v=a[i];
if(v==i)break;
st[v]=1;
swap(a[i],a[v]);
}
}
}
printf("%d\n",n-res);
return 0;
}?C
输入一张牌，问比他大的有几种牌，直接看第一个字符
#include<bits/stdc++.h>
using namespace std;
char a[]="234567891JQKA";
int main(){
string str;
cin>>str;
char c;
if(str.size()==2){
c='1';
}
else c=str[0];
int n=strlen(a);
for(int i=0;i<n;i++){
if(c==a[i]){
cout<<n-i-1;
return 0;
}
}
}
D，给定一堆点和圆的半径r，问至少要在x轴画几个圆，才能把这些点都盖住。
直接做不好做：
换一种思考方式：
对每一个点P（x,y），我们考虑求出x轴上的某个区间[L,R] 满足，在这个区间内任意一点画半径r的圆都能盖住点P,区间外面任意一个点画圆都无法盖住点P
如果 abs(y)>r ，那么区间不存在，解就不存在
否则由平面几何知识知，区间为?
对所有点都能求出这样的区间
问题转化为，求最少的点数，使得每个区间内都至少有一点
贪心即可：把所有区间按右端点从小到大排序贪心，每次遇到一个区间内没有圆心，就取其右端点作为一个圆心。
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<db,db> PDD;
const int N=1e5+500;
PDD lines[N];
bool cmp(PDD a,PDD b){
return a.second<b.second;
}
const db eps=1e-8;
int main(){
int n;db r;
cin>>n>>r;
bool ok=1;
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(r<(db)abs(y)-eps)ok=0;
else {
db d=sqrt(r*r-(db)y*y);
lines[i]={(db)x-d,(db)x+d};
}
}
if(!ok){
cout<<-1;
return 0;
}
sort(lines+1,lines+n+1,cmp);
int cnt=0;
double ed=-2e9;
for(int i=1;i<=n;i++){
if(lines[i].first>ed+eps){
cnt++;
ed=lines[i].second;
}
}
cout<<cnt;
}
E
给定每个点的能量，每次能随机往前走1，2，3，4，5，6格，且移动次数不超过m次，每踩到一个点都要加能量，问走到终点最差情况下能获得多少能量。
数据范围不大，n和m都不超过1000，
考虑dp
设dp(i,j)表示当前在第i格(且未获得当前位置的能量)，且还能移动j次，到终点获得的最少能量数，
问题问的就是dp(0,m)
初始条件是：到终点时，dp(n,i)=a[n] i=0,1,.....,m
转移方程是dp(i,j)=min ( dp ( i +?t , j - 1 ) + a[ i ] ) (t=1,2,3,4,5,6)
#include<bits/stdc++.h>
using namespace std;
const int N=1050;
typedef long long ll;
ll f[N][N];
ll a[N];
#define ckmin(x,y) x=((x)<(y))?(x):(y)
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
memset(f,0x3f,sizeof f);
for(int i=0;i<=m;i++)f[n][i]=a[n];
for(int i=n-1;i>=0;i--){
for(int j=1;j<=m;j++){
for(int t=1;t<=6;t++){
if(i+t>n)break;
ckmin(f[i][j],f[i+t][j-1]+a[i]);
}
}
}
if(f[0][m]<1e16)
cout<<(f[0][m]);
else puts("-1");
}
F
给定n，求出n有多少种 不同的 拆分成若干个数的和 的方案 且满足 这些数互不相同，且都是Fibonacci数列中的项
这题数据范围为1e16
实际上可以更大
加强版链接P4133 [BJOI2012]最多的方案 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我这里直接给出一种O（log（n））的做法
对n的每一种分解方式
我们考虑这里面最大的数p：
我们设是小于等于n的最大的Fibonacci数列中的项
那么我们可以断言p只能是或
:
为什么：
直观的感觉：
首先Fibonacci数列增长速度是很快的，基本上是一个指数级的增长，
实际上我们有通项公式?
?（这个为什么，请自行查阅资料）
那么他的和数列应该也是一个指数级的数列，
因为考虑的是最大的数p，所以除了p以外，n的分解中其他项都严格小于p
p和之前的数的和一定都和p “ 差不多”（可以自己试试，一般就差个两三倍最多），如果p比较小的话，那么他们的和，会比n小很多，就不可能是n了
严格的证明：记表示Fibonacci数列前k项和
Fibonacci数有一个神奇的性质：
如
f? ?1? 1? 2? 3? 5? ?8
s? 1? 2? 4? 7? 12 20
这个有很多种证明方法，在这里就不讲了（你可以直接把通项代入验证）
那么如果?
则
因此,而p之前的所有数之和一定是不超过
的，因此他们加起来也不可能到p，所以这是不可能的
有了以上结论，就很容易做了
为了避免重复，我们设Fibonacci数列第零项和第一项分别是1和2
我们设dp(n,x)表示和为n，且分解式中最大的数小于等于Fibonacci数列的第x项的方案数
那么答案就是?????????? ? ? ? ，?其中????????
请思考为什么要加上限制条件：最大的数小于等于第x项
记k为使最大的k
我们考虑分解式中最大的那个数?
那么n的，满足最大数小于等于的分解方案数，就是?
(请思考这是为什么，为什么这里能写等号)
因为数比较大，所以不能用数组存状态，我们采取递归加记忆化搜索的方式，用哈希表或者map来存状态，因为Fibonacci数列增长的很快，且几乎为指数级，所以这样做的复杂度是O（log n）的
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[200],s[200];
int getk(ll x){
for(int i=0;i<=130;i++)if(f[i]>x)return i-1;
}
map<pair<ll,ll>,ll> ans;
ll solve(ll n,ll x){//和为n,且都<=第x项
if(n==0)return ans[{0,x}]=1;
if(n==1)return ans[{1,x}]=1;
if(ans.find({n,x})!=ans.end())return ans[{n,x}];
int k=getk(n);
ll rt=0;
for(int i=0;i<2;i++){
if(k-i-1>=0){
if(s[k-i-1]>=n-f[k-i]&&k-i<=x)rt+=solve(n-f[k-i],k-i-1);
}
}
return ans[{n,x}]=rt;
}
int main(){
f[0]=1,f[1]=2;
s[0]=1,s[1]=3;
for(int i=2;i<=140;i++)f[i]=f[i-1]+f[i-2],s[i]=s[i-1]+f[i];
ll n;cin>>n;
cout<<solve(n,getk(n));
}
压行过后的代码（纯属没事干瞎jb乱搞）
#include<bits/stdc++.h>
long long n,fb[200],sf[200];
int getk(long long x){for(int i=0;i<=130;i++)if(fb[i]>x)return i-1;}
std::map<std::pair<long long ,long long >,long long > ans;
long long solve(long long n,long long x){
if(ans.find({n,x})!=ans.end())return ans[{n,x}];
if(n==0||n==1)return ans[{n,x}]=1;
int k=getk(n);long long rt=0;
for(int i=0;i<2;i++)if(k-i-1>=0&&sf[k-i-1]>=n-fb[k-i]&&k-i<=x)rt+=solve(n-fb[k-i],k-i-1);
return ans[{n,x}]=rt;
}
main(){
fb[0]=1,fb[1]=2;sf[0]=1,sf[1]=3;
for(int i=2;i<=140;i++)fb[i]=fb[i-1]+fb[i-2],sf[i]=sf[i-1]+fb[i];
std::cin>>n;std::cout<<solve(n,getk(n));
}