Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
土办法,直接从后向前,分割递归static const int NMAX = 10000; static int sl[NMAX]; //left endpoint static int sr[NMAX]; //right endpoint static char flag[NMAX]; static const int MAX_LEN = 10000000; static int N; // the N input intervals void calc(int l, int r, int i) { if (i < 0) return; int l2 = sl[i]; int r2 = sr[i]; if (l2 <= r && r2 >= l) flag[i] = 1; if (r2 < r) { int t = (r2+1) < l ? l : (r2+1); calc (t, r, i-1); } if (l2 > l) { int t = (l2-1) > r ? r : (l2-1); calc(l, t, i-1); } } static void processcase() { int lmin = 100000000; int lmax = 0; memset(flag, 0, sizeof(flag)); scanf("%d", &N); for (int i = 0; i<N; i++) scanf("%d %d", &sl[i], &sr[i]); calc(1, MAX_LEN, N-1); int total = 0; for (int i = 0; i<N; i++) if (flag[i] != 0) total++; printf("%d\n", total); } int main() { int ncase = 0; scanf("%d", &ncase); for (int i = 0; i<ncase; i++) { processcase(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator