<![CDATA[KDTalker]]> http://x2studio.net/u/index.php zh-cn http://x2studio.net/u/read.php?24 <![CDATA[圣诞赛P1010[第m个排列],二分查找]]> Jucady <admin@yourname.com> Sat, 05 Dec 2009 18:33:16 +0000 http://x2studio.net/u/read.php?24 http://acm.zjut.edu.cn/ShowContestProblem.aspx?ShowID=1010&MID=361

首先祝贺老吕获得第六的好成绩，然后他推荐我做下这个题目。

他是模拟STL函数next_permutation(num,num+n)实现的代码。【点击进入】

于是我也去做了下。（我不能提交，代码正确性还没证明）

对于这种找第几个，而且是有序的队列的题目，我首先蹦出的思想就是二分。仔细想想，这个题目二分可行，而且是这样分的：我们算在mid这个数字时，比它小的有几个。算这个有几个的时候就是用排列组合的知识了。

在算比它小有几个的时候，从高位往低位用i枚举，每位有这么几种情况：

折叠C/C++ 代码复制内容到剪贴板
  1. for(i = 1; i <= n; i++)   
  2. {   
  3.     if(a[i] > 0 && a[i] <= n)   
  4.     {   
  5.         ans += docan(a[i], b) * nt(n - i);   
  6.         if(b[a[i]] == 1) return (ans == m) ? (ans + 1) : ans;   
  7.         b[a[i]] = 1;   
  8.     }   
  9.     else  
  10.     if(a[i] == 0) return (ans == m) ? (ans + 1) : ans;   
  11.     else  
  12.     if(a[i] > n)   
  13.     {   
  14.         ans += docan(n + 1, b) * nt(n - i);   
  15.         return (ans == m) ? (ans + 1) : ans;   
  16.     }   
  17. }  
  •  

 

①当这位的数a[i]在1跟n之间时，也就是说，这个数字是组成排列数所需的数字时，比它小的数有这位数在(1~a[i]-1)能选的数字乘以下一位的阶乘。比如7250000的第三位是5，那么这位在(1~4)能取的是1、3、4三个，那么比它小的有3*4!。并且如果这位数在之前出现过（我们每枚举一位，就把b[a[i]]记为1以表示这个数已经出现过了），那么可以跳出枚举返回答案了。

②当这位数等于0的时候，就直接返回答案了。因为再枚举下去都没意义了。

③当这位数大于n时，就是说它能取的范围是(1~n)之间能取的数，也就是说比它小的有(1~n)之间能取的数乘以下一位的阶乘。然后就可以跳出枚举返回答案了。

在以上几种情况返回的时候我们要判断下ans是不是已经等于m了，如果等于m，我们就要把ans值加1。举个例子，因为这个ans里包括了最终的答案的那个数。就这样返回的话，输出的就是现在这个数而不是最终的答案了。举个例子，如果最终的答案是34152，那么比34157小的数的个数刚好就是m。

④最后还有一种情况，就是当位枚举完了还没返回值，也就是说这个数的各位数全部由无重复的1~n中的数组成，那么别忘了把这个数的本身加回去再返回。

最后贴上代码

