头像

huaqingren




离线:1小时前


活动打卡代码 AcWing 3284. 化学方程式



import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main
{
    private static int u=0;

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        scan.nextLine();

        while(n--!=0)
        {
            String str=scan.nextLine().trim();
            int k=str.indexOf('=');
            Map<String,Integer> right=work(str.substring(k+1));
            Map<String,Integer> left=work(str.substring(0, k));

            if(left.equals(right))
                System.out.println("Y");
            else
                System.out.println("N");

//          for(String c:left.keySet())
//              System.out.println(c+" "+left.get(c));
//          System.out.println();
//          for(String c:right.keySet())
//              System.out.println(c+" "+right.get(c));
        }


        scan.close();

    }

    private static Map<String, Integer> work(String str)
    {
        Map<String, Integer> res=new HashMap<>();

        for(int i=0;i<str.length();i++)
        {
            int j=i+1;
            while(j<str.length()&&str.charAt(j)!='+') j++;
            String item=str.substring(i, j);
            i=j;
            int cnt=1,k=0;
            while(k<item.length()&&Character.isDigit(item.charAt(k))) k++;
            if(k!=0) cnt=Integer.valueOf(item.substring(0,k));
            u=k;
            Map<String, Integer> t=dfs(item);
            for(String c:t.keySet())
            {
                int s=res.get(c)==null?0:res.get(c);
                res.put(c, t.get(c)*cnt+s);
            }
        }



        return res;
    }

    private static Map<String, Integer> dfs(String str)
    {
        Map<String, Integer> res=new HashMap<>();

        while(u<str.length())
        {
            if(str.charAt(u)=='(')
            {
                u++;//跳过(
                Map<String, Integer> t = dfs(str);
                u++;//跳过)
                int cnt=1,k=u;
                while(k<str.length()&&Character.isDigit(str.charAt(k))) k++;
                if(k>u)
                {
                    cnt=Integer.valueOf(str.substring(u, k));
                    u=k;
                }
                for(String c:t.keySet())
                {
                    int s=res.get(c)==null?0:res.get(c);
                    res.put(c, t.get(c)*cnt+s);
                }
            }
            else if(str.charAt(u)==')') break;
            else
            {
                int k = u + 1;
                while (k < str.length() && str.charAt(k) >= 'a' && str.charAt(k) <= 'z') k ++ ;
                String key = str.substring(u, k);
                u = k;
                int cnt = 1;
                while (k < str.length() && Character.isDigit(str.charAt(k))) k ++ ;
                if (k > u)
                {
                    cnt = Integer.valueOf((str.substring(u,k)));
                    u = k;
                }
                int s=res.get(key)==null?0:res.get(key);
                res.put(key, s+cnt);

            }
        }





        return res;
    }

}






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

public class Main
{

    private static int N=6010;
    private static List<Integer>[] list=new ArrayList[N];
    private static int[] w=new int[N];
    private static boolean[] st=new boolean[N];
    private static int[][] f=new int[N][2];


    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        for(int i=1;i<=n;i++)
            w[i]=scan.nextInt();

        for(int i=1;i<=n;i++)
            list[i]=new ArrayList<>();

        for(int i=0;i<n-1;i++)
        {
            int a=scan.nextInt();
            int b=scan.nextInt();
            list[b].add(a);
            st[a]=true;
        }

        int root=1;
        while(st[root]) root++;

        dfs(root);

        System.out.println(Math.max(f[root][0], f[root][1]));


        scan.close();

    }


    private static void dfs(int u)
    {
        f[u][0]=0;
        f[u][1]=w[u];

        for(int i=0;i<list[u].size();i++)
        {
            int j=list[u].get(i);
            dfs(j);
            f[u][0]+=Math.max(f[j][0], f[j][1]);
            f[u][1]+=f[j][0];
        }

    }

}



活动打卡代码 AcWing 3302. 表达式求值



