[LGR-055]洛谷11月月赛 蒟蒻的题解

本次比赛难度是真的水(然而因为和noi.ac的比赛冲突,所以并没有认真做),前两道题都是送分水题。

本次月赛说明了一点:人有多大胆,题有多大分。(不少暴力的分数都超乎你的想象)

PS:chen_zhe AK!

A. 终于结束的起点

题解

算法一

考虑\(M \leq 2018\)的情况,暴力计算可以拿70分。

但该算法的时间复杂度真的是题目里所说的\(O(M^2)\)吗?

事实上可以证明,该算法实际的复杂度上界是\(O(6M)\),对于\( M \leq 706150 \)的数据绰绰有余。(因为判了\( M \leq 2018 \)才跑暴力的本蒟蒻已经哭死)

#include <stdio.h>
int f[2];
int main()
{
 int m;
 scanf("%d",&m);
 f[0]=0,f[1]=1;
 for(int i=2;;i++)
 {
  f[i%2]=(f[0]+f[1])%m;
  if((f[0]==0||f[1]==0)&&(f[0]+f[1])%m==1)
  {
   printf("%d\n",i);
   return 0;
  }
 }
 return 0;
}

算法二

(已经没有算法二了)

B. 跳跳!

题解

通过样例可以假设:每次让高度差值最大,可以使得体力消耗最大。

事实上,这样的猜想是正确的。(证明略)

#include <iostream>
#include <algorithm>
using namespace std;
int h[305],vis[305];
int main()
{
 int n;
 long long ans=0;
 cin>>n;
 for(int i=1;i<=n;i++)
  scanf("%d",&h[i]);
 int curh=0;
 for(int i=1;i<=n;i++)
 {
  int maxd=0,to;
  for(int j=1;j<=n;j++)
   if((!vis[j])&&abs(curh-h[j])>=maxd)
   {
    to=j;
    maxd=abs(curh-h[j]);
   }
  ans+=maxd*maxd;
  vis[to]=1;
  curh=h[to];
 }
 cout<<ans<<endl;
 return 0;
}

D. 不围棋

题解

算法零

考虑\( n=1\)的情况,直接输出-1 -1便可白拿10分。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注