注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

CodeChef October Challenge 2014  

2014-10-08 08:59:15|  分类: CodeChef |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Chef and Ground (CHEFGR)
给一个n个整数组成的序列,问是否能进行恰好m次操作,每次操作给某一个数+1,使得最后序列的所有数相等。
Solution
用除法算出来最后的数是什么,然后看看是否超过了原来的最大值。
  1. int a[108];
  2. int main(){
  3. int T; scanf("%d", &T);
  4. while(T--){
  5. int n, m; scanf("%d%d", &n, &m);
  6. int max = 0, sum = 0;
  7. f(i, 1, n){
  8. scanf("%d", a + i);
  9. if(a[i] > max) max = a[i];
  10. sum += a[i];
  11. }
  12. int av = sum + m;
  13. if(av % n) printf("No\n");
  14. else if(av / n < max) printf("No\n");
  15. else printf("Yes\n");
  16. }
  17. return 0;
  18. }
DevuLand, Dinosaurs and Laddus (PRLADDU)
有一排n个村庄,相邻的距离为1,每个里面要么全是好人要么全是坏人,保证好人和坏人个数的总和相等。现在每个好人要给一个坏人送东西(=_=||),要求一一对应,问所有好人走的最短的总路程。
Solution
显然是从左到右,第i个好人给第i个坏人送东西,是最优的。
  1. //pos, val
  2. std::queue<PII> A, B; 
  3. int main(){
  4. int T; scanf("%d", &T);
  5. while(T--){
  6. int n; scanf("%d", &n);
  7. f(i, 1, n){
  8. int a; scanf("%d", &a);
  9. if(a > 0) A.push(PII(i, a));
  10. else if(a < 0) B.push(PII(i, -a));
  11. }
  12. LL ans = 0;
  13. while(A.size() && B.size()){
  14. PII &a = A.front();
  15. PII &b = B.front();
  16. int c = std::min(a.second, b.second);
  17. ans += (LL) std::abs(a.first - b.first) * (LL) c;
  18. if(!(a.second -= c)) A.pop();
  19. if(!(b.second -= c)) B.pop();
  20. }
  21. printf("%lld\n", ans);
  22. }
  23. return 0;
  24. }
Magical Girl and Colored Liquid Potions (PRPOTION)
给3个数,有m次机会,每次可以给一个数除以2(向下取整),问最后最大的数的最小值。
(原来的题面是,还要把其他的数+1,然后发现标程挂啦233,所以改题了)
Solution
每次取最大的数除以2就行了。
  1. int main(){
  2. int T; scanf("%d", &T);
  3. while(T--){
  4. int nr, ng, nb, M; scanf("%d%d%d%d", &nr, &ng, &nb, &M);
  5. int A[3]; memset(A, 0, sizeof(A));
  6. while(nr--){
  7. int a; scanf("%d", &a);
  8. if(a > A[0]) A[0] = a;
  9. }
  10. while(ng--){
  11. int a; scanf("%d", &a);
  12. if(a > A[1]) A[1] = a;
  13. }
  14. while(nb--){
  15. int a; scanf("%d", &a);
  16. if(a > A[2]) A[2] = a;
  17. }
  18. std::sort(A, A + 3);
  19. while(M--){
  20. A[2] >>= 1; std::sort(A, A + 3);
  21. }
  22. printf("%d\n", A[2]);
  23. }
  24. return 0;
  25. }
Remy paints the fence (FATCHEF)
一个墙水平分成了n块,有m个油漆桶,每个桶放在某个位置,装了某个颜色。现在可以选任何一个桶开始,按照任意顺序走动,每次来到一个地点,如果有油漆桶,就把刷子涂上这个颜色。然后把这块墙刷成这种颜色。全部刷上色后,问合法的颜色序列的个数mod 1000000009。
n≤100000。
Solution
把所有桶排序,考虑相邻的两个桶,如果颜色相同那么中间部分的方案数为1,否则方案数为它们的距离。把所有的方案数乘起来就是答案了。
  1. PII a[100086];
  2. int main(){
  3. int T; scanf("%d", &T);
  4. while(T--){
  5. int n; scanf("%*d%d", &n);
  6. LL ans = 1;
  7. g(i, 0, n){
  8. char buf[4]; scanf("%s%d", buf, &a[i].first);
  9. a[i].second = buf[0];
  10. }
  11. std::sort(a, a + n);
  12. g(i, 1, n) if(a[i].second != a[i - 1].second) ans = ans * (LL) (a[i].first - a[i - 1].first) % 1000000009LL;
  13. printf("%d\n", (int) ans);
  14. }
  15. return 0;
  16. }
