前言：就剩一场了

啊，今天下午这场，2点半才睡醒，爬起来开始写题。然后经历了最舒服的前1个小时和最自闭的后2个半小时。

A、模板

这个题不难，可以定义在签到题的位置上。但是！我一上场，一看题干，就和我之前做过的一道题重合了。都是对字符串进行编辑来进行变化。

编辑距离

这两个题长得太像了，前者就是个普通的计数，后者就得dp。完全是两个概念的。刚一看到题，我还想今天说要降难度，咋一上来就整个这。

  1. import java.util.*;
  2. class q{
  3.     q(){
  4.         Scanner scanner=new Scanner(System.in);
  5.         int n=scanner.nextInt();
  6.         int m=scanner.nextInt();
  7.         char[] s1=scanner.next().toCharArray();
  8.         char[] s2=scanner.next().toCharArray();
  9.         int times=Math.abs(n-m);
  10.         int k=Math.min(n,m);
  11.         for(int i=0;i<k;i++){
  12.             if(s1[i]!=s2[i])times++;
  13.         }
  14.         System.out.println(times);
  15.     }
  16. }
  17. public class Main { public static void main(String[] args) {new q(); }}

B、牛牛战队的比赛地

一开始没理解这个题啥意思，后来知道他的意思是取能令其考试地点到其所有培训基地最小的横坐标。

有点意思。

  1. import java.util.*;
  3. class q {
  4.     private double[][] k;
  5.     private int n;
  6.     private double length(double x){
  7.         double max=0.0;
  8.         for(int i=0;i<n;i++)max=Math.max(max,k[i][0]-x)*(k[i][0]-x)+k[i][1]*k[i][1]);
  9.         return max;
  10.     }
  11.     q() {
  12.         Scanner scanner=new Scanner(System.in);
  13.         n=scanner.nextInt();
  14.         k=new double[n][2];
  15.         double left=999999.0;
  16.         double right=-999999.0;
  17.         for(int i=0;i<n;i++){
  18.             k[i][0]=scanner.nextDouble();
  19.             k[i][1]=scanner.nextDouble();
  20.             if(left>k[i][0])left=k[i][0];
  21.             if(right<k[i][0])right=k[i][0];
  22.         }
  23.         double midl,midr;
  24.         for(int i=0;i<100;i++){
  25.             midl=(left+left+right)/3;
  26.             midr=(left+right+right)/3;
  27.             if(length(midl)>length(midr)) left=midl;
  28.             else right=midr;
  29.         }
  30.         System.out.println(Math.pow(length(left),0.5));
  31.     }
  32. }
  34. public class Main {public static void main(String[] args) {new q();}}

C、C语言IDE

