字符串处理题目
SGU 127: Telephone directory
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=127
题目大意：
一个同学要做一本电话簿，电话号码有四个数字组成，开头不含0和8，封面和说明用了2页，每页不能超过K个号码，每个新号码为第一个数字的要另起一页，每个号码按照递增顺序。给你n个号码，问最少需要用多少页纸。
解题思路：
因为页码只跟每个开头数字的号码数量有关，比如1开头的号码有7个，每页最大号码数是5，那么1开头的号码要用2页，每个数字开头的都算出来，然后加上2页封面和说明就是答案。
解题代码：
#include<iostream>
#include<cstring>
using namespace std;
int s[10];
int main(){
int k,n;
while(cin>>k>>n){
int t;
memset(s,0,sizeof(s));
while(n--){
cin>>t;
s[t/1000]++;
}
int sum=0;
for(int i=1;i<10;i++){
if(s[i]%k)
sum+=s[i]/k+1;
else
sum+=s[i]/k;
}
sum+=2;
cout<<sum<<endl;
}
}
SGU 112：a^b-b^a
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=112
题目大意：
输入a,b输出a^b-b^a的值。（1<=a,b<=100）
解题思路：
肯定是用高精度算法，可是比较懒阿，先用JAVA写一个，然后C++的以后写吧。
解题代码：
import java.math.*;
import java.io.*;
import java.util.*;
public class Solution{
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
int a,b;
while(cin.hasNext()){
a=cin.nextInt();
b=cin.nextInt();
System.out.println(BigInteger.valueOf(a).pow(b).subtract(BigInteger.valueOf(b).pow(a)));
}
}
}
扩展知识：http://blog.csdn.net/soberman/archive/2009/03/10/3978074.aspx
SGU 113: Nearly prime numbers
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=113
题目大意：
如果一个数可以分解成2个素数的乘积，那么就输出yes否则输出no.
解题思路：
先筛选出素数，然后判断找到那个能整除这个数的素数，判断商是否为素数就行啦！起先题目给看错了以为是相邻的素数的积。
解题代码：
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define Max 50000
bool isprime[Max];
int prime[Max];
int cp;
void mkprime(){
cp=1;
memset(isprime,true,Max);
prime[0]=2;
for(int i=2;i<Max;i++){
if(isprime[i]==true){
prime[cp++]=i;
for(int j=1;i*j<Max;j++)
isprime[i*j]=false;
}
}
}
bool isp(int n){
if(n==1) return false;
if(((n!=2)&&!(n%2))||((n!=3)&&!(n%3))||
((n!=5)&&!(n%5))||((n!=7)&&!(n%7)))
return false;
int t=sqrt(n);
for(int i=2;i<t;i++)
if(n%i==0)
return false;
return true;
}
int main(){
mkprime();
int cas;
cin>>cas;
while(cas--){
int n;
cin>>n;
int flag=0;
for(int i=0;i<cp;i++){
if(n%prime[i]==0)
if(isp(n/prime[i])){
flag=1;
break;
}
}
if(flag)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
SGU 107: 987654321 problem
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=107
题目大意：
求出多少个N位数的平方末尾是987654321。
解题思路：
因为末尾多少是跟后几位相乘有关的，所以先试探一些值，9位以下都没有解，9位有8个，10位有8*9个，递推下去11位以上就是8*9*（n-10）个。因为n的范围是10^6，所以用公式不能算，会溢出，这里用了一个小技巧，因为后面都是0，所以算10位后面就直接输出输出72然后加上(n-10)个0。
解题代码：
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
if(n<9)
cout<<0<<endl;
else if(n==9)
cout<<8<<endl;
else if(n==10)
cout<<72<<endl;
else{
cout<<72;
for(int i=1;i<=n-10;i++)
cout<<0;
cout<<endl;
}
return 0;
}
扩展知识：http://blog.csdn.net/ZERO2046/archive/2007/05/20/1618507.aspx
SGU 184: Patties
题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=184
题目大意：
一个人喜欢办Party,家里有3种东西，知道要举办一个party每种东西需要的量，问家里的东西能过举办几场party.
解题思路：
分别求出每种东西能办几场，最小的值就是答案。
解题代码：
#include<iostream>
using namespace std;
int main(){
int p,m,c,k,r,v;
while(cin>>p>>m>>c>>k>>r>>v){
int a=p/k,b=m/r,d=c/v;
int n=a;
if(n>b) n=b;
if(n>d) n=d;
cout<<n<<endl;
}
return 0;
}