Chef and Square (CHEFSQUA)
给平面上n个点,问加几个点能使其中的4个组成正方形。
n≤2000。
Solution
如果n≤2那么直接输出4-n。
否则,枚举正方形的对角线,看另外两个点在不在里面。O(n^2 log n)。
  1. int n;
  2. PII a[2086];
  3. inline int need(PII x){
  4. return *std::lower_bound(a, a + n, x) != x;
  5. }
  6. int main(){
  7. scanf("%d", &n);
  8. memset(a, 0x7f, sizeof(a));
  9. g(i, 0, n){
  10. scanf("%d%d", &a[i].first, &a[i].second);
  11. a[i].first <<= 1; a[i].second <<= 1;
  12. }
  13. std::sort(a, a + n);
  14. n = std::unique(a, a + n) - a;
  15. if(n <= 2) printf("%d\n", 4 - n);
  16. else{
  17. int bans = 4;
  18. g(i, 0, n) g(j, 0, i){
  19. int cans = need(PII((a[i].first + a[j].first + a[i].second - a[j].second) >> 1, (a[i].second + a[j].second - a[i].first + a[j].first) >> 1)) + need(PII((a[i].first + a[j].first - a[i].second + a[j].second) >> 1, (a[i].second + a[j].second + a[i].first - a[j].first) >> 1));
  20. if(cans < bans) bans = cans;
  21. }
  22. printf("%d\n", bans);
  23. }
  24. return 0;
  25. }
Chef and Painting (CHEFPNT)
n×m的格子,有一些是黑的,其余是白的。每次可以选一个白格子,然后选一个方向(上下,或,左右),按照这个方向把沿途白色格子全染成红色,直到遇到红色或黑色或边界。要用尽可能少的步数把所有白格染成红色。步数越少得分越高。
n,m≤1000。数据随机。
Solution
我只会骗分……for(每个格子) if(是白的) 染色(这个格子,左右);
  1. int n, m, k;
  2. int map[108][108];
  3. std::vector<PII> ans;
  4.  
  5. int main(){
  6. read(n, m, k);
  7. FILL(map, 0);
  8. f(i, 0, n + 1) map[i][0] = map[i][m + 1] = 1;
  9. f(j, 0, m + 1) map[0][j] = map[n + 1][j] = 1;
  10. while(k--){
  11. int x, y; read(x, y); map[x][y] = 1;
  12. }
  13. f(i, 1, n) f(j, 1, m) if(!map[i][j]){
  14. ans.push_back(PII(i, j));
  15. for(int k = j; !map[i][k]; ++k) map[i][k] = 1;
  16. }
  17. writeln(ans.size());
  18. foreach(it, ans) writesln(it->first, it->second, 0);
  19. return 0;
  20. }