这道题的意思很好想，理解起来不难。就是代码奇丑无比。这里我贴上官方题解。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. string source;
  5. void replaceAll(string &s, string oldstr, string newstr)
  6. {
  7.     for (string::size_type pos = 0; pos != string::npos; pos += newstr.length())
  8.         if ((pos = s.find(oldstr, pos)) != string::npos) s.replace(pos, oldstr.length(), newstr);
  9.         else break;
  10. }
  11. struct functions{
  12.     string inClass, name, outputType;
  13.     vector<string> inputType;
  14.     functions(string inClass = "", string name = "", string outputType = "void", vector<string> inputType = vector<string>(0))
  15.     :inClass(inClass), name(name), outputType(outputType), inputType(inputType) {}
  16. };
  17. vector<functions> funs;
  18. void solve(string &s)
  19. {
  20.     replaceAll(s, "/*", " /* ");
  21.     replaceAll(s, "*/", " */ ");
  22.     replaceAll(s, "//", " // ");
  23.     replaceAll(s, "(", " ( ");
  24.     replaceAll(s, ")", " ) ");
  25.     replaceAll(s, "{", " { ");
  26.     replaceAll(s, "}", " } ");
  27.     replaceAll(s, "=", " = ");
  28.     replaceAll(s, "\"", " \" ");
  29.     replaceAll(s, "'", " ' ");
  30.     replaceAll(s, ";", " ; ");
  31.     replaceAll(s, ",", " , ");
  32.     replaceAll(s, "+ = ", "+=");
  33.     replaceAll(s, "- = ", "-=");
  34.     replaceAll(s, "* = ", "*=");
  35.     replaceAll(s, "/ = ", "/=");
  36.     replaceAll(s, "^ = ", "^=");
  37.     replaceAll(s, "| = ", "|=");
  38.     replaceAll(s, "& = ", "&=");
  39.     replaceAll(s, ":", " : ");
  40.     replaceAll(s, " :  : ", "::");
  41.     vector<string> tokens; string now = "";
  42.     for (int i = 0; s[i]; i++)
  43.     {
  44.         if (s[i] == ' ' || s[i] == '\t' || s[i] == '\r' || s[i] == '\n' || s[i] == '\0')
  45.         {
  46.             if (now != "")
  47.             {
  48.                 if (now == ":" && tokens.back() == ")")
  49.                 {
  50.                     string tmpnow = "";
  51.                     for (int j = i + 1; s[j]; j++)
  52.                     {
  53.                         if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0')
  54.                         {
  55.                             if (tmpnow == "{")
  56.                             {
  57.                                 now = "{";
  58.                                 i = j - 1;
  59.                                 break;
  60.                             }
  61.                             tmpnow = "";
  62.                         }
  63.                         else tmpnow += s[j];
  64.                     }
  65.                     continue;
  66.                 }
  67.                 if (now == "const")
  68.                 {
  69.                     now = "";
  70.                     continue;
  71.                 }
  72.                 if (now == "//")
  73.                 {
  74.                     for (int j = i; s[j]; j++)
  75.                     {
  76.                         if (s[j] == '\n')
  77.                         {
  78.                             i = j - 1;
  79.                             break;
  80.                         }
  81.                     }
  82.                     now = "";
  83.                     continue;
  84.                 }
  85.                 if (now == "/*")
  86.                 {
  87.                     int num = 1;
  88.                     string tmpnow = "";
  89.                     for (int j = i + 1; s[j]; j++)
  90.                     {
  91.                         if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0')
  92.                         {
  93.                             if (tmpnow == "/*") num++;
  94.                             if (tmpnow == "*/")
  95.                             {
  96.                                 num--;
  97.                                 if (num == 0)
  98.                                 {
  99.                                     i = j - 1;
  100.                                     break;
  101.                                 }
  102.                             }
  103.                             tmpnow = "";
  104.                         }
  105.                         else tmpnow += s[j];
  106.                     }
  107.                     now = "";
  108.                     continue;
  109.                 }
  110.                 //cout << now << s[i];
  111.                 tokens.push_back(now);
  112.                 now = "";
  113.             }
  114.             //else cout << s[i];
  115.         }
  116.         else now += s[i];
  117.     }
  118.     int cnt = 0;
  119.     string nowNamespace = "";
  120.     for (int i = 1; i < (int)tokens.size(); i++)
  121.     {
  122.         if ((tokens[i] == "struct" || tokens[i] == "class") && tokens[i + 2] == "{")
  123.         {
  124.             cnt = 0;
  125.             nowNamespace = tokens[i + 1];
  126.             i += 2;
  127.         }
  128.         functions tmp(nowNamespace);
  129.         if (tokens[i] == "{" && tokens[i - 1] == ")")
  130.         {
  131.             int num = 1;
  132.             for (int j = i - 2; j >= 0; j--)
  133.             {
  134.                 if (tokens[j] == ")") num++;
  135.                 if (tokens[j] == "(")
  136.                 {
  137.                     num--;
  138.                     if (num == 0)
  139.                     {
  140.                         tmp.name = tokens[j - 1];
  141.                         tmp.outputType = "";
  142.                         for (int k = j - 2; k >= 0; k--)
  143.                             if (tokens[k] != "}" && tokens[k] != "}" && tokens[k] != ";" &&
  144.                                 tokens[k].back() != ':' && tokens[k] != "inline" &&
  145.                                 tokens[k] != "static" && tokens[k][0] != '#' &&
  146.                                 tokens[k].back() != '\"' && tokens[k].back() != '>')
  147.                                 tmp.outputType = tmp.outputType == "" ? tokens[k] : tokens[k] + " " + tmp.outputType;
  148.                             else break;
  149.                         int last = i - 2;
  150.                         for (int k = i - 2; k >= j; k--)
  151.                         {
  152.                             if (tokens[k] == "(" || tokens[k] == ",")
  153.                             {
  154.                                 string tt = "";
  155.                                 for (int t = k + 1; t < last; t++)
  156.                                     tt = tt == "" ? tokens[t] : tt + " " + tokens[t];
  157.                                 if (tt != "") tmp.inputType.push_back(tt);
  158.                                 last = k - 1;
  159.                             }
  160.                             if (tokens[k] == "=" || tokens[k] == ")") last = k - 1;
  161.                         }
  162.                         reverse(tmp.inputType.begin(), tmp.inputType.end());
  163.                         break;
  164.                     }
  165.                 }
  166.             }
  167.             funs.push_back(tmp);
  168.             num = 1;
  169.             for (int j = i + 1; j < (int)tokens.size(); j++)
  170.             {
  171.                 if (tokens[j] == "{") num++;
  172.                 if (tokens[j] == "}")
  173.                 {
  174.                     num--;
  175.                     if (num == 0)
  176.                     {
  177.                         i = j;
  178.                         //cout << tmp.outputType << " " << tmp.name << " ";
  179.                         //cout << j << endl;
  180.                         break;
  181.                     }
  182.                 }
  183.             }
  184.             continue;
  185.         }
  186.         if (nowNamespace != "")
  187.         {
  188.             //cout << i << " " << nowNamespace << " " << cnt << endl;
  189.             if (tokens[i] == "{") cnt++;
  190.             if (tokens[i] == "}")
  191.             {
  192.                 cnt--;
  193.                 if (!cnt) nowNamespace = "";
  194.             }
  195.         }
  196.     }
  197. }
  198. int main()
  199. {
  200.     char ch;
  201.     while ((ch = getchar()) != EOF)
  202.         source += ch;
  203.     solve(source);
  204.     for (auto & i: funs)
  205.     {
  206.         if (i.outputType != "") cout << i.outputType << " ";
  207.         if (i.inClass != "") cout << i.inClass << "::";
  208.         cout << i.name << "(";
  209.         for (int j = 0; j < (int)i.inputType.size(); j++)
  210.             cout << i.inputType[j] << (j == (int)i.inputType.size() - 1 ? ")" : ",");
  211.         if ((int)i.inputType.size() == 0) cout << ")";
  212.         cout << endl;
  213.     }
  214.     return 0;
  215. }

