LessonTwo.md

Posted on | In

计导交流课(2)

数列求和

时间限制
1S

内存限制
1000Kb

问题描述
有一分数序列：
2/1,3/2,5/3,8/5,13/8,21/13,……An/Bn
A1=2，A2=3，An=An-1+An-2；
B1=1，B2=2，Bn=Bn-1+Bn-2。
求出这个数列的前n(2<=n<=30)项之和。

输入说明
一个整数n

输出说明
输出一个实数表示数列前n项之和，结果保留2位小数（四舍五入）

输入样例
2
输出样例
3.50

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>

double MAKE(int A2,int A1,int B2,int B1,int remain)
{
    if(remain==0)return 0;
    double res=MAKE(A2+A1,A2,B2+B1,B2,remain-1)+(double)(A2+A1)/(B2+B1);
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    double res=MAKE(2,3,1,2,n-2)+2+(double)3/2;
    printf("%.2lf",res);
}

字符串压缩

时间限制
1S

内存限制
1000Kb

问题描述
有一种简单的字符串压缩算法，对于字符串中连续出现的同一个英文字符，用该字符加上连续出现的次数来表示（连续出现次数小于3时不压缩）。
例如，字符串aaaaabbbabaaaaaaaaaaaaabbbb可压缩为a5b3aba13b4。
请设计一个程序，将采用该压缩方法得到的字符串解压缩，还原出原字符串并输出。

输入说明
输入数据为一个字符串（长度不大于50，只包含字母和数字），表示压缩后的字符串

输出说明
在一行上输出解压缩后的英文字符串（长度不超过100），最后换行。

输入样例
a5b3aba13b4

输出样例
aaaaabbbabaaaaaaaaaaaaabbbb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <cstring>
using namespace std;

char zip[123];
int len;

int combine(int l,int r)
{
    int o=0;
    for(int i=l;i<=r;i++)o=o*10+zip[i]-'0';
    return o;
}

int main()
{
    scanf("%s",zip);
    len=strlen(zip);
    for(int i=0;i<len;i++)
    {
        char cnt,c=zip[i];
        if(zip[i+1]>='0'&&zip[i+1]<='9')
        {
            int a=i+1;
            while(zip[a+1]>='0'&&zip[a+1]<='9')a++;
            cnt=combine(i+1,a);
            i=a;
        }
        else cnt=1;
        for(int j=1;j<=cnt;j++)putchar(c);
    }
}

井字棋

Alice和Bob在下井字棋，Alice先手。

请输出有多少种可能的过程，最后的结果为Alice胜

两种过程不一样当且仅当下棋过程中任何一方有任何一步与另一过程不一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <cstring>

struct node
{
    char state[3][3];
    node(){memset(state,0,sizeof(state));}
    bool Win()
    {
        bool flag;
        for(int row=0;row<3;row++)
        {
            flag=true;
            for(int col=0;col<3;col++)
                if(state[row][col]!='A')flag=false;
            if(flag==true)return true;
        }
        for(int col=0;col<3;col++)
        {
            flag=true;
            for(int row=0;row<3;row++)
                if(state[row][col]!='A')flag=false;
            if(flag==true)return true;
        }
        flag=true;
        for(int i=0;i<3;i++)
            if(state[i][i]!='A')flag=false;
        if(flag==true)return true;
        for(int i=0;i<3;i++)
            if(state[i][2-i]!='A')flag=false;
        if(flag==true)return true;
        return false;
    }
};

long long count=0;

void Play(node sta,bool player)
{
    if(sta.Win())
    {
        count++;
        return;
    }
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
        if(sta.state[i][j]==0)
        {
            node next_sta=sta;
            next_sta.state[i][j]=(player==1)?'A':'B';
            Play(next_sta,1-player);
        }
}

long long Chess()
{
    node ori;
    Play(ori,1);
    return count;
}

int main()
{
    printf("%lld",Chess());
}