Sereja and two strings (SEATSR)
给两个字符串s,w,每次可以花费a的代价删掉s的一位,或者向s插入一位,或者花费b的代价把s的某个字符换成另一个字符。现在想把s变成w,如果最小代价不超过k,输出之,否则输出-1。
|s|,|w|≤100000,0≤a,b,k≤100。
Solution
如果a=0那么直接输出0。如果b=0,输出a*abs(|s|-|w|)。现在考虑a,b>0的情况。
先考虑平方级的dp。设dp[i][j]表示,把s的前i位变成w的前j位的最小代价,那么:
dp[i][j]=min(dp[i-1][j]+a,dp[i][j-1]+a,dp[i-1][j-1]+b)。
容易发现,如果abs(i-j)>100,那么dp[i][j]必然大于100,那么就没有意义了。所以只计算abs(i-j)≤100的状态就行了。
  1. int a, b, k;
  2. char s[100086], t[100086], sl, tl;
  3. int _dp[100086][208];
  4. #define dp(i, j) _dp[(i)][(i) - (j) + 104]
  5. int main(){
  6. int T; scanf("%d", &T);
  7. while(T--){
  8. scanf("%s%s%d%d%d", s + 1, t + 1, &a, &b, &k);
  9. int ans = 1000000086;
  10. int sl = strlen(s + 1), tl = strlen(t + 1);
  11. memset(_dp, 0x1f, sizeof(_dp));
  12. if(a == 0) ans = 0;
  13. else if(b == 0) ans = std::abs(sl - tl) * a;
  14. else if(std::abs(sl - tl) <= 100){
  15. f(i, 0, sl) f(j, i - 100, i + 100){
  16. if(j < 0 || j > tl) continue;
  17. if(i == 0 && j == 0) dp(i, j) = 0;
  18. else if(i == 0) dp(i, j) = dp(i, j - 1) + a;
  19. else if(j == 0) dp(i, j) = dp(i - 1, j) + a;
  20. else dp(i, j) = std::min(std::min(dp(i - 1, j) + a, dp(i, j - 1) + a), dp(i - 1, j - 1) + (s[i] == t[j] ? 0 : b));
  21. }
  22. ans = dp(sl, tl);
  23. }
  24. if(ans > k) printf("-1\n"); else printf("%d\n", ans);
  25. }
  26. return 0;
  27. }
