Codeforces Round #380~#400 div2 总结

*：刷这些题注要是为了提升1A率，以及做题效率，读题效率，英语水平…

Round 380：

• 耗时：45min 错误：A*1，B*0，C*1. 评价：低
  主要时间浪费在第三题的调试和读题上

A. Interview with Oleg

• 题意：
  给你一个字符串，把其中的ogogogo串用***代替，输出操作后的串。
• 题解：
  O(n)扫一遍，检验每个点延伸到的最远的ogogo串，然后在ans数组中加上***。
• 错误：
  1.被题意杀，以为一个ogo用1个*。

B. Spotlights

• 题意：
  给你一个n行m列的01图，对于一个点的一个方向，它有贡献当且仅当该位置为0且该方向上至少有一个1.
• 题解：
  记录4个数组分别表示每个点的上下左右有没有1，最后统计一遍。
• 错误：1A

C. Road to Cinema

• 题意：
  给你n(<=2e5)，k(<=2e5)，s(<=2e9)，t(<=2e9)分别表示车的数量，加油站的数量，终点距离，要求时间（在t或t之前到）。
  每辆车有两个属性：c（价格），v（油量）。
  车有两种模式：
  
  1. 平常模式：2分钟1单位长度，油耗为1。
  2. 加速模式：1分钟1单位长度，油耗为2。

在加油站加油不需要时间且能加满。
起点为0，终点为s。
接下来给出所有车的信息（c，v）和加油站的信息（离起点的距离）
求在t时间及以内达到s的最小代价（车价），若不能则输出-1。

• 题解：
  首先发现很容易判断对于一个容量是否可行，那么就可以二分这个容量，找到最小合法容量再借此找到最小代价。
• 错误：
  1.数组范围开小了。。

Round 381：

• 耗时：25min 错误：A*1，B*0，C*0. 评价：中
  主要时间浪费在第三题读题上

A. Alyona and copybooks

• 题意：
  给你四个数：n，a，b，c(0<=n,a,b,c<=1e9)，表示已有n本书，买1本书a元，2本b元，3本c元，求最小的代价使（n+买的书）%4=0。
• 题解：
  先把n%4不用说，然后分讨买i(0< i <=4)本书的最小代价。
  f[1]=min(a,min(b+c,3*c));
f[2]=min(b,min(a+a,c+c));
f[3]=min(c,min(3*a,a+b));
f[4]=0;
• 错误：
  1.f[1]漏讨论3*c的情况。
  2.以为1e9不会溢出就没开long long.

B. Alyona and flowers

• 题意：
  给你一个长度为n(<=100)的数组，其中有正有负，再给你m(<=100)个l,r,表示这个操作的价值为∑ri=lai
  对于每个操作你可以选也可以不选，求最大的价值。
• 题解：
  维护前缀和，如果某个操作的前缀和>0就加上去。
• 错误：1A

C. Alyona and mex

• 题意：（这题意真是。。。）
  定义mex为从0开始，不在集合中的最小的数。
  给你n，m，分别表示a[]数组元素个数和信息数量，接着给出m个询问l,r表示a[]数组中a[l]~a[r]的mex，现在要求出a数组，使所有询问中最小的mex最大。
• 题解：
  看懂这题目就真是简单了。。。首先最小的mex最大那就是最小的区间的元素个数嘛，然后a数组就只需要在每个位置对ans取模即为答案了（保证别的询问都大于它）
• 错误：1A

Round 382：

• 耗时：33min 错误：A*0，B*0，C*0. 评价：中
  主要时间浪费在第三题推导上

A. Ostap and Grasshopper

• 题意：
  给你一个字符串，由'.','#','G','T'组成，这四个分别代表空地，障碍，起点，终点，障碍上不能站。
  再给你一个数字代表一步跳的长度，问是否能从起点到达终点。
• 题解：
  先判无障碍情况能不能到，然后再模拟一步步跳
• 错误：1A

B. Urbanization

• 题意：
  给你n，n1，n2，n个数字，从这n个数字中分别选出n1，n2个数（一个数只能选一次），使Set n1的平均数+Set n2的平均数最大，输出这个值，精度误差1e6以内。
