本文共 6545 字，大约阅读时间需要 21 分钟。

**

ICPC训练联盟2021寒假冬令营（1）（部分题解）：

B - Pig-Latin：

You have decided that PGP encryptation is not strong enough for your email. You have decided to supplement it by first converting your clear text letter into Pig Latin before encrypting it with PGP. Input and Output You are to write a program that will take in an arbitrary number of lines of text and output it in Pig Latin. Each line of text will contain one or more words. A “word” is defined as a consecutive sequence of letters (upper and/or lower case). Words should be converted to Pig Latin according to the following rules (non-words should be output exactly as they appear in the input): 1. Words that begin with a vowel (a, e, i, o, or u, and the capital versions of these) should just have the string “ay” (not including the quotes) appended to it. For example, “apple” becomes “appleay”. 2. Words that begin with a consonant (any letter than is not A, a, E, e, I, i, O, o, U or u) should have the first consonant removed and appended to the end of the word, and then appending “ay” as well. For example, “hello” becomes “ellohay”. 3. Do not change the case of any letter. Sample Input

This is the input.

Sample Output

hisTay isay hetay inputay.

---

题意：以a、e、i、o、u(包括大写)开头的单词在后面加ay，以其他字母开头将该字母转移到单词后再加ay（字符串基本操作题）

代码：

#include
   
    using namespace  std;typedef long long int ll;#define N 200005int judge(char c){
       if(c=='a'||c=='A'||c=='e'||c=='E'||c=='i'||c=='I'||c=='o'||c=='O'||c=='u'||c=='U')    return 1;    else if(c>='a'&&c<='z'||c>='A'&&c<='Z') return 0;    else return 2;}int main(){
       char c;    string s;    while(scanf("%c",&c)!=EOF){
           if(judge(c)!=2)        {
               s+=c;        }        else{
               string tem="ay";            char t=s[0];            if(judge(t)==1){
                   s=s+tem;            }            if(judge(t)==0){
                   s.erase(0,1);                s=s+t;                s=s+tem;            }            cout<
    <
   

C - Tic Tac Toe：

Tic Tac Toe is a child’s game played on a 3 by 3 grid. One player, X, starts by placing an X at an unoccupied grid position. Then the other player, O, places an O at an unoccupied grid position. Play alternates between X and O until the grid is filled or one player’s symbols occupy an entire line (vertical, horizontal, or diagonal) in the grid. We will denote the initial empty Tic Tac Toe grid with nine dots. Whenever X or O plays we fill in an X or an O in the appropriate position. The example below illustrates each grid configuration from the beginning to the end of a game in which X wins. … X… X.O X.O X.O X.O X.O X.O

… … … … .O. .O. OO. OO.

… … … …X …X X.X X.X XXX

Your job is to read a grid and to determine whether or not it could possibly be part of a valid Tic Tac Toe game. That is, is there a series of plays that can yield this grid somewhere between the start and end of the game?

Input The first line of input contains N, the number of test cases. 4N-1 lines follow, specifying N grid configurations separated by empty lines. Output For each case print “yes” or “no” on a line by itself, indicating whether or not the configuration could be part of a Tic Tac Toe game. Sample Input 2 X.O OO. XXX

O.X

XX. OOO Sample Output yes no 题意：判断井字棋棋局是否合理存在（找出所有不合理的情况即可） 不合理的情况: 棋子数量来看：1.O数量多于X(X先手的话X数量大于等于O) 2.X数量比O多两枚及以上（X数量大于等于O,最多能比O多一颗） 获胜情况来看：1.X赢了但是X数量等于O的数量 2.O赢了但是X数量不等于O的数量 3.遍历棋盘发现OX同时获胜（其实第1种情况已经包含这种情况）

代码：

#include
   
    using namespace  std;typedef long long int ll;#define N 200005int main(){
       int n;    cin>>n;    while(n--){
           int nx=0,no=0;        char bod[3][3];        for(int i=0;i<3;i++)        for(int j=0;j<3;j++)        {
               cin>>bod[i][j];            if(bod[i][j]=='X') nx++;            if(bod[i][j]=='O') no++;        }        if(no>nx||nx-2>=no){
           //以数量为依据            cout<<"no"<
   

E - Function Run Fun

We all love recursion! Don’t we? Consider a three-parameter recursive function w(a, b, c): if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 。if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.

Input The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result. Output Print the value for w(a,b,c) for each triple. Sample Input 1 1 1 2 2 2 10 4 6 50 50 50 -1 7 18 -1 -1 -1 Sample Output w(1, 1, 1) = 2 w(2, 2, 2) = 4 w(10, 4, 6) = 523 w(50, 50, 50) = 1048576 w(-1, 7, 18) = 1

题意：如果按照题目所给的递归条件直接写递归函数将会调用太多次函数，耗时太长，让我们写个耗时少点的程序

递归能实现的功能，递推一样能实现，直接三层for循环计算出递推计算出w[i][j][k]即可.虽然On^3,但数据只有20X20X20，不会超时 代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 10005typedef long long int ll;int main(){ ll w[21][21][21]; // w[0][0][0]=1; for(int i=0;i<21;i++) for(int j=0;j<21;j++) for(int k=0;k<21;k++) { if(i==0||j==0||k==0) w[i][j][k]=1; else if(i
         
          
           >a>>b>>c){ if(a==-1&&b==-1&&c==-1) break; if(a<=0||b<=0||c<=0) printf("w(%d, %d, %d) = %lld\n",a,b,c,1); else if(a>20||b>20||c>20) printf("w(%d, %d, %d) = %lld\n",a,b,c,w[20][20][20]); else printf("w(%d, %d, %d) = %lld\n",a,b,c,w[a][b][c]); } return 0;}
          
         
        
       
      
     
    
   

F - Simple Addition

题面见图：

题意，根据题目所给出的两个函数计算p ~ q之间f(p ~ q)的和；

这个题如果直接遍历p ~ q之间的数肯定是会超时，于是可以将p~q之间个位数不为0的数处理完，再将个位数为零的数除以十，产生新的处理区间 如：处理10~ 20，先将10~ 20的个位不为零的数%10累加，剩下10、20,除以10后递归进入函数，变成处理1~ 2，再将1~2按照前面的方法进行处理 直至最终p~ q的间隔小于十，即q-p<10，但要注意的是，1~ 10、0~9均满足此情况，但是0、10要特殊处理（因为我没有使用f这个递归函数，是直接计算并累加，如果用这个函数去找f(i)就不用担心这些特殊情况） 代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 10000typedef long long int ll;ll res;int cal(ll p,ll q){ ll i,j; if(q-p<10){ for(int k=p;k<=q;k++) if(k%10!=0||(k%10==0&&k==0)) res+=(k%10); else res+=1; //10-1=9<10,10%10=0,特殊处理（0的话就不加，也要特殊处理） return 0; } for(i=p; i%10!=0;i++) res+=(i%10); for(j=q;j%10!=0;j--) res+=(j%10); res+=45*(j-i)/10; //45=1+2+3+...+9 cal(i/10,j/10); return 0;}int main(){ ll p,q; while (cin>>p>>q) { if(p==-1&&q==-1) break; res=0; cal(p,q); cout<
         
          <
         
        
       
      
     
    
   

转载地址：http://hkyc.baihongyu.com/