2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)

时间:2022-10-23 22:00:54

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);
}