头像

暂时换个名字




在线 


活动打卡代码 AcWing 1233. 全球变暖

裂开来,可能是今天状态不太好吧,这么简单的一道题居然写了3,4个小时。思路十分清晰,但是写成代码就是出现一个又一个的bug。
本题的实质是遍历出所有的连通块,并计算符合条件的连通块数量
方法一:有返回值的dfs
原理:false&任何值=false;我们要找完全被淹没的大陆,因此这个岛屿完全被淹没时为true(有一块陆地不会被淹没就返回false,因此无论其他大陆是否被淹没,整个联通块都将返回false)(只有当所有的陆地都会被淹没时,即都返回true时,整个连通块才会返回true)
易错点一:不能直接return dfs,这样不会将整个连通块访问完,而是只遍历当前方块一个方向的dfs到的方块,故应该用一个boolean变量接收dfs返回值,当遍历完当前方块4个方向的dfs时,再返回上述dfs的最终值
易错点二:注意判断是否为单方块连通块。因此先判断当前方块是否为海,若是海直接跳过不进入dfs.当是岛时,开始遍历连通块,若是单方块连通块,将不会进入循环,单方块联通块肯定会被淹没,因此直接返回true,故ans赋初值为true
易错点三:ans=ans&dfs&check,而不是ans=dfs&check
易错点四:要用&而不是&&

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int n,res;
    static char[][] arr;
    static boolean[][] flag;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());arr=new char[n][n];flag=new boolean[n][n];
        for(int i=0;i<n;i++)arr[i]=br.readLine().toCharArray();
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++){
                if(!flag[i][j]){
                    if(dfs(i,j))res++;
                }
            }
        }
        System.out.println(res);
    }
    static int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
    static boolean dfs(int x,int y) {
        flag[x][y]=true;
        int xx,yy;
        boolean ans=true;
        for(int d=0;d<4;d++) {
            xx=x+dx[d];yy=y+dy[d];
            if(xx>=0&&xx<n&&yy>=0&&yy<n&&flag[xx][yy]==false&&arr[xx][yy]=='#') {
                ans=ans&check(x,y)&dfs(xx,yy);
            }
        }
        return ans;
    }
    static boolean check(int x,int y) {
        for(int d=0;d<4;d++) {
            if(arr[x+dx[d]][y+dy[d]]=='.')return true;
        }
        return false;
    }

}

方法二 增加一个全局变量用来计数,不用有返回值的dfs函数

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int n,res,total;//total记录当前遍历的联通块是否含不能被淹没的岛屿
    static char[][] arr;
    static boolean[][] flag;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());arr=new char[n][n];flag=new boolean[n][n];
        for(int i=0;i<n;i++)arr[i]=br.readLine().toCharArray();
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++){
                if(arr[i][j]=='#'&&!flag[i][j]){
                    dfs(i,j);
                    if(total==0)res++;
                    else total=0;
                }
            }
        }
        System.out.println(res);
    }
    static int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
    static void dfs(int x,int y) {
        flag[x][y]=true;
        if(!check(x,y))total++;//如果当前岛屿不能被淹没,total++
        int xx,yy;
        for(int d=0;d<4;d++) {
            xx=x+dx[d];yy=y+dy[d];
            if(xx>=0&&xx<n&&yy>=0&&yy<n&&flag[xx][yy]==false&&arr[xx][yy]=='#') {
                dfs(xx,yy);
            }
        }
    }
    static boolean check(int x,int y) {
        for(int d=0;d<4;d++) {
            if(arr[x+dx[d]][y+dy[d]]=='.')return true;
        }
        return false;
    }

}


活动打卡代码 AcWing 3250. 通信网络

