https://ac.nowcoder.com/acm/contest/3002

前言：关于我心态是如何爆炸的

写这个这个文档的时候还在比赛，不过我心态有一点崩了，先说一下这次的比赛时的状况，开场先写的B题（签到题），然后开始看A题，，感觉A题就是个数学题，一行公式就全解决了，但实际情况是，我5分钟码出代码，调试了半个小时也没解决，开始自闭，然后写D题，也是个签到题，感觉稍好了点，然后发现E题居然还是个签到题，良好的自我感觉到此为止，然后剩下的4个小时我开始全方位体会自己的菜。

一、honoka和格点三角形

这道题的意思就是，你能在一个大小为n*m的矩形格点阵中找到多少个至少有一个边在坐标轴上的面积为1的不同的三角形。思路也好想，先算出一个边在x轴上的有多少个，在算出一个边在y轴上的有多少个，两者加起来，因为重复计算，所以再减去有两条边分别在x轴和y轴上的三角形，然后再取1000000007的余数就算出来了。因为这个题的数据贼大，所以我在算的时候反复求余避免超范围。

（刚刚交流群里有个初二的ak了，艹）

（知道为啥了，题目说没给小于2的数据，但他其实给了）

  1. import java.util.Scanner;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc=new Scanner(System.in);
  6.         long mod=1000000007;
  7.         long n=sc.nextLong();long m=sc.nextLong();
  8.         if(m==1||n==1) {
  9.             System.out.println(0);
  10.         }else {
  11.             long ans=2*((n-2)*(n-2)%mod*(m-1)%mod+(m-2)*(m-2)%mod*(n-1)%mod+(n-1)*n%mod*(m-2)%mod+(m-1)*m%mod*(n-2)%mod)%mod;
  12.            System.out.println(ans%mod);
  13.         }
  14.     }
  15. }


二、kotori和bangdream

这个题贼简单，没啥说的，是人就会。

  1. #include<stdio.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     long long a,b,n,x;
  6.     scanf("%lld%lld%lld%lld",&n,&x,&a,&b);
  7.     printf("%.2lf",((double)(n*(a*x+(100-x)*b)))/100);
  8.     return 0;
  9. }

三、umi和弓道

这个题我刚一拿到手的想法是我去把得到的数据进行一个压缩，由题干的能否遮挡的说明，可以把点压缩到格点间的线段上，射影到x轴和y轴上，再用滑动窗口去扫描，感觉这个题应该就是这么个思路，然而当时写这道题的时候心态已经崩了，所以编了一半就编不动了，下面贴个伪代码，回头有时间了再去实现。

  1. //头文件
  3. //变量声明
  4. bool can=false;
  5. int x_val[];
  6. int y_val[];
  7. int x,y,length;
  8. //坐标压缩函数
  9. void zip(int x1,int y1){
  10.     //由三角形相似，确认压缩比例
  12.     //把压缩后数据导入x轴或y轴
  13.     if()x_val[]++;
  14.     else y_val[]++；
  15. }
  17. void block(int k[]){
  18.     //从上往下扫，使用不够就走前指针，够就走后指针。在切换点记录长度并
  19. }
  20. int main(){
  21.     //数据初始化
  22.     int count
  23.     {
  24.         //先获取初始的4个数据，根据目标点象限确定之后哪些点需要被压缩
  25.         int num,max;
  26.         //获取靶子数据
  27.         while(){
  28.             //获取靶子的坐标x1,y1
  29.             zip(x1,y1);
  30.             //统计有哪些箭是必然可以射到的
  31.             count++;
  32.             //统计哪些是挡了x轴才必然可以射到的
  33.             count_x++;
  34.             //统计哪些是挡了y轴才必然可以射到的
  35.             count_y++;
  36.         }
  37.     }
  39.     //看看是否必然可以达到目标值
  40.     if(count>=max)printf("-1");
  41.     if(count_x+count<max)block(x_val);
  42.     if(count_y+count<max)block(y_val);
  44.     if(can)printf("%d",length);
  45.     else printf("-1");
  46.     return 0;
  47. }

