杭电ACM基础题（2352、2549、2564、2565、2567、2572、2609、2607、2707、2708、2719、2721、2723）

2352、Verdis Quo[将罗马数字转化为十进制数字]

The Romans used letters from their Latin alphabet to represent each of the seven numerals in their number system. The list below shows which
letters they used and what numeric value each of those letters represents:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
Using these seven numerals, any desired number can be formed by following the two basic additive and subtractive rules. To form a number using
the additive rule the Roman numerals are simply written from left to right in descending order, and the value of each roman numeral is added
together. For example, the number MMCLVII has the value 1000 + 1000 + 100 + 50 + 5 + 1 + 1 = 2157. Using the addition rule alone could lead to
very long strings of letters, so the subtraction rule was invented as a result. Using this rule, a smaller Roman numeral to the left of a larger one is
subtracted from the total. In other words, the number MCMXIV is interpreted as 1000 - 100 + 1000 + 10 - 1 + 5 = 1914.

Over time the Roman number writing system became more standardized and several additional rules were developed. The additional rules used today
are:

1. The I, X, or C Roman numerals may only be repeated up to three times in succession. In other words, the number 4 must be represented as IV
   and not as IIII.
2. The V, L, or D numerals may never be repeated in succession, and the M numeral may be repeated as many 2. times as necessary.
3. Only one smaller numeral can be placed to the left of another. For example, the number 18 is represented as XVIII but not as XIIX.
4. Only the I, X, or C can be used as subtractive numerals.
5. A subtractive I can only be used to the left of a V or X. Likewise a X can only appear to the left of a L or C, and a C can only be used to the
   left of a D or M. For example, 49 must be written as XLIX and not as IL.

Your goal is to write a program which converts Roman numbers to base 10 integers.
Input
The input to this problem will consist of the following:
A line with a single integer “N” (1 ≤ N ≤ 1000), where N indicates how many Roman numbers are to be converted.
A series of N lines of input with each line containing one Roman number. Each Roman number will be in the range of 1 to 10,000 (inclusive)
and will obey all of the rules laid out in the problem’s introduction.
Output
For each of the N Roman numbers, print the equivalent base 10 integer, one per line.
Sample Input

3
IX
MMDCII
DXII

Sample Output

9
2602
512

Code:

/*将罗马数字转化为十进制数 I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000 注意当输入的罗马数字，左边的数字比右边小时为负数 */ 
#include<iostream>
#include<cstring>
using namespace std;
char c[10000];
int num[10000];
int main(){
    int t;cin>>t;while(t--){
    cin>>c;int len=strlen(c);int j=0;//将输入的各个罗马数字存储在int数组 for(int i=0;i<len;i++){
    switch(c[i]){
    case 'I':num[j++]=1;break;case 'V':num[j++]=5;break;case 'X':num[j++]=10;break;case 'L':num[j++]=50;break;case 'C':num[j++]=100;break;case 'D':num[j++]=500;break;case 'M':num[j++]=1000;break;}}//遍历num[]数组int sum=0;if(j==1){
    cout<<num[0]<<endl;continue;}for(int i=0;i<j-1;i++){
    if(num[i]<num[i+1]){
    sum+=(-1)*num[i];}if(num[i]>=num[i+1]){
    sum+=num[i];}if(i+1==j-1){
    sum+=num[i+1];}} cout<<sum<<endl;}return 0; 
}

2549、让你算出小数点后第n位是什么

问题是这样的：给你一个小数x，让你算出小数点后第n位是什么，(1 <= n <= 6)
Input
首先输入一个t,表示有t组数据，跟着t行：
每行输入一个小数（输入数据保证一定是a.b的形式,为了简单化问题，没有循环小数的情况）
然后跟一个n,表示小数点后第几位
Output
输出一个数表示小数点后第n位的数
Sample Input

3
1.234 1
2.345 2
3.456 3

Sample Output

2
4
6

Code

//输出小数点后的第n位数字
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char a[100];
int main(){
    int t;cin>>t;while(t--){
    int n;cin>>a>>n;string s="";s=strstr(a,".");//返回a字符串中.首次出现的地址，此处返回.（包含）之后的字符串 int len=s.size();if(len>=7) cout<<s[n]<<endl;//小数位数不足6位以0补足 else if(n<=len-1){
    cout<<s[n]<<endl;}else{
    cout<<0<<endl;}}return 0;
} 

2564、词组缩写

定义：一个词组中每个单词的首字母的大写组合称为该词组的缩写。
比如，C语言里常用的EOF就是end of file的缩写。
Input
输入的第一行是一个整数T，表示一共有T组测试数据；
接下来有T行，每组测试数据占一行，每行有一个词组，每个词组由一个或多个单词组成；每组的单词个数不超过10个，每个单词有一个或多个大写或小写字母组成；
单词长度不超过10，由一个或多个空格分隔这些单词。
Output
请为每组测试数据输出规定的缩写，每组输出占一行。
Sample Input

