链接：http://211.140.156.254:2333/contest/65
这次Rating重回Rank18，我是20的守门员（滑稽）
这次题目和数据普遍偏水，我T2打错了一个变量名竟然过了所有的样例而且有90分（滑稽）
但最后一题SB了，忽略了还有不为2的几次幂的情况，所以炸成10分。
200分竟然Rank6，不过xu‘yi’zhou大佬直接AK了这场比赛。
T1 类欧几里得算法（不存在的，爆搜+打表找规律）
给出的标算是这样的：
比较简单的类欧几里得算法，考虑如果当前所需电阻
大于1，串联 1Ω 电阻
小于1，并联 1Ω 电阻
然后给出我的算法：
首先根据简单的物理学知识，可以得到当目前电阻为a/b时，再加上一个电阻的情况有：
a+b/b(串联上一个1Ω的电阻)
a/a+b(并联上一个1Ω的电阻)
所以我们暴力广搜，别指望过去
然后准备好纸和笔，令读入的两个数为a/b，开始：
for (a=1;;++a)
for (b=1;;++b)
让你的暴力开始跑吧，我们定义ans=(a,b)
可以得到这些性质：
(a,1)=(1,a)=a
(a,b)=(b,a)
(a,b+a)=(a,b)+b/a
然后发现这些性质后就可以直接递归求解了（我用了迭代，注意边界为a=1）
CODE
#include<cstdio>
using namespace std;
typedef long long LL;
LL a,b,ans;
inline void swap(LL &a,LL &b)
{
LL t=a; a=b; b=t;
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
scanf("%lld%lld",&a,&b);
for(;;)
{
if (a>b) swap(a,b);
if (a==) { printf("%lld",ans+b); break; }
if (b%a==) { printf("%lld",ans+b/a); break; }
ans+=b/a; b%=a;
}
return ;
}
T2 一道比较简单的贪心题目
先把数组sort一遍，如果没有1的话就输-1
考虑已经能组合出 1∼x 的数值
那么下一个硬币取 x 以内最大的数 k
使能组合出 1∼x+k，直到得到要求的个数
由于这里x的范围较大，所以每一次推进不能拿来加（要不然就等着吃TLE吧），%一下即可
CODE
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL N=;
LL a[N],ans,x,n,now,last;
inline char tc(void)
{
static char fl[],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
x=; char ch=tc();
while (ch<''||ch>'') ch=tc();
while (ch>=''&&ch<='') x=x*+ch-'',ch=tc();
}
int main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
register int i;
read(x); read(n);
for (i=;i<=n;++i)
read(a[i]);
sort(a+,a+n+);
if (a[]!=) { puts("-1"); return ; }
ans=now=last=; a[n+]=x+;
while (now<x)
{
while (now>=a[last+]-&&last<n) ++last;
if (last==n) { ans+=(x-now)/a[last]; break; }
ans+=(a[last+]-now-)/a[last]+; now+=((a[last+]-now-)/a[last]+)*a[last];
}
printf("%lld",ans);
return ;
}
T3 首先可以考虑一下性质：对于数列中的数，如果不是2的整数幂只要在最后乘上去就可以了（原理很简单，主要开始没想到这个导致写了一个可以过的DP但后来放弃了）
还有一点，当所有的数都是2的幂次的时候，判断是否可以合出2048只需要判断它们的和是否达到2048即可（可以自己想像2进制的加法，就是2048的原理）
所以我们用一个类似于背包的东西来记录所有价值和小于2048的方案（大于的可能会很麻烦），用子段的总数减去即可。
所有还要乘上非2的幂次的数，由于全部都是2的幂次，快速幂求之。
CODE
#include<cstdio>
using namespace std;
const int P=,mod=;
int f[P],n,x,m,tot,ans;
inline char tc(void)
{
static char fl[],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=; char ch=tc();
while (ch<''||ch>'') ch=tc();
while (ch>=''&&ch<='') x=x*+ch-'',ch=tc();
}
inline void inc(int &x,int y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void dec(int &x,int y)
{
if ((x-=y)<) x+=mod;
}
inline int quick_pow(int x,int p)
{
int res=;
while (p)
{
if (p&) res=((long long)res*x)%mod;
x=((long long)x*x)%mod;
p>>=;
}
return res;
}
int main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
register int i,j;
read(n); f[]=;
for (i=;i<=n;++i)
{
read(x);
if (x^(x&-x)) continue;
for (++m,j=P-;j>=x;--j)
inc(f[j],f[j-x]);
}
for (i=;i<P;++i)
inc(tot,f[i]);
int now=quick_pow(,m);
dec(ans=quick_pow(,m),tot);
ans=((long long)ans*quick_pow(,n-m))%mod;
printf("%d",ans);
return ;
}