对于有向图,把边的方向反过来建一次图,然后遍历每一个结点可到达结点数量与能到达该结点的结点数量

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int[] h1=new int[10010],h2=new int[10010],e=new int[2*10010],ne=new int[2*10010];
    static int idx=-1;
    static int n,m;
    static boolean[] flag1,flag2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h1, -1);Arrays.fill(h2, -1);
        n=sc.nextInt();m=sc.nextInt();flag1=new boolean[n+1];flag2=new boolean[n+1];
        for(int i=0;i<m;i++) {
            int a=sc.nextInt(),b=sc.nextInt();
            insert(h1,a,b);insert(h2,b,a);
        }
        yxc();
    }
    static void yxc() {
        int res=0;
        for(int i=1;i<=n;i++) {
            Arrays.fill(flag1, false);Arrays.fill(flag2, false);
            dfs(i,h1,flag1);dfs(i,h2,flag2);
            int temp=0;
            for(int j=1;j<=n;j++)
                if(flag1[j]||flag2[j])temp++;
            if(temp==n)res++;
        }
        System.out.println(res);
    }
    static void dfs(int u,int[] h,boolean[] flag) {
        flag[u]=true;
        for(int i=h[u];i!=-1;i=ne[i]) {
            int next=e[i];
            if(!flag[next])dfs(next,h,flag);
        }
    }
    static void insert(int[] h,int a,int b) {
        idx++;
        ne[idx]=h[a];
        h[a]=idx;
        e[idx]=b;
    }
}


活动打卡代码 AcWing 3240. 压缩编码

自己最开始的方法
根据样例猜测,可能可以先根据频率先创建哈夫曼树,然后将所有的叶子结点从左至右修改频率为按字典序排序的对应的字母的频率,最后计算所有的叶子结点的编码长度*频率
但是这样做是错的。 因为哈夫曼树不唯一,当每一个结点都存储好了他对应的频率和对应的字符与编码,那么同一个结点的左右子树是可以交换的。但是字典序哈夫曼树是不允许同一个结点的左右子树进行交换的,因为一个结点的子树在左边还是在右边决定了这个子树的叶子结点对应什么频率和字符和编码。
拓展 给每个结点增加一个最大子树深度字段,并且令该字段更大的结点做左孩子,得到的将是从右往左越来越深的哈夫曼树。

package 每日一题活动.提高组;

import java.util.PriorityQueue;
import java.util.Scanner;

public class 压缩编码 {
    static PriorityQueue<Node> queue = new PriorityQueue<>();
    static Node root;
    static Node[] nodes;
    static int[] arr;
    static long res;
    static int index;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();arr = new int[n];char[] words = new char[n];
        for(int i=0;i<n;i++) {arr[i]=sc.nextInt();words[i]=(char)(i+'a');}
        createTree(arr,words);
        dfsFill(root,"");
        System.out.println(res);
        //for(int i=0;i<nodes.length;i++)System.out.println(nodes[i].code);
    }
    static void createTree(int[] power,char[] words) {
        nodes=new Node[power.length];
        for(int i=0;i<power.length;i++) {
            nodes[i]=new Node(power[i],1);
            queue.add(nodes[i]);
        }
        while(queue.size()>1) {
            Node l=queue.poll(),r=queue.poll(),temp;
            if(r.revh>l.revh) {temp=l;l=r;r=temp;}//因为哈夫曼树不唯一,结点的左孩子和右孩子可以交换,我们令深度更长的树做左孩子
            int revh=Math.max(l.revh,r.revh);
            Node parent =new Node(l.power+r.power,l,r,revh+1);
            queue.add(parent);
        }
        root=queue.peek();
    }
    static void dfsFill(Node node,String code) {
        node.code=code;
        if(node.l==null&&node.r==null) {
            System.out.println(node.word+node.code+" "+node.power);
            //res+=code.length()*arr[index++];
            res+=code.length()*node.power;
        }
        else {
            if(node.l!=null)dfsFill(node.l,code+"0");
            if(node.r!=null)dfsFill(node.r,code+"1");
        }
    }
    static class Node implements Comparable<Node>{
        int power,revh;
        char word;
        String code;
        Node l,r;
        public Node(int power,int revh){
            this.power=power;this.revh=revh;
        }
        public Node(int power,Node l,Node r,int revh) {
            this.power=power;this.l=l;this.r=r;this.revh=revh;
        }
        public int compareTo(Node o) {
            return this.power-o.power;
        }
    }
}

根据研究,字典序哈夫曼树是唯一的,且决定不同的字典序编码树路径之和的是每个叶子结点的深度,即每个叶子结点的频率是确定的,但是每个叶子结点的深度不同将导致最终的路径之和不同,我们既要保证所有叶子结点的深度组成的序列能保证组建出一个二叉树,又要保证能路径之和最小,这就是字典序哈夫曼树