1
end of file 

Sample Output

EOF

Code

//词组缩写-一个词组中每个单词的首字母的大写组合称为该词组的缩写
#include<iostream>
#include<string>
#include<string.h>
#include<cstring>
using namespace std;
char b[100];
int main(){
    int t;cin>>t;getchar();//吸收回车符 while(t--){
    string a;getline(cin,a);int len=a.size();bool flag=true;//将缩写后的字符存在b[]中 int num=0;for(int i=0,j=0;i<len;i++){
    if(a[i]==' '){
    flag=true;continue;}else if(flag==true){
    num++;if(a[i]>='a'&&a[i]<='z')b[j]=a[i]-32;elseb[j]=a[i];j++;flag=false;}}for(int i=0;i<num;i++){
    cout<<b[i];} cout<<endl;}return 0;
} 

2565、放大的X[画图]

请你编程画一个放大的’X’。
如3*3的’X’应如下所示：

X X
X
X X

5*5的’X’如下所示：
X X
X X
X
X X
X X
Input
输入数据第一行是一个整数T，表示有T组测试数据；
接下来有T行，每行有一个正奇数n（3 <= n <= 79），表示放大的规格。
Output
对于每一个n打印一个规格为n * n放大的’X’；每组输出后面空一行。
Sample Input

2
3
5 

Sample Output

X XX
X XX   XX XXX X
X   X

Code

//输出大大的X
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n,num=0;cin>>n;for(int i=0;i<n;i++){
    num=0;for(int j=0;j<n;j++){
    if(i==j||(i+j)==n-1){
    cout<<"X";num++;//控制每行最后一个X后无空格 if(i!=n/2&&num==2){
    break;}else if(i==n/2&&num==1){
    break;}}else{
    cout<<" ";}}cout<<endl;}cout<<endl;}return 0;
} 

2567、将第二个字符串插入第一个字符串中央

有2行字符串，其中第一个串的长度为偶数，现在要求把第2个串插入到第一个串的正中央，如此便能开启墓碑进入墓中。
Input
输入数据首先给出一个整数n，表示测试数据的组数。
然后是n组数据，每组数据2行，每行一个字符串，长度大于0，小于50，并且第一个串的长度必为偶数。
Output
请为每组数据输出一个能开启古墓的字符串，每组输出占一行。
Sample Input

2
HDCM
UA
Aw
CFlo

Sample Output

HDUACM
ACFlow

Code
方法一

//输入两个字符串，将第二个字符串插入第一个字符串正中央
#include<iostream>
#include<string>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    string s1,s2,str1="",str2="",s="";cin>>s1>>s2;int len=s1.size();for(int i=0;i<len;i++){
    if(i<len/2){
    str1+=s1[i];}else{
    str2+=s1[i];}}s=str1+s2+str2;cout<<s<<endl;}return 0;
} 

方法二：利用sbustr()函数

//输入两个字符串，将第二个字符串插入第一个字符串正中央
#include<iostream>
#include<string>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    string s1,s2,s="";cin>>s1>>s2;int len=s1.size();s=s1.substr(0,len/2)+s2+s1.substr(len/2,len/2);cout<<s<<endl;}return 0;
} 

2572、查找包含子串的字符串

给出三个字符串,说出第一串的某个子串，要求该子串长度最小，并且同时包含第2个串和第3个串，如果有多个这样的子串，则输出字母序最小的那一个
Input
输入数据首先是一个整数C，表示测试数据有C组；
接着是C组数据，每组包含三行字符串，第一个字符串长度大于1小于100
后面两个串的长度大于1且小于10
Output
请对应每组输入数据输出满足条件的最短子串；
如果没有，请输出 No
Sample Input

2
abcd
ab
bc
abc
ab
bd

Sample Output

abc
No

Code

/*给出三个字符串,说出第一串的某个子串，要求该子串长度最小，并且同时包含第2个串和第3个串 如果有多个这样的子串，则输出字母序最小的那一个 思路：将第一个子串暴力找到所有连续的子串，每次判断该子串中是否包含子串2和子串3 */
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    string s1,s2,s3,str,s;cin>>s1>>s2>>s3;int len=s1.size();if(s1.find(s2)==-1||s1.find(s3)==-1){
    cout<<"No"<<endl;continue;} str=s1;for(int i=0;i<len;i++){
    //遍历s1字符串 for(int j=i+1;j<=len;j++){
    s=s1.substr(i,j-i);//找到从i位置起，长度为j-i的子串 if(s.find(s2)!=-1&&s.find(s3)!=-1){
    //返回-1，说明s中不存在s2和s3的子串 if(s.size()<str.size()){
    str=s;}else if(s.size()==str.size()){
    //如果有多个这样的子串，则输出子母序最小的那一个 //如：同时str=bca,s=abc，则输出abc; if(s<str)str=s;}} } }cout<<str<<endl;}return 0;
} 