折叠C/C++ 代码复制内容到剪贴板
  1. #include<stdio.h>   
  2.   
  3. int nt(int a)   
  4. {   
  5.     int ans = 1, i;   
  6.     for(i = 2; i <= a; i++) ans *= i;   
  7.     return ans;   
  8. }   
  9.   
  10. int docan(int a, int *b)   
  11. {   
  12.     int i, ans = 0;   
  13.     for(i = a - 1; i >= 1; i--)   
  14.         if(b[i] == 0) ans++;   
  15.     return ans;   
  16. }   
  17.   
  18. int doans(long mid, int n, int m)   
  19. {   
  20.     int i, a[10], b[10], ans = 0;   
  21.     for(i = n; i >= 1; i--)   
  22.     {   
  23.         a[i] = mid % 10;   
  24.         mid /= 10;   
  25.         b[i] = 0;   
  26.     }   
  27.        
  28.     for(i = 1; i <= n; i++)   
  29.     {   
  30.         if(a[i] > 0 && a[i] <= n)   
  31.         {   
  32.             ans += docan(a[i], b) * nt(n - i);   
  33.             if(b[a[i]] == 1) return (ans == m) ? (ans + 1) : ans;   
  34.             b[a[i]] = 1;   
  35.         }   
  36.         else  
  37.         if(a[i] == 0) return (ans == m) ? (ans + 1) : ans;   
  38.         else  
  39.         if(a[i] > n)   
  40.         {   
  41.             ans += docan(n + 1, b) * nt(n - i);   
  42.             return (ans == m) ? (ans + 1) : ans;   
  43.         }   
  44.     }   
  45.     return (ans + 1);   
  46. }   
  47.   
  48. int domid(long l, long r, int m, int n)   
  49. {   
  50.     int mid, tmp;   
  51.     mid = (l + r) / 2;   
  52.     while(r - l > 1)   
  53.     {   
  54.         tmp = doans(mid, n, m);   
  55.         if(tmp > m) r = mid;   
  56.         else  
  57.         if(tmp < m) l = mid;   
  58.         else return mid;   
  59.         mid = (l + r) / 2;   
  60.     }   
  61.     if(doans(l, n, m) == m) return l;   
  62.     else return r;   
  63. }   
  64.   
  65. int main()   
  66. {   
  67.     long i, j, k, n, m, l, r, mid;   
  68.        
  69.     for(i = 1; i <= 2; i = 1)   
  70.     {   
  71.         scanf("%d%d", &n, &m);   
  72.         if(n == 0 && m == 0) break;   
  73.         l = 0; r = 0;   
  74.         for(j = n, k = 1; j > 0; j--, k++)   
  75.         {   
  76.             r = (r * 10) + j;   
  77.             l = (l * 10) + k;   
  78.         }   
  79.         r++;   
  80.         l--;   
  81.            
  82.         printf("%d\n", domid(l, r, m, n));   
  83.     }   
  84.        
  85.     system("pause");   
  86.     return 0;   
  87. }   

 

]]> http://x2studio.net/u/read.php?23 <![CDATA[在空间里翻到算法的好东西了]]> Jucady <admin@yourname.com> Wed, 02 Dec 2009 04:44:28 +0000 http://x2studio.net/u/read.php?23 今天在ACM群里看到一个人发了一段树状数组的代码。我就瞅着Lowbit眼熟，好一段时间才想起来这是树状数组。

好久没玩算法了，都忘了！兄弟们都忘了！

忘了就忘了吧，我记得以前学树状数组这个东西是在一个PPT里看的，貌似还在空间里，于是就去找了，最后还发现了这么个宝库。嗯，应该可以把以前丢掉的东西重新都捡回来了吧。

颓废了颓废了，该改改了。要好好复习算法。嗯，今天高数还认真，都坐第一排去了。

顺便学学Matrix67大牛，做个适合自己的Cheat Sheet，好好背，好好学。

]]> http://x2studio.net/u/read.php?22 <![CDATA[期中高数挂了]]> Jucady <admin@yourname.com> Tue, 01 Dec 2009 07:30:05 +0000 http://x2studio.net/u/read.php?22 看着悲惨的分数，我纠结了。

想想前段时间太不认真了，整天忙工作，在程峰的“谆谆教导”的数学课上昏昏欲睡，导致了现在的结果。

事实证明，大学大学，还是要学的。所以接下来该有所行动了。嗯，12月19，也就是我生日那天，要考四级了，我现在要做充分准备。我觉得把电脑带到学校就是个错误，不过既带之则安之，不如好好利用起来。荒废太久了。

今天开始要重新阅读大牛们的博客，然后看算法、做题目。海报什么之类的尽量少做，少而精才是王道的。

