2015 ACM/ICPC Asia Regional Changchun Online

Show All Problems

Soluble Problems
Alisha’s Party
Unknown Treasure

Alisha’s Party

/** Sep 13, 2015 12:39:06 PM
 * PrjName:0913-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {
	static Person[] per;
	static Pair[] cm;
	static PriorityQueue<Person> que = new PriorityQueue<Person>(new Person.Comp());
	static Vector<String> ans = new Vector<String>();

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int T = in.nextInt();
		while (T-- > 0) {
			int n = in.nextInt();
			int m = in.nextInt();
			int q = in.nextInt();
			per = new Person[n];
			for (int i = 0; i < n; i++)
				per[i] = new Person(in.next(), in.nextInt(), i + 1);
			cm = new Pair[m];
			for (int i = 0; i < m; i++)
				cm[i] = new Pair(in.nextInt(), in.nextInt());
			Arrays.sort(cm, new Pair.Comp());
			que.clear();
			int t = 0;
			ans.clear();
			for (int i = 0; i < n; i++) {
				que.add(per[i]);
				if (t < m && cm[t].l == i + 1) {
					for (int j = 0; j < cm[t].r && !que.isEmpty(); j++)
						ans.add(que.poll().name);
					t++;
				}
			}
			while (!que.isEmpty())
				ans.add(que.poll().name);
			while (q-- > 0) {
				out.print(ans.get(in.nextInt() - 1) + (q > 0 ? " " : ""));
			}
			out.println();
		}
		out.flush();
		out.close();
	}
}

class Person {
	String name;
	int v, t;
	Person() {
	}
	Person(String _nm, int _v, int _t) {
		name = _nm;
		v = _v;
		t = _t;
	}
	static class Comp implements Comparator<Person> {
		public int compare(Person p1, Person p2) {
			if (p1.v == p2.v)
				return Integer.compare(p1.t, p2.t);
			return -Integer.compare(p1.v, p2.v);
		}
	}
}

class Pair {
	int l, r;
	Pair() {
	}
	Pair(int a, int b) {
		l = a;
		r = b;
	}
	static class Comp implements Comparator<Pair> {
		public int compare(Pair o1, Pair o2) {
			if (o1.l == o2.l)
				return Integer.compare(o1.r, o2.r);
			return Integer.compare(o1.l, o2.l);
		}
	}
}

能不能别再搞那个复杂的合并了啊……还有不要对空优先队列做push操作啊……

Unknown Treasure

/** Sep 13, 2015 9:26:58 AM
 * PrjName:0913-10
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;

public class Main {

    final static int maxn = 110000;
    static long[] fac = new long[maxn];
    static long[] p, a;
    static long x, y;

    static void Get_Fac(long n) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
            fac[i] %= n;
        }
    }

    static void extgcd(long a, long b) {
        if (b == 0L) {
            x = 1L;
            y = 0L;
            return;
        }
        extgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
    }

    static long pow_mod(long n, long m, long mod) {
        long res = 1L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                res = res * n % mod;
            n = n * n % mod;
            m >>= 1;
        }
        return res;
    }

    static long mul_mod(long n, long m, long mod) {
        long ans = 0L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                ans = (ans + n) % mod;
            m >>= 1;
            n = (n + n) % mod;
        }
        return ans;
    }

    static long div_mod(long n, long m, long mod) {
        return n * pow_mod(m, mod - 2, mod) % mod;
    }

    static long C(long n, long m, long mod) {
        int a = (int) (n % mod), b = (int) (m % mod);
        return div_mod(fac[a], mul_mod(fac[a - b], fac[b], mod), mod);
    }

    static long Lucas(long n, long m, long mod) {
        long ret = 1L;
        while (n > 0L && m > 0L) {
            if (n % mod < m % mod)
                return 0L;
            ret = mul_mod(ret, C(n, m, mod), mod);
            ret %= mod;
            n /= mod;
            m /= mod;
        }
        return ret;
    }

    // 中国剩余定理 x == a[i] (mod m[i]) 共有n个方程。
    static long CRT(long n, long[] a, long[] m) {
        long pro = 1L, res = 0L;
        for (int i = 0; i < n; i++)
            pro *= m[i];
        for (int i = 0; i < n; i++) {
            long w = pro / m[i];
            extgcd(m[i], w);
            res = (res + mul_mod(y, mul_mod(w, a[i], pro), pro)) % pro;
        }
        return (res + pro) % pro;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int T = in.nextInt();
        while (T-- > 0) {
            long n = in.nextLong();
            long m = in.nextLong();
            long num = in.nextLong();
            p = new long[15];
            a = new long[15];
            for (int i = 0; i < num; i++)
                p[i] = in.nextLong();
            for (int i = 0; i < num; i++) {
                Get_Fac(p[i]);
                a[i] = Lucas(n, m, p[i]);
            }
            out.println(CRT(num, a, p));
        }
        out.flush();
        out.close();
    }

}

一堆数论模板的集体亮相……但是为何解n个方程的中国剩余定理模板就难以被收集？