贴一个我看见的最短用时，读了一下，思路基本一致。

  1. import java.util.*;
  2. public class Main{
  3.     public static void main(String[] args){
  4.         Scanner in = new Scanner(System.in);
  5.         long x0 = in.nextLong();
  6.         long y0 = in.nextLong();
  7.         int n = in.nextInt();
  8.         int k = in.nextInt();
  9.         double [] x = new double[n];
  10.         double [] y = new double[n];
  11.         int x_k = 0;
  12.         int y_k = 0;
  13.         for(int i=0;i<n;i++){
  14.             long store_x = in.nextLong();
  15.             long store_y = in.nextLong();
  16.             if(store_x * x0 > 0 && store_y * y0 > 0){
  17.                 continue;
  18.             }
  19.             if(store_y * y0 > 0){
  20.                 y[y_k] = 1.0 * (store_x * y0 - x0 * store_y)/ (store_x-x0);
  21.                 y_k++;
  22.                 continue;
  23.             }
  24.             if(store_x * x0 > 0){
  25.                 x[x_k] = 1.0 * (store_y * x0 - y0 * store_x)/(store_y-y0);
  26.                 x_k++;
  27.                 continue;
  28.             }
  29.             y[y_k] = 1.0 * (store_x * y0 - x0 * store_y)/ (store_x-x0);
  30.             x[x_k] = 1.0 * (store_y * x0 - y0 * store_x)/(store_y-y0);
  31.             x_k++;
  32.             y_k++;
  33.         }
  34.         if(x_k < n-k && y_k < n-k){
  35.             System.out.println("-1");
  36.             return;
  37.         }
  38.         double min = 2000000000;
  39.         int no = n - k; //不能射中的数量
  40.         for(int i=x_k;i<n;i++){
  41.             x[i] = min;
  42.         }
  43.         for(int i=y_k;i<n;i++){
  44.             y[i] = min;
  45.         }
  46.         Arrays.sort(x);
  47.         Arrays.sort(y);
  48.         for(int i=0;i<x_k-(n-k)+1;i++){
  49.             double store = x[i+no-1]-x[i];
  50.             if(store < min) min = store;
  51.         }    
  52.         for(int i=0;i<y_k-(n-k)+1;i++){
  53.             double store = y[i+no-1]-y[i];
  54.             if(store < min) min = store;
  55.         }  
  56.         System.out.println(min);
  58.     }
  59. }

四、hanayo和米饭

水题，是人就会。

  1. import java.util.Scanner;
  2. class p{
  3.     p() {
  4.         Scanner scan = new Scanner(System.in);
  5.         long k=scan.nextInt();
  6.         int s=0;
  7.         long i=0;
  8.         while(s < k-1){
  9.             i+=scan.nextLong();
  10.             s++;
  11.         }
  12.         System.out.println((k*(k+1)/2)-i);
  13.     }
  14. }
  15. public class Main {
  16.     public static void main(String[] args) {
  17.         new p();
  18.     }
  19. }

五、rin和快速迭代

一道考递归的题目，上手不难。说白了就是全部跑一遍比他小的数，看有几个可以被整除，然后再把得到的结果去再次计算，直到算到只有两个因子（他自己和1）。

这个里头有几个小点，就是判断平方根那里，因为2020牛客寒假算法基础集训营1 - 图1，所以b是因子，c必然也是因子，故只需算到平方根那里即可，然后把所得结果乘2就可以了，记得平方根只能按一次计算，有必要时应去重。

  1. import java.util.Scanner;
  3. class p{
  4.     int o=0;
  5.     private void q(long k){
  6.         if(k==2)return;
  7.         o++;
  8.         long i=1;
  9.         int s=0;
  10.         long w= (long) Math.sqrt(k);
  11.         for(;i<=w;i++){
  12.             if(k%i==0)s++;
  13.         }
  14.         s*=2;
  15.         if(k==w*w)s--;
  16.         q(s);
  17.         return;
  18.     }
  19.     p() {
  20.         Scanner scan = new Scanner(System.in);
  21.         long k=scan.nextLong();
  22.         q(k);
  23.         System.out.println(o);
  24.     }
  25. }
  26. public class Main {
  27.     public static void main(String[] args) {
  28.         new p();
  29.     }
  30. }

