UVA 369: Combinations
题目大意:
GIVEN:
Compute the EXACT value of:
给你N和M求C。
解题思路：
由于直接求出阶乘数据庞大，要用高精度算法。但是据题目说答案不超过32位，所以就用新的方法来做。把公式转化为
然后把m+1到n都存入数组，用（n-m）到1去和数组的数一起除以它们的最大公约数。最后把数组里面的数相乘起来就是答案。
解题代码：
#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
题目大意：
定义一个新的进制数，把这种新数转化为十进制数。
解题代码：
#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农场，题目自己看吧～看起来是挺费劲的，简直是考英语阅读理解～
解题代码：
#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?
题目大意：
密码破解是一门艺术啊，现在要你分析一段密文，输出各个字母分别是多少个。
解题思路：
统计一下，输出来就是啦，一些不熟悉的字符函数用用。
解题代码：
#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在同一堆积木中，那么这样的动作算是不合法的。所有不合法的动作被忽略，也就是对其个积木都不改变。
解题思路：
一道模拟题，按着它规定的操作执行，编程相对复杂点，由于没有看对题目错了一次。
解题代码：
#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
题目大意：
按键盘的时候有时候会不小心按到右边的键，现在要你还原回来。
解题思路:
跟密码问题是一样的，但是这题规律没有那么好定义，就按对应关系自己去构造联系。
解题代码：
#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;
}