2609、How many[计数多少相同的字符串]

Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me
How many kinds of necklaces total have.(if two necklaces can equal by rotating ,we say the two necklaces are some).
For example 0110 express a necklace, you can rotate it. 0110 -> 1100 -> 1001 -> 0011->0110.
Input
The input contains multiple test cases.
Each test case include: first one integers n. (2<=n<=10000)
Next n lines follow. Each line has a equal length character string. (string only include ‘0’,‘1’).
Output
For each test case output a integer , how many different necklaces.
Sample Input

4
0110
1100
1001
0011
4
1010
0101
1000
0001

Sample Output

1
2

Code:

/*输出有多少种不同的字符串，注意：字符串可以旋转 思路：最小表示法+set去重 最小表示法：用来处理字符串的重复问题 */ 
#include<iostream>
#include<string>
#include<set> 
using namespace std;int minshow(string str){
    int i=0,j=1,k=0;int len=str.size();while(i<len&&j<len&&k<len){
    int t=str[(i+k)%len]-str[(j+k)%len];if(t==0){
    k++;    }else{
    if(t>0) i=i+k+1;else j=j+k+1;if(i==j){
    j++;}k=0;}}return i<j?i:j;
}int main(){
    string str,s;set<string> st;int n,min;while(cin>>n){
    while(n--){
    cin>>str;min=minshow(str);//寻找字符串的最小表示法 s=str.substr(min,str.size()-min)+str.substr(0,min);st.insert(s);}cout<<st.size()<<endl;st.clear();}return 0;
}

2607、Let the Balloon Rise II[异或运算]

I knew you had solved the HDOJ 1004 Let the Balloon Rise already, so please settle the another version quickly. I have a lot of balloons and each has a color and I give each of them a number, same color has the same number. For example, red balloon is No.1, pink is No.2, black is No.3 . etc. I also have many rooms to store all the balloons.
There are some rules :

1. Every room stores several balloons but no two have the same color.
2. Collect all the balloons, we can find each color has even number of times of balloons except one.

Your task is to find which is the odd color and calculate its number of times.
Input
Input file consists from multiple data sets separated by one or more empty lines.
Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.
Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of No.X, X+Z, X+2Z, X+3Z, …, X+KZ, …(while (X+KZ)<=Y). This line represents that in this room there exists (K+1) balloons whose No. is No.X, No.X+Z, No.X+2Z, No.X+3Z, …, No.X+K*Z, …etc.
Output
For each input data set you should print to standard output new line of text with two integers separated by single space (first one is No. that occurs odd number of times and second one is count of that kind of balloon).
If all have even number of times output “None.”
Sample Input

1 10 1
1 10 11 5 1
6 10 1
1 10 1
4 4 11 5 1
2 5 1
2 5 1
2 5 1

Sample Output

None.
4 3
1 1

Code

/* 题目理解： 给定一种数据压缩的格式 给定n组数据，求所有数中出现次数为奇数的唯一一个数是多少以及出现的次数，或者所有数出现次数均为偶数 如：给出的4组数据为 1 5 1 代表该房间存储的气球的颜色其标号：1 2 3 4 5 6 10 1 代表的标号：6 7 8 9 10 1 10 1 代表的标号：1 2 3 4 5 6 7 8 9 10 4 4 1 代表的标号：4 统计：1出现的次数为2（偶数个）,2出现的次数为2（偶数个）...4出现的个数为奇数个且其个数为3故输出4 3 思路：异或，因为标记为偶数个数的异或之后必为0，所以当出现标号为奇数个时，异或之后所保留的就是该奇数个的标号 然后就查找该标号的个数 输入输出：输入要求以空行作为输出标志，并且两组数据之间可能有多个空行 */ 
#include<iostream>
#include<cstring>
using namespace std;
int a[50010],b[50010],c[50010];
char s[100]; 
int main(){
    int i=0,m=0,num;bool flag;//区分是第几次输入的空格 while(gets(s)!=NULL){
    //等于空意味着什么都没有输入 //输入的不是空行 if(s[0]>='0'&&s[0]<='9'){
    flag=1; //sscanf()会将参数str的字符串根据参数format字符串来转换并格式化数据。转换后的结果存于对应的参数内。sscanf(s,"%d %d %d",&a[i],&b[i],&c[i]);for(int j=a[i];j<=b[i];j+=c[i]){
    m^=j;}i++;}//输入的是空行，此时进行输出 else{
     //flag为1，说明之前输入的不是空行，要开始输出之前的输入 if(flag==1){
    //说明都为偶数个if(m==0){
     cout<<"None."<<endl; } //m即为值为奇数个的数，遍历，计算m的个数 else{
    int n=i;//n代表共输入有多少行数 num=0;//查找值为m的个数 for(int i=0;i<n;i++){
    for(int j=a[i];j<=b[i];j+=c[i]){
    if(j==m){
    num++;}}}cout<<m<<" "<<num<<endl; }    } i=0;m=0;flag=0; }}if(flag==1){
    //说明都为偶数个if(m==0){
     cout<<"None."<<endl; } //m即为值为奇数个的数，遍历，计算m的个数 else{
    int n=i;//n代表共输入有多少行数 num=0;//查找值为m的个数 for(int i=0;i<n;i++){
    for(int j=a[i];j<=b[i];j+=c[i]){
    if(j==m){
    num++;}}}cout<<m<<" "<<num<<endl; }    } return 0;
} 