Stringology is Magic (QSTRING)
给一个长度为n的字符串T,对于一个子串T[l..r],定义k1为这个子串在T的所有不相同子串中的字典序的排名,k2为这个子串在T的所有这种相同子串的位置的排名。
m次操作,每次给l r求k1 k2,或给k1 k2求l r。
n,m≤1000000。时间限制4秒。
Solution
先考虑k1怎么求。
先建出后缀数组,然后对于每一项,新的不相同子串的个数就是length-height,而且是有序的。
那么已知k1求一个合法的l r就可以做了。
对于l r,如果发现l对应的height≥r-l+1,就要一直向前找,找到这个串第一次出现的位置,倍增一下就好了。
然后看k2。
还是倍增,倍增完了在这个倍增找出的范围内求区间第k小数,或是找一个数的排名,就行了。可以可持久化线段树前缀和搞。
(后缀数组写得很丑……我会说我是第一次写嘛……)
  1. struct PIII{
  2. int first, second, third;
  3. inline PIII(){}
  4. inline PIII(int a, int b, int c) :first(a), second(b), third(c){}
  5. };
  6. inline bool operator !=(const PIII x, const PIII y){
  7. return x.first != y.first || x.second != y.second;
  8. }
  9.  
  10. int n, rank[1000086], t[1000086], sa[1000086], height[1000086], st[20][1000086], tt[20][1000086];
  11. LL sh[1000086];
  12. PIII a[1000086], b[1000086];
  13. char s[1000086];
  14.  
  15. struct node;
  16. struct node{
  17. node *ls, *rs; int sum;
  18. } pool[30000086], *cp = pool;
  19. node *root[1000086];
  20.  
  21. inline node *newnode(node *ls, node *rs){
  22. cp->ls = ls; cp->rs = rs; cp->sum = ls->sum + rs->sum; return cp++;
  23. }
  24. inline node *newnode(int x){
  25. cp->ls = cp->rs = NULL; cp->sum = x; return cp++;
  26. }
  27. inline node *build(int x){
  28. if(x > 1) return newnode(build((x + 1) >> 1), build(x >> 1)); else return newnode(0);
  29. }
  30. inline node *inc(node *root, int x, int l = 1, int r = n){
  31. if(l == r) return newnode(root->sum + 1);
  32. else{
  33. int m = (l + r) >> 1;
  34. if(x <= m) return newnode(inc(root->ls, x, l, m), root->rs);
  35. else return newnode(root->ls, inc(root->rs, x, m + 1, r));
  36. }
  37. }
  38. inline int sum(node *po, node *ne, int ll, int rr, int l = 1, int r = n){
  39. if(l == ll && r == rr) return po->sum - ne->sum;
  40. else{
  41. int m = (l + r) >> 1;
  42. if(rr <= m) return sum(po->ls, ne->ls, ll, rr, l, m);
  43. else if(ll > m) return sum(po->rs, ne->rs, ll, rr, m + 1, r);
  44. else return sum(po->ls, ne->ls, ll, m, l, m) + sum(po->rs, ne->rs, m + 1, rr, m + 1, r);
  45. }
  46. }
  47. inline int kth(node *po, node *ne, int k, int l = 1, int r = n){
  48. while(l < r){
  49. int ck = po->ls->sum - ne->ls->sum, m = (l + r) >> 1;
  50. if(k <= ck){
  51. po = po->ls; ne = ne->ls; r = m;
  52. }else{
  53. po = po->rs; ne = ne->rs; k -= ck; l = m + 1;
  54. }
  55. }
  56. return l;
  57. }
  58.  
  59.  
  60. int main(){
  61. scanf("%s", s + 1); n = strlen(s + 1);
  62. f(i, 1, n) rank[i] = s[i] - 'a' + 1;
  63. f(j, 1, 20){
  64. memset(t, 0, sizeof(t));
  65. // f(i, 1, n) printf("rank %d = %d\n", i, rank[i]);
  66. f(i, 1, n){
  67. int tmp = i + (1 << (j - 1));
  68. if(tmp <= n){
  69. a[i] = PIII(rank[i], rank[tmp], i); ++t[rank[tmp]];
  70. }else{
  71. a[i] = PIII(rank[i], 0, i); ++t[0];
  72. }
  73. }
  74. // f(i, 1, n) printf("a %d = %d %d\n", i, a[i].first, a[i].second);
  75. f(i, 1, 1000000) t[i] += t[i - 1];
  76. h(i, n, 1) b[t[a[i].second]--] = a[i];
  77. // f(i, 1, n) printf("b %d = %d %d\n", i, b[i].first, b[i].second);
  78. memset(t, 0, sizeof(t));
  79. f(i, 1, n) ++t[b[i].first];
  80. f(i, 1, 1000000) t[i] += t[i - 1];
  81. h(i, n, 1) a[t[b[i].first]--] = b[i];
  82. rank[a[1].third] = 1;
  83. // f(i, 1, n) printf("a %d = %d %d\n", i, a[i].first, a[i].second);
  84. f(i, 2, n) rank[a[i].third] = rank[a[i - 1].third] + (int) (a[i] != a[i - 1]);
  85. }
  86. f(i, 1, n) sa[rank[i]] = i;
  87. int k = 0;
  88. f(i, 1, n){
  89. if(k) --k;
  90. if(rank[i]){
  91. int j = sa[rank[i] - 1];
  92. while(s[i + k] == s[j + k]) ++k;
  93. }
  94. height[rank[i]] = k;
  95. }
  96. memset(st, 0, sizeof(st));
  97. f(i, 1, n) st[0][i] = height[i];
  98. f(j, 1, 19) f(i, (1 << (j - 1)) + 1, n) st[j][i] = std::min(st[j - 1][i], st[j - 1][i - (1 << (j - 1))]);
  99. memset(tt, 0, sizeof(tt));
  100. f(i, 1, n) tt[0][i] = height[i];
  101. f(j, 1, 19) h(i, n - (1 << (j - 1)), 1) tt[j][i] = std::min(tt[j - 1][i], tt[j - 1][i + (1 << (j - 1))]);
  102. sh[1] = 1;
  103. f(i, 2, n) sh[i] = sh[i - 1] + (LL) (n - sa[i - 1] + 1 - height[i - 1]);
  104. root[0] = build(n);
  105. f(i, 1, n) root[i] = inc(root[i - 1], sa[i]);
  106. // f(i, 1, n) printf("rank %d = %d\n", i, rank[i]);
  107. // f(i, 1, n) printf("height %d = %d\n", i, height[i]);
  108. // f(i, 1, n) printf("sh %d = %I64d\n", i, sh[i]);
  109. int m; scanf("%d", &m);
  110. while(m--){
  111. char buf[8]; scanf("%s", buf);
  112. if(buf[0] == 'S'){
  113. LL x; int y; scanf("%lld%d", &x, &y);
  114. int ind = std::upper_bound(sh + 1, sh + n + 1, x) - sh - 1;
  115. int len = (int) (x - sh[ind]) + height[ind] + 1;
  116. // printf("ind %d len %d\n", ind, len);
  117. int top = ind;
  118. h(i, 19, 0) if(st[i][top] >= len) top -= (1 << i);
  119. int bot = ind + 1;
  120. h(i, 19, 0) if(tt[i][bot] >= len) bot += (1 << i);
  121. --bot;
  122. // printf("top %d bot %d\n", top, bot);
  123. int ans = kth(root[bot], root[top - 1], y);
  124. printf("%d %d\n", ans, ans + len - 1);
  125. }else{
  126. int x, y; scanf("%d%d", &x, &y);
  127. int ls = rank[x], len = y - x + 1;
  128. int top = ls;
  129. h(i, 19, 0) if(st[i][top] >= len) top -= (1 << i);
  130. int bot = ls + 1;
  131. h(i, 19, 0) if(tt[i][bot] >= len) bot += (1 << i);
  132. --bot;
  133. // printf("top %d bot %d\n", top, bot);
  134. LL ans = sh[top] + (LL) (len - height[top] - 1);
  135. printf("%lld %d\n", ans, sum(root[bot], root[top - 1], 1, x));
  136. }
  137. }
  138. return 0;
  139. }
