IME++ Starters Try-outs 2019 CF二星GYM补题

亦凉 2022-12-25 11:58 99阅读 0赞

### 目录 ###

*  E. Essay Time
 *   *  题目：
     *  分析：
     *  AC代码：
 *  G. Grade Concept（线段树）
 *   *  题目：
     *  分析：
     *  AC代码：
 *  H. High Hopes
 *   *  题目：
     *  分析：
     *  AC代码：

# E. Essay Time #

## 题目： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

## 分析： ##

挖坑，后边补

## AC代码： ##

![在这里插入图片描述][20201201213918488.png]

import java.util.*;
    import java.io.*;
     
    public class E { 
     
        public static void main(String[] args) throws IOException { 
            Scanner sc = new Scanner(System.in);
            PrintWriter pw = new PrintWriter(System.out);
            int t = sc.nextInt();
            int z=0;
            HashSet<String>used= new HashSet<>();
            StringBuffer sol= new StringBuffer();
            while (t-->0){ 
                String s = sc.nextLine();
                if(s.length()>=4){ 
                    if (used.contains(s)){ 
                        if (z>0)
                            sol.append("\n");
                        z++;
                        sol.append(s);
                    }
                    else used.add(s);
                }
            }
            if (z>0) { 
                pw.println(z);
                pw.println(sol);
            }
            else pw.println("SAFO");
            pw.flush();
        }
     
        static class Scanner { 
            StringTokenizer st;
            BufferedReader br;
     
            public Scanner(FileReader r) { 
                br = new BufferedReader(r);
            }
     
            public Scanner(InputStream s) { 
                br = new BufferedReader(new InputStreamReader(s));
            }
     
            public String next() throws IOException { 
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            }
     
            public int nextInt() throws IOException { 
                return Integer.parseInt(next());
            }
     
            public long nextLong() throws IOException { 
                return Long.parseLong(next());
            }
     
            public String nextLine() throws IOException { 
                return br.readLine();
            }
     
            public double nextDouble() throws IOException { 
                String x = next();
                StringBuilder sb = new StringBuilder("0");
                double res = 0, f = 1;
                boolean dec = false, neg = false;
                int start = 0;
                if (x.charAt(0) == '-') { 
                    neg = true;
                    start++;
                }
                for (int i = start; i < x.length(); i++)
                    if (x.charAt(i) == '.') { 
                        res = Long.parseLong(sb.toString());
                        sb = new StringBuilder("0");
                        dec = true;
                    } else { 
                        sb.append(x.charAt(i));
                        if (dec)
                            f *= 10;
                    }
                res += Long.parseLong(sb.toString()) / f;
                return res * (neg ? -1 : 1);
            }
     
            public boolean ready() throws IOException { 
                return br.ready();
            }
        }
    }

# G. Grade Concept（线段树） #

## 题目： ##

time limit per test1 second  
memory limit per test256 megabytes  
inputstandard input  
outputstandard output  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]

## 分析： ##

线段树问题，维护一个线段树即可，模板问题

## AC代码： ##

![在这里插入图片描述][20201201213040608.png]