话说磊哥让我立下军令状让我期末高数考90分以上，真要把书啃上几遍了。至少像我现在这样上课没很认真，复习也没很认真是不行的。

还有每节课都要认真听了，包括那什么让我有点无语的C语言、计算机科学与技术方法论啊什么的。

话说那方法论还挺高级的，树啊、图论啊什么的都有，可惜都是涉及不深。说实话我还是对算法比较感兴趣的，不过为了我的学业，还是都要学的。

幸好班主任还有英语老师对我的印象很不错。我想只要把成绩提上来一切都会好起来的。

也罢，学校拉风也拉够了，要静下心来了。

嗯，跟室友们说好，好好努力，营造一个OK的学习环境。

]]> http://x2studio.net/u/read.php?21 <![CDATA[P1307[连接电脑2]，简单搜索]]> Jucady <admin@yourname.com> Sun, 15 Nov 2009 04:36:48 +0000 http://x2studio.net/u/read.php?21 http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1307

数据范围不大，所以搜索足矣解决。开个n*n的数组来存每一台电脑各与那几台电脑连通，然后用深度优先搜索，把与此电脑连通的电脑都标记为vis。最后计算有几个独立的块，网线就是块数-1。

接下来是代码

折叠C/C++ 代码复制内容到剪贴板
  1. /*  
  2. ZJUT1307[连接电脑2]  
  3. Code by Jucady  
  4. */  
  5. #include<stdio.h>   
  6. #include<string.h>   
  7.   
  8. int lk[201][201], vis[201];   
  9.   
  10. void sch(int i)   
  11. {   
  12.     int j;   
  13.     vis[i] = 1;   
  14.     for(j = 1; j <= lk[i][0]; j++)   
  15.         if(vis[lk[i][j]] == 0) sch(lk[i][j]);   
  16. }   
  17.   
  18. int main()   
  19. {   
  20.     int n, m, i, tmpI, tmpII, l;   
  21.     while(scanf("%d%d", &n, &m))   
  22.     {   
  23.         if(n == 0 && m == 0) break;   
  24.            
  25.         l = 0;   
  26.         memset(lk, 0, sizeof(lk));   
  27.         memset(vis, 0, sizeof(vis));   
  28.         for(i = 1; i <= m; i++)   
  29.         {   
  30.             scanf("%d%d", &tmpI, &tmpII);   
  31.                
  32.             lk[tmpI][0]++;   
  33.             lk[tmpI][lk[tmpI][0]] = tmpII;   
  34.             lk[tmpII][0]++;   
  35.             lk[tmpII][lk[tmpII][0]] = tmpI;   
  36.         }   
  37.            
  38.         for(i = 1; i <= n; i++)   
  39.             if(vis[i] == 0)   
  40.             {   
  41.                 l++;   
  42.                 sch(i);   
  43.             }   
  44.                
  45.         printf("%d\n", l - 1);   
  46.     }   
  47.        
  48.     return 0;   
  49. }  

 

]]> http://x2studio.net/u/read.php?20 <![CDATA[在OIBH淘到的一段牛X的签名]]> Jucady <admin@yourname.com> Sun, 15 Nov 2009 03:10:20 +0000 http://x2studio.net/u/read.php?20 jki14

这位用户的签名

I am the bone of codemachine.
吾身为代码机器
Code is my body, and algorithm is my blood.
字符成身，算法为血
I have created over a thousand program.
铸程过千，身经百战
Unknown to fail, Nor known to win.
未有败绩，也未有成功
Have withcode world to create many codes.
常独自一人沉醉于编程世界
Yet, those hands will never hold anything.
因此，一无所有，一无所获
So as I pray, unlimited code works.
故我所求，无限代码制

]]> http://x2studio.net/u/read.php?19 <![CDATA[P1410[Maximum Energy],四个状态的动规]]> Jucady <admin@yourname.com> Thu, 12 Nov 2009 06:40:45 +0000 http://x2studio.net/u/read.php?19 http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1410