D、牛牛与牛妹的约会

嘤嘤嘤，题目跟我秀恩爱可还行。一道典型的贪心题目。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int T; cin>>T;
  6.     while(T--){
  7.         int a, b; scanf("%d%d", &a, &b);
  8.         double ans = 0;
  9.         double ca = a, cb = b;
  10.         double p = 1.0/3.0;
  11.         while(1){
  12.             double na;
  13.             if(ca < 0) na = -pow(-ca,p);
  14.             else na = pow(ca, p);
  15.             if(abs(na-cb)+1.0 < abs(ca-cb)) ans += 1.0, ca = na;
  16.             else {
  17.                 ans += abs(ca-cb); break;
  18.             }
  19.         }
  20.         printf("%.9f\n", ans);
  21.     }
  22.     return 0;
  23. }

E、Enjoy the game

又是一道水题。

这个题看上去挺别扭，其实就是个判断是不是二的倍数。具体流程如下：

这里假定一共 2020牛客寒假算法基础集训营5 - 图1 张牌
1、看看 2020牛客寒假算法基础集训营5 - 图2 是不是奇数，如果是，那么先手必胜。
2、若 2020牛客寒假算法基础集训营5 - 图3 为偶数，那么此时先手应当出偶数个，不然轮到对方时，就成了对方的奇数先手。
3、同理，对方也应当出偶数。这样的话看来，若我们假定双方出的偶数都为2，那么当2020牛客寒假算法基础集训营5 - 图4为奇数时，先手必胜。
4，把2020牛客寒假算法基础集训营5 - 图5，然后在回到步骤2，直到最后可以获得一个不为1的奇数时，可以判断先手必胜，若为1，那么先手必输。