六、maki和tree

啊，这个题的考察背景是并查集，问你到黑点有几个挑选方法说白了就是进行一个路径压缩，然后进行两两排列组合，就可以求出来了。

因为是树图，所以两者能达到的方式本身就是最短距离，所以只需看两者间有几个黑点，又或者以每一个黑点为中心，向两边延申，即一个路径上的三个黑色节点，一侧黑节点到中央黑节点之间的白色节点到对面黑节点到中央黑节点之间的白节点的路径即为所求路径。然后就是个码代码了。

下面贴一个相关资料，挺有意思，写的很好。

超有爱的并查集~
https://blog.csdn.net/niushuai666/article/details/6662911

这里贴一个C++

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
  4. #define pa pair<int,int>
  5. #define mod 998244353
  6. #define ll long long
  7. #define mk make_pair
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define cl(x) memset(x,0,sizeof x)
  13. const int INF = 0x7fffffff;
  14. const int N=1e5+5;
  15. inline int read(){
  16.     int x=0,rev=0,ch=getchar();
  17.     while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
  18.     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  19.     return rev?-x:x;
  20. }
  21. struct Edge{
  22.     int nxt,v;
  23. }e[N<<1];
  24. int n,tot,head[N];
  25. ll ans,f[N][2];
  26. char s[N];
  28. void add(int u,int v){
  29.     e[++tot].nxt=head[u],head[u]=tot,e[tot].v=v;
  30.     e[++tot].nxt=head[v],head[v]=tot,e[tot].v=u;
  31. }
  33. void dfs(int x,int fa){
  34.     for(int i=head[x];i;i=e[i].nxt){
  35.         int j=e[i].v;
  36.         if(j==fa) continue;
  37.         dfs(j,x);
  38.         if(s[x]=='B') ans+=f[x][1]*f[j][0],f[x][1]+=f[j][0];
  39.         else ans+=f[x][1]*f[j][0]+f[x][0]*f[j][1],f[x][1]+=f[j][1],f[x][0]+=f[j][0];
  40.     }
  41.     if(s[x]=='B') f[x][1]++;
  42.     else f[x][0]++;
  43.     ans+=f[x][1];
  44. }
  46. int main(){
  47.     n=read(),scanf("%s",s+1);
  48.     for(int i=1;i<n;i++) add(read(),read());
  49.     dfs(1,0);
  50.     for(int i=1;i<=n;i++) if(s[i]=='B') ans--;
  51.     cout<<ans;
  52.     return 0;
  53. }

七、eli和字符串

这个题的意思就是个扫描，用的知识点是双指针，也可以称之为滑动窗口。然后用队列结构记录点坐标就可以了。

从头向后扫描，遇到一个字母就记录在其对应队列里，如果单个字母里记录的已抵达目标数量，则刷新记录，并且poll一个Obj出去。依次循环，知道全部过完一遍为止。

（这道题就是所谓的事后AC，一开始忘记考虑K==1的情况了）

  1. import java.util.*;
  2. class p{
  3.     p() {
  4.         Scanner scan = new Scanner(System.in);
  5.         int n=scan.nextInt();
  6.         int m=scan.nextInt();
  7.         char[] q=scan.next().toCharArray();
  8.         int min=-1;
  9.         if(m==1)System.out.println(1);
  10.         else{
  11.             Queue[] a=new Queue[26];
  12.             for(int i=0;i<n;i++){
  13.                 int k=q[i]-'a';
  14.                 if(a[k]==null){
  15.                     a[k]=new LinkedList<Integer>();
  16.                 }else {
  17.                     if(a[k].size()==m-1){
  18.                         if(min==-1)min=i-(Integer) a[k].poll()+1;
  19.                         else min=Math.min(min,i-(Integer) a[k].poll()+1);
  20.                     }
  21.                 }
  22.                 a[k].add(i);
  23.             }
  24.             System.out.println(min);
  25.         }
  27.     }
  28. }
  29. public class Main {
  30.     public static void main(String[] args) {
  31.         new p();
  32.     }
  33. }