2707、Steganography[字符串解密]

In cryptography, the goal is to encrypt a message so that, even if the the message is intercepted, only the intended recipient can decrypt it. In steganography, which literally means “hidden writing”, the goal is to hide
the fact that a message has even been sent. It has been in use since 440 BC. Historical methods of steganography include invisible inks and tatooing messages on messengers where they can’t easily be seen. A modern method is to encode a message using the least-significant bits of the RGB color values of pixels in a digital image.
For this problem you will uncover messages hidden in plain text. The spaces within the text encode bits; an odd number of consecutive spaces encodes a 0 and an even number of consecutive spaces encodes a 1. The
four texts in the example input below (terminated by asterisks) encode the following bit strings: 11111, 000010001101101, 01, and 000100010100010011111. Each group of five consecutive bits represents a
binary number in the range 0–31, which is converted to a character according to the table below. If the last group contains fewer than five bits, it is padded on the right with 0’s.
" " (space) 0
“A” – “Z” 1–26
“’” (apostrophe) 27
“,” (comma) 28
“-” (hyphen) 29
“.” (period) 30
“?” (question mark) 31
The first message is 111112 = 3110 = “?”. The second message is (00001, 00011, 01101)2 = (1, 3, 13)10 =
“ACM”. The third message is 010002 = 810 = “H”, where the underlined 0’s are padding bits. The fourth message is (00010, 00101, 00010, 01111, 10000)2 = (2, 5, 2, 15, 16)10 = “BEBOP”.
Input
The input consists of one or more texts. Each text contains one or more lines, each of length at most 80 characters, followed by a line containing only “" (an asterisk) that signals the end of the text. A line containing only “#” signals the end of the input. In addition to spaces, text lines may contain any ASCII letters, digits, or punctuation, except for "” and “#”, which are used only as sentinels.
Output
For each input text, output the hidden message on a line by itself. Hidden messages will be 1–64 characters long.
Note: Input text lines and output message lines conform to all of the whitespace rules listed in item 7 of Notes to Teams except that there may be consecutive spaces within a line. There will be no spaces at the beginning or end of a line.
Sample Input

Programmer,
I  would  like  to  see
a  question
mark.
*
Behold, there is more to  me than you might
think  when  you read  me  the first  time.
*
Symbol for  hydrogen?
*
A B C D  E F G H  I J  K L M N  O P Q  R  S  T  U  V
*
#

Sample Output

?
ACM
H
BEBOP

Code

