UVA 369: Combinations
题目大意:
GIVEN:
Compute the EXACT value of:
给你N和M求C。
解题思路：
由于直接求出阶乘数据庞大，要用高精度算法。但是据题目说答案不超过32位，所以就用新的方法来做。把公式转化为
然后把m+1到n都存入数组，用（n-m）到1去和数组的数一起除以它们的最大公约数。最后把数组里面的数相乘起来就是答案。
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<iostream>using namespace std;typedef long long ll;ll s[105];ll gcd(ll a,ll b){ return a%b==0?b:gcd(b,a%b);}int main(){ ll n,m; while(cin>>n>>m&&m+n){ for(int i=1;i<=n;i++) s[i]=i; ll t=n-m,sum=1; if(t!=0){ while(t!=1){ for(int i=m+1,j=t;i<=n&&j!=1;i++){ ll g=gcd(s[i],j); s[i]/=g; j/=g; } t--; } for(int i=m+1;i<=n;i++) sum*=s[i]; } cout<<n<<" things taken "<<m<<" at a time is "<<sum<<" exactly."<<endl; } return 0;} |
UVA 575: Skew Binary
题目大意：
定义一个新的进制数，把这种新数转化为十进制数。
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 | #include<iostream>using namespace std;int main(){ string s; while(cin>>s&&s!="0"){ int sum=0; int len=s.length(); for(int i=0;i<len;i++) sum+=(s[i]-'0')*((1<<(len-i))-1); cout<<sum<<endl; }} |
UVA 10300: Ecological Premium
题目大意：
关于什么农场分钱，我先看看我的QQ农场，题目自己看吧～看起来是挺费劲的，简直是考英语阅读理解～
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include<iostream>using namespace std;int main(){ int n; cin>>n; while(n--){ int m,sum=0; cin>>m; while(m--){ int a,b,c; cin>>a>>b>>c; sum+=a*c; } cout<<sum<<endl; } return 0;} |
扩展知识：http://qzone.qq.com/
UVA 10008: What's Cryptanalysis?
题目大意：
密码破解是一门艺术啊，现在要你分析一段密文，输出各个字母分别是多少个。
解题思路：
统计一下，输出来就是啦，一些不熟悉的字符函数用用。
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream>#include<string>#include<cctype>#include<algorithm>using namespace std;struct node{ char c; int v; node(){ c='\0'; v=0; }}s[26];bool cmp(node a,node b){ if(a.v==b.v) return a.c<b.c; else return a.v>b.v;}int main(){ int n; string cry; while(cin>>n){ for(int i=0;i<=n;i++){ getline(cin,cry); int len=cry.length(); for(int j=0;j<len;j++) if(isalpha(cry[j])){ char t=toupper(cry[j]); s[t-'A'].c=t; s[t-'A'].v++; } } sort(s,s+26,cmp); for(int i=0;i<26&&s[i].v!=0;i++){ cout<<s[i].c<<' '<<s[i].v<<endl; } } return 0;} |
扩展知识：
http://blog.csdn.net/lin49940/archive/2010/04/27/5535700.aspx
http://en.wikipedia.org/wiki/Cryptanalysis
UVA 101: The Blocks Problem
题目大意：
模拟机器人操作，英语不好题目容易看错，翻译如下：
机器手臂有以下几种合法的操作方式（a和b是积木的编号）：
move a onto b
在将a搬到b上之前，先将a和b上的积木放回原来的位置（例如：1就放回1的最开始位罝）
move a over b
在将a搬到b所在的那堆积木之上之前，先将a上的积木放回原来的位罝（b所在的那堆积木不动）
pile a onto b
将a本身和其上的积木一起放到b上，在搬之前b上方的积木放回原位
pile a over b
将a本身和其上的积木一起搬到b所在的那堆积木之上
quit动作结束
前四个动作中若a=b，或者a, b在同一堆积木中，那么这样的动作算是不合法的。所有不合法的动作被忽略，也就是对其个积木都不改变。
解题思路：
一道模拟题，按着它规定的操作执行，编程相对复杂点，由于没有看对题目错了一次。
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include<iostream>using namespace std;int b[26][26];int f[25];int n;void init(){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++) if(j==0) b[i][j]=i; else b[i][j]=-1; f[i]=i; }}void move(string s1,int s,string s2,int d){ if(f[s]!=f[d]){ int i=0,j=0,fs=f[s],fd=f[d],p,q; while(b[fs][i]!=s)i++; p=i; if(s1=="move"){ while(b[fs][++i]!=-1){ b[b[fs][i]][0]=b[fs][i]; f[b[fs][i]]=b[fs][i]; b[fs][i]=-1; } } if(s2=="onto"){ while(b[fd][j]!=d)j++; q=j+1; } else{ while(b[fd][j]!=-1)j++; q=j; } if(s2=="onto"){ while(b[fd][++j]!=-1){ b[b[fd][j]][0]=b[fd][j]; f[b[fd][j]]=b[fd][j]; b[fd][j]=-1; } } i=p;j=q; while(b[fs][i]!=-1){ b[fd][j++]=b[fs][i]; f[b[fs][i]]=fd; b[fs][i]=-1; i++; } }}void print(){ for(int i=0;i<n;i++){ cout<<i<<':'; for(int j=0;j<n;j++){ if(b[i][j]!=-1) cout<<' '<<b[i][j]; else{ cout<<endl; break; } } }}int main(){ while(cin>>n){ string s1; init(); while(cin>>s1){ if(s1=="quit") break; int s,d; string s2; cin>>s>>s2>>d; move(s1,s,s2,d); } print(); } return 0;} |
扩展知识：http://en.wikipedia.org/wiki/Artificial_intelligence
UVA 10082: WERTYU
题目大意：
按键盘的时候有时候会不小心按到右边的键，现在要你还原回来。
解题思路:
跟密码问题是一样的，但是这题规律没有那么好定义，就按对应关系自己去构造联系。
解题代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include<iostream>#include<string>using namespace std;string p="AVXSWDFGUHJKNBIOQEARYCQZTZ";string no="9`12345678";string ex="-=[]\\;',./";string ep="0-P[]L;M,.";int find(char c){ for(int i=0;i<10;i++) if(c==ex[i]) return i; return -1;}int main(){ string s; while(getline(cin,s)){ int len=s.length(),j; for(int i=0;i<len;i++){ if(s[i]>='A'&&s[i]<='Z') cout<<p[s[i]-'A']; else if(s[i]>='0'&&s[i]<='9') cout<<no[s[i]-'0']; else if((j=find(s[i]))!=-1) cout<<ep[j]; else cout<<s[i]; } cout<<endl; } return 0;} |