EZ 2018 03 23 NOIP2018 模拟赛(五)

  链接: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 ;
}
上一篇:Java的static关键字


下一篇:ABP理论学习之发布说明