二叉树非叶子结点权值之和即为叶子结点的路径之和

import java.util.Scanner;

public class Main{
    static int[][] biao;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();int[] arr = new int[n+1];biao=new int[n+1][n+1];
        for(int i=1;i<=n;i++)arr[i]=sc.nextInt()+arr[i-1];
        dp(arr);
    }
    static void dp(int[] arr) {
        for(int length=2;length<arr.length;length++) {
            for(int begin=1;begin<=arr.length-length;begin++) {
                int l=begin,r=begin+length-1,temp=Integer.MAX_VALUE;
                for(int k=l;k<r;k++) {
                    temp=Math.min(temp, biao[l][k]+biao[k+1][r]);
                }
                biao[l][r]=temp+arr[r]-arr[l-1];
            }
        }
        System.out.println(biao[1][arr.length-1]);
    }
}


活动打卡代码 AcWing 3215. 网络延时

这道题正好和刚放寒假开始学算法时做的一道题”大臣的旅费”几乎一样,比那道题简单一些
用自己那个时候写的方法来写这道题

import java.util.ArrayList;
import java.util.Scanner;

public class Main{
    static int n,m,p,step;
    static Node[] nodes;
    static boolean[] flag;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();m=n+sc.nextInt();nodes=new Node[n+m+1];flag=new boolean[n+m+1];
        for(int i=1;i<=m;i++)nodes[i]=new Node(i);
        for(int i=2;i<=n;i++) {
            int father=sc.nextInt();
            nodes[father].list.add(i);
            nodes[i].list.add(father);
        }
        for(int i=n+1;i<=m;i++) {
            int father = sc.nextInt();
            nodes[father].list.add(i);
            nodes[i].list.add(father);
        }
        dfs(1,0);
        flag = new boolean[n+m+1];step=0;
        dfs(p,0);
        System.out.println(step);
    }
    static void dfs(int begin,int nowStep) {
        flag[begin]=true;
        if(nowStep>step) {step=nowStep;p=begin;}
        for(int son:nodes[begin].list) {
            if(flag[son]==false)dfs(son,nowStep+1);
        }
    }
    static class Node{
        int xu;
        ArrayList<Integer> list = new ArrayList<>();
        Node(int xu){
            this.xu=xu;
        }
    }
}

经过一个寒假的学习,下面是新的写法
1.优化了实现树的数据结构
2.用了yxc的方法一遍dfs

    static class Main{
        static int n,m,ans;
        static int[] h=new int[10010],e=new int[2*10010],ne=new int[2*10010];
        static int idx=-1;
        static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n=sc.nextInt();m=sc.nextInt()+n;
            Arrays.fill(h, -1);
            for(int i=2;i<=m;i++) {
                int father=sc.nextInt();
                insert(father,i);insert(i,father);
            }
        }
        static void insert(int a,int b) {
            idx++;//生成新结点的哈希值
            ne[idx]=h[a];//头插法,
            h[a]=idx;//更新头结点
            e[idx]=b;//记录弧头
        }
        int dfs(int now) {
            int d1=0,d2=0;
            for(int i=h[now];i!=-1;i=ne[i]) {
                int next=e[i];
                int d=dfs(next);
                if(d>d1) {d2=d1;d1=d;}
                else if(d>d2)d2=d;
            }
            ans=Math.max(ans, d1+d2);
            return d1+1;
        }
    }
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
class Main{
    static int n,m,ans;
    static int[] h=new int[10010*2],e=new int[2*10010],ne=new int[2*10010];
    static int idx=-1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();m=sc.nextInt()+n;
        Arrays.fill(h, -1);
        for(int i=2;i<=m;i++) {
            int father=sc.nextInt();
            insert(father,i);//insert(i,father);
        }
        int d=dfs(1);
        System.out.println(ans);
    }
    static void insert(int a,int b) {
        idx++;//生成新结点的哈希值
        ne[idx]=h[a];//头插法,
        h[a]=idx;//更新头结点
        e[idx]=b;//记录弧头
    }
    static int dfs(int now) {
        int d1=0,d2=0;
        for(int i=h[now];i!=-1;i=ne[i]) {
            int next=e[i];
            int d=dfs(next);
            if(d>=d1) {d2=d1;d1=d;}
            else if(d>d2)d2=d;
        }
        ans=Math.max(ans, d1+d2);
        return d1+1;
    }
}


