Debug Life -- 编程爱好者博客

PKU ACM 1013 Counterfeit Dollar(2009-09-16 21:41:00)

摘要：#include <iostream>
#include <string>
using namespace std;
struct input{
string left;
string right;
string state;
}in[3];
bool Light(char &ch)
{
for(int i=0;i<3;i++)
{
  switch(in[i].state[0])
  {
  case 'u':
   if(in[i].right.find(ch)==string::npos)
    return true;
   break;
  case 'd':
   if(in[i].left.find(ch)==string::npos)
    return true;
   break;
  case 'e':
   if(in[i].left.find(ch)!=string::npos||in[i].right.find(ch)!=string::npos)
    return true;
   break;
  default:
   return false;
  }
}
return false;
}
bool Heavy(char &ch)
{
for(int i=0;i<3;i++)
{
&......

阅读全文(1243) | 评论:0

PKU 1061 (扩展欧几里德)(2009-09-13 00:41:00)

摘要：所谓扩展欧几里德,就是在欧几里德算法的基础上加入变量X,Y,使得aX-bY=GCD(a,b)。此时X，Y是该不定方程式的一组解。求a * x + b * y = n的整数解的过程: 1、先计算Gcd(a,b)，若c不能被Gcd(a,b)整除，则方程无整数；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此时Gcd(a',b')=1; 2、利用上面所说的欧几里德算法求出方程a' * x + b' * y = 1的一组整数解x0,y0，则n' * x0,n' * y0是方程a' * x + b' * y = n'的一组整数解； 3、根据数论中的相关定理，可得方程a' * x + b' * y = n'的所有整数解为：
            x = n' * x0 + b' * t
            y = n' * y0 - a' * t
                (t为整数)
上面的解也就是a * x + b * y = n 的全部整数解。关于1061的解法由题意:     (x+mt)-(y+nt)=pL =>(m-n)t-(y-x)=pL =>(m-n)t-pL=(y-x) 即 (m-n)t≡(y-x)MOD(L) 令a=m-n,b=L,c=y-x,X=t,Y=p 则原等式转换为 aX-bY=c 使用扩展欧几里德求出一组解X0,Y0=>aX0-bY0=GCD(a,b) 令d=GCD(a,b) 若c%d!=0 则无解 ......

阅读全文(1934) | 评论:3

ACM基本算法分类、推荐学习资料和配套pku习题(2009-09-08 00:13:00)

摘要：一.动态规划

参考资料：

刘汝佳《算法艺术与信息学竞赛》《算法导论》

推荐题目：

http://acm.pku.edu.cn/JudgeOnline/problem?id=1141

简单

http://acm.pku.edu.cn/JudgeOnline/problem?id=2288

中等，经典TSP问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=2411

中等，状态压缩DP

http://acm.pku.edu.cn/JudgeOnline/problem?id=1112

中等

http://acm.pku.edu.cn/JudgeOnline/problem?id=1848

中等，树形DP。可参考《算法艺术与信息学竞赛》动态规划一节的树状模型

http://acm.zju.edu.cn/show_problem.php?pid=1234

中等，《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1947

中等，《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1946

中等，《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1737

中等，递推

http://acm.pku.edu.cn/JudgeOnline/problem?id=1821

中等，需要减少冗余计算

http://acm.zju.edu.cn/show_problem.php?pid=2561

中等，四边形不等式的简单应用

http://acm.pku.edu.cn/JudgeOnline/problem?id=1038

较难，状态压缩DP，《......

阅读全文(3330) | 评论:0

快速排序的随机化版本(2009-09-06 15:19:00)

摘要： #define MAX_SIZE 100
#include <iostream>
#include <ctime>
using namespace std; //交换指针p1,p2指向的值
void exchange(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
//pa为指向A[]的数组，p,r为下标，对A[p..r]进行就地重排，以A[r]为主元
//划分为小于主元和大于主元的两部分，返回主元的下标q
//例如：A[1..6]={18,8,16,6,9,10}结果：A[1..6]={8,6,9,10,18,16} q=4
//(元素顺序可能与结果不一致，但小于10的元素在10前面，大于10的元素在10后面)s
int partition(int *pa,int p,int r)
{
    int x=*(pa+r); //主元
    int i=p-1,j; //i表示小于主元的最后一个元素q
    for(j=p;j<r;j++)
    {
        if(*(pa+j)<x)
        {
            i++;
            exchange((pa+i),(pa+j));
        }......

阅读全文(2110) | 评论:1

快速排序的C++实现(2009-09-05 01:07:00)

摘要： //quick_sort by suqiang @ neuq & jlu 更详细的内容请访问：http://blog.csdn.net/china8848 #define MAX_SIZE 100
#include <iostream>
using namespace std; //交换指针p1,p2指向的值
void exchange(int *p1,int *p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}
//pa为指向A[]的数组，p,r为下标，对A[p..r]进行就地重排，以A[r]为主元
//划分为小于主元和大于主元的两部分，返回主元的下标q
//例如：A[1..6]={18,8,16,6,9,10}结果：A[1..6]={8,6,9,10,18,16} q=4
//(元素顺序可能与结果不一致，但小于10的元素在10前面，大于10的元素在10后面)s
int partition(int *pa,int p,int r)
{
    int x=*(pa+r); //主元
    int i=p-1,j; //i表示小于主元的最后一个元素q
    for(j=p;j<r;j++)
    {
        if(*(pa+j)<x)
        {
            i++;
            exchange((pa+i),(p......

阅读全文(1262) | 评论:0

ACM PKU 1011 Sticks 深度优先搜索(2009-09-04 22:46:00)

摘要：以下是lowai的程序，牛啊，学习中。 #include <stdio.h>
#include <stdlib.h> //due to:qsort
#include <string.h> int n;
int stick[100];
int total;
int ns;            //一共需要还原出的木棍数ns
int ok;
int len;           //当次需要达到的长度 int cmp(const void *a,const void *b) {
   int a1 = *(int *)a;
   int a2 = *(int *)b;
   return a2 - a1;
}
int used[100]; int adds() {
   int j = 0;
   for (int i = 1;i <= n;i++)
      j += stick[i];
   return j;
} void search(int,int,int); void s(int x) {         //x 正在还原第x根木棍
   if (x > ns) {
      ok = 1;
    &nb......

阅读全文(2030) | 评论:0

PKU ACM 1008--玛雅历(2009-09-02 10:13:00)

摘要： //第一次做的，结果不正确！！ /* 玛雅历Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 32258 Accepted: 9841
Description
上周末，M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳（玛雅人用于记事的工具）中，教授发现玛雅人使用了一个一年有365天的叫做hMonth的历法。这个hMonth历法拥有19个月，在开始的18个月，一个月有20天，月份的名字分别是pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu。这些月份中的日期用0到19表示。hMonth历的最后一个月叫做uayet，它只有5天，用0到4表示。玛雅人认为这个日期最少的月份是不吉利的，在这个月法庭不开庭，人们不从事交易，甚至没有人打扫屋中的地板。因为宗教的原因，玛雅人还使用了另一个历法，在这个历法中年被称为Tzolkin(holly年)，一年被分成13个不同的时期，每个时期有20天，每一天用一个数字和一个单词相组合的形式来表示。使用的数字是1~13，使用的单词共有20个，它们分别是：imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau。注意：年中的每一天都有着明确唯一的描述，比如，在一年的开始，日期如下描述： 1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, ，8 imix, 9 ik, 10 akbal ……也就是说数字和单词各自独立循环使用。 hMonth历和Tzolkin历中的......

阅读全文(1934) | 评论:0

c++中string的用法(2009-09-01 13:04:00)

摘要：原文地址：http://hi.baidu.com/clnju/blog/item/4e10b81bc622e4118618bf1a.html 之所以抛弃char*的字符串而选用C++标准程序库中的string类，是因为他和前者比较起来，不必担心内存是否足够、字符串长度等等，而且作为一个类出现，他集成的操作函数足以完成我们大多数情况下(甚至是100%)的需要。我们可以用 = 进行赋值操作，== 进行比较，+ 做串联（是不是很简单?）。我们尽可以把它看成是C++的基本数据类型。首先，为了在我们的程序中使用string类型，我们必须包含头文件 <string>。如下：
#include <string> //注意这里不是string.h string.h是C字符串头文件 1．声明一个C++字符串
声明一个字符串变量很简单：
string Str;
这样我们就声明了一个字符串变量，但既然是一个类，就有构造函数和析构函数。上面的声明没有传入参数，所以就直接使用了string的默认的构造函数，这个函数所作的就是把Str初始化为一个空字符串。String类的构造函数和析构函数如下：
a) string s; //生成一个空字符串s
b) string s(str) //拷贝构造函数生成str的复制品
c) string s(str,stridx) //将字符串str内"始于位置stridx"的部分当作字符串的初值
d) string s(str,stridx,strlen) //将字符串str内"始于stridx且长度顶多strlen"的部分作为字符串的初值
e) string s(cstr) //将C字符串作为s的初值
f) string s(chars,chars_len) //将C字符串前chars_len个字符作为字符串s的初值。
g) string s(num,c) //生成一个字符串，包含num个c字符
h) string s(beg,end) //以区间beg;end(不包含end)内的字符作为字符串s的初值
i) s.~string() //销毁所有字符，释放内存
都很简单，我就不解释了。 2．......

阅读全文(1643) | 评论:0

如何把字符串转换为整型数(2009-09-01 12:27:00)

摘要：    char*   c="123";
int   i=atoi(c);

//
char*   ch="12.3";
double   j=atof(ch);......

阅读全文(1222) | 评论:0

怎样初始化一个动态数组的所有元素为0.(2009-08-27 20:36:00)

摘要： (CC++)怎样初始化一个动态数组的所有元素为0.数组很大.若建议用循环初始化谢绝回复.谢谢! 悬赏分：0 - 解决时间： 2009年02月25日 00时05分动态申请的数组.编译器应该不会自动初始化为0值吧. 提问者： sdf7895 - 超级魔法师九级最佳答案＃include ＜iostream＞
＃include ＜memory.h＞
using namespace std,

void main()
{
int n=100000,
long＊ array=new long［n］,
memset(array. 0. n＊sizeof(array)),
} 出自：http://it.wenda.sogou.com/question/2161539.html......

阅读全文(2207) | 评论:0

博客介绍

文章分类

博文