//ACM/ICPC Seoul 2005,UVa15851 #include <iostream>2 #include <cstring>3 using namespace std;4 int main (void )5 {6 int a;7 cin >>a;8 while (a) 9 {1011 string s; 12 cin >>s;13 int n =s.size (); 14 int num =0,ans =0;15 for (int i =0;i <n;i++)16 { 17 if (s[i] =='O')18 num++; 19 else20 {21 for (int j =1;j <=num;j++) 22 ans +=j;23 num =0; 24 }25 }26 for (int j =1;j <=num;j++) 27 ans +=j;28 cout <<ans <<endl; 29 a--;30 }31 return 0; 32 }3-1 Score2017年10月1日15:00// ACM/ICPC Seoul 2007,UVa15861 #include <iostream>2 #include <cstring>3 #include <cctype>4 #include <iomanip>5 using namespace std;6 const double Mass[] = {0,0,12.01,0,0,0,0,1.008,0,0,0,0,0,14.01,16.00};7 int main (void )8 {9 int n; 10 cin >>n;11 while (n) 12 { 13 string s; 14 double ans =0; 15 cin >>s; 16 for (int i =0;i <s.size ();i++)17 { 18 int num; 19 if (isupper (s[i])) 20 { 21 if (isdigit (s[i+1])) 22 {23 num =s[i+1] -'0'; 24 for (int j =i+2;j <s.size () &&isdigit (s[j]);j++) 25 num =num*10+s[j] -'0'; 26 ans +=num*Mass[s[i] -'A']; 27 } 28 else29 ans +=Mass[s[i] -'A']; 30 } 31 } 32 cout <<setiosflags (ios::fixed) <<setprecision (3) <<ans <<endl; 33 n--; 34 }35 return 0; 36 }3-2 Molar Mass2017年10月1日15:04// ACM/ICPC Danang 2007,UVa12251 #include <iostream>2 #include <cstring>3 using namespace std;4 int main (void )5 {6 int num;7 cin >>num;8 while (num) 9 {10 int s[10];11 memset (s,0,sizeof (s)); 12 int n,LS;13 cin >>n; 14 for (int i =1;i <=n;i++)15 {16 int LS2 =i; 17 while (LS2)18 { 19 LS =LS2%10;20 s[LS]++;21 LS2 /=10; 22 }23 } 24 for (int i =0;i <9;i++)25 cout <<s[i] <<" ";26 cout <<s[9] <<endl; 27 num--;28 } 29 return 0;30 }3-3 Digit Counting2017年10月1日15:06// UVa4551 #include <iostream>2 #include <cstring>3 using namespace std;4 int next1[80];5 void GetNext (int n,const char s[]){ //获取Next 数组，预处理6 int i =0,k = -1; //表示字符长度（位置）7 memset (next1,0,sizeof (next1));8 next1[0] = -1; //字符串的前缀和后缀最大公共长度 9 while (i <n) //n 为主串长度10 {11 if (k == -1||s[i] ==s[k])12 {13 next1[i+1] =k+1; 14 i++;15 k++;16 }17 else18 k =next1[k]; 19 }20 }21 int main (void )22 {23 int num; 24 cin >>num;25 while (num)26 {27 bool out =true ; 28 char s[80];29 cin >>s;30 int n =strlen (s);31 GetNext (n,s);3233 //GetNext 成功获取34 /*35 for(int i = 0;i <= n;i++)36 cout << next1[i] << " ";37 cout << endl;38 */ 39 if (n % (n -next1[n]) ==0&&next1[n] !=0)40 cout <<n -next1[n] <<endl;41 else42 cout <<n <<endl;43 if (num >1) 44 cout <<endl;45 num--;46 }47 return 0;3-4 Periodic Strings2017年10月1日15:0747 return0;48 }// ACM/ICPC World Finals 1993,UVa2271 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #define maxn5 5 using namespace std;6 bool check (int x,int y,int n){7 switch (n)8 { 9 case 1: 10 if (x ==0) 11 return false ; 12 else 13 return true ; 14 break ;15 case 2: 16 if (x ==4) 17 return false ; 18 else 19 return true ; 20 break ; 21 case 3: 22 if (y ==4)23 return false ; 24 else 25 return true ; 26 break ; 27 case 4: 28 if (y ==0) 29 return false ; 30 else31 return true ; 32 break ; 33 } 34 } 35 int main (void ) 36 { 37 int kase =0; 38 while (1)39 { 40 char s[maxn][maxn]; 41 42 for (int i =0;i <5;i++) 43 for (int j =0;j <5;j++) 44 { 45 s[i][j] =getchar ();46 if (s[0][0] =='Z') 47 return 0; 48 if (s[i][j] =='\n') 49 j--; 50 } 51 523-5 Puzzle2017年10月1日15:085253 //成功读入数组54 /*55 cout << endl;56 for(int i = 0;i < 5;i++)57 {58 for(int j = 0;j < 5;j++)59 cout << s[i][j];60 cout << endl;61 }62 */63 int x,y;64 for(int i =0;i <5;i++)65 for(int j =0;j <5;j++)66 if(s[i][j] ==' ')67 {68 x =i;69 y =j;70 }71 // cout << "x: " << x << "y: " << y << endl;72 bool flag =true;73 getchar(); //吃换行符74 while(1)75 {76 char ch;77 if((ch =getchar()) !='\n')78 {79 // cout << "ch: " << ch << endl;80 if(ch =='0')81 break;82 else if(ch =='A'&&check(x,y,1))83 {84 s[x][y] =s[x-1][y];85 s[x-1][y] =' ';86 x--;87 }88 else if(ch =='B'&&check(x,y,2))89 {90 s[x][y] =s[x+1][y];91 s[x+1][y] =' ';92 x++;93 }94 else if(ch =='R'&&check(x,y,3))95 {96 s[x][y] =s[x][y+1];97 s[x][y+1] =' ';98 y++;99 }100 else if(ch =='L'&&check(x,y,4))101 {102 s[x][y] =s[x][y-1];103 s[x][y-1] =' ';104 y--;105 }106 else107 flag =false;107 flag =false;108 }109 }110 //cout << endl;111 if(kase) //输出格式注意！ 112 cout <<endl;113 cout <<"Puzzle #"<< ++kase <<":"<<endl;114115 if(flag)116 {117118 bool first =true;119 for(int i =0;i <5;i++)120 {121 for(int j =0;j <5;j++)122 {123 if(first)124 {125 cout <<s[i][j];126 first =0;127 }128 else129 cout <<" "<<s[i][j];130 }131 first =true;132 cout <<endl;133 }134 }135 else136 cout <<"This puzzle has no final configuration."<<endl;137138 }139 return0;140 }// ACM/ICPC World Finals 1994,UVa2321 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #define maxn 15 5 char s[maxn][maxn];6 int start_num[maxn][maxn];7 using namespace std;8 int Across (int i,int j,int c){9 if (start_num[i][j] !=0) 10 { 11 if (start_num[i][j] <10) //'%3d' 12 cout <<" "<<start_num[i][j] <<"."; 13 else 14 cout <<" "<<start_num[i][j] <<".";15 for (j;j <c;j++) 16 { 17 if (s[i][j] =='*')18 { 19 cout <<endl; 20 return j;21 } 22 else 23 cout <<s[i][j];24 } 25 cout <<endl; 26 return j;27 } 28 return j; 29 }30 31 int Down (int i,int j,int r){32 if (start_num[i][j] !=0) 33 { 34 if (start_num[i][j] <10)35 cout <<" "<<start_num[i][j] <<"."; 36 else 37 cout <<" "<<start_num[i][j] <<".";38 for (i;i <r;i++) 39 { 40 if (s[i][j] =='*')41 { 42 cout <<endl; 43 return 0;44 } 45 else 46 {47 cout <<s[i][j];3-6 Crossword Answers2017年10月1日15:0947 cout <<s[i][j];48 start_num[i][j] =0;49 }50 }51 cout <<endl;52 }53 }5455 int main(void)56 {57 int kase =0;58 while(1)59 {60 int r,c;61 cin >>r;62 if(r ==0)63 return0;64 cin >>c;65 for(int i =0;i <r;i++)66 scanf("%s", &s[i]);6768 //Read in69 /*70 for(int i = 0;i < r;i++)71 {72 for(int j = 0;j < c;j++)73 cout << s[i][j];74 cout << endl;75 }76 */7778 int num =0;79 memset(start_num,0,sizeof(start_num));8081 //the first number82 for(int i =0;i <r;i++)83 for(int j =0;j <c;j++)84 {85 if(s[i][j] !='*')86 {87 if(i ==0||j ==0)88 start_num[i][j] = ++num;89 else if(s[i][j-1] =='*'||s[i-1][j] =='*')90 start_num[i][j] = ++num;91 }92 }9394 //check the first number95 /*96 for(int i = 0;i < r;i++)97 {98 for(int j = 0;j < c;j++)99 cout << start_num[i][j];99 cout << start_num[i][j];100 cout << endl;101 }102 */103 if(kase)104 cout <<endl;105 cout <<"puzzle #"<< ++kase <<":"<<endl; 106107 cout <<"Across"<<endl;108 for(int i =0;i <r;i++)109 for(int j =0;j <c;j++)110 j =Across(i,j,c);111112 cout <<"Down"<<endl;113 for(int i =0;i <r;i++)114 for(int j =0;j <c;j++)115 Down(i,j,r);116117 }118 return0;119 }// ACM/ICPC Seoul 2006,UVa13681 #include <iostream>2 #include <cstdio>3 #include <cstring>4 using namespace std;5 int main (void )6 {7 int num;8 int Hamans =0;9 cin >>num;10 while (num) 11 { 12 int m,n; 13 cin >>m >>n;14 char s[m][n]; 15 for (int i =0;i <m;i++) 16 cin >>s[i];1718 //数组正确读入19 /* 20 for(int i = 0;i < m;i++) 21 { 22 for(int j = 0;j < n;j++)23 cout << s[i][j]; 24 cout << endl; 25 } 26 */27 28 int LS =0; 29 int Repeat[4]; 30 char ans[n];31 for (int j =0;j <n;j++) 32 { 33 memset (Repeat,0,sizeof (Repeat));34 for (int i =0;i <m;i++) 35 { 36 if (s[i][j]=='A')Repeat[0]++; 37 else if (s[i][j]=='C')Repeat[1]++;38 else if (s[i][j]=='G')Repeat[2]++; 39 else Repeat[3]++;40 //思路：检查Hamming 距离最小的字符，若有相同的情况则再判断字典序 41 } 4243 //测试Repeat 的数据是否正确44 /*45 for(int LS = 0;LS < 4;LS++) 46 cout << Repeat[LS] << " "; 47 cout << endl; 48 */49 int PD =0; 50 int LSans =0;3-7 DNA Consensus String2017年10月1日15:1050 int LSans =0;51 for(int LS =0;LS <4;LS++)52 if(PD <Repeat[LS])53 {54 PD =Repeat[LS];55 LSans =LS;56 }5758 Hamans += (m -Repeat[LSans]); //求Hamming距离的总和5960 //测试当前最大的数组下标是否正确61 /*62 cout << "LSans: " << LSans << endl;63 */64 switch(LSans)65 {66 case0:67 ans[j] ='A';68 break;69 case1:70 ans[j] ='C';71 break;72 case2:73 ans[j] ='G';74 break;75 case3:76 ans[j] ='T';77 break;78 }79 }8081 for(int j =0;j <n;j++)82 cout <<ans[j];83 cout <<endl;84 cout <<Hamans <<endl;85 Hamans =0; //清零Hamming距离以便下一次计算86 num--;87 }88 return0;89 }// ACM/ICPC World Finals 1990,UVa2021 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #define maxn 50000005 using namespace std;6 int s[maxn],next1[maxn],YS[maxn],repeat[maxn]; 78 void GetNext (const int n){ 9 memset (next1,0,sizeof (next1)); 10 next1[0] = -1; 11 int i =0,k = -1;12 while (i <n) 13 { 14 if (k == -1||repeat[i] ==repeat[k]) 15 { 16 next1[i+1] =k+1;17 i++; 18 k++; 19 } 20 else21 k =next1[k]; 22 } 23 } 2425 void Next_Loop (int n,int &loop){ 26 int j; 27 bool flag1 =true ; 28 for (int i =0;i <n;i++) 29 {30 if (next1[i] == -1||next1[i] ==0) 31 continue ; 32 j =i -next1[i]; 33 if (i %j ==0)34 { 35 loop =i/2; 36 if (YS[n] ==YS[n+loop]) 37 break ;38 } 39 } 40 } 41 int main (void ) 42 {43 int a,b; 44 int YS_1 =0; 45 int loop =0; 46 while (scanf ("%d", &a) !=EOF)47 { 48 scanf ("%d", &b); 49 int a1 =a; 50 bool flag =true ;51 52 memset (s,0,sizeof (s)); 53 memset (YS,0,sizeof (YS)); 5455 //模拟四则运算,计算50000位，maxn 较大56 for (int i =0;i <50000;i++) 57 { 58 if (a >=b)59 s[i] =a/b; 60 if (a <b) 61 s[i] =0;3-8 Repeating Decimals2017年10月1日15:1261 s[i] =0;62 a = (a -s[i]*b)*10;63 YS[i] =a;64 if(a ==0)65 {66 flag =false;67 break;68 }69 }70 if(flag)71 {7273 //模拟四则运算测试输出74 /*75 cout << s[0] << ".";76 for(int i = 1;i < b*3;i++)77 cout << s[i];78 cout << endl;79 */8081 //从后面开始复制以避开干扰数8283 memset(repeat,0,sizeof(repeat));84 for(int i =0;i <3*b+1;i++)85 repeat[i] =s[i+b+1];8687 GetNext(3*b+1);88 Next_Loop(3*b+1,loop);8990 //检查next数组91 /*92 cout << "Next: " << endl;93 for(int i = 0; i < 50; i++)94 cout << next1[i];95 cout << endl;96 */9798 //检查周期99 // cout << "loop: " << loop << endl;100101 //用于排除前方干扰数的影响（使用余数）102 bool flag2 =true;103104 for(int i =0;i <maxn;i++)105 {106 for(int j =0;j <loop;j++)107 if(YS[i] !=YS[i+loop])108 flag2 =false;109 if(flag2)110 {111 i++;112 int num =0;113 cout <<a1 <<"/"<<b <<" = ";114 cout <<s[0] <<".";115 for(int j =1;j <i;j++)116 {117 cout <<s[j];118 num++;119 }120 cout <<"(";121 if(i ==0)i++;122 if(loop >50)123 {124 for(int j =i;j <50-num+i;j++)124 for(int j =i;j <50-num+i;j++)125 cout <<s[j];126 cout <<"...";127 }128 else129 for(int j =i;j <loop+i;j++)130 cout <<s[j];131 cout <<")"<<endl;132 cout <<" "<<loop <<" = number of digits in repeating cycle"<<endl; 133 break;134 }135 flag2 =true;136 }137 }138 //整除的情况139 else140 {141 cout <<a1 <<"/"<<b <<" = ";142 cout <<s[0] <<".";143 for(int i =1;i <maxn;i++)144 {145 if(YS[i-1] ==0)146 break;147 cout <<s[i];148 }149 cout <<"(0)"<<endl;150 cout <<" "<<"1 = number of digits in repeating cycle"<<endl;151 }152 cout <<endl;153 }154 return0;155 }// UVa 103401 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #define maxn 100000000 5 char k[maxn]; 6 char s[maxn]; 7 using namespace std; 8 int main (void ) 9 { 10 while (scanf ("%s", &k) !=EOF) 11 { 12 13 scanf ("%s", &s); 14 int n1 =strlen (k); 15 int n2 =strlen (s); 16 int num =0; 17 int wz =0; 18 for (int j =0;j <n1;j++) 19 for (int i =wz;i <n2;i++) 20 if (k[j] ==s[i]) 21 { 22 num++; 23 wz =i+1; 24 break ; 25 } 26 if (num ==n1)27 cout <<"Yes"<<endl; 28 else 29 cout <<"No"<<endl; 30 } 31 return 0; 32 }1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <algorithm>5 #define maxn 1000006 using namespace std;7 char s1[maxn],s2[maxn];8 int value2[2][maxn];9 int main (void )10 { 11 while (~scanf ("%s%s", &s1, &s2)) 12 { 13 memset (value2,0,sizeof (value2)); 14 int i,j; 15 int tem =1; 16 for (i =0;s1[i];i++) 17 { 18 for (j =0;s2[j];j++) 19 { 20 if (s1[i] ==s2[j]) 21 value2[tem][j] =value2[1-tem][j-1]+1; 22 else23 value2[tem][j] =max (value2[1-tem][j],value2[tem][j-1]); //状态转移方程 24 }25 tem =1-tem; //空间优化 26 } 27 if (value2[1-tem][j-1] ==strlen (s1)) 28 cout <<"Yes"<<endl; 29 else3-9 All in All2017年10月1日15:1429 else30 cout <<"No"<<endl;31 }32 return0;33 }// ACM/ICPC NEERC 2004,UVa15871 #include <iostream>2 #include <cstring>3 #include <algorithm>4 #include <cstdio>5 using namespace std;6 struct box7 {8 int x;9 int y;10 }s[6]; 11 bool cmp (const box &x,const box &y) 12 {13 return x.x*x.y >y.x*y.y; 14 } 1516 int main (void ) 17 { 18 memset (s,0,sizeof (s)); 1920 //读入长宽数据21 while (scanf ("%d %d", &s[0].x, &s[0].y) !=EOF) 22 {23 for (int i =1;i <6;i++) 24 cin >>s[i].x >>s[i].y; 2526 //长宽定义统一27 for (int i =0;i <6;i++) 28 if (s[i].x <s[i].y)29 swap (s[i].x,s[i].y); 30 31 bool flag =true ; 3233 //面积排序34 sort (s,s+6,cmp); 3536 //排序函数正常37 /* 38 cout << endl;39 for(int i = 0;i < 6;i++) 40 cout << s[i].x << " " << s[i].y << endl; 41 */4243 //判断矩形各面是否合法，思路来源CSDN: codekun44 //巧妙之处：排序后memcmp 只存在0或大于0的返回值！45 if (memcmp (s,s+1,sizeof (box)) ||memcmp (s+2,s+3,sizeof (box)) ||memcmp (s+4,s+5,sizeof (box))) 46 flag =false ; 4748 //判断矩形各长宽高是否合法49 if (s[0].x !=s[2].x ||s[0].y !=s[4].x ||s[2].y !=s[4].y) 50 flag =false ; 5152 //输出53 if (flag) 54 cout <<"POSSIBLE"<<endl;55 else 56 cout <<"IMPOSSIBLE"<<endl; 57 }58 return 0; 59 }3-10 Box2017年10月1日15:14// ACM/ICPC NEERC 2006,UVa15881 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #include <cmath>5 using namespace std;6 int main (void )7 {8 string s1,s2;9 while (cin >>s1 >>s2) 10 {11 int ans =s1.size () +s2.size (); 12 bool flag;13 for (int i =0;i <s1.size ();i++)14 { 15 flag =true ;16 int k =i; //起点 17 for (int j =0;j <s2.size ();j++)18 {19 if (k <s1.size () &&s1[k++] +s2[j] -'0'-'0'>3) 20 {21 flag =false ;22 break ; 23 }24 } 25 if (flag) 26 {27 ans =max (s1.size (),s2.size ()+i);28 break ;29 }30 } 31 for (int i =0;i <s2.size ();i++)32 {33 flag =true ;34 int k =i; //起点 35 for (int j =0;j <s1.size ();j++)36 {37 if (k <s2.size () &&s2[k++] +s1[j] -'0'-'0'>3) 38 { 39 flag =false ;40 break ;41 } 42 }43 if (flag) 44 { 45 int temp =max (s2.size (),s1.size ()+i);3-11 Kickdown2017年10月1日15:1545 int temp =max(s2.size(),s1.size()+i);46 ans =min(ans,temp);47 break;48 }49 }50 cout <<ans <<endl;51 }52 return0;53 }// UVa118091 #include <iostream>2 #include <cstring>3 #include <cstdio>4 #include <sstream>5 #include <cmath>6 using namespace std;7 long long table[15][35];8 double table2[15][35];9 template <class Type>10 Type stringToNum (const string&str){ 11 istringstream iss (str);12 Type num;13 iss >>num;14 return num;15 }16 void make_tab (){ 17 for (int i =0;i <10;i++)18 for (int j =1;j <=30;j++)19 {20 double expow =pow (2,j) -1; //mantissa and exponent21 double mansa =1-pow (2, -1-i); 22 double t =log10(mansa) +expow*log10(2);23 table[i][j] =t;table2[i][j] =pow (10,t-table[i][j]); //使用对数来缩小规模24 } //若试图使用结果直接计算，会在约2^991处（不一定相同）卡死 25 } 26 int main (void )27 {28 string s,num;29 make_tab ();30 while (cin >>s &&s !="0e0") 31 {3233 num =s.substr (0,s.find ('e'));34 s =s.substr (s.find ('e')+1,s.size ());35 double A =stringToNum<double >(num);36 int B =stringToNum<int >(s); 37 while (A <1){A *=10;B -=1;}38 for (int i =0;i <10;i++)39 for (int j =1;j <=30;j++)40 {41 if (B ==table[i][j] && (fabs (A -table2[i][j]) <1e-4||fabs (A /10-table2[i][j]) <1e-4)) 42 {43 cout <<i <<" "<<j <<endl;44 break ;45 }46 } 47 }48 return 0;49 }50 //CSDN:crazysillynerd 的思路3-12 Floating-Point Numbers2017年10月1日15:16。