入手这个题目脑袋里第一个跳过的反应就是动规。并且我们将它定义为四个状态：

    ①取第i个，且第i个为当前取了的第奇数个的最大值。

    ②取第i个，且第i个为当前取了的第偶数个的最大值。

    ③不取第i个，且之前取了奇数个的最大值。

    ④不取第i个，且之前取了偶数个的最大值。

然后每种状态就在之前的相关状态中找max。比如第i个的第一种情况，就应该在第i-1个的2、4中找max然后状态转移。

这个转移方程是这样的。为了省空间，我们可以读一个做一个，不用数组存储每个苹果的v，而是直接读tmp做tmp。

接下来就是f了。150000的数据貌似我会开爆掉。所以能省则省，开个f[2][4]就好了，拿来滚动，反正最后只要用到最后一个苹果的四种状态，前面的状态都可以删除掉。所以我们做两次就可以覆盖一次了。

接下来贴上代码：

折叠C/C++ 代码复制内容到剪贴板
  1. /*  
  2. ZJUT1410[Maximum Energy]  
  3. Code by Jucady  
  4. */  
  5. #include<iostream>   
  6. using namespace std;   
  7.   
  8. int main()   
  9. {   
  10.     int max, n, i, j, tmp, f[2][5];   
  11.     while(cin >> n)   
  12.     {   
  13.         cin >> tmp;   
  14.         f[0][1] = tmp;   
  15.         f[0][2] = 0;   
  16.         f[0][3] = 0;   
  17.         f[0][4] = 0;   
  18.         for(i = 2; i <= n; i++)   
  19.         {   
  20.             scanf("%d", &tmp);   
  21.             f[(i + 1) % 2][1] = (f[i % 2][2] > f[i % 2][4]) ? f[i % 2][2] + tmp : f[i % 2][4] + tmp;   
  22.             f[(i + 1) % 2][2] = (f[i % 2][1] > f[i % 2][3]) ? f[i % 2][1] - tmp : f[i % 2][3] - tmp;   
  23.             f[(i + 1) % 2][3] = f[(i + 1) % 2][2] + tmp;   
  24.             f[(i + 1) % 2][4] = f[(i + 1) % 2][1] - tmp;   
  25.         }   
  26.         max = 0;   
  27.         for(i = 0; i <= 1; i++)   
  28.             for(j = 1; j <= 4; j++)   
  29.                 max = (max > f[i][j]) ? max : f[i][j];   
  30.   
  31.         cout << max << endl;   
  32.     }   
  33.   
  34.     return 0;   
  35. }   

 

]]> http://x2studio.net/u/read.php?18 <![CDATA[P1684[丢失的筷子]，赤裸裸的异或]]> Jucady <admin@yourname.com> Wed, 11 Nov 2009 15:45:57 +0000 http://x2studio.net/u/read.php?18 http://www.vijos.cn/Problem_Show.asp?id=1684

怎么说呢，这个题目其实就是让我们用异或的。首先BS一下没有说明数据范围的出题人。

一个数和另一个数异或一次，再用同一个数异或一次就变回了这个数的本身。也就是说把所有数异或一遍，那么所有偶数个的数都会被抵消掉，剩下那个没有被抵消的就是我们所需要找的数了。

下面贴上代码：(PS:用C写的WA了一个点，不知道错在哪，哪位高人帮忙看看哈)

 
  1. {
  2. Code by Jucady
  3. VIJOS1684丢失的筷子
  4. }
  5.  
  6. var
  7.   i: longint;
  8.   n, tmp, ans: int64;
  9.  
  10. begin
  11.   readln(n);
  12.   read(ans);
  13.   for i := 2 to n do
  14.   begin
  15.     read(tmp);
  16.     ans := ans xor tmp;
  17.   end;
  18.   writeln(ans);
  19. end.