活动打卡代码 AcWing 3205. 最优配餐

调试将近一小时,终于AC了,前面因为判断顾客这部分算法写的不好到第7个和第9个样例就TLC了
1.因为输入数据十分庞大,因此使用字符缓冲流而不是Scanner。这能优化100~200ms甚至更多
2.判断该结点是否存在顾客,判断是否存在基本上都可以用哈希来优化,因此开一个二维数组来存放该结点是否有顾客

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static Queue<Point> queue = new LinkedList<>();
    static int n,m,k,not;
    static boolean[][] flag;
    static int[][] hash;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str;
        str=br.readLine().split(" ");
        n=Integer.parseInt(str[0]);m=Integer.parseInt(str[1]);k=Integer.parseInt(str[2]);not=Integer.parseInt(str[3]);
        flag=new boolean[n+1][n+1];hash=new int[n+1][n+1];
        for(int i=0;i<m;i++) {str=br.readLine().split(" ");queue.add(new Point(Integer.parseInt(str[0]),Integer.parseInt(str[1]),0));}
        for(int i=0;i<k;i++) {
            str=br.readLine().split(" ");
            //下面这部分代码因为审题不仔细卡了很长时间,应该是+=而不是=
            //因为一个点一个顾客可以点很多单,但是一个点不一定只有一个顾客,可以有多个顾客
            //但是把多个顾客的订单数合并在一起就可以看成是一个顾客了
            hash[Integer.parseInt(str[0])][Integer.parseInt(str[1])]+=Integer.parseInt(str[2]);
        }
        for(int i=0;i<not;i++) {str=br.readLine().split(" ");flag[Integer.parseInt(str[0])][Integer.parseInt(str[1])]=true;}
        bfs();
    }
    static int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
    static void bfs() {
        //System.out.println("-----");
        long res=0;
        while(queue.size()!=0) {
            Point p = queue.poll();
            int xx,yy;
            for(int d=0;d<4;d++) {
                xx=p.x+dx[d];yy=p.y+dy[d];
                if(xx>0&&xx<=n&&yy>0&&yy<=n&&flag[xx][yy]==false) {
                    flag[xx][yy]=true;
                    if(hash[xx][yy]>0)res+=hash[xx][yy]*(p.step+1);
                    queue.add(new Point(xx,yy,p.step+1));
                }
            }
        }
        System.out.println(res);
    }
    static class Point{
        int x,y,step;
        Point(int x,int y,int step){
            this.x=x;this.y=y;this.step=step;
        }
    }
}

最开始的写法。是创建了一个集合存放每一个顾客的位置和订单数,每经过一个结点就判断这个结点是不是这些顾客其中之一的位置。因此算法复杂度要多乘于O(k),最高可达O(n^2)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static Queue<Point> queue = new LinkedList<>();
    static ArrayList<Point> custom = new ArrayList<>();
    static int n,m,k,not;
    static boolean[][] flag;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();m=sc.nextInt();k=sc.nextInt();not=sc.nextInt();
        flag=new boolean[n+1][n+1];
        for(int i=0;i<m;i++)queue.add(new Point(sc.nextInt(),sc.nextInt(),0));
        for(int i=0;i<k;i++)custom.add(new Point(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        for(int i=0;i<not;i++)flag[sc.nextInt()][sc.nextInt()]=true;
        bfs();
    }
    static int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
    static void bfs() {
        long res=0;
        while(queue.size()!=0) {
            Point p = queue.poll();
            for(Point cus:custom)
                if(p.x==cus.x&&p.y==cus.y) {
                    res+=p.step*cus.step;
                    //custom.remove(cus);//为什么不需要删除这个结点是因为访问过这个结点之后,flag数组就会标记这个结点被访问过
                }//变相于删除了这个顾客
            int xx,yy;
            for(int d=0;d<4;d++) {
                xx=p.x+dx[d];yy=p.y+dy[d];
                if(xx>0&&xx<=n&&yy>0&&yy<=n&&flag[xx][yy]==false) {
                    flag[xx][yy]=true;
                    queue.add(new Point(xx,yy,p.step+1));
                }
            }
        }
        System.out.println(res);
    }
    static class Point{
        int x,y,step;
        Point(int x,int y,int step){
            this.x=x;this.y=y;this.step=step;
        }
    }
}