八、nozomi和字符串

这道题我感觉也可以是双指针（滑动窗口）做法，即，方法和上一道题基本一样，就是约束条件变一下，先对变成0的情况进行扫描，在对变成1的情况进行扫描，最后输出其中的大者。

  1. import java.util.*;
  2. class p{
  3.     private char[] q;
  4.     private int m;
  5.     private int n;
  6.     private int qqq(char a){
  7.         int start=0,end=0,length=0;
  8.         int k=0;
  9.         for(;end<n-1;end++){
  10.             if(q[end]!=a){
  11.                 if(k==m){
  12.                     length=Math.max(length,end-start);
  13.                     do{
  14.                         start++;
  15.                     }while(q[start]!=a&&start<end);
  16.                 }else {
  17.                     k++;
  18.                 }
  19.             }
  20.         }
  21.         if(start==0){
  22.             if(k<m)return n;
  23.             else {
  24.                 if(q[n-1]==a)return n;
  25.             }
  26.         }
  27.         if(q[end]!=a)end=end-1;
  28.         length=Math.max(length,end-start+1);
  29.         return length;
  30.     }
  31.     p() {
  32.         Scanner scan = new Scanner(System.in);
  33.         n=scan.nextInt();
  34.         m=scan.nextInt();
  35.         q=scan.next().toCharArray();
  36.         System.out.println(Math.max(qqq('1'),qqq('0')));
  37.     }
  38. }
  39. public class Main {
  40.     public static void main(String[] args) {
  41.         new p();
  42.     }
  43. }

九、nico和niconiconi

一道典型的贪心题，从前向后扫描，时刻选取使当前状态利益最大化的字符。根据题目给出的a，b，c可确定不同的贪心策略。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #define mem(a,b) memset(a,b,sizeof(a))
  5. #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
  6. using namespace std;
  7. typedef long long LL;
  8. int read()
  9. {
  10.     int x=0,flag=1;
  11.     char c=getchar();
  12.     while((c>'9' || c<'0') && c!='-') c=getchar();
  13.     if(c=='-') flag=0,c=getchar();
  14.     while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
  15.     return flag?x:-x;
  16. }
  18. const int maxn=3e5+5;
  19. char s[maxn];
  20. LL a,b,c,f[maxn];
  21. int n;
  23. int main()
  24. {
  25.     cin>>n>>a>>b>>c;
  26.     scanf("%s",s+1);
  27.     REP(i,1,n)
  28.     {
  29.         f[i]=f[i-1];
  30.         if(i>=4 && s[i]=='o' && s[i-1]=='c' && s[i-2]=='i' && s[i-3]=='n')
  31.             f[i]=max(f[i],f[i-4]+a);
  32.         if(i>=6 && s[i]=='i' && s[i-1]=='n' && s[i-2]=='o' && s[i-3]=='c' && s[i-4]=='i' && s[i-5]=='n')
  33.             f[i]=max(f[i],f[i-6]+b);
  34.         if(i>=10 && s[i]=='i' && s[i-1]=='n' && s[i-2]=='o' && s[i-3]=='c' && s[i-4]=='i' && s[i-5]=='n' && s[i-6]=='o' && s[i-7]=='c' && s[i-8]=='i' && s[i-9]=='n')
  35.             f[i]=max(f[i],f[i-10]+c);
  36.     }
  37.     cout<<f[n];
  39.     return 0;
  40. }

十、u’s的影响力

一道考察矩阵快速幂的题目，没啥可说的，都是套路。

非常类似于我之前遇到的G题，之前在那上面已经写了对这种题的感觉了。

G - Recursive sequence

这里贴出相关论文

根据递推公式构造系数矩阵用于快速幂
https://blog.csdn.net/u012061345/article/details/52224623

矩阵快速幂和递推式构造常矩阵总结（感觉这个里头总结的最全）
https://blog.csdn.net/weixin_43872728/article/details/98113251