折叠C/C++ 代码复制内容到剪贴板
  1. /*  
  2. Code by Jucady  
  3. VIJOS1684丢失的筷子  
  4. */  
  5. #include<stdio.h>   
  6.   
  7. int main()   
  8. {   
  9.     __int64 ans, tmp;   
  10.     int i, n;   
  11.     scanf("%d", &amp;n);   
  12.   
  13.     for(i = 1; i <= n; i++)   
  14.     {   
  15.         scanf("%d", &amp;tmp);   
  16.         if(i == 1) ans = tmp;   
  17.         else ans ^= tmp;   
  18.     }   
  19.     printf("%d\n", ans);   
  20.       
  21.     return 0;   
  22. }   

 

]]> http://x2studio.net/u/read.php?17 <![CDATA[P1278[最多拦截导弹数]]]> Jucady <admin@yourname.com> Wed, 11 Nov 2009 15:42:25 +0000 http://x2studio.net/u/read.php?17
折叠C/C++ 代码复制内容到剪贴板
  1. /*  
  2. Code by Jucady  
  3. ZJUT1278[最多拦截导弹数]  
  4. */  
  5. #include<stdio.h>   
  6. #include<string.h>   
  7.   
  8. int main()   
  9. {   
  10.     int n, i, j, bmb[1001], f[1001], max;   
  11.     while(scanf("%d", &amp;n))   
  12.     {   
  13.         if(n == 0) break;   
  14.   
  15.         memset(f, 0, sizeof(f));   
  16.         for(i = 1; i <= n; i++)   
  17.         {   
  18.             scanf("%d", &amp;bmb[i]);   
  19.             f[i] = 1;   
  20.   
  21.             for(j = 1; j < i; j++)   
  22.                 if(bmb[j] >= bmb[i])   
  23.                     f[i] = (f[i] < f[j] + 1) ? f[j] + 1 : f[i];   
  24.         }   
  25.   
  26.         max = 0;   
  27.         for(i = 1; i <= n; i++)   
  28.             max = (max > f[i]) ? max : f[i];   
  29.   
  30.         printf("%d\n", max);   
  31.     }   
  32.   
  33.     return 0;   
  34. }   

 

]]> http://x2studio.net/u/read.php?16 <![CDATA[P2021[发工资咯：）],背包问题]]> Jucady <admin@yourname.com> Wed, 11 Nov 2009 15:40:19 +0000 http://x2studio.net/u/read.php?16 http://acm.hdu.edu.cn/showproblem.php?pid=2021 虽然题目叫发工资，但这是一个典型的背包问题。 只需要做出在这个数目中，加上某种面值所需要的最少张数为多少，以此类推即可。

 转移方程如下：

折叠C/C++ 代码复制内容到剪贴板
  1. f[j] = (f[j] <= f[j - v[k]] + 1) ? f[j] : f[j - v[k]] + 1;   

方程的意思是：f[j]代表j工资的最少张数，在j的工资里，如果需要v[k]的钱币，那么它的张数就是f[j - v[k]]加上一张。那么比较一下是这种情况所需的钱少还是原状态的钱少即可。

