题解链接：
今天是新队伍的第一场组队赛，算是跟队友们相互适应的热身赛！怎么说，到今天为止，我的算法基础还是不太好，所以今天只是看着队友过了一题线段树。然后，又因为昨晚cf搞太晚了，今天精神一般，在努力过题的队友隔壁不知不觉睡着了.....
其实今天打的可谓是非常被动，其他学校的神牛刚开始不到几分钟就过题了，然后我们也就尝试跟着神牛的步伐，尝试由易到难逐题击破。当然，这样也就发生一个很严重的问题了！我们三个（特别是我，因为我睡着了- -）除了神牛带路的三题（卡了两题，1001在我睡觉的时候，队友证明到一个方法了，之后跟teletubbi他们队交流，也说了想法是对的，不过他们在比赛的过程中没能做出；1005一直用错了方法，算错了复杂度，TLE了一个下午），其他题我们基本上都没去想怎么做，甚至是没看题...囧。大牛们一直都教导着我们，比赛的时候应该把所有题都要看一遍，可是这次居然就犯这么严重的错误，现在想起来真的觉得很不应该！
上面是今天的情况，其实可以看出1003、1004、1009都是可以尝试的。尤其是1004，稍微看一看题都知道，这显然是一个dp，可是我们却没人打算开这题。- - 虽然不知道当场能不能过，不过试都没试就真的是觉得太可惜了！然后就是，怎么越来越觉得我什么都不懂............ 没事，我相信可以那些知识漏洞是补上的！继续努力！！！
发一下刚刚写的1006线段树（1y）的代码，整段覆盖，单点查询：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 #define lson l, m, rt << 1 8 #define rson m + 1, r, rt << 1 | 1 9 #define root 0, mx - 1, 1 10 11 using namespace std; 12 13 #define debug 0 14 15 int min2(int _a, int _b){ return _a < _b ? _a : _b;} 16 int max2(int _a, int _b){ return _a > _b ? _a : _b;} 17 18 const int maxn = 100001; 19 20 int x[maxn << 2], M, N, nx, mx; 21 int lt[maxn << 4], mk[maxn << 4]; 22 int s[maxn], t[maxn], tt[maxn]; 23 24 void load(){ 25 scanf("%d%d", &N, &M); 26 nx = 0; 27 for (int i = 0; i < N; i++){ 28 scanf("%d%d", &s[i], &t[i]); 29 x[nx++] = s[i]; 30 x[nx++] = t[i]; 31 } 32 for (int i = 0; i < M; i++){ 33 scanf("%d", &tt[i]); 34 x[nx++] = tt[i]; 35 } 36 sort(x, x + nx); 37 mx = nx; 38 39 #if debug 40 printf("mx %d nx %d\n", mx, nx); 41 #endif 42 } 43 44 void build(int l, int r, int rt){ 45 lt[rt] = mk[rt] = 0; 46 if (l == r) return ; 47 48 int m = (l + r) >> 1; 49 50 build(lson); 51 build(rson); 52 } 53 54 void down(int rt){ 55 if (lt[rt]){ 56 lt[rt << 1] += lt[rt]; 57 lt[rt << 1 | 1] += lt[rt]; 58 mk[rt << 1] += lt[rt]; 59 mk[rt << 1 | 1] += lt[rt]; 60 lt[rt] = 0; 61 } 62 } 63 64 void add(int L, int R, int l, int r, int rt){ 65 if (L <= x[l] && x[r] <= R){ 66 lt[rt]++; 67 mk[rt]++; 68 return ; 69 } 70 down(rt); 71 72 int m = (l + r) >> 1; 73 74 if (L <= x[m]) add(L, R, lson); 75 if (x[m + 1] <= R) add(L, R, rson); 76 } 77 78 int query(int k, int l, int r, int rt){ 79 if (l == r){ 80 return mk[rt]; 81 } 82 down(rt); 83 84 int m = (l + r) >> 1; 85 86 if (k <= x[m]) return query(k, lson); 87 else return query(k, rson); 88 } 89 90 void deal(int k){ 91 load(); 92 build(root); 93 #if debug 94 puts("built"); 95 #endif 96 for (int i = 0; i < N; i++){ 97 add(s[i], t[i], root); 98 #if debug 99 printf("%d add\n", i);100 #endif101 }102 printf("Case #%d:\n", k);103 for (int i = 0; i < M; i++){104 printf("%d\n", query(tt[i], root));105 #if debug106 printf("%d query\n", i);107 #endif108 }109 }110 111 int main(){112 int T;113 114 scanf("%d", &T);115 for (int i = 1; i <= T; i++){116 deal(i);117 }118 return 0;119 }
（2012-07-31 20:35 更新）
我挺喜欢1001这题数论，那时没想到原理，然后现在明白了以后，顺便学了一下快速幂取模的，AC的很爽~虽然中间搞反了a和b的位置，搞到wa了几次.....简单说一下我的理解，如果某数x（十进制）在a进制下是有限小数，那么如果想x在b进制下也必定是有限小数，那么必须要存在一个整数k使得b^k%a==0。具体原因需要将x用a进制和b进制的多项式表示，这样才能明白！其实也就是要找到本质的原因.....
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 #define lson l, m, rt << 1 8 #define rson m + 1, r, rt << 1 | 1 9 #define root 0, mx - 1, 110 11 using namespace std;12 13 #define debug 014 15 typedef __int64 ll;16 int min2(int _a, int _b){ return _a < _b ? _a : _b;}17 int max2(int _a, int _b){ return _a > _b ? _a : _b;}18 19 ll mm(ll x, ll y, ll mo){20 ll t;21 22 x %= mo;23 for (t = 0; y; x = (x << 1) % mo, y >>= 1){24 if (y & 1) t = (t + x) % mo;25 }26 return t;27 }28 29 ll me(ll num, ll t, ll mo){30 ll ret = 1, temp = num % mo;31 32 for (; t; t >>= 1, temp = mm(temp, temp, mo)){33 if (t & 1) ret = mm(ret, temp, mo);34 }35 return ret;36 }37 38 int main(){39 int n;40 ll a, b;41 42 scanf("%d", &n);43 for (int i = 1; i <= n; i++){44 scanf("%I64d%I64d", &a, &b);45 printf("Case #%d: ", i);46 if (me(b, 100, a) == 0){47 printf("YES\n");48 }49 else{50 printf("NO\n");51 }52 }53 54 return 0;55 }
其余会不断更新上来！
——written by Lyon