UVA 299: Train Swapping
题目大意：
按序号从大到小排列火车，相邻之间才能交换。求交换次数。
解题思路：
就是冒泡法排序嘛～
解题代码：
#include<iostream>
using namespace std;
int t[100];
int n;
int swap(){
int count=0;
for(int i=0;i<n-1;i++)
for(int j=0;j<n-1-i;j++)
if(t[j]>t[j+1]){
int tmp=t[j];
t[j]=t[j+1];
t[j+1]=tmp;
count++;
}
return count;
}
int main(){
int cas;
cin>>cas;
while(cas--){
cin>>n;
for(int i=0;i<n;i++)
cin>>t[i];
cout<<"Optimal train swapping takes "<<swap()<<" swaps."<<endl;
}
return 0;
}
UVA 494: Kindergarten Counting Game
题目大意：
求字符串的单词数。
解题思路：
做个标记，当第一次出现字母时候数量加一标记失效，遇到非字母标记有效。
解题代码：
#include<iostream>
#include<string>
using namespace std;
bool in(char c){
if((c>='a'&&c<'z')||(c>='A'&&c<='Z'))
return true;
return false;
}
int main(){
string s;
while(getline(cin,s)){
int len=s.length();
int flag=1;
int count=0;
for(int i=0;i<len;i++){
if(flag&&in(s[i]))
count++,flag=0;
else
if(!in(s[i]))
flag=1;
}
cout<<count<<endl;
}
return 0;
}
扩展知识：http://en.wikipedia.org/wiki/String_%28computer_science%29
UVA 113: Power of Cryptography
题目大意：
一个数k的n次方等于p，给你n和p求出k。
, 
。
解题思路：
看到数据范围吓到了，难道是高精度？难度要用JAVA高精度？才头几题有必要这么可怕？后来实在不行了，看解题报告，看一下吐血，float的范围为-2^128 ~ +2^127，也即-3.40E+38 ~ +3.40E+38；double的范围为-2^1024 ~ +2^1023，也即-1.79E+308 ~ +1.79E+308。所以只要用double和pow就行～还用了下C++精度控制。
解题代码：
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main(){
double n,p;
while(cin>>n>>p){
cout<<fixed<<setprecision(0)<<pow(p,1/n)<<endl;
}
return 0;
}
UVA 108: Maximum Sum
题目大意：
一个二维矩阵求哪个子矩阵的和最大，输出最大值。
解题思路：
由于是二维矩阵，如果枚举的话复杂度很高。一维的连续子串的最大和问题有个很好的O(n)算法，我们能不能把二维的转化成一维的来做呢？答案是肯定的。我们通过预处理把当前行里面的数存的是同一列前面行全部数的加上自己的和，要得到某列某两行之间数的和就直接两行的数之差，就转化成一个一维数组，每个这样的一维数组求最大值就是答案。
解题代码：
#include<iostream>
using namespace std;
int a[200][200],tmp[200];
int n;
int maxv(int *s){
int max=-10000000;
int sum=0;
for(int i=0;i<n;i++){
sum+=s[i];
if(sum>max) max=sum;
if(sum<0)sum=0;
}
return max;
}
void input(){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>a[i][j];
if(i!=0){
a[i][j]+=a[i-1][j];
}
}
}
int work(){
int max=-1000000;
for(int i=0;i<n;i++)
for(int j=-1;j<i;j++){
for(int k=0;k<n;k++)
if(j==-1)
tmp[k]=a[i][k];
else
tmp[k]=a[i][k]-a[j][k];
int p=maxv(tmp);
if(p>max) max=p;
}
return max;
}
int main(){
while(cin>>n){
input();
cout<<work()<<endl;
}
}
扩展知识：http://linjiazhen.is-programmer.com/admin/drafts/25634/edit
UVA 10018: Reverse and Add
题目大意：
一个数加上它反过来的数的和再做同样操作，直到这个和是一个回文数。
解题思路：
按照题目意思做，但是要注意数据大小，题目说是结果不大于4,294,967,295，所以用unsigned就行。
解题代码：
#include<iostream>
using namespace std;
unsigned reverse(unsigned n){
unsigned t=0;
while(n){
t=t*10+n%10;
n/=10;
}
return t;
}
int main(){
int n;
cin>>n;
while(n--){
unsigned t,c=0;
cin>>t;
while(t!=reverse(t)){
t+=reverse(t);
c++;
}
cout<<c<<' '<<t<<endl;
}
}
UVA 10035: Primary Arithmetic
题目大意：
小学生问题，两个数加起来求进位的次数，如999+11进位3次。
解题思路：
从低位开始加，大于等于10就进位。不小心错了一次，要加到最长那个数最高位为止，每次都有一些地方让我不能1Y。
要是题目每个数很大，那就必须要用高精度算法处理啦。
解题代码：
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
ll a,b;
while(cin>>a>>b&&a+b){
int c=0,count=0;
while(a||b){
c=(a%10+b%10+c)>=10;
if(c)
count++;
a/=10;
b/=10;
}
if(count==0)
cout<<"No carry operation."<<endl;
else
if(count==1)
cout<<"1 carry operation."<<endl;
else
cout<<count<<" carry operations."<<endl;
}
}
扩展知识：
http://wenku.baidu.com/view/a03d3ccfa1c7aa00b52acb46.html
http://www.cnblogs.com/ghost-draw-sign/articles/1533798.html