至于为什么当最后为1时就不行…….因为这个数你如果为1的话，从你计算的时候的意义上来看，是你必须在第一次时就拿走所有的牌你才能赢。但这很明显不合题意，所以不行。

  1. import java.util.*;
  2. class q{
  3.     private boolean ok(long k){
  4.         if(k==1)return false;
  5.         if(k%2==1)return true;
  6.         else return ok(k/2);
  7.     }
  8.     q(){
  9.         Scanner scanner=new Scanner(System.in);
  10.         long k=scanner.nextLong();
  11.         System.out.println(ok(k)?"Bob":"Alice");
  12.     }
  13. }
  14. public class Main { public static void main(String[] args) {new q(); }}

F、碎碎念

G、街机争霸

H、Hash

I、I题是个签到题

啊，顾名思义，这的确是个签到题。

说白了就是在读取的时候，实时维护整个数据里头前三大的数。然后在最后再判定一下是不是人数大于所有人的2020牛客寒假算法基础集训营5 - 图6。没了，就这，贼水。

  1. import java.util.*;
  3. class q {
  4.     private ArrayList<Integer> k = new ArrayList<>(3);
  5.     private int where(int qqq) {
  6.         int i=k.size();
  7.         if(i==0||k.get(0)<=qqq)return 0;
  8.         if(i==1||k.get(1)<=qqq)return 1;
  9.         if(i==2||k.get(2)<=qqq)return 2;
  10.         else return 3;
  11.     }
  12.     q() {
  13.         Scanner scanner = new Scanner(System.in);
  14.         int n = scanner.nextInt();
  15.         double m = scanner.nextInt();
  16.         int kkk = 0;
  17.         boolean ok=false;
  18.         for (int i = 0; i < n; i++) {
  19.             int o = scanner.nextInt();
  20.             if(i==8)kkk=o;
  21.             int s=where(o);
  22.             if(s<3){
  23.                 if(k.size()==3)k.remove(2);
  24.                 k.add(s,o);
  25.             }
  26.         }
  27.         double ppp=kkk/m;
  28.         if(k.indexOf(kkk)!=-1)ok=true;
  29.         if(ppp>=0.8)ok=true;
  30.         System.out.println(ok?"Yes":"No");
  31.     }
  32. }
  33. public class Main {public static void main(String[] args) {new q();}}

J、牛牛战队的秀场

这是个数学题…..上过初中的就会……

根据给的2020牛客寒假算法基础集训营5 - 图7，先选出来劣弧是哪一段，然后再得到我们要求的长度应为2020牛客寒假算法基础集训营5 - 图8。然后写式子就可以了。

  1. import java.util.*;
  2. class q{
  3.     q(){
  4.         Scanner scanner=new Scanner(System.in);
  5.         double n=scanner.nextInt();
  6.         double r=scanner.nextInt();
  7.         int i=scanner.nextInt();
  8.         int j=scanner.nextInt();
  9.         double l=2* r *Math.sin(Math.PI/n);
  10.         if(i>j){
  11.             if(j+n-i>i-j) System.out.printf("%.6f",(i-j)*l);
  12.             else  System.out.printf("%.6f",(j+n-i)*l);
  13.         }else {
  14.             if(i+n-j>j-i) System.out.printf("%.6f",(j-i)*l);
  15.             else  System.out.printf("%.6f",(i+n-j)*l);
  16.         }
  17.     }
  18. }
  19. public class Main { public static void main(String[] args) {new q(); }}