import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Main
{   
    private static Stack<Integer> num=new Stack<>();
    private static Stack<Character> op=new Stack<>();
    private static Map<Character,Integer> pr=new HashMap<>();

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        pr.put('+',1);
        pr.put('-',1);
        pr.put('*',2);
        pr.put('/',2);

        String str=scan.nextLine();

        for(int i=0;i<str.length();i++)
        {
            char c=str.charAt(i);
            if(Character.isDigit(c))
            {
                int x=0,j=i;
                while(j<str.length()&&Character.isDigit(str.charAt(j)))
                    x=x*10+(str.charAt(j++)-'0');
                i=j-1;
                num.push(x);
            }
            else if(c=='(')
                op.push(c);
            else if(c==')')
            {
                while(op.peek()!='(') eval();
                op.pop();
            }
            else
            {
                while(!op.isEmpty()&&pr.get(op.peek())!=null&&pr.get(op.peek())>=pr.get(c)) eval();
                op.push(c);
            }
        }

        while(!op.isEmpty()) eval();

        System.out.println(num.peek());


        scan.close();

    }

    private static void eval()
    {
        int b=num.pop();
        int a=num.pop();
        char c=op.pop();
        int x;
        if(c=='+') x=a+b;
        else if(c=='-') x=a-b;
        else if(c=='*') x=a*b;
        else x=a/b;
        num.push(x);
    }



}



活动打卡代码 AcWing 3302. 表达式求值



import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Main
{
    private static Stack<Integer> num=new Stack<>();
    private static Stack<Character> op=new Stack<>();
    private static Map<Character,Integer> pr=new HashMap<>();

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);


        pr.put('+',1);
        pr.put('-',1);
        pr.put('*',2);
        pr.put('/',2);

        String str=scan.nextLine();

        for(int i=0;i<str.length();i++)
        {
            char c=str.charAt(i);
            if(Character.isDigit(c))
            {
                int x=0,j=i;
                while(j<str.length()&&Character.isDigit(str.charAt(j)))
                {
                    x=x*10+(str.charAt(j)-'0');
                    j++;
                }

                i=j-1;
                num.push(x);
            }
            else if(c=='(')
                op.push(c);
            else if(c==')')
            {
                while(op.peek()!='(') eval();
                op.pop();//弹出 (
            }
            else //普通运算符
            {
                while(!op.isEmpty()&&pr.get(op.peek())!=null&&pr.get(op.peek())>=pr.get(c)) eval();
                op.push(c);
            }   
        }

        while(op.size()!=0) eval();

        System.out.println(num.pop());

        scan.close();

    }

    private static void eval()
    {
        int b=num.pop();
        int a=num.pop();
        char c=op.pop();
        int x;
        if(c=='+') x=a+b;
        else if(c=='-') x=a-b;
        else if(c=='*') x=a*b;
        else x=a/b;
        num.push(x);

    }

}



活动打卡代码 AcWing 3268. 小明放学



import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int r=scan.nextInt();
        int y=scan.nextInt();
        int g=scan.nextInt();

        long res=0;
        int n=scan.nextInt();

        while(n--!=0)
        {
            int k=scan.nextInt();
            long t=scan.nextInt();
            if(k==0)
                res+=t;
            else
            {
                if(k==1)
                    t=r-t;
                else if(k==2)
                    t=r+y+g-t;
                else
                    t=r+g-t;
                t+=res;
                t%=r+y+g;
                if(t<r)
                    res+=r-t;
                else if(t>=r+g)
                    res+=(long)r+y+g-t+r;
            }
        }

        System.out.println(res);

        scan.close();

    }

}



活动打卡代码 AcWing 3267. 小明上学



import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int r=scan.nextInt();
        int y=scan.nextInt();
        int g=scan.nextInt();

        int res=0;
        int n=scan.nextInt();
        while(n--!=0)
        {
            int k=scan.nextInt();
            int t=scan.nextInt();
            if(k==0)
            {
                res+=t;
            }
            else if(k==1)
            {
                res+=t;
            }
            else if(k==2)
            {
                res+=t+r;
            }

        }

        System.out.println(res);
        scan.close();

    }

}






import java.util.Scanner;

public class Main
{
    private static int N=100010;
    private static int[] a=new int[N];
    private static int[] q=new int[N];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        for(int i=0;i<n;i++)
            a[i]=scan.nextInt();

        int len=0;
        q[0]=-2000000000;
        for(int i=0;i<n;i++)
        {
            int l=0,r=len;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(q[mid]<a[i]) l=mid;
                else r=mid-1;
            }
            len=Math.max(len, r+1);
            q[r+1]=a[i];
        }

        System.out.println(len);
//      for(int i=0;i<=len;i++)
//          System.out.print(q[i]+" ");
        scan.close();

    }

}



