题目列表
呜呜呜卞宇轩等巨佬出的太毒瘤了呜呜呜
cube
模拟。
真就模拟。
好好想咋模拟。
不然和我一样瞎写。
我瞎写写了 $7\ \tt{KB}$ 的模拟。
我太菜了只会这种一点一点转。
不像 爬不？立刻！ 巨佬一样 $5\ \tt{min}$ 爆切。
代码
#include<bits/stdc++.h>
using namespace std;
int t;
int a[130];
bool check()
{
return a['a']==a['b']&&a['b']==a['c']&&a['c']==a['d']&&a['e']==a['f']&&a['f']==a['g']&&a['g']==a['h']&&a['i']==a['j']&&a['j']==a['k']&&a['k']==a['l']&&a['m']==a['n']&&a['n']==a['o']&&a['o']==a['p']&&a['q']==a['r']&&a['r']==a['s']&&a['s']==a['t']&&a['u']==a['v']&&a['v']==a['w']&&a['w']==a['x'];
}
void solve()
{
cin>>a['a']>>a['b']>>a['c']>>a['d']>>a['e']>>a['f']>>a['g']>>a['h']>>a['i']>>a['j']>>a['k']>>a['l']>>a['m']>>a['n']>>a['o']>>a['p']>>a['q']>>a['r']>>a['s']>>a['t']>>a['u']>>a['v']>>a['w']>>a['x'];
int c;
/*
o->p
p->u
u->w
...
*/
if(check()){puts("YES");return;}
//1
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
if(check()){puts("YES");return;}
//2
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
//3
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
if(check()){puts("YES");return;}
//4
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
c=a['o'];
a['o']=a['r'];
a['r']=a['t'];
a['t']=a['e'];
a['e']=a['f'];
a['f']=a['w'];
a['w']=a['u'];
a['u']=a['p'];
a['p']=c;
//1
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
if(check()){puts("YES");return;}
//2
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
//3
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
if(check()){puts("YES");return;}
//4
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
c=a['m'];
a['m']=a['q'];
a['q']=a['s'];
a['s']=a['g'];
a['g']=a['h'];
a['h']=a['x'];
a['x']=a['v'];
a['v']=a['n'];
a['n']=c;
//1
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
if(check()){puts("YES");return;}
//2
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
//3
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
if(check()){puts("YES");return;}
//4
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
c=a['o'];
a['o']=a['m'];
a['m']=a['k'];
a['k']=a['i'];
a['i']=a['g'];
a['g']=a['e'];
a['e']=a['c'];
a['c']=a['a'];
a['a']=c;
//1
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
if(check()){puts("YES");return;}
//2
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
//3
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
if(check()){puts("YES");return;}
//4
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
c=a['p'];
a['p']=a['n'];
a['n']=a['l'];
a['l']=a['j'];
a['j']=a['h'];
a['h']=a['f'];
a['f']=a['d'];
a['d']=a['b'];
a['b']=c;
puts("NO");
}
int main()
{
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
cin>>t;
while(t--)
{
solve();
}
return 0;
}defly
首先，长宽高肯定自己能穿过一些，但是会有重复的。
重复的有什么呢？两两配对 GCD 之和即为个数。
但这样如果有三个长宽高都有的快就多减了，所以再加上三者 GCD。
答案即为 $L+W+H-\gcd(L,W)-\gcd(L,H)-\gcd(W,H)+\gcd(L,W,H)$。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("defly.in","r",stdin);
freopen("defly.out","w",stdout);
long long l,w,h;
cin>>l>>w>>h;
cout<<l+w+h-__gcd(l,w)-__gcd(w,h)-__gcd(l,h)+__gcd(__gcd(l,w),h)<<endl;
return 0;
}florr
先咕着。
代码
generals
so lazy
就贴个剪切板吧。
我自己也说不清
cyx防止洛谷炸了，偷偷复制的一份源码
## 题解
### 递推过程
- 每次可以选择向上走,或者左拐一段再向上,或者右拐一段再向上: 显然地,左拐与右拐等价
- $a_i$ 为可以走 $i$ 步的答案:
$a_0=1,a_1=3,a_2=7,...$
- 考虑啥时候向上拐:
$a_i=a_{i-1}+2\times(a_{i-2}+...+a_0+1)$
对上式解释: 可以直接向上 $a_{i-1}$ ,或向左(右)一步再向上 $2\times a_{i-2}$ ... 或者最后一步上拐 $2\times a_0$ ,或者不上拐(一直直走) $2$
- 令 $S_i=\sum\limits_{j=0}^ia_i$ , 有:
$a_i=a_{i-1}+2\times S_{i-2}+2$
- 做如下变形:
$S_{i-2}=\dfrac{a_i-a_{i-1}-2}{2} ......①$
$S_{i-1}=\dfrac{a_{i+1}-a_i-2}{2} ......②$
用 ②减① ,有:
$\dfrac{a_{i+1}-2\times a_i+a_{i-1}}{2}=a_{i-1}$
于是: $a_{i+1}=2\times a_i+a_{i-1}$
所以: $a_i=2\times a_{i-1}+a_{i-2}$
### 矩阵快速幂
不会的建议学习矩阵快速幂以及斐波那契的 $O(\log n)$ 算法
$\begin{bmatrix}a_i&a_{i-1}\end{bmatrix}=\begin{bmatrix}a_{i-1}&a_{i-2}\end{bmatrix}\begin{bmatrix}2&1\\1 &0\\\end{bmatrix}$
### 注意事项
1. 进行矩阵快速幂时, $n$ 较小需特判(避免某些错误比如负数次方)
2. 记得取模,开 `long long`
### 奉上代码
```
#include<iostream>
#include<cstdio>
using namespace std;
/*
- a_1=3
- a_2=7
- a_3=17
[a_i,a_{i-1}]=[a_{i-1},a_{i-2}]*[2,1]
[1,0]
*/
const long long md=1000000007;
struct Matrix
{
long long a[2][2];
};
Matrix operator *(const Matrix &as,const Matrix &bs)//Matrix Mul
{
Matrix cs;
cs.a[0][0]=(as.a[0][0]*bs.a[0][0]+as.a[0][1]*bs.a[1][0])%md;
cs.a[0][1]=(as.a[0][0]*bs.a[0][1]+as.a[0][1]*bs.a[1][1])%md;
cs.a[1][0]=(as.a[1][0]*bs.a[0][0]+as.a[1][1]*bs.a[1][0])%md;
cs.a[1][1]=(as.a[1][0]*bs.a[0][1]+as.a[1][1]*bs.a[1][1])%md;
return cs;
}
Matrix qpw(Matrix as,long long bs)//Matrix Pow
{
Matrix rt;
rt.a[0][0]=1; rt.a[0][1]=0;
rt.a[1][0]=0; rt.a[1][1]=1;
while(bs)
{
if(bs&1)
rt=rt*as;
as=as*as;
bs>>=1;
}
return rt;
}
long long f(long long x)//Calc
{
if(x==0) return 1;
if(x==1) return 3;
if(x==2) return 7;
Matrix rt;
rt.a[0][0]=2; rt.a[0][1]=1;
rt.a[1][0]=1; rt.a[1][1]=0;
rt=qpw(rt,x-2);
return (7*rt.a[0][0]+3*rt.a[1][0])%md;
}
int T;
int main()
{
//scanf("%d",&T);
T=1;
while(T--)
{
long long n;
scanf("%lld",&n);
printf("%lld\n",f(n));
}
return 0;
}
```
70pts 代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long f[10000020];
int main()
{
freopen("generals.in","r",stdin);
freopen("generals.out","w",stdout);
f[0]=1;
f[1]=3;
long long n;
cin>>n;
for(int i=2;i<=n;i++)
{
f[i]=2*f[i-1]+f[i-2];
f[i]%=mod;
}
cout<<f[n]<<endl;
return 0;
}