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