浅谈斐波那契数列——从递推到矩阵乘法
https://blog.csdn.net/ganjingxian/article/details/77160271

（其实就是个模板题，背背模板就可了）

这里贴出相关代码

  1. import java.math.MathContext;
  2. import java.util.Scanner;
  3. import java.math.BigInteger;
  4. class Matrix {
  5.     long[][] a=new long[3][3];
  6.     public static int mod=1000000007-1;
  7.     void clear(){
  8.         for(int i=0;i<3;i++){
  9.             for(int j=0;j<3;j++){
  10.                 a[i][j]=0;
  11.             }
  12.         }
  13.     }
  14.     Matrix multiply(Matrix B){
  15.         Matrix C=new Matrix();
  16.         C.clear();
  17.         for(int i=0;i<3;i++){
  18.             for(int j=0;j<3;j++){
  19.                 for(int k=0;k<3;k++){
  20.                     C.a[i][j]+=a[i][k]*B.a[k][j]%mod;
  21.                     C.a[i][j]%=mod;
  22.                 }
  23.             }
  24.         }
  25.         return C;
  26.     }
  27. }
  28. public class Main {
  29.     public static long calc(long N,long x1,long x2,int tp){
  30.         if(N==1) return x1;
  31.         if(N==2) return x2;
  32.         N-=2;
  33.         Matrix A=new Matrix();
  34.         A.clear();
  35.         A.a[0][0]=x2;
  36.         A.a[0][1]=x1;
  37.         if(tp==1) A.a[0][2]=1;
  38.         Matrix B=new Matrix();
  39.         B.clear();
  40.         B.a[0][0]=1;B.a[0][1]=1;
  41.         B.a[1][0]=1;
  42.         if(tp==1) {
  43.             B.a[2][0]=1;B.a[2][2]=1;
  44.         }
  45.         Matrix res=new Matrix();
  46.         res.clear();
  47.         res.a[0][0]=res.a[1][1]=1;
  48.         if(tp==1) res.a[2][2]=1;
  49.         while(N!=0){
  50.             if(N%2==1) res=res.multiply(B);
  51.             B=B.multiply(B);
  52.             N>>=1;
  53.         }
  54.         A=A.multiply(res);
  55.         return A.a[0][0];
  56.     }
  57.     public static void main(String[] args){
  58.         Scanner cin=new Scanner(System.in);
  59.         BigInteger n=cin.nextBigInteger();
  60.         BigInteger x=cin.nextBigInteger();
  61.         BigInteger y=cin.nextBigInteger();
  62.         BigInteger a=cin.nextBigInteger();
  63.         BigInteger b=cin.nextBigInteger();
  64.         BigInteger mod=BigInteger.valueOf(1000000007);
  65.         BigInteger p=a.modPow(b,mod);
  66.         if(n.equals(BigInteger.valueOf(1))==true) System.out.println(x.mod(mod));
  67.         else if(n.equals(BigInteger.valueOf(2))==true) System.out.println(y.mod(mod));
  68.         else if(n.equals(BigInteger.valueOf(3))==true) System.out.println(x.multiply(y).multiply(p).mod(mod));
  69.         else if(n.equals(BigInteger.valueOf(4))==true) System.out.println(x.multiply(y).multiply(y).multiply(p).multiply(p).mod(mod));
  70.         else {
  71.             n=n.subtract(BigInteger.valueOf(4));
  72.             String s=n.toString();
  73.             long N=0;
  74.             for(int i=0;i<s.length();i++){
  75.                 N=N*10+(long)s.charAt(i)-'0';
  76.             }
  77.             BigInteger x1=BigInteger.valueOf(calc(N,2,3,0));
  78.             BigInteger x2=BigInteger.valueOf(calc(N,3,5,0));
  79.             BigInteger x3=BigInteger.valueOf(calc(N,4,7,1));
  80.             System.out.println(x.modPow(x1,mod).multiply(y.modPow(x2,mod)).multiply(p.modPow(x3,mod)).mod(mod));
  81.         }
  82.     }
  83. }