前言：谁和我说这次题会简单一些的？？？

我就信了出题人的鬼话，谁跟我说这次题目会稍微简单一些的？真是实力劝退，这次5000多人没一个ak的，我真是服了。

A、欧几里得

这个题的定位应该是签到题，贼简单，就是个斐波那契数列的递推，没啥说的。

  1. import java.util.Arrays;
  2. import java.util.*;
  3. class q {
  4.     private long[] l=new long[83];
  5.     private long a(int n){
  6.         if(l[n]==0){
  7.             l[n]=a(n-1)+a(n-2);
  8.         }
  9.         return l[n];
  10.     }
  11.     q() {
  12.         Arrays.fill(l,0);
  13.         l[0]=1;
  14.         l[1]=1;
  15.         l[2]=2;
  16.         l[3]=3;
  17.         l[4]=5;
  18.         Scanner scanner=new Scanner(System.in);
  19.         int T=scanner.nextInt();
  20.         while(T--!=0){
  21.             int s=scanner.nextInt();
  22.             if(s==0){
  23.                 System.out.println(1);
  24.                 continue;
  25.             }
  26.             if(s==1){
  27.                 System.out.println(3);
  28.                 continue;
  29.             }
  30.             System.out.println(a(s+2));
  31.         }
  32.     }
  33. }
  34. public class Main{public static void main(String[] args) {new q();}}

B、括号序列

这个题我在刷leetcode的时候遇到过原题……..和题干一模一样。

考的就是个栈，相同就出栈，不同就入栈，最后看有没有剩下的。

  1. import java.util.*;
  2. class q {
  3.     private boolean isValid(String s) {
  4.         if (s.length() == 0)return true;
  5.         if (s.length() % 2 == 1)return false;
  6.         Stack<Character> q = new Stack<>();
  7.         for (char e : s.toCharArray()) {
  8.             if (q.size() == 0){
  9.                 if (e == ']' || e == '}' || e == ')')return false;
  10.                 q.push(e);
  11.             } else {
  12.                 char www = q.lastElement();
  13.                 if (www == '{' && (e == ']' || e == ')'))return false;
  14.                 if (www == '(' && (e == '}' || e == ']'))return false;
  15.                 if (www == '[' && (e == '}' || e == ')'))return false;
  16.                 if (www == '{' && e == '}')q.pop();
  17.                 else if (www == '[' && e == ']')q.pop();
  18.                 else if (www == '(' && e == ')')q.pop();
  19.                 else q.push(e);
  20.             }
  21.         }
  22.         return q.size() == 0;
  23.     }
  24.     q() {
  25.         String k = new Scanner(System.in).next();
  26.         if(k.equals("i"))System.out.print("Yes");
  27.         else {
  28.             if (isValid(k)) System.out.print("Yes");
  29.             else System.out.print("No");
  30.         }
  31.     }
  32. }
  33. public class Main {public static void main(String[] args) {new q();}}

C、子段乘积

这道题一上场信心满满，感觉就是个先乘再除，后来发现这个得考虑到 2020牛客寒假算法基础集训营4 - 图1 之后不能直接除的问题，就没了思路，刚刚查找了相关的数论知识，了解到这个题涉及到了卢卡斯定理这个知识，这个题就是：知道这个卢卡斯定理的就做得出来，不知道的就做不出来。本质是个求乘法逆元的过程。然后就是走模板了。感觉这个题和之前遇到的什么分数求模有相同的背景。啊，明白了。

卢卡斯定理

  1. import java.util.Scanner;
  2. class q{
  3.     private long qpow(long a, long b, long p)
  4.     {
  5.         long ans=1;
  6.         while(b!=0){
  7.             if(b%2!=0)ans=ans*a%p;
  8.             a=a*a%p;
  9.             b>>=1;
  10.         }
  11.         return ans;
  12.     }
  13.     private long inv(long a, long p){return qpow(a,p-2,p);}
  14.     q(){
  15.         Scanner cin=new Scanner(System.in);
  16.         int n=cin.nextInt();
  17.         int k=cin.nextInt();
  18.         long[] a=new long[n];
  19.         long ans=0,S=1;
  20.         long mod=998244353;
  21.         long num=0;
  22.         for(int i=0;i<n;i++){
  23.             a[i]=cin.nextLong();
  24.             if(a[i]==0){
  25.                 S=1;
  26.                 num=0;
  27.             }
  28.             else
  29.             {
  30.                 S=S*a[i]%mod;
  31.                 num+=1;
  32.                 if(num>k){
  33.                     S=S*inv(a[i-k],mod)%mod;
  34.                     num-=1;
  35.                 }
  36.                 if(num==k)ans=Long.max(ans,S%mod);
  37.             }
  38.         }
  39.         System.out.println(ans);
  40.     }
  41. }
  42. public class Main { public static void main(String[] args) {new q();}}