/* 寻找输入的多行字符串中，单词之间空格的数量，若为奇数则编码为0，若为偶数，编码为1，然后每5位转化为一个十进制数 按给定规则进行解密 思路： 1、输入字符串，每两个单词之间统计一次空格数量，将其编码的值存在一个字符数组中 2、若该字符数组的大小是5的倍数，则直接将其每五位转化为一个10进制数，存在一个整型数组中 3、若该字符数组的大小不是5的倍数，则将其右边添0到5的倍数，同2 4、根据解密规则，对整型数组中存的每一位值进行解密 */ 
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
char a[1000]; 
int b[100];
int main(){
    string str,s;int j=0,p=0; //j为存储二进制编码的字符数组的下标，p为存储转化为十进制数的数组的下标 while(getline(cin,str)){
    if(str=="#") break;//输入结束，进行输出 if(str=="*"){
    int digit=0;//对a[]补0 if(j%5!=0){
    //需要补的0的数量 int zero=5-j%5;for(int i=j;i<j+zero;i++){
    a[i]='0';}j=j+zero;//此时a的长度 }//将a[]中的值每5位转化为十进制,a数组的长度为j int count=0;for(int k=0;k<j;k++){
    if(k%5==0){
    count++;if(a[k]=='1')digit+=16;elsedigit+=0;}else if(k%5==1){
    count++;if(a[k]=='1')digit+=8;elsedigit+=0;}else if(k%5==2){
    count++;if(a[k]=='1')digit+=4;elsedigit+=0;}else if(k%5==3){
    count++;if(a[k]=='1')digit+=2;elsedigit+=0;}else if(k%5==4){
    count++;if(a[k]=='1')digit+=1;elsedigit+=0;}if(count%5==0){
    b[p]=digit;p++;digit=0;}}//按规则对b[]数组中的值进行解密//输出的字符串首尾不能有空格int i=0;while(b[i]==0){
    i++;}int k=p-1;while(b[k]==0){
    k--;}p=k+1;bool flag=0;for(;i<p;i++){
    flag=1;if(b[i]>=1&&b[i]<=26){
    //将字符转化为字符串 char c='A'+b[i]-1;string str;stringstream stream;stream<<c;s+=stream.str();}else if(b[i]==27){
    s+="'";}else if(b[i]==28){
    s+=",";}else if(b[i]==29){
    s+="-";}else if(b[i]==30){
    s+=".";}else if(b[i]==31){
    s+="?";}else if(b[i]==0){
    s+=" ";}}//注意输出的字符串首尾不能有空格 if(flag==1){
    cout<<s<<endl;}j=0;p=0;s="";continue; }int len=str.size();int num=0;//num用来计算两个单词间空格的数量 for(int i=0;i<len;i++){
    //遇到空格 if(str[i]==' '){
    num++;//两个单词间空格的数量 if(str[i+1]!=' '){
    if(num%2==0){
    a[j]='1';j++;}else{
    a[j]='0';j++;}num=0;//每次统计完两个单词之间的空格数量后将其置为0 }}}//for循环结束，即统计一行单词间空格数量结束 }
} 

2708、Vertical Histogram[直方图]

Write a program to read four lines of upper case (i.e., all CAPITAL LETTERS) text input (no more than 72 characters per line) from the input file and print a vertical histogram that shows how many times each letter (but not blanks, digits, or punctuation) appears in the all-upper-case input. Format your output exactly as shown.
Input

• Lines 1…4: Four lines of upper case text, no more than 72 characters per line.
  Output
• Lines 1…??: Several lines with asterisks and spaces followed by one line with the upper-case alphabet separated by spaces. Do not print unneeded blanks at the end of any line. Do not print any leading blank lines.
  Sample Input

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

Sample Output

                            ***                   **                   *     *   **                   *     *   *
*       *     *             *     *   *
*       *     * *     * *   *     * * *
*       *   * * *     * *   * *   * * * *
*     * * * * * *     * * * * *   * * * *     * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Code

//输入四行字符串，输出一个垂直的直方图表示各个字母出现的次数 
/* 注意：每行最后一个*后不输空格多组测试 */
#include<iostream>
#include<string>
#include<map>
using namespace std;
char a[200][27];
int main(){
    string s1,s2,s3,s4;while(getline(cin,s1)){
    getline(cin,s2);getline(cin,s3);getline(cin,s4);int len1=s1.size();int len2=s2.size();int len3=s3.size();int len4=s4.size();//利用map数组存放各个字母的数量map<char,int>m; //初始化map数组 for(int i=0;i<26;i++){
    m['A'+i]=0;}//遍历第一个字符串,统计出第一个字符串中各个字母的个数，利用map数组 for(int i=0;i<len1;i++){
    if(s1[i]>='A'&&s1[i]<='Z')m[s1[i]]++;} for(int i=0;i<len2;i++){
    if(s2[i]>='A'&&s2[i]<='Z')m[s2[i]]++;} for(int i=0;i<len3;i++){
    if(s3[i]>='A'&&s3[i]<='Z')m[s3[i]]++;} for(int i=0;i<len4;i++){
    if(s4[i]>='A'&&s4[i]<='Z')m[s4[i]]++;} //找出map中最大的值，即出现的最大次数,即后面要构造的二维数组的行数 int max=0; for(map<char,int>::iterator it=m.begin();it!=m.end();it++){
    if(it->second>max){
    max=it->second;}}//构造一个二维数组 for(int i=0;i<26;i++){
    //共有26列 for(int j=0;j<=max;j++){
    //共有max+1行 if(j<=max-m['A'+i]-1){
    a[j][i]=' ';}else if(j==max){
    a[j][i]=char('A'+i);}else{
    a[j][i]='*';}} }//输出该二维数组,不要输出多余空格 int count;for(int i=0;i<=max;i++){
    count=0;for(int j=0;j<26;j++){
    if(a[i][j]!=' '){
    count++;//统计第i行有几个非空值 }}int t=0;//输出第i行的值 for(int j=0;j<26;j++){
    if(a[i][j]!=' '){
    t++;if(t==count){
    cout<<a[i][j];break;}else if(j==25){
    cout<<a[i][j];}else{
    cout<<a[i][j]<<" ";}}else{
    if(j==25){
    cout<<a[i][j];}else{
    cout<<a[i][j]<<" ";}    }}cout<<endl;}}return 0;
} 

