A. Find a Number
找到一个树，可以被d整除，且数字和为s
记忆化搜索
1 static class S{ 2 int mod,s; 3 String str; 4 5 public S(int mod, int s, String str) { 6 this.mod = mod; 7 this.s = s; 8 this.str = str; 9 } 10 } 11 12 public static void main(String[] args) { 13 IO io = new IO(); 14 int[][]vis=new int[550][5500]; 15 int d=io.nextInt(),s=io.nextInt(); 16 Queue<S>q=new ArrayDeque<>(10000); 17 q.add(new S(0,0,"")); 18 while (!q.isEmpty()){ 19 S cur=q.poll(); 20 if (cur.mod==0&&cur.s==s){ 21 io.println(cur.str);return; 22 } 23 for (int i = 0; i <=9; i++) { 24 int mm=(cur.mod*10+i)%d; 25 int ss=cur.s+i; 26 if (vis[mm][ss]==0&&ss<=s){ 27 q.add(new S(mm,ss,cur.str+i)); 28 vis[mm][ss]=1; 29 } 30 } 31 } 32 io.println(-1); 33 }
B. Berkomnadzor——我选择狗带……这题目有毒啊
C. Cloud Computing
有m个计划，每个计划的内容是从[l，r]天内，总共有c个处理器，每个p元。问，从[1，n]天，每天买k个处理器（尽量买齐k个）最小花费是多少
线段树表示当天有效的计划，处理器价格就是叶子编号。注意此题要全部开long，tre[i][0]是个数总和，tre[i][1]是价值总和。（才发现把tre拆成两个数组会快一倍）
1 private static final int c = 1000100; 2 static long[] S = new long[c << 2]; 3 static long[] sum = new long[c << 2]; 4 static long ans; 5 static ArrayList<long[]>[] plan = new ArrayList[c]; 6 7 static void update(int t, int l, int r, long c, long p) { 8 S[t] += c; 9 sum[t] += c * p; 10 if (l == r) return; 11 int mid = l + r >> 1; 12 if (p <= mid) update(t << 1, l, mid, c, p); 13 else update(t << 1 | 1, mid + 1, r, c, p); 14 } 15 16 static long query(int t, int l, int r, long k) { 17 if (k <= 0) return 0; 18 if (S[t] <= k) return sum[t]; 19 if (l == r) return k * l; 20 int mid = l + r >> 1; 21 return query(t << 1, l, mid, k) + 22 query(t << 1 | 1, mid + 1, r, k - S[t << 1]); 23 } 24 25 public static void main(String[] args) { 26 for (int i = 0; i < plan.length; i++) plan[i] = new ArrayList<>(); 27 IO io = new IO(); 28 int n = io.nextInt(), k = io.nextInt(), m = io.nextInt(); 29 for (int i = 0; i < m; i++) { 30 int l = io.nextInt(), r = io.nextInt(), c = io.nextInt(), p = io.nextInt(); 31 plan[l].add(new long[]{c, p}); 32 plan[r + 1].add(new long[]{-c, p}); 33 } 34 for (int i = 1; i <= n; i++) { 35 for (long[] v : plan[i]) update(1, 1, c, v[0], v[1]); 36 ans += query(1, 1, c, Math.min(S[1], k)); 37 } 38 io.println(ans); 39 }
D. Garbage Disposal
有n天，每天产生ni的垃圾，每个垃圾袋容量为k，每天产生的垃圾最迟第二天要丢掉，第n天的垃圾当天要丢掉，问使用的垃圾袋最少个数
模拟
1 private static final int c = (int) 2e6; 2 3 public static void main(String[] args) { 4 IO io=new IO(); 5 long n=io.nextLong(),k=io.nextLong(); 6 long[]a=new long[2]; 7 long ans=0; 8 for (int i=1;i<=n;i++){ 9 int now=i&1,pre=now^1; 10 long t=io.nextLong(); 11 if (i==n){ 12 ans+=Math.ceil((double)(t+a[pre])/k); 13 break; 14 } 15 if (a[pre]!=0){ 16 ans+=Math.ceil((double) a[pre]/k); 17 long more=k-a[pre]%k; 18 t-=more; 19 if (t<0)t=0; 20 } 21 ans+=t/k; 22 t%=k; 23 a[now]=t; 24 } 25 io.println(ans); 26 }