（一）例题记录
A-人见人爱 A ^ B
求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”
Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。
Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。
Sample Input
2 3
12 6
6789 10000
0 0
Sample Output
8
984
1
理解
为了防止数据过大而采用取模，可直接得出后三位数字。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
while(~scanf("%d%d",&a,&b)){
if(a==0&&b==0) break;
if(b==0) cout << 1 << endl;
if(a==0) cout << 0 << endl;
if(a != 0&& b != 0){
int s = 1;
for(int i = 0;i < b;i++){
s= s * a;
s= s % 1000; //取模运算，防止s过大
}
cout << s << endl;
}
}
return 0;
}
B-人见人爱 A - B
参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）
呵呵，很简单吧？
Input
每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束，不做处理。
Output
针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.
Sample Input
3 3 1 2 3 1 4 7
3 7 2 5 8 2 3 4 5 6 7 8
0 0
Sample Output
2 3
NULL
理解
对a，b两个数组进行比较，若a中有b没有的数字，则存入c数组里，最后输出。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int M = 100 + 5;
void bubble_sort(int*,int);
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
if(n == 0 && m == 0) break;
int a[M],b[M],c[M],i;
for(i = 0;i < n;i++)
scanf("%d",&a[i]);
for(i = 0;i < m;i++)
scanf("%d",&b[i]);
int y=0;
for(i = 0;i < n;i++){
int x=0;
for(int j = 0;j < m;j++){
if(a[i] == b[j])
x++; //当两个数组中没有相同的数字时，x=0，进入下个判断
}
if(x == 0){
c[y] = a[i]; //将得到的目标存入新数组中
y++;
}
}
//若y==0，表示c数组为空，即a有的b都有
if(y == 0){
printf("NULL\n");
continue;
}
sort(c,y + c);
for(i = 0;i < y;i++){
if(i == y - 1)
printf("%d \n",c[i]);
else
printf("%d ",c[i]);
}
}
return 0;
}
C-Number Sequence（HDU-1005）
Problem Description
A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
Output
For each test case, print the value of f(n) on a single line.
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5
理解
为何要取模还是无法理解
AC代码
#include<stdio.h>
int arr[10000];
int main()
{
int A,B,n;
arr[1] = arr[2] = 1;
while(~scanf("%d %d %d",&A,&B,&n))
{
if(A == 0&&B == 0&&n==0) break;
int i;
for(i=3; i<10000 ;i++)
{
arr[i] = (A*arr[i-1] + B*arr[i-2]) % 7;
if(arr[i] == 1 && arr[i-1] == 1)
break;
}
n = n % (i-2); //取模
arr[0] = arr[i-2];
printf("%d\n",arr[n]);
}
return 0;
}
D-Fibonacci Again（HDU-1021）
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).
Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
Output
Print the word “yes” if 3 divide evenly into F(n).
Print the word “no” if not.
Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no
理解
关键之处还是在于取模
AC代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[1000001];
a[0] = 7;
a[1] = 11;
for(int i = 2;i < 1000001;i++){
a[i] = a[i-1]+a[i-2];
a[i] %= 3; //取模防止数组过大
}
int n;
while(~scanf("%d",&n)){
if(a[n] % 3 == 0)
printf("yes");
else
printf("no");
printf("\n");
}
}
E-Rightmost Digit 最右边的数（HDU-1061）
Given a positive integer N, you should output the most right digit of N^N.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).
Output
For each test case, you should output the rightmost digit of N^N.
Sample Input
2
3
4
Sample Output
7
6
Hint
In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.
理解
这道题可以先试着找出规律，找到最右边数字的规律之后，存进数组中进行打表输出结果。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int x;
int a[10] = {0,1,4,7,6,5,6,3,6,9};
int b[10] = {0,1,6,3,6,5,6,7,4,9};
cin >> x ;
while(x--){
int n;
cin >> n;
//对输入的数进行取模运算
if((n/10)%2 == 0) cout << a[n%10] << endl;
if((n/10)%2 != 0) cout << b[n%10] << endl;
}
return 0;
}
F-多项式求和 （HDU-2011）
多项式的描述如下：
1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + …
现在请你求出该多项式的前n项的和。
Input
输入数据由2行组成，首先是一个正整数m（m<100），表示测试实例的个数，第二行包含m个正整数，对于每一个整数(不妨设为n,n<1000），求该多项式的前n项的和。
Output
对于每个测试实例n，要求输出多项式前n项的和。每个测试实例的输出占一行，结果保留2位小数。
Sample Input
2
1 2
Sample Output
1.00
0.50
理解
控制好每项的正负值是该题的重点，可根据项数的奇偶性来确定。
AC代码
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
int n,x;
double sum,k;
cin >> n;
while(n--){
sum = 0;
cin >> x;
for(int i = 1;i <= x;i++){
k = 1.0 / i;
if(i % 2 == 0){
k = k * (-1);
}
sum = sum + k;
}
printf("%.2lf\n",sum);
}
return 0;
}
F-The 3n + 1 problem （3n+1问题）HDU-1032
Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n <- 3n + 1
5. else n <- n / 2
6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no opperation overflows a 32-bit integer.。
Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
理解
首先要对a，b两个数字进行排序，然后建立一个从min 到 max的循坏，代表对a-b所有的数字进行遍历。
按照题目要求写个判断，最后输出最小的循环次数。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long a,b,max,min;
while(~scanf("%lld%lld",&a,&b))
{
long long i,flag,t,max0 = 0;
if(a > b)
{
max = a;
min = b;
}
else{
max = b;
min = a;
}
for(i = min;i<=max;i++)
{
flag = 1;
t = i;
while(t > 1)
{
if(t % 2 == 0)
t = t / 2;
else
t = t * 3 + 1;
flag++;
}
if(max0<=flag)
max0 = flag;
}
printf("%d %d %d",a,b,max0);
printf("\n");
}
return 0;
}
F-整除的尾数（HDU-2099）
一个整数，只知道前几位，不知道末二位，被另一个整数除尽了，那么该数的末二位该是什么呢？
Input
对应每组数据，将满足条件的所有尾数在一行内输出，格式见样本输出。同组数据的输出，其每个尾数之间空一格，行末没有空格。
Output
对于每个测试实例n，要求输出多项式前n项的和。每个测试实例的输出占一行，结果保留2位小数。
Sample Input
200 40
1992 95
0 0
Sample Output
00 40 80
15
理解
本题要求写出最后的两位数，我们只需将题目给我们的数乘100之后再加上0-99直接的数字，
看是否能被给定的数字整除即可。值得注意的是，题目要求结尾没有空格，所以需要加一个flag来控制空格
的输出。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b,j = 0,x,f = 0;
while(~scanf("%d%d",&a,&b))
{
if(a==0&&b==0)
break;
f = 0; //定义初始值为0，为了区分第一个数，即如果只有一个结果就不输出空格，反之输出
for(int i = 0;i < 100;i++){
x = a * 100 + i;
if(x % b == 0){
if(f) //如果f ！= 0就执行
printf(" ");
printf("%02d",i);
f++;
}
}
printf("\n");
}
return 0;
}
F-WERTYU
A common typing error is to place the hands on the keyboard one row to the right of the correct position. So ‘Q’ is typed as ‘W’ and ‘J’ is typed as ‘K’ and so on. You are to decode a message typed in this manner.
Input
Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except
Q, A, Z), or punctuation shown above [except back-quote (‘)]. Keys labelled with words [Tab, BackSp,
Control, etc.] are not represented in the input.
Output
You are to replace each letter or punction symbol by the one immediately to its left on the ‘QWERTY’
keyboard shown above. Spaces in the input should be echoed in the output.
Sample Input
O S, GOMR YPFSU/
Sample Output
I AM FINE TODAY.
理解
简单的打表法
AC代码
#include <bits/stdc++.h>
using namespace std;
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int main(){
char c;
while((c=getchar()) != EOF){
char *p = strchr(s,c);
if(!p)
putchar(c);
else putchar (s[p-s-1]);
}
return 0;
}
F-Lomar Mass（摩尔质量）UVA-1586
An organic compound is any member of a large class of chemical compounds whose molecules contain carbon. The molar mass of an organic compound is the mass of one mole of the
organic compound. The molar mass of an organic compound can be computed from the standard atomic weights of the elements. When an organic compound is given as a molecular formula, Dr. CHON wants to find its molar mass. A molecular formula, such as C3H4O3, identifies each constituent element by its chemical symbol and indicates the number of atoms of each element found in each discrete molecule of that compound. If a molecule contains more than one atom of a particular element, this quantity is indicated using a subscript after the chemical symbol. In this problem, we assume that the molecular formula is represented by only four elements, ‘C’
(Carbon), ‘H’ (Hydrogen), ‘O’ (Oxygen), and ‘N’ (Nitrogen) without parentheses. The following table shows that the standard atomic weights for ‘C’, ‘H’, ‘O’, and ‘N’
For example, the molar mass of a molecular formula C6H5OH is 94.108 g/mol which is computed by
6 × (12.01 g/mol) + 6 × (1.008 g/mol) + 1 × (16.00 g/mol).
Given a molecular formula, write a program to compute the molar mass of the formula
Input
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case is given in a single line, which contains a molecular formula as a string. The chemical symbol is given by a capital letter and the length of the string is greater than 0 and less than 80. The quantity number n which is represented after the chemical symbol would be omitted when the number is 1 (2 ≤ n ≤ 99).
Output
Your program is to write to standard output. Print exactly one line for each test case. The line should contain the molar mass of the given molecular formula.
Sample Input
4
C
C6H5OH
NH2CH2COOH
C12H22O11
Sample Output
12.010
94.108
75.070
342.296
理解
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
char s[100+5];
scanf("%s",s);
int len = strlen(s);
double ans = 0.0;
int wei = 1;
int shu = 1;
for(int i = len - 1;i >= 0;i--){
if(s[i] == 'C'){
ans += shu*12.01;
wei = 1;
shu = 1;
}
else if(s[i] == 'H' ){
ans += shu*1.008;
wei = 1;
shu = 1;
}
else if(s[i] == 'O' ){
ans += shu*16.00;
wei = 1;
shu = 1;
}
else if(s[i] == 'N' ){
ans += shu*14.01;
wei = 1;
shu = 1;
}
else {
int a = s[i] - '0';
if(wei == 1){
shu = a;
wei = 2;
}
else{
shu = shu + a * 10;
}
}
}
printf("%.3lf\n",ans);
}
return 0;
}
F-Digit counting UVA-1225
Trung is bored with his mathematics homeworks. He takes a piece of chalk and starts writing a sequence
of consecutive integers starting with 1 to N (1 < N < 10000). After that, he counts the number of
times each digit (0 to 9) appears in the sequence. For example, with N = 13, the sequence is:
12345678910111213
In this sequence, 0 appears once, 1 appears 6 times, 2 appears 2 times, 3 appears 3 times, and each
digit from 4 to 9 appears once. After playing for a while, Trung gets bored again. He now wants to
write a program to do this for him. Your task is to help him with writing this program.
Input
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets. For each test case, there is one single line containing the number N.
Output
For each test case, write sequentially in one line the number of digit 0, 1, . . . 9 separated by a space.
数。
Sample Input
2
3
13
Sample Output
0 1 1 1 0 0 0 0 0 0
1 6 2 2 1 1 1 1 1 1
理解
题目大意是算1...n中，1-9出现的次数。所以建一个空数组a[10]保存每个数出现的次数，
然后对x取模得到个位数，该个位数对应的下标加一，以此类推最后得到每个下标即每个数字出现的次数。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,t;
cin >> n;
while(n--){
int m;
cin >> m;
int a[10] = {0};
for(int i = 1;i <= m;i++){
int x;
x = i;
while(x>0){
t = x%10;//取模
a[t]++;//出现一次下标，对应的数组加一
x /= 10;//整除十以得个位数
}
}
cout << a[0]; //防止结尾有空格，所以先输出a[0]
for(int i = 1;i < 10;i++){
cout << ' ' << a[i];
}
cout << endl;
}
}
F- All in All（UVA - 10340 ）
You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string. Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.
Input
The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace. Input is terminated by EOF.
Output
For each test case output, if s is a subsequence of t.
Sample Input
sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter
Sample Output
Yes
No
Yes
No
理解
本题题意是在数组b中查找数组a的元素，若数组b中全包含数组a中的元素，则输出“yes” ，否则输出“no”。
首先定义两个数组再对两个数组进行比较。
AC代码
#include<bits/stdc++.h>
using namespace std;
#include<string.h>
char a[100001],b[100001];
int main(){
int len1,len,i,f,j;
while(scanf("%s%s",a,b) !=EOF ){
i = 0;
f = 0;
len = strlen(a);
len1 = strlen(b);
for(j = 0;j < len1;j++){
if(b[j] == a[i]&&i<len){
f++;//记录相同元素的个数
i++;
}
}
if(f == len) //相同元素若等于a数组的长度，则表示b中含有a的全部元素
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
F-Together （AtCoder - 3524）
You are given an integer sequence of length N, a1,a2,…,aN.
For each 1≤i≤N, you have three choices: add 1 to ai, subtract 1 from ai or do nothing.
After these operations, you select an integer X and count the number of i such that ai=X.
Maximize this count by making optimal choices.
Input
The input is given from Standard Input in the following format:
N
a1 a2 … aN
Output
Print the maximum possible number of i such that ai=X.
Sample Input 1
7
3 1 4 1 5 9 2
Sample Output 1
4
For example, turn the sequence into 2,2,3,2,6,9,2 and select X=2 to obtain 4, the maximum possible count.
Sample Input 2
10
0 1 2 3 4 5 6 7 8 9
Smaple Output 2
3
Sample Input 3
1
99999
Sample Output 3
1
理解
题目大意是给定一个a位数，可以对a1～aN的每位数数进行加一或减一操作，最后得出的新的a位数，求新
数列里出现最多的数字的次数。
AC代码
#include<bits/stdc++.h>
using namespace std;
int b[1000005];
int main()
{
int n;
memset(b,0,sizeof(b));
cin >> n;
int a[n],max = 0;
for(int i = 0;i < n;i++){
cin >> a[i];
if(max < a[i])
max = a[i];//求出数组里最大值，防止下面循环次数过多
b[a[i]]++;
b[a[i]-1]++;
b[a[i]+1]++;
}
int max1 = 0;
for(int i = 0;i <= max + 1;i++){
if(max1 < b[i])
max1 = b[i];
}
cout << max1;
return 0;
}