2719、The Seven Percent Solution[字符串]

Uniform Resource Identifiers (or URIs) are strings like http://icpc.baylor.edu/icpc/, mailto:foo@bar.org, ftp://127.0.0.1/pub/linux, or even just readme.txt that are used to identify a resource, usually on the Internet or a local computer. Certain characters are reserved within URIs, and if a reserved character is part of an identifier then it must be percent-encoded by replacing it with a percent sign followed by two hexadecimal digits representing the ASCII code of the character. A table of seven reserved characters and their encodings is shown below. Your job is to write a program that can percent-encode a string of characters.
Character Encoding
" " (space) %20
“!” (exclamation point) %21
“$” (dollar sign) %24
“%” (percent sign) %25
“(” (left parenthesis) %28
“)” (right parenthesis) %29
"" (asterisk) %2a*

Input
The input consists of one or more strings, each 1–79 characters long and on a line by itself, followed by a line containing only “#” that signals the end of the input. The character “#” is used only as an end-of-input marker and will not appear anywhere else in the input. A string may contain spaces, but not at the beginning or end of the string, and there will never be two or more consecutive spaces.
Output
For each input string, replace every occurrence of a reserved character in the table above by its percent-encoding, exactly as shown, and output the resulting string on a line by itself. Note that the percent-encoding for an asterisk is %2a (with a lowercase “a”) rather than %2A (with an uppercase “A”).
Sample Input

Happy Joy Joy!
http://icpc.baylor.edu/icpc/
plain_vanilla
(**)
?
the 7% solution
#

Sample Output

Happy%20Joy%20Joy%21
http://icpc.baylor.edu/icpc/
plain_vanilla
%28%2a%2a%29
?
the%207%25%20solution

Code
方法一：字符转为字符串