活动打卡代码 AcWing 116. 飞行员兄弟



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

public class Main
{
    private static int[][] state=new int[4][4];

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        for(int i=0;i<4;i++)
        {
            String str=scan.nextLine();
            for(int j=0;j<4;j++)
            {
                if(str.charAt(j)=='+')
                {
                    state[i][j]=1;
                }

            }
        }

        List<Node> ans=new ArrayList<>();
        for(int k=0;k<1<<16;k++)
        {
            //先要保存一下state
            int[][] temp=new int[4][4];
            for(int i=0;i<4;i++)
                for(int j=0;j<4;j++)
                    temp[i][j]=state[i][j];

            List<Node> list=new ArrayList<>();
            for(int j=0;j<16;j++)
            {
                //所在位置为1就要操作一下
                if((k>>j&1)==1)
                {
                    int x=j/4,y=j%4;
                    change(temp,x,y);
                    list.add(new Node(x,y));
                }
            }
            //如果当前temp满足要求,并且最终答案数组ans为空,或者有更短的方案,则要更新
            if(get_sum(temp)&&(ans.isEmpty()||ans.size()>list.size()))
                ans=list;

        }

        System.out.println(ans.size());
        for(Node t:ans)
        {
            System.out.println((t.x+1)+" "+(t.y+1));
        }

        scan.close();

    }

    private static boolean get_sum(int[][] temp)
    {
        int sum=0;
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                sum+=temp[i][j];
        return sum==0;
    }

    //更改x,y所在行列数值的状态
    private static void change(int[][] temp,int x, int y)
    {
        temp[x][y]^=1;
        //上
        int tx=x-1,ty=y;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            tx--;
        }
        //下
        tx=x+1;
        ty=y;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            tx++;
        }

        //左
        tx=x;
        ty=y-1;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            ty--;
        }

        //右
        tx=x;
        ty=y+1;
        while(tx>=0&&tx<4&&ty>=0&&ty<4)
        {
            temp[tx][ty]^=1;
            ty++;
        }



    }

    private static class Node
    {
        private int x;
        private int y;
        public Node(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }

}



活动打卡代码 AcWing 95. 费解的开关



import java.util.Scanner;

public class Main
{

    private static char[][] map=new char[5][5];
    private static int[] dx= {0,-1,0,1,0},dy= {0,0,1,0,-1};

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);


        int n=scan.nextInt();
        scan.nextLine();

        while(n--!=0)
        {
            for(int i=0;i<5;i++)
                map[i]=scan.nextLine().toCharArray();
            if(n!=0)
                scan.nextLine();
            System.out.println(work());
        }


        scan.close();


    }

    private static void turn(int x,int y)
    {
        for(int i=0;i<5;i++)
        {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(tx>=0&&tx<5&&ty>=0&&ty<5)
            {
                map[tx][ty]=(char)(map[tx][ty]^1);//0 1互换
            }
        }
    }

    private static int work()
    {
        int ans=10000000;

        //枚举第一行所有可能的情况
        for(int k=0;k<1<<5;k++)
        {
            int res=0;
            char[][] temp=new char[5][5];
            for(int i=0;i<5;i++)
                for(int j=0;j<5;j++)
                    temp[i][j]=map[i][j];
            for(int j=0;j<5;j++)
            {
                if((k>>j&1)==1)
                {
                    turn(0,j);
                    res++;
                }
            }

            for(int i=0;i<4;i++)
            {
                for(int j=0;j<5;j++)
                {
                    if(map[i][j]=='0')
                    {
                        turn(i+1,j);
                        res++;
                    }

                }
            }
            boolean flag=true;
            for(int j=0;j<5;j++)
                if(map[4][j]=='0')
                {
                    flag=false;
                    break;
                }
            if(flag)
                ans=Math.min(ans, res);

            for(int i=0;i<5;i++)
                for(int j=0;j<5;j++)
                    map[i][j]=temp[i][j];
        }

        if(ans>6) return -1;
        return ans;
    }

}



活动打卡代码 AcWing 892. 台阶-Nim游戏

import java.util.*;


public class Main
{
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        int res=0;
        for(int i=1;i<=n;i++)
        {
            int x=scan.nextInt();
            if(i%2==1)
                res^=x;
        }

        if(res!=0)
            System.out.println("Yes");
        else
            System.out.println("No");



        scan.close();

    }



}