2011年10月31日星期一

POJ 1326


#include
#include
int main()
{
char a[20],b[20],c[3];
int dis,sum = 0;
while(scanf("%s",a)){
if(a[0] == '0'){printf("%d\n",sum);sum = 0;continue;}
if(a[0] == '#')break;
scanf("%s%d%s",b,&dis,c);
if(c[0] == 'F')sum += dis * 2;
if(c[0] == 'B')sum += ceil(dis * 1.5);   //取大于1.5倍dis的最小整数
if(c[0] == 'Y'){
if(dis <= 500)sum += 500;
else sum += dis;
}
}
return 0;
}




水题,无以复加的水  = =
越做越水。。。。代码也水。。。
但竟然用了32ms,神奇了 = =

2011年10月30日星期日

POJ 1316


#include
int a[11000];
int main()
{
for(int i = 1;i < 10000;i++){
int s = 0,t = i;
while(t){
s += t % 10;
t /= 10;
}
s += i;
if(s > 10000)break;
a[s] = 1;
}
for(int i = 1;i <= 9994;i ++)
if(!a[i])printf("%d\n",i);
return 0;
}

这题原本看题目的时候就看出有规律了,但是保险起见还是小范围模拟下,发现是9个11和1个2之间的循环。不过还是先交了暴力的代码。再回头对比发现,前面的数据一样,然后中间不知道怎么的就少了2。看来还是有坑爹的地方啊。。。囧

POJ 1298


很水的一题,我都不好意思贴上来了 - -!

#include
#include
int main()
{
static char a[250],b[250];
while(gets(a)){
if(!strcmp(a,"START"))continue;
if(!strcmp(a,"END")){
printf("%s\n",b);
memset(b,'\0',250 * sizeof(char));
memset(a,'\0',250 * sizeof(char));
continue;
}
if(!strcmp(a,"ENDOFINPUT"))break;
for(int i = 0;i < strlen(a);i ++){
if(a[i] >= 'A' && a[i] <= 'E')b[i] = a[i] + 21;
else if(a[i] >='F' && a[i] <= 'Z')b[i] = a[i] - 5;
else b[i] = a[i];
}
}
return 0;
}

2011年10月29日星期六

POJ1318 字符串处理(初试vector)


第一次用vector,感觉确实好用 = =
只是功能太多,一下还没有完全会用,特别是迭代器,还需继续研究 = =


#include
#include
#include
#include
using namespace std;
int main()
{
vector dic;
string t;
for(int i = 0;;i++){
cin>>t;
if(t[0] == 'X')break;
dic.push_back(t);           //push back输入数据,更新size值
}
sort(&dic[0],&dic[0] + dic.size());    //先按字典排序
vectordic2(dic.begin(),dic.end());     //复制一个排好序的副本
for(int i = 0;i < dic2.size();i ++)
sort(&dic2[i][0],&dic2[i][0] + dic2[i].size());    //对副本每个元素(string)排序
while(cin>>t){
if(t[0] == 'X')break;
sort(&t[0],&t[0] + t.size());     //对输入的string排序
int flag = 0;
for(int i = 0;i < dic2.size();i ++)
if(t == dic2[i]){cout<
if(!flag)cout<<"NOT A VALID WORD\n";
cout<<"******\n";
}
return 0;
}

2011年10月27日星期四

POJ 1250

思路很清晰,模拟过。可惜找不到更好的方法,感觉效率不是很高,应该还可以优化。细节问题比较多,总体是简单题(貌似我能做出来的都是简单题吧 = =!!)


#include
#include
int main()
{
int n,t,i,j,sum=0;
while(scanf("%d",&n) && n){
char a[22]={'\0'};
char c[5000]={'\0'};
scanf("%s",c);
t = strlen(c);
for(i = 0;i < t;i ++){
for(j = 0;j < n;j ++)
if(a[j] == c[i]){a[j] = '\0';break;}   //先检查是否有相同的,有则重置为0
if(j < n)continue;                   //并跳过下面操作,进入下一个字符的比较
for(j = 0;j < n;j ++)
if(a[j] == '\0'){a[j] = c[i];break;}   //为0则写入
if(j == n)sum++;                        //满则人数+1
}
if(!sum)printf("All customers tanned successfully.\n");
else printf("%d customer(s) walked away.\n",sum/2);
sum = 0;
}
return 0;
}

2011年10月26日星期三

算法之道—形而之上谓之道



注:本文转载自程序员


1966年3月的一天,美国加州大学洛杉矶分校的Andrew J. Viterbi教授在给研究生讲解缠绕编码的时序译码算法SDCD。但不管他如何讲解,学生就是听不明白。思来想去,Viterbi觉得学生不能理解的原因是该算法的证明过于复杂。于是他开始考虑如何简化这个证明。在经历了持久的烦躁和困惑后,他灵感顿现:需要简化的不是算法的证明,而是算法本身。于是Viterbi对SDCD算法进行了少许修改,提出了基于Trellis的概率译码算法。这个算法就是后来著名的CDMA技术的基石。Viterbi也因此而身价暴涨(创立了高通公司,赚取了数十亿美元)。

POJ 1247 水过


#include
int main()
{
int n,a[31]={0};
while(scanf("%d",&n) && n){
int sum = 0;
for(int i = 0;i < n;i ++){
scanf("%d",&a[i]);
sum += a[i];
}
for(int i = 0,t = 0;2 * t <= sum;i ++){     //原来用的sum/2,忘了考虑小数的问题,后改为乘法
t += a[i];
if(2 * t == sum){
printf("Sam stops at position %d and Ella stops at position %d.\n",i+1,i+2);
break;
}
if(2 * t > sum)printf("No equal partitioning.\n");    //这里总感觉有点别扭= =
}
}
return 0;
}

百练 2972:确定进制


#include
#include
int f(int x,int j)     //将j进制数x换成10进制
{
int i = 0,t = 0;
while(x){
if(x % 10 >= j)return -1;     //开始没有考虑到这个重要的问题 = =
t += (x % 10) * pow(j+0.0,i+0.0);
x /= 10;
i++;
}
return t;
}


int main()
{
int n,p,q,r,i;
scanf("%d",&n);
while(n--){
scanf("%d%d%d",&p,&q,&r);
for(i = 2;i <= 16;i ++)
if(f(p,i) * f(q,i) == f(r,i)){printf("%d\n",i);break;}
if(i == 17)printf("0\n");
}
return 0;
}



//数据很水,如果出大数来卡时间的话很可能TLE

2011年10月24日星期一

周赛某题:异或解法


Problem Description

Give you a sequence of number,in which except for one element,
all number appears twice,your task is to find such a special one.

Input

The first line:N(N<=1000000)
The second line:a1,a2...an
(Use 'scanf' instead of 'cin' to esacpe from TLE,and use 64_bit
integer to hold the input)

Output

Only one number,the special one

Sample Input

   5
   1 1 2 2 3

Sample Output

3






#include
int main()
    int n; __int64 t,m; scanf("%d%I64d",&n,&t);    while(--n){
          scanf("%I64d",&m); t ^= m;
    }
    printf("%I64d\n",t); 
    return 0;
 }