Children Trips (TRIPS)
给n个点的树,边权是1或2。有m个询问,每次给出s f w,表示一个体力为p的人要从s走到f。
体力值的意思是,这个人每天最多能走w的距离,而且每天必须在一个点(不能再边上)停下。
问每个人要走的天数。
n,m≤100000。时间限制8秒。
Solution
10万8秒,一看就是3log左右的节奏……于是我就想了一个n sqrt n log n的算法……
首先可以通过倍增求出:p[j][i],i的2^j父亲;pw[j][i],i到2^j父亲的边权和。
然后就可以设计一个函数:getnext(i, w),体力值为w的人从i向根走一天,能到达的最远点。这个函数可以通过pw[][]计算,时间复杂度O(logn)。
对于每个询问,如果它的p超过了sqrt n,那么就直接用getnext()模拟,时间复杂度O(sqrt n log n)。
下面处理p≤sqrt n的情况。
令next[k][j][i]表示p=k时,从i向根走2^j天能到达的最远点,那么next[k][0][i]可以用getnext()算出,next[k][j][i]可以倍增算出,预处理复杂度O(n sqrt n log n)。
对于每次询问,直接在next[][][]里面找就行了,时间复杂度O(log n)。
这样总的时间复杂度就是O((n+m) sqrt n log n)。
然后就发现了一个问题,空间也是O(n sqrt n log n)的……1.5G内存貌似开不下。如果sqrt取小一点的话(只能取到225)时间就跪了……
然后发现,next[][][]里面的数最大是10万,开个int是大材小用,但unsigned short又不够用,于是就手写了个int24(=_=||...),然后就卡过了……
(估计出题人气疯了……)
(下面的代码里面内存算错了,所以写的是int20,实际上是int24……)
  1. struct int20{
  2. unsigned char top; unsigned short bot;
  3. inline int20(){}
  4. inline int20(unsigned int x){
  5. top = x >> 16u; bot = x & 65535u;
  6. }
  7. inline unsigned int toInt(){
  8. return (((unsigned int) top) << 16) ^ ((unsigned int) bot);
  9. }
  10. };
  11.  
  12. #define SQRT 300
  13. int p[17][100001], pw[17][100001], dep[100001], sw[100001];
  14. int20 next[SQRT - 1][17][100001];
  15. int head[100001], nx[200001], t[200001], w[200001];
  16.  
  17. inline void dfs(int x, int fa, int fw){
  18. p[0][x] = fa; pw[0][x] = fw; dep[x] = dep[fa] + 1; sw[x] = sw[fa] + fw;
  19. for(int c = head[x]; c; c = nx[c]) if(t[c] ^ fa) dfs(t[c], x, w[c]);
  20. }
  21. inline int lca(int x, int y){
  22. if(dep[x] < dep[y]) std::swap(x, y);
  23. int dx = dep[x] - dep[y];
  24. h(i, 16, 0) if(dx & (1 << i)) x = p[i][x];
  25. h(i, 16, 0) if(p[i][x] ^ p[i][y]){
  26. x = p[i][x]; y = p[i][y];
  27. }
  28. if(x == y) return x; else return p[0][x];
  29. }
  30. inline int getnext(int xx, int ww){
  31. // printf("getnext %d %d = ", x, w);
  32. register int x = xx; register int w = ww;
  33. h2(i, 16, -1){
  34. register int tmp = pw[i][x];
  35. if(tmp <= w){
  36. w -= tmp; x = p[i][x];
  37. }
  38. }
  39. // printf("%d\n", x);
  40. return x;
  41. }
  42. inline void getans(int ss, int tt, int w, int &div, int &mod){
  43. register int s = ss; register int t = tt;
  44. div = 0;
  45. if(w <= SQRT) h2(i, 16, -1){
  46. int tmp = next[w - 2][i][s].toInt();
  47. // printf("i %d tmp %d\n", i, tmp);
  48. if(dep[tmp] > dep[t]){
  49. div += (1 << i); s = tmp;
  50. }
  51. }else for(;;){
  52. register int tmp = getnext(s, w);
  53. if(dep[tmp] > dep[t]){
  54. ++div; s = tmp;
  55. }else break;
  56. }
  57. mod = sw[s] - sw[t];
  58. if(mod == w){
  59. mod = 0; ++div;
  60. }
  61. }
  62.  
  63. int main(){
  64. // printf("%d\n", (int) sizeof(int20));
  65. int n; scanf("%d", &n);
  66. memset(head, 0, sizeof(head));
  67. f(i, 2, n){
  68. int ss, tt, ww; scanf("%d%d%d", &ss, &tt, &ww);
  69. t[i] = tt; w[i] = ww; nx[i] = head[ss]; head[ss] = i;
  70. t[i + n] = ss; w[i + n] = ww; nx[i + n] = head[tt]; head[tt] = i + n;
  71. }
  72. dep[0] = sw[0] = 0;
  73. dfs(1, 0, 0);
  74. f(j, 1, 16) f(i, 0, n){
  75. p[j][i] = p[j - 1][p[j - 1][i]];
  76. pw[j][i] = pw[j - 1][i] + pw[j - 1][p[j - 1][i]];
  77. }
  78. f(k, 2, SQRT){
  79. {
  80. register int20 *tmp = next[k - 2][0] + n;
  81. h2(i, n, -1) *(tmp--) = getnext(i, k);
  82. }
  83. f(j, 1, 16){
  84. register int20 *nextkj = next[k - 2][j];
  85. register int20 *nextkj1 = next[k - 2][j - 1];
  86. register int20 *nextkj2 = next[k - 2][j - 1];
  87. register int TT = n + 1;
  88. while(TT--) *(nextkj++) = nextkj1[(nextkj2++)->toInt()];
  89. }
  90. }
  91. int m; scanf("%d", &m);
  92. while(m--){
  93. int s, t, w; scanf("%d%d%d", &s, &t, &w);
  94. int u = lca(s, t), d1, m1, d2, m2;
  95. getans(s, u, w, d1, m1); getans(t, u, w, d2, m2);
  96. printf("%d\n", d1 + d2 + (m1 + m2 + w - 1) / w);
  97. }
  98. // printf("%d\n", (int) clock());
  99. return 0;
  100. }
Union on Tree (BTREE)
前9题都是一眼题,这题不是……
想了一天没idea,弃疗……(集训队作业还没做呢QAQ)
无限orz CLJ……
  评论这张
 
阅读(218)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018