• 题解：
  贪心，首先肯定选n1+n2个最大的数，那么怎么分配？ 我们稍稍脑补一下就可以知道应该是将前面的大的数分给min（n1，n2）。这样做一遍就可以了
• 错误：1A

C. Tennis Championship

• 题意：
  n（<=1e18）个人进行比赛。
  一个人能和另一个人比赛的条件是他们所赢场数的差小于等于1.
  一个人失败后立刻淘汰，问胜利者最多能进行多少场比赛

• 题解：
  显然我们的思路是将n分成两块比n小的来看，那么实质上就是这两块的胜利者再比一次，这时我们发现分配这两块的人数十分困难，那么假设答案为ans，那么这时我们想到最赚的方法肯定是一个赢ans-1的和一个赢ans-2的人比，而且这两个都是可以递推的，最后其实我们发现这就是一个斐波那契数列，我们的答案便是最大的小于n的斐波那契数的项数。（这肯定有点绕，但这确实是我的思考过程）

• 错误：1A

Round 383：

• 耗时：–min(评测机GG) 错误：A*1，B*6，C*4. 评价：低到爆炸
  想必我做这套题的时候在睡觉…

A. Arpa’s hard exam and Mehrdad’s naive cheat

• 题意：
  求1378^n最后一位,n<=1e9
• 题解：
  显然做8^n次就可以了,然后再化为2^3n,然后mod一下,然后就没有然后了…
• 错误：
  1.那个规律数组都能打错…

B. Arpa’s obvious problem and Mehrdad’s terrible solution

• 题意：
  给你n,x(<=100000),求∑ni=1∑nj=i+1[a[i] xor a[j]=x].
• 题解：
  开cnt数组记录每个数出现的次数,那么ans=∑1e5i=1cnt[i]∗cnt[x xor i]
  但其中有个例外,当x^i==i时答案只能加cnt[i]*(cnt[x^i]-1)
• 错误：
  1.因为数组大小原因没有特盘x^i>1e5的情况RE了
  2.没有讨论x^i==i的情况WA了
  3.意识模糊随便乱交…

C. Arpa’s loud Owf and Mehrdad’s evil plan

• 题意：
  给你长度为n(<=100)的数组,表示一个人的后继,让你求一个数x,使其满足这个条件:
  设a的x次后继为b,那么要求b的x次后继为a;
  注意:一个人的后继有可能是自己.

• 题解：
  首先有两三种情况:

  1. 一个人的a次后继是自己且他在a次之内访问过的人的a次后继也是自己(即这若干个人形成了一个环)
  2. 一个人走若干次能到达另一个人,而另一个人却到不了这个人(即非环).
  3. 一个人的后继就是自己(第一种的特殊情况).

  那么显然如果含第二种情况显然GG了.
  所以现在只考虑1,3情况,由于第三种情况可以不考虑.(显然无论几次后继都是自己)
  好那么就只剩第1种了,这就很简单了,只要求这些数的lcm就可以了.

• 错误：1A

Round 384：

• 耗时：<30min(评测机继续GG) 错误：A*1，B*1，C*1. 评价：低

A. Vladik and flights

• 题意：
  给你一个01字符串,以及起点和终点,同色穿梭不需要代价,异色穿梭代价为两点的坐标差,求起点到终点的代价
• 题解：
  同色为0,异色为1(脑补一下呗…)
• 错误：
  1.我居然naive到还去找了离起点最近的异色点…(手动巴掌)

B. Chloe and the sequence

• 题意：
  给你n，k,分别表示操作次数,询问的位置.
  初始序列为1,每次操作为:原串+’操作次数’+原串. 例子:原串为121,操作后变为1213121
  求n次操作后第k个位置的数是什么
• 题解：
  我们稍微观察一下就能发现这和二分搜索有奥妙重重的关系->a[i]=n-二分搜到这个位置的次数.那么我们就这么做就可以了
• 错误：
  1.二分的mid没开long long…

C. Vladik and fractions

• 题意：
  给你n,求2n=1x+1y+1z 中x,y,z.
  输出任意解,如果没有就输-1.

• 题解：
  首先我们模拟一遍样例,然后我们就能发现规律:x=n,y=n+1,z=n*(n+1),好,输出就行了…

• 错误：
  1.如此一道弱智题我竟忘了1要特判-1…