看yxc的代码之后的优化方式,额外开一个二维数组记录到每一个结点的最短路,当bfs结束之后额外遍历一遍顾客集合。但是只能过9个样例,需多加O(k)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static Queue<Point> queue = new LinkedList<>();
    static ArrayList<Point> custom = new ArrayList<>();
    static int n,m,k,not;
    static boolean[][] flag;
    static int[][] step;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();m=sc.nextInt();k=sc.nextInt();not=sc.nextInt();
        flag=new boolean[n+1][n+1];step=new int[n+1][n+1];
        for(int i=0;i<m;i++)queue.add(new Point(sc.nextInt(),sc.nextInt(),0));
        for(int i=0;i<k;i++)custom.add(new Point(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        for(int i=0;i<not;i++)flag[sc.nextInt()][sc.nextInt()]=true;
        bfs();
    }
    static int[] dx= {-1,0,1,0},dy= {0,1,0,-1};
    static void bfs() {
        long res=0;
        while(queue.size()!=0&&custom.size()!=0) {
            Point p = queue.poll();
            int xx,yy;
            for(int d=0;d<4;d++) {
                xx=p.x+dx[d];yy=p.y+dy[d];
                if(xx>0&&xx<=n&&yy>0&&yy<=n&&flag[xx][yy]==false) {
                    flag[xx][yy]=true;
                    step[xx][yy]=p.step+1;
                    queue.add(new Point(xx,yy,p.step+1));
                }
            }
        }
        for(Point cus:custom) {
            res+=cus.step*step[cus.x][cus.y];
        }
        System.out.println(res);
    }
    static class Point{
        int x,y,step;
        Point(int x,int y,int step){
            this.x=x;this.y=y;this.step=step;
        }
    }
}


活动打卡代码 AcWing 3195. 有趣的数

方法一 数学知识+枚举

import java.util.Scanner;
public class Main{
    static int n;
    static int p=1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        yxc(sc.nextInt());
    }
    static void yxc(int n) {
        long res=0;
        for(int i=2;i<n-1;i++) {
            res=(res+(n-i-1)*(i-1)*cnr(n-1,i,p))%p;
        }
        System.out.println(res);
    }
    static long cnr(int n,int r,int p) {
        long res=1;
        for(int i=1;i<=r;i++) {
            res=(res*n--)%p;
            res=(res*quick_mi(i,p-2,p))%p;
        }
        return res;
    }
    static long quick_mi(long base,int mi,int p) {
        long res=1;
        while(mi>0) {
            if((mi&1)==1) res=(res*base)%p;
            mi>>=1;
            base=(base*base)%p;
        }
        return res;
    }
}


活动打卡代码 AcWing 507. 积木大赛

看了一眼算法标签直觉觉得应该怎么做,至于原理暂知道

import java.util.Scanner;

public class Main{
    static int[] arr;
    static int[] chafen;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        arr=new int[n+1];chafen=new int[n+1];
        for(int i=1;i<=n;i++) {
            arr[i]=sc.nextInt();
            chafen[i]=arr[i]-arr[i-1];
        }
        int res=0;
        for(int i=1;i<=n;i++) {
            if(chafen[i]>0)res+=chafen[i];
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 148. 合并果子

这道题和哈夫曼编码很像,但比哈夫曼编码简单,哈夫曼还要手动构建二叉树,这道题只要遍历一遍优先队列即可

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main{
    static PriorityQueue<Integer> queue=new PriorityQueue<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++)queue.add(sc.nextInt());
        f();
    }
    static void f() {
        long res=0;
        while(queue.size()!=1) {
            int a=queue.poll()+queue.poll();
            res+=a;
            queue.add(a);
        }
        System.out.println(res);
    }
}