回头得整理到数论的专题里。

D、子段异或

因为昨天刚刚细细品味了数位DP，导致这个题我的第一反应就是数位DP。数位DP倒不是不能做，就是在自找麻烦，数位dp本身就是把所有的情况推一遍，导致了这道题复杂度 2020牛客寒假算法基础集训营4 - 图2 。然后刚刚在看别人的解答的时候，发现了一个比较有趣的思路，感觉很棒，利用了累乘的特性，这里贴出来。

  1. import java.util.*;
  2. class q{
  3.     q(){
  4.         Scanner sc=new Scanner(System.in);
  5.         long a[]=new long[200005];
  6.         Map<Long,Long> map=new HashMap<Long,Long>();
  7.         a[0]=0;
  8.         int n=sc.nextInt();
  9.         for(int i=1;i<=n;i++) {
  10.             int x=sc.nextInt();
  11.             a[i]=a[i-1]^x;
  12.         }
  13.         long ans=0;
  14.         map.put(0L,1L);
  15.         for(int i=1;i<=n;i++) {
  16.             if(map.containsKey(a[i])) {
  17.                 ans+=map.get(a[i]);
  18.                 map.put(a[i],map.get(a[i])+1);
  19.             }
  20.             else map.put(a[i],1L);
  21.         }
  22.         System.out.println(ans);
  23.     }
  24. }
  25. public class Main { public static void main(String[] args) {new q();}}

E、最小表达式

这个题…..有点玄妙，这么说，他居然特意去用数据卡了Java的大数。

这个题的本意不难，就是个流程题，具体步骤为：

2020牛客寒假算法基础集训营4 - 图3

没了，剩下的就是码代码了。

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. #include <math.h>
  5. using namespace std;
  6. char ch[1000000],ans[1000000];
  7. int num[11];
  8. int main(){
  9.     scanf("%s",ch);
  10.     int n=strlen(ch);
  11.     int cnt=1;
  12.     for(int i=0;i<n;i++){
  13.         if(ch[i]=='+')cnt++;
  14.         else num[ch[i]-'0']++;
  15.     }
  16.     int k=0,temp=0,cnt1=0;
  17.     for(int i=9;i>=1;i--){
  18.         for(int j=1;j<=num[i];j++){
  19.             temp+=i;
  20.             k++;
  21.             if(k%cnt==0){
  22.                ans[cnt1++]=temp%10+'0';
  23.                temp/=10;
  24.             }
  25.         }
  26.     }
  27.     while(temp){
  28.         ans[cnt1++]=temp%10+'0';
  29.         temp/=10;
  30.     }
  31.     for(int i=cnt1-1;i>=0;i--)printf("%c",ans[i]);
  32.     printf("\n");
  33.     return 0;
  34. }

F、树上博弈

啊，当时没看这个题，现在说说对这个的想法，由题意，因为每一步都必须要走，所以应该想办法让两者之间的距离（最短路径长度）为奇数，这样，总会有一步起，两者间的距离会变成1，然后只要牛牛走一步，牛妹就必须后退一步（突然羡慕牛牛有可爱的妹子），直到牛妹被逼到死胡同。然后的就是算出来有多少种取样方式，可以使两者之间的距离为奇数。预计时间复杂度2020牛客寒假算法基础集训营4 - 图4。问题是怎么去举可以令计算次数尽量的小。感觉可以用记录的方法，即：记录这个节点到树顶点的距离，然后进行个分治，即通过距离来算。
刚刚看了看别人的代码，大部分都是先数据初始化，把父子节点的关系先整明白，然后在去深搜来确定位置关系，然后用 2020牛客寒假算法基础集训营4 - 图5 直接把结果算出来。等等，看到了个直接用结构体，然后直接记录深度的，啊，这个才是正常的想法。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <string>
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long long LL;
  10. template <class T> inline T rd(){T x = 0;ll f = 1; char c = getchar();while(c > '9' || c < '0') f = c == '-' ? -1 : 1, c = getchar();while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();return x * f;}
  11. #define rdi rd<int>
  12. #define N 1000005
  13. struct node{
  14.     int fa;
  15.     int dep;
  16. }a[N];
  17. int main() {
  18.     int n = rdi();
  19.     for (int i = 2 ; i <= n ; i++ ) {
  20.         a[i].fa = rdi();
  21.         a[i].dep = a[a[i].fa].dep + 1;
  22.     }
  24.     LL cnt1 = 0, cnt2 = 0;
  25.     for (int i = 1 ; i <= n ; i++ ) {
  26.         if (a[i].dep % 2 == 0) cnt2++;
  27.         else cnt1++;
  28.     }
  29.     LL ans = cnt1 * (cnt1 - 1) / 2 + cnt2 * (cnt2 - 1) / 2;
  30.     cout << ans * 2 << '\n';
  31. }