折叠C/C++ 代码复制内容到剪贴板
  1. /*  
  2. Code by Jucady  
  3. HDU2021[发工资咯：）]  
  4. */  
  5.   
  6. #include<stdio.h>   
  7. #include<string.h>   
  8.   
  9. int main()   
  10. {   
  11.     int n, i, j, k, f[10001], mny, v[6] = {1, 2, 5, 10, 50, 100};   
  12.     while(scanf("%d", &amp;amp;n))   
  13.     {   
  14.         int cnt = 0;   
  15.         if(n == 0) break;   
  16.         for(i = 1; i <= n; i++)   
  17.         {   
  18.             scanf("%d", &amp;amp;mny);   
  19.             for(j = 1; j <= mny; j++) f[j] = 100000;   
  20.             f[1] = 1; f[2] = 1; f[5] = 1; f[10] = 1; f[50] = 1; f[100] = 1;   
  21.             for(j = 1; j <= mny; j++)   
  22.             {   
  23.                 for(k = 0; k <= 5; k++)   
  24.                 {   
  25.                     if(j - v[k] < 1) break;   
  26.                     f[j] = (f[j] <= f[j - v[k]] + 1) ? f[j] : f[j - v[k]] + 1;   
  27.                 }   
  28.             }   
  29.             cnt += f[mny];   
  30.         }   
  31.         printf("%d\n", cnt);   
  32.     }   
  33. }   
]]> http://x2studio.net/u/read.php?15 <![CDATA[P1075[数太阳],简单的floodfill]]> Jucady <admin@yourname.com> Wed, 11 Nov 2009 15:33:22 +0000 http://x2studio.net/u/read.php?15 http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1075
说白了就是搜索。对一个点进行搜索，把与其连通的点全部连根拔起，然后记下来表示这个点已经被搜索过就OK了。

折叠C/C++ 代码复制内容到剪贴板
  1. /*  
  2. Code by Jucady  
  3. ZJUT1075[数太阳]  
  4. */  
  5.   
  6. #include<stdio.h>   
  7. #include<string.h>   
  8.   
  9. int bool_mat[11][11], h, w;   
  10. char mat[11][11];   
  11.   
  12. void floodfill(int y, int x)   
  13. {   
  14.     if(y - 1 >= 1 &amp;&amp; mat[y - 1][x] == '1' &amp;&amp; bool_mat[y - 1][x] == 0)   
  15.     {   
  16.         bool_mat[y - 1][x] = 1;   
  17.         floodfill(y - 1, x);   
  18.     }   
  19.     if(y + 1 <= h &amp;&amp; mat[y + 1][x] == '1' &amp;&amp; bool_mat[y + 1][x] == 0)   
  20.     {   
  21.         bool_mat[y + 1][x] = 1;   
  22.         floodfill(y + 1, x);   
  23.     }   
  24.     if(x - 1 >= 1 &amp;&amp; mat[y][x - 1] == '1' &amp;&amp; bool_mat[y][x - 1] == 0)   
  25.     {   
  26.         bool_mat[y][x - 1] = 1;   
  27.         floodfill(y, x - 1);   
  28.     }   
  29.     if(x + 1 <= w &amp;&amp; mat[y][x + 1] == '1' &amp;&amp; bool_mat[y][x + 1] == 0)   
  30.     {   
  31.         bool_mat[y][x + 1] = 1;   
  32.         floodfill(y, x + 1);   
  33.     }   
  34. }   
  35.   
  36. int main()   
  37. {   
  38.     int n, i;   
  39.     scanf("%d", &amp;n);   
  40.     for(i = 1; i <= n; i++)   
  41.     {   
  42.         memset(bool_mat, 0, sizeof(bool_mat));   
  43.         scanf("%d%d", &amp;h, &amp;w);   
  44.         int j, k, cnt = 0;   
  45.         for(j = 1; j <= h; j++)   
  46.             for(k = 1; k <= w; k++)   
  47.             {   
  48.                 scanf("%c", &amp;mat[j][k]);   
  49.                 if(mat[j][k] != '0' &amp;&amp; mat[j][k] != '1') scanf("%c", &amp;mat[j][k]);   
  50.             }   
  51.                
  52.         for(j = 1; j <= h; j++)   
  53.             for(k = 1; k <= w; k++)   
  54.                 if(mat[j][k] == '1' &amp;&amp; bool_mat[j][k] == 0)   
  55.                 {   
  56.                     cnt++;   
  57.                     bool_mat[j][k] = 1;   
  58.                     floodfill(j, k);   
  59.                 }   
  60.            
  61.         printf("%d\n", cnt);   
  62.     }   
  63. }   

 

]]>