import java.io.*;
    import java.util.*;
     
    public class G implements Closeable { 
     
      private InputReader in = new InputReader(System.in);
      private PrintWriter out = new PrintWriter(System.out);
     
      private class Node { 
        private int idx, lo, hi, min, max, sum;
     
        private void merge(Node left, Node right) { 
          min = Math.min(left.min, right.min);
          max = Math.max(left.max, right.max);
          sum = left.sum + right.sum;
        }
     
        private void assign(int value) { 
          min = max = sum = value;
        }
      }
     
      private class SegmentTree { 
        private int[] x;
        private Node[] nodes;
     
        private SegmentTree(int[] x) { 
          int n = x.length;
          this.x = x;
          nodes = new Node[4 * n + 1];
          for (int i = 0; i < nodes.length; i++) { 
            nodes[i] = new Node();
          }
          init(1, 0, n - 1);
        }
     
        private void init(int idx, int left, int right) { 
          nodes[idx].lo = left;
          nodes[idx].hi = right;
          if (left == right) { 
            nodes[idx].assign(x[left]);
          } else { 
            int mid = (left + right) / 2;
            init(idx << 1, left, mid);
            init(idx << 1 | 1, mid + 1, right);
            nodes[idx].merge(nodes[idx << 1], nodes[idx << 1 | 1]);
          }
        }
     
        private int query(int left, int right) { 
          Node result = query(1, left, right);
          return result.sum - result.min - result.max;
        }
     
        private Node query(int idx, int a, int b) { 
          if (a <= nodes[idx].lo && nodes[idx].hi <= b) { 
            return nodes[idx];
          }
          int mid = (nodes[idx].lo + nodes[idx].hi) / 2;
          if (a > mid) { 
            return query(2 * idx + 1, a, b);
          }
          if (b <= mid) { 
            return query(2 * idx, a, b);
          }
     
          Node result = new Node();
          result.merge(query(2 * idx, a, mid), query(2 * idx + 1, mid + 1, b));
          return result;
        }
     
        private void update(int idx, int value) { 
          update(1, idx, idx, value);
        }
     
        public void update(int idx, int left, int right, int value) { 
          if (nodes[idx].lo > right || nodes[idx].hi < left) return;
          if (nodes[idx].lo == left && nodes[idx].hi == right) { 
            nodes[idx].assign(value);
            return;
          }
          update(idx << 1, left, right, value);
          update(idx << 1 | 1, left, right, value);
          nodes[idx].merge(nodes[idx << 1], nodes[idx << 1 | 1]);
        }
      }
     
      public void solve() { 
        int n = in.ni(), q = in.ni();
        int[] x = new int[n];
        for (int i = 0; i < n; i++) { 
          x[i] = in.ni();
        }
        SegmentTree tree = new SegmentTree(x);
        while (q-- > 0) { 
          int type = in.ni();
          if (type == 1) { 
            int left = in.ni() - 1, right = in.ni() - 1;
            out.println(tree.query(left, right));
          } else { 
            int idx = in.ni() - 1, value = in.ni();
            tree.update(idx, value);
          }
        }
      }
     
      @Override
      public void close() throws IOException { 
        in.close();
        out.close();
      }
     
      static class InputReader { 
        public BufferedReader reader;
        public StringTokenizer tokenizer;
     
        public InputReader(InputStream stream) { 
          reader = new BufferedReader(new InputStreamReader(stream), 32768);
          tokenizer = null;
        }
     
        public String next() { 
          while (tokenizer == null || !tokenizer.hasMoreTokens()) { 
            try { 
              tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) { 
              throw new RuntimeException(e);
            }
          }
          return tokenizer.nextToken();
        }
     
        public int ni() { 
          return Integer.parseInt(next());
        }
     
        public long nl() { 
          return Long.parseLong(next());
        }
     
        public void close() throws IOException { 
          reader.close();
        }
      }
     
      public static void main(String[] args) throws IOException { 
        try (G instance = new G()) { 
          instance.solve();
        }
      }
    }

# H. High Hopes #

## 题目： ##

## 分析： ##

任何数的0次方都等于1.

## AC代码： ##

![在这里插入图片描述][20201201204445807.png]

import java.util.*;
    public class h{ 
    	public static void main(String[] a) { 
    	    Scanner s=new Scanner(System.in);
    		int n=s.nextInt();
    		while(n-->0)
    			System.out.println(0);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20221120/7ae3cdc2392244ee9f2bdb3b0a39f84a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20221120/92910ceb9b954c719a4a5cabf0028129.png
[20201201213918488.png]: https://img-blog.csdnimg.cn/20201201213918488.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201201203008387.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201201203047569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[20201201213040608.png]: https://img-blog.csdnimg.cn/20201201213040608.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201201203250457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[20201201204445807.png]: https://img-blog.csdnimg.cn/20201201204445807.png