知识复习:优先队列PriorityQueue
1.PriorityQueue和LinkedList一样是Queue接口的实现类
2.优先队列可以对其中元素进行排序,可以放基本的包装类型或自定义的类,对于基本类型的包装类,优先队列中元素的默认排列顺序是升序,但是对于自定义类来说,需要自定义比较类
3.对元素采用的是堆排序,头是按指定排序方式的最小元素。堆排序只能保证根是最大(最小),整个堆并不是有序的。



活动打卡代码 AcWing 496. 机器翻译

哈希+队列
方法一:手动模拟队列
自己用数组模拟队列时注意让数组长度为m+1,且模的也是m+1,保证当存第m+1个数据时尾指针与头指针才会重合

import java.util.Scanner;

public class Main{
    static int m,n;
    static int[] arr,haxi=new int[1001],queue;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m=sc.nextInt()+1;n=sc.nextInt();
        arr=new int[n];queue=new int[m];
        for(int i=0;i<n;i++)arr[i]=sc.nextInt();
        f();
    }
    static int head,index,res;
    static void f() {
        for(int i=0;i<arr.length;i++) {
            if(haxi[arr[i]]==0) {
                res++;
                haxi[arr[i]]=1;
                index=(index+1)%m;//从1开始存
                queue[index]=arr[i];
                if(index==head) {
                    head=(head+1)%m;
                    haxi[queue[head]]=0;
                }
            }
        }
        System.out.println(res);
    }
}

调库写法

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static int m,n,res;
    static int[] arr,haxi=new int[1001];
    static Queue<Integer> queue = new LinkedList<Integer>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m=sc.nextInt();n=sc.nextInt();
        arr=new int[n];
        for(int i=0;i<n;i++)arr[i]=sc.nextInt();
        f();
    }
    static void f(){
        for(int i=0;i<arr.length;i++){
            if(haxi[arr[i]]==0){
                res++;
                haxi[arr[i]]=1;
                if(queue.size()==m){int temp=queue.poll();haxi[temp]=0;}
                queue.add(arr[i]);
            }
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 211. 计算系数

方法一:费马小定理+快速幂求解Cnr

import java.util.Scanner;

public class Main {
    static int a,b,k,n,m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a=sc.nextInt();b=sc.nextInt();k=sc.nextInt();n=sc.nextInt();m=sc.nextInt();
        System.out.println(f());
    }
    static long f() {
        if((n+m)!=k)return 0;
        long res=(qm(a,n,10007)*qm(b,m,10007))%10007;
        res=(res*cnr(k,m))%10007;
        return res;
    }
    static long cnr(int n,int r) {
        long res=1;
        for(int i=1;i<=r;i++) {
            res=(res*n)%10007;
            n--;
            res=(res*qm(i,10005,10007))%10007;
        }
        return res;
    }
    static long qm(long ji,int mi,int p) {
        long res=1;
        while(mi>0) {
            if((mi&1)!=0)res=(res*ji)%p;
            mi>>=1;
            ji=ji*ji%p;
        }
        return res;
    }
}

方法二 扩展欧拉算法求Cnr

import java.util.Scanner;

public class Main {
    static int a,b,k,n,m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a=sc.nextInt();b=sc.nextInt();k=sc.nextInt();n=sc.nextInt();m=sc.nextInt();
        System.out.println(f());
    }
    static long f() {
        if((n+m)!=k)return 0;
        long res=(qm(a,n,10007)*qm(b,m,10007))%10007;
        res=(res*cnr(k,m))%10007;
        return res;
    }
    static long cnr(int n,int r) {
        long res=1;
        for(int i=1;i<=r;i++) {
            res=(res*n)%10007;n--;
            x=0;y=0;
            exGcd(i,10007);
            res=(res*(x+10007)%10007)%10007;
        }
        return res;
    }
    static int x,y;
    static void exGcd(int a,int b){
        if(b==0){
            x=1;y=0;
            return;
        }
        exGcd(b,a%b);
        int temp=x;
        x=y;
        y=temp-a/b*y;
    }
    static long qm(long ji,int mi,int p) {
        long res=1;
        while(mi>0) {
            if((mi&1)!=0)res=(res*ji)%p;
            mi>>=1;
            ji=ji*ji%p;
        }
        return res;
    }
}

用的时间差不多