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

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

本次月赛说明了一点：人有多大胆，题有多大分。（不少暴力的分数都超乎你的想象）

A. 终于结束的起点

题解

算法一

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

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

事实上可以证明，该算法实际的复杂度上界是 \(O(6M)\)，对于 \( M \leq 706150 \) 的数据绰绰有余。

#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\) 分。