vp上古场次ing
CF225A Dice Tower
1.题目简述：
有 \(n\) 个骰子被叠在了一起。对于每个骰子上的一个数，与它对面的数的和始终为 \(7\) 。
你是小明，你只能从正面看这个骰子塔，你看到了每一个骰子的两面 \(a\) 与 \(b\) 。以及最顶上的数。
试问是否有可能用正常的骰子叠出描述中的骰子塔？
如果可以输出 \(\text{YES}\) ，否则输出 \(\text{NO}\) 。
2.解析：
问你是否能用正常的骰子堆出描述中的塔，那就是判断是否这个塔里会有不正常的骰子，也就是不是每个面的数字互不相同。
我们发现我们知道了顶上骰子的三个面，那么我们根据面对面的数字和为 \(7\) 。可以把第一个骰子的六面确定。
然后，这时第二个骰子的六面中也有三面被确定了。然后就可以往下做。
那么我们就只需要判定是否有一个骰子中有两面是相同的。
由于我们已知合法两面，那我们只用判断这两面是否有一面的值为骰子的顶部元素或者骰子的底部元素即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
int n,x,y;
struct node{
int a,b;
}f[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>n>>x;
y=7-x;
for(int i=1;i<=n;i++){
cin>>f[i].a>>f[i].b;
if(f[i].a==x||f[i].a==y){
printf("NO");return 0;
}
if(f[i].b==x||f[i].b==y){
printf("NO");return 0;
}
}
printf("YES");
return 0;
}
CF225B Well-known Numbers
1.题目描述：
将一个数拆成若干个 \(k\) 阶斐波那契数的和，要求总数不小于 \(2\) 。
2.解析：
我们都知道传统的斐波那契数列是 \(f_i=f_{i-1}+f_{i-2}\) 。是将前两个数加起来作为自己的值。而扩展的斐波那契数列就是将自己的前 \(k\) 个数加起来作为自己的值。
然后在 \(f_k\) 之前的数为 \(0\) ， \(f_k=1\) 。
我们发现 \(k\) 很大。直接去求就死了。
那么我们可以把 \(k\) 当为 \(1\) ，然后所有数减去一个 \(k\) 。
这样就是从 \(0\) 开始了，然后因为在 \(k\) 之前的数都为 \(0\) 。
所以不需要考虑这些数的值，然后计算每个 \(f\) 就做前缀和就完事了。
然后因为我们知道斐波那契数在几千次后已经很大了，同理的我们只用求几千次的 \(k\) 阶斐波那契数，然后从大到小往下取。
如果取出来，个数不满，那就加上 \(0\) 就是了。
因为 \(0\) 也是一个满足要求的斐波那契数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50000;
int sum,k,s[N],f[N],tot,ans[N],num;
signed main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>sum>>k;
//你模拟一下，就发现他就是加前面的k个
f[0]=0;f[1]=1;f[2]=1;
s[0]=0;s[1]=1;s[2]=2;
int g=0;
for(int i=3;i<=4000;i++){
int it=max(i-k,(int)1);
f[i]=s[i-1]-s[it-1];
s[i]=s[i-1]+f[i];
if(f[i]<0){
g=i-1;
break;
}
}
for(int i=g;i>=1;i--){
if(sum>=f[i]){
sum-=f[i];
ans[++num]=f[i];
}
}
if(num<=2){
ans[++num]=0;
}
sort(ans+1,ans+num+1);
cout<<num<<"\n";
for(int i=1;i<=num;i++){
cout<<ans[i]<<" ";
}
return 0;
}