/* 按如下规则对输入的字符串进行编码 Character Encoding " " (space) %20 "!" (exclamation point) %21 "$" (dollar sign) %24 "%" (percent sign) %25 "(" (left parenthesis) %28 ")" (right parenthesis) %29 "*" (asterisk) %2a */ 
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
char s[100];
int main(){
    string str,s="";while(getline(cin,str)){
    if(str=="#") break;int len=str.size();int j=0;for(int i=0;i<len;i++){
    switch(str[i]){
    case ' ':s+="%20";break;case '!':s+="%21";break;case '$':s+="%24";break;case '%':s+="%25";break;case '(':s+="%28";break;case ')':s+="%29";break;case '*':s+="%2a";break;default://将字符转为字符串 char c=str[i];string str;stringstream stream;stream<<c;s+=stream.str();}}cout<<s<<endl;s="";}return 0;
} 

方法二、每次直接输出字符

/* 按如下规则对输入的字符串进行编码 Character Encoding " " (space) %20 "!" (exclamation point) %21 "$" (dollar sign) %24 "%" (percent sign) %25 "(" (left parenthesis) %28 ")" (right parenthesis) %29 "*" (asterisk) %2a */ 
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
char s[100];
int main(){
    string str,s="";while(getline(cin,str)){
    if(str=="#") break;int len=str.size();int j=0;for(int i=0;i<len;i++){
    switch(str[i]){
    case ' ':cout<<"%20";break;case '!':cout<<"%21";break;case '$':cout<<"%24";break;case '%':cout<<"%25";break;case '(':cout<<"%28";break;case ')':cout<<"%29";break;case '*':cout<<"%2a";break;default://每次直接输出cout<<str[i]; }}cout<<endl;s="";}return 0;
} 

2721、Persistent Bits[字符串]

WhatNext Software creates sequence generators that they hope will produce fairly random sequences of 16-bit unsigned integers in the range 0–65535. In general a sequence is specified by integers A, B, C, and S, where 1 ≤ A < 32768, 0 ≤ B < 65536, 2 ≤ C < 65536, and 0 ≤ S < C. S is the first element (the seed) of the sequence, and each later element is generated from the previous element. If X is an element of the sequence, then the next element is

(A * X + B) % C

where ‘%’ is the remainder or modulus operation. Although every element of the sequence will be a 16-bit unsigned integer less than 65536, the intermediate result A * X + B may be larger, so calculations should be done with a 32-bit int rather than a 16-bit short to ensure accurate results.

Some values of the parameters produce better sequences than others. The most embarrassing sequences to WhatNext Software are ones that never change one or more bits. A bit that never changes throughout the sequence is persistent. Ideally, a sequence will have no persistent bits. Your job is to test a sequence and determine which bits are persistent.

For example, a particularly bad choice is A = 2, B = 5, C = 18, and S = 3. It produces the sequence 3, (23+5)%18 = 11, (211+5)%18 = 9, (29+5)%18 = 5, (25+5)%18 = 15, (215+5)%18 = 17, then (217+5)%18 = 3 again, and we’re back at the beginning. So the sequence repeats the the same six values over and over:
Decimal 16-Bit Binary
3 0000000000000011
11 0000000000001011
9 0000000000001001
5 0000000000000101
15 0000000000001111
17 0000000000010001
overall 00000000000???1

The last line of the table indicates which bit positions are always 0, always 1, or take on both values in the sequence. Note that 12 of the 16 bits are persistent. (Good random sequences will have no persistent bits, but the converse is not necessarily true. For example, the sequence defined by A = 1, B = 1, C = 64000, and S = 0 has no persistent bits, but it’s also not random: it just counts from 0 to 63999 before repeating.) Note that a sequence does not need to return to the seed: with A = 2, B = 0, C = 16, and S = 2, the sequence goes 2, 4, 8, 0, 0, 0, …
Input
There are from one to sixteen datasets followed by a line containing only 0. Each dataset is a line containing decimal integer values for A, B, C, and S, separated by single blanks.
Output
There is one line of output for each data set, each containing 16 characters, either ‘1’, ‘0’, or ‘?’ for each of the 16 bits in order, with the most significant bit first, with ‘1’ indicating the corresponding bit is always 1, ‘0’ meaning the corresponding bit is always 0, and ‘?’ indicating the bit takes on values of both 0 and 1 in the sequence.
Sample Input

2 5 18 3
1 1 64000 0
2 0 16 2
256 85 32768 21845
1 4097 32776 248
0

Sample Output

00000000000????1
????????????????
000000000000???0
0101010101010101
0???000011111???

Code

/* 给出a、b、c、s。s是初值，每次变化有s = (a*s+b)%c。 如此直到重复。 这些数都表示成二进制，如果某位在所有数都是0则输出0，是1则输出1，如果都有可能输出问号。 如： 3 00000000000 00011 11 00000000000 01011 9 00000000000 01001 5 00000000000 00101 15 00000000000 01111 17 00000000000 1000100000000000 ????1 */
#include<iostream>
#include<cstring>
using namespace std;
int seque[1000000];//存放产生的随机数的数组 
int main(){
    int a,b,c,s;int binary[17]; while(cin>>a){
    if(a==0) break;cin>>b>>c>>s;memset(seque,0,sizeof(seque));int t=s,k=0,j=0;//计算第一个随机数s的二进制表示while(t!=0) {
    binary[k++]=t%2;t=t/2;}for(int i=k;i<16;i++){
    binary[i]=0;//补齐0 } seque[s]=1;//第二个随机数t=(a*s+b)%c; while(seque[t]==0){
    //第一次出现，随机数没有重复k=0; seque[t]=1;//计算下一个数的二进制数，并同上一个作比较 int se=t;while(se!=0){
    int temp=se%2;if(temp!=binary[k]){
    binary[k]=2;}se=se/2;k++;} //t=((a*t)%c+b%c)%c;t=(a*t+b)%c;     } //出现重复，对binary[]倒序输出for(int i=15;i>=0;i--){
    if(binary[i]==2){
    cout<<"?";}else{
    cout<<binary[i];}}cout<<endl; } return 0;
} 

2723、Electronic Document Security[字符串处理]

The Tyrell corporation uses a state-of-the-art electronic document system that controls all aspects of document creation, viewing, editing, and distribution. Document security is handled via access control lists (ACLs). An ACL defines a set of entities that have access to the document, and for each entity defines the set of rights that it has. Entities are denoted by uppercase letters; an entity might be a single individual or an entire division. Rights are denoted by lowercase letters; examples of rights are a for append, d for delete, e for edit, and r for read.

The ACL for a document is stored along with that document, but there is also a separate ACL log stored on a separate log server. All documents start with an empty ACL, which grants no rights to anyone. Every time the ACL for a document is changed, a new entry is written to the log. An entry is of the form ExR, where E is a nonempty set of entities, R is a nonempty set of rights, and x is either “+”, “–”, or “=”. Entry E+R says to grant all the rights in R to all the entities in E, entry E–R says to remove all the rights in R from all the entities in E, and entry E=R says that all the entities in E have exactly the rights in R and no others. An entry might be redundant in the sense that it grants an entity a right it already has and/or denies an entity a right that it doesn’t have. A log is simply a list of entries separated by commas, ordered chronologically from oldest to most recent. Entries are cumulative, with newer entries taking precedence over older entries if there is a conflict.

Periodically the Tyrell corporation will run a security check by using the logs to compute the current ACL for each document and then comparing it with the ACL actually stored with the document. A mismatch indicates a security breach. Your job is to write a program that, given an ACL log, computes the current ACL.
Input
The input consists of one or more ACL logs, each 3–79 characters long and on a line by itself, followed by a line containing only “#” that signals the end of the input. Logs will be in the format defined above and will not contain any whitespace.
Output
For each log, output a single line containing the log number (logs are numbered sequentially starting with one), then a colon, then the current ACL in the format shown below. Note that (1) spaces do not appear in the output; (2) entities are listed in alphabetical order; (3) the rights for an entity are listed in alphabetical order; (4) entities with no current rights are not listed (even if they appeared in a log entry), so it’s possible that an ACL will be empty; and (5) if two or more consecutive entities have exactly the same rights, those rights are only output once, after the list of entities.
Sample Input

MC-p,SC+c
YB=rde,B-dq,AYM+e
GQ+tju,GH-ju,AQ-z,Q=t,QG-t
JBL=fwa,H+wf,LD-fz,BJ-a,P=aw
#

Sample Output

1:CSc
2:AeBerMeYder
3:
4:BHJfwLPaw

Code

/* 为了对一个文件进行访问控制，会给每个文件建立一个访问控制列表（ACL） 每个列表里有若干个entity（类似于用户组），每个entity有若干个right（权限） 给出一个文件的权限更改日志，日志是ExR形式的短语构成 E是这次操作影响的entity（多个），R是right，x是一个操作符，可以为+、-、= 为+的时候表示把权限加到entity上，为-的时候表示从entity减去相应权限，为=的时候表示把entity设为相应权限 最后输出每个entity对应的权限，没有权限的不输出，2个相邻的entity如果有相同的权限，合并输出 */
#include<iostream>
#include<cstring>
using namespace std;
//s存放输入的字符串，temp数组存放实体的字符 
char s[110],temp[110];
//数组Map存放的是实体和权限的对应关系，如Map[0][0]=1,表示实体(0+'A')A具有权限(0+'a')a 
//数组ans存放的是遍历Map数组之后存放其中具有权限的实体 
int Map[70][70],ans[70];
int main(){
    int count=0;while(cin>>s){
    if(strcmp(s,"#")==0) break;count++;int len=strlen(s);int len1=0;memset(Map,0,sizeof(Map));for(int i=0;i<len;i++){
    if(s[i]==','){
    //第一个日志记录完毕 memset(temp,0,sizeof(temp));len1=0; }else if(s[i]=='+'){
    for(int j=i+1;s[j]!=','&&j<len;j++){
    for(int k=0;k<len1;k++){
    Map[temp[k]-'A'][s[j]-'a']=1;}}}else if(s[i]=='-'){
    for(int j=i+1;s[j]!=','&&j<len;j++){
    for(int k=0;k<len1;k++){
    Map[temp[k]-'A'][s[j]-'a']=0;//将实体与权限对应起来 }}}else if(s[i]=='='){
    //重新给实体赋值，故需要现将其之前对应的权限清空 for(int k=0;k<len1;k++){
    memset(Map[temp[k]-'A'],0,sizeof(Map[0]));for(int j=i+1;s[j]!=','&&j<len;j++){
    Map[temp[k]-'A'][s[j]-'a']=1;}}}else{
    temp[len1++]=s[i];}}cout<<count<<":";int no=0,flag;for(int i=0;i<26;i++){
    flag=1;for(int j=0;j<26;j++){
    if(Map[i][j]!=0){
    flag=0;}}//若flag=1,说明该实体没有任何权限，不需要保存该实体 if(flag==0){
    ans[no++]=i;//该数组中存放有权限的实体 }}memset(temp,0,sizeof(temp));len1=0;for(int i=0;i<no;i++){
    int flag=0;if(i!=no-1){
    for(int j=0;j<26;j++){
    if(Map[ans[i]][j]!=Map[ans[i+1]][j]){
    flag=1;}}}//flag==0表示相邻实体有相同的权限 temp[len1++]='A'+ans[i];//相邻实体没有相同的权限 if(flag==1||i==no-1){
    for(int j=0;j<len1;j++){
    cout<<temp[j];//输出实体字符 }memset(temp,0,sizeof(temp));len1=0;for(int j=0;j<26;j++){
    if(Map[ans[i]][j]!=0){
    //实体具有权限 cout<<(char)(j+'a');//输出权限 }}}}cout<<endl;memset(s,0,sizeof(s));}return 0;
}