T1 斐波那契

题意去 \(luogu\) 上面看吧

通过观察发现每个月的增量构成了斐波那契数列

然后我们前缀和，还照样是个斐波那契数列（这个好像我原来还不知道）

所以可以发现每个点的父亲标号为

其中 \(fib_{idx}\) 为大于等于 \(x\) 的首个斐波那契数

我的做法是暴力记录一个点到根路径上的所有值

然后挂成了 \(70\)（\(luogu\) 上就可以过了）

然后学习发现可以对于两个点每次跳那个标号大的点的父亲，然后手写个二分就能过去了

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=100,inf=1e12;
	int fib[N],x=4,s[N]; set<int> st;
	inline int calc(int val)
	{
		int l=1,r=x,ans=x;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			
			if(s[mid]>=val) ans=mid,r=mid-1;
			else l=mid+1;
		}
		return ans;
	}
	inline void work()
	{
		st.clear();
		int a=read(),b=read();
		while(a!=b)
		{
		    if(a<b) swap(a,b);
		    int ma=calc(a); a-=s[ma-1];
		}
		printf("%lld\n",a);
		return ;
	}
	signed main()
	{
		fib[1]=s[1]=1; s[2]=(fib[2]=1)+1; s[3]=(fib[3]=1)+2;
		while(s[x-1]<=inf) fib[x]=fib[x-1]+fib[x-2],s[x]=s[x-1]+fib[x],++x; --x;
		int T=read(); while(T--) work();
		return 0;
	}
}
signed main(){return yspm::main();}

T2 数颜色

题面去 \(Luogu\) 看

本题卡主席树，然后换了个 \(vector\)

就过去了

T3 矩阵游戏

推式子，暴力 \(80\) 都挺无脑的

但是正解好像比 \(80\) 还好写……

就是个推式子

固定一维推一维

没想着写 \(\sum\) 毁了我

T4 优美的序列

link

「考试总结2020-08-03」可期

原文：https://www.cnblogs.com/yspm/p/13426905.html