G、音乐鉴赏

坦白的说，这个题我一开始没读懂题意。然后我刚刚看了看别人的代码是个什么意思。

如果随机占比为 2020牛客寒假算法基础集训营4 - 图6 ，一个人分数为 2020牛客寒假算法基础集训营4 - 图7，那么他优秀的概率为 2020牛客寒假算法基础集训营4 - 图8。

这个概率可以这么计算：首先把分数减90，大于0就优秀，那么就变成2020牛客寒假算法基础集训营4 - 图9，其中y是一个随机的0到90之间的数字。2020牛客寒假算法基础集训营4 - 图10，这个概率就是上面所写的概率。

  1. ![](https://cdn.nlark.com/yuque/__latex/93b1ca751196ceac8794118c9deeb46d.svg#card=math&code=E%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%28score_i-90%29%281-x%29%7D%7B90x%7D%3D0.1n&height=49&width=269)，解方程可知答案为![](https://cdn.nlark.com/yuque/__latex/6efbd407270ca3ba4ebc2e13881c5837.svg#card=math&code=%5Cfrac%7B%5Csum_%7Bi%3D1%7D%5En%28score_i-90%29%7D%7B9n%2B%5Csum_%7Bi%3D1%7D%5En%28score_i-90%29%7D&height=49&width=178)。
  1. import java.util.*;
  2. public class Main{
  3.     static long MOD = 998244353;
  4.     public static void main(String[] args){
  5.         Scanner in = new Scanner(System.in);
  6.         int n = in.nextInt();
  7.         int num = 0;
  8.         for(int i=0;i<n;i++) num += in.nextInt();
  9.         double average = num*1.0 / n;
  10.         double p = (average - 90)*100 / (average -81);
  11.         System.out.printf("%.2f", p);
  12.         System.out.println("%");
  13.     }
  14. }

H、坐火车

这个题我感觉应该是采用记忆的方式，即每扫描一个车厢，就在以经过该种车厢的颜色的计数板上+1，之后每次在后边可以直接用2020牛客寒假算法基础集训营4 - 图11来计算某种颜色对这节车厢的贡献。然后如果直接写代码的话会TLE，所以得进行个维护。

这个是TLE版。

  1. import java.util.Scanner;
  2. class color{
  3.     int left=0;
  4.     int right=1;
  5. }
  6. class q{
  7.     q(){
  8.         Scanner scanner=new Scanner(System.in);
  9.         int n=scanner.nextInt();
  10.         color[] colors=new color[500001];
  11.         int[][] train=new int[n][3];
  12.         for(int i=0;i<n;i++){
  13.             train[i][0]=scanner.nextInt();
  14.             train[i][1]=scanner.nextInt();
  15.             train[i][2]=scanner.nextInt();
  16.             if(colors[train[i][0]]==null)colors[train[i][0]]=new color();
  17.             else colors[train[i][0]].right++;
  18.         }
  19.         long sum=0;
  20.         System.out.print(0);
  21.         System.out.print(" ");
  22.         colors[train[0][0]].right--;
  23.         colors[train[0][0]].left++;
  24.         for(int i=1;i<n-1;i++){
  25.             colors[train[i][0]].right--;
  26.             for(int j=train[i][1];j<=train[i][2];j++){
  27.                 if(colors[j]!=null)sum+=(colors[j].left*colors[j].right);
  28.             }
  29.             System.out.print(sum);
  30.             System.out.print(" ");
  31.             sum=0;
  32.             colors[train[i][0]].left++;
  33.         }
  34.         System.out.print(0);
  35.         System.out.print(" ");
  36.     }
  37. }
  38. public class Main { public static void main(String[] args) {new q(); }}

正常版

  1. import java.util.Scanner;
  2. class color{int left=0;int right=1;}
  3. class q{
  4.     private int N = 500050;
  5.     private long[] sz=new long[N];
  6.     private void add(int p, int x){
  7.         while(p<N){
  8.             sz[p]+=x;
  9.             p+=p&-p;
  10.         }
  11.     }
  13.     private long query(int p){
  14.         long ret = 0;
  15.         while(p!=0){
  16.             ret+=sz[p];
  17.             p-=p&-p;
  18.         }
  19.         return ret;
  20.     }
  21.     q(){
  22.         Scanner scanner=new Scanner(System.in);
  23.         int n=scanner.nextInt();
  24.         color[] colors=new color[500001];
  25.         int[][] train=new int[n][3];
  26.         for(int i=0;i<n;i++){
  27.             train[i][0]=scanner.nextInt();
  28.             train[i][1]=scanner.nextInt();
  29.             train[i][2]=scanner.nextInt();
  30.             if(colors[train[i][0]]==null)colors[train[i][0]]=new color();
  31.             else colors[train[i][0]].right++;
  32.         }
  33.         for(int i=0;i<n;i++){
  34.             colors[train[i][0]].right-=1;
  35.             add(train[i][0],-colors[train[i][0]].left);
  36.             System.out.print(query(train[i][2])-query(train[i][1]-1));
  37.             System.out.print(" ");
  38.             colors[train[i][0]].left+=1;
  39.             add(train[i][0],colors[train[i][0]].right);
  40.         }
  41.     }
  42. }
  43. public class Main { public static void main(String[] args) {new q(); }}

I、匹配星星

这个题有点迷，看解析，意思是采用贪心，

  • 如果 2020牛客寒假算法基础集训营4 - 图12，查询比他X坐标小的Y坐标最大的 2020牛客寒假算法基础集训营4 - 图13 的点，进行配对，如果配对成功则将那个点都从候选点中排除。
  • 如果 2020牛客寒假算法基础集训营4 - 图14，将该点加入候选点。

证明

假设最优方案中排序后2020牛客寒假算法基础集训营4 - 图15的第 1 个没有按贪心策略匹配的点 2020牛客寒假算法基础集训营4 - 图16 ，在设 2020牛客寒假算法基础集训营4 - 图17 在2020牛客寒假算法基础集训营4 - 图18中它能匹配的 2020牛客寒假算法基础集训营4 - 图19 最大的点为 2020牛客寒假算法基础集训营4 - 图20，如果 2020牛客寒假算法基础集训营4 - 图21 被点 2020牛客寒假算法基础集训营4 - 图22 匹配了，有两种情况：

  • 原先 2020牛客寒假算法基础集训营4 - 图23 没有和任何匹配，则直接去掉 2020牛客寒假算法基础集训营4 - 图24 的匹配，将 2020牛客寒假算法基础集训营4 - 图25 和 2020牛客寒假算法基础集训营4 - 图26 匹配。
  • 原先 2020牛客寒假算法基础集训营4 - 图27 和 2020牛客寒假算法基础集训营4 - 图28 匹配，则将 2020牛客寒假算法基础集训营4 - 图29 改成和 2020牛客寒假算法基础集训营4 - 图30 匹配，将 2020牛客寒假算法基础集训营4 - 图31 和 2020牛客寒假算法基础集训营4 - 图32 匹配，由于2020牛客寒假算法基础集训营4 - 图33， 这样的匹配一定是成立的。并且修改后的匹配数不会变少，因此按照该贪心策略可以得到最优解。
  1. #include <set>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  9. struct P{
  10.     int a,b,c;
  11.     bool operator < (const P &rhs) const{
  12.         if(a == rhs.a)return c>rhs.c;
  13.         return a<rhs.a;
  14.     }
  15. }alp[300030];
  16. int n;
  17. int main() {
  18.     cin>>n;
  19.     for(int i=0;i<n;i++) cin>>alp[i].a>>alp[i].b>>alp[i].c;
  20.     sort(alp,alp+n);
  21.     multiset<int> pool;
  22.     multiset<int>::iterator it;
  23.     int ans = 0;
  24.     for(int i=0;i<n;i++){
  25.         if(alp[i].c){
  26.             it = pool.lower_bound(alp[i].b);
  27.             if(it!=pool.begin()){
  28.                 --it;
  29.                 pool.erase(it);
  30.                 ans+=1;
  31.             }
  32.         }else{
  33.             pool.insert(alp[i].b);
  34.         }
  35.     }
  36.     cout<<ans<<endl;
  38.     return 0;
  39. }

J、二维跑步