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());
}

Posted on | In

计导交流课(1)

内容

1、字符串

2、指针

3、函数

字符串

计算器的改良

题目背景

NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。

题目描述

为了很好的完成这个任务，ZL先生首先研究了一些一元一次方程的实例：

4+3x=84+3x=8

6a−5+1=2−2a6a−5+1=2−2a

−5+12y=0−5+12y=0

ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及+、-、=这三个数学符号（当然，符号“-”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。

代码

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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

long long x=0,num=0,f=0,rev=0;
char res;

void TP(char c)
{
    if(c=='=')rev=1,f=0;
    else if(c=='+')f=0;
    else if(c=='-')f=1;
}

inline bool input()
{
    char c=getchar();long long o;
    TP(c);
    if(c>='a'&&c<='z')res=c,x+=(f^rev)?-1:1;
    while(c>57||c<48)
    {
        if(c==EOF)return 0;
        f|=(c=='-');
        c=getchar();
    }
    for(o=0;c>47&&c<58;c=getchar())o=(o<<1)+(o<<3)+c-48;
    //将系数/数字累加
    if(c>='a'&&c<='z')res=c,x+=(f^rev)?-o:o;
    else num+=(f^rev)?-o:o;
    //判断下一个数是正数/负数  /  到达等式右端
    TP(c);
    if(c==EOF)return 0;
    return 1;
}

int main()
{
    //freopen("In.txt","r",stdin);
    while(input());
    double ans=(double)-num/x;
    printf("%c=%.3lf",res,ans==0?abs(ans):ans);
}

指针

  1. 编写矩阵定义、初始化函数；

  2. 编写矩阵加法函数；

  3. 编写矩阵减法函数；

  4. 编写矩阵乘法函数；

  5. 编写求矩阵均值函数；

  6. 编写求一个矩阵的子阵函数；

  7. 编写矩阵输出函数；

  8. 编写主控函数；

主要函数和结构参考原型如下：

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
typedef struct{
	double ** mat;
	int row;
	int col;
}Matrix;

 

void InitialMatrix(Matrix *T, int row,int col);   //只分配空间不初始化；

void InitialMatrixZero(Matrix *T,int row, int col);  //初始化为0

void InitialMatrixRand(Matrix *T,int row, int col); //初始化为50以内随机正整数

void InputMatrix(Matrix *T);               //键盘输入矩阵

void DestroyMatrix(Matrix *T);                // 释放矩阵空间

void PrintfMatrix(Matrix *T);              //矩阵输出

int AddMatrix(Matrix *A,Matrix *B,Matrix *C); // 矩阵加

int MinusMatrix(Matrix *A,Matrix *B,Matrix *C); // 矩阵减

int MultiMatrix(Matrix *A,Matrix *B,Matrix *C); //矩阵乘法

double MeanMatrix(Matrix *T);  //矩阵元素均值

int SubMatrix(Matrix *T1,Matrix *T2,int BeginRow,int BeginCol,int EndRow,int EndCol); //求T1的子矩阵T2;

参考代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct{
	double ** mat;
	int row;
	int col;
}Matrix;

void InitialMatrix(Matrix *T, int row,int col)
{
    (*T).row=row;
    (*T).col=col;
    (*T).mat=(double**)malloc(sizeof(double*)*row);
    for(int i=0;i<row;i++)
        (*T).mat[i]=(double*)malloc(sizeof(double)*col);
}//只分配空间不初始化；

void InitialMatrixZero(Matrix *T,int row, int col)
{
    InitialMatrix(T,row,col);
    (*T).row=row;
    (*T).col=col;
    for(int i=0;i<row*col;i++)
        **((*T).mat+i)=0;
}//初始化为0

void InitialMatrixRand(Matrix *T,int row, int col)
{
    InitialMatrix(T,row,col);
    (*T).row=row;
    (*T).col=col;
    for(int i=0;i<row*col;i++)
        **((*T).mat+i)=rand()%50+1;
}//初始化为50以内随机正整数

void InputMatrix(Matrix *T)
{
    printf("row:");
    printf("col:");
    scanf("%d",&(*T).row);
    scanf("%d",&(*T).col);
    printf("Now input the hole matrix:\n");
    InitialMatrix(T,(*T).row,(*T).col);
    for(int i=0;i<(*T).row;i++)
    for(int j=0;j<(*T).col;j++)
        scanf("%lf",&(*T).mat[i][j]);
}//键盘输入矩阵

void DestroyMatrix(Matrix *T)
{
    free(T);
    T=NULL;
}// 释放矩阵空间

void PrintfMatrix(Matrix *T)
{
    int row=(*T).row,col=(*T).col;
    for(int i=0;i<row;i++,putchar('\n'))
    for(int j=0;j<col;j++)
        printf("%.0lf ",(*T).mat[i][j]);
}//矩阵输出
void AddMatrix(Matrix *A,Matrix *B,Matrix *C)
{
    int row=(*A).row,col=(*A).col;
    InitialMatrix(C,row,col);
    for(int i=0;i<row;i++)
    for(int j=0;j<col;j++)
        (*C).mat[i][j]=(*B).mat[i][j]+(*A).mat[i][j];
}// 矩阵加
void MinusMatrix(Matrix *A,Matrix *B,Matrix *C)
{
    int row=(*A).row,col=(*A).col;
    InitialMatrix(C,row,col);
    for(int i=0;i<row;i++)
    for(int j=0;j<col;j++)
        (*C).mat[i][j]=-(*B).mat[i][j]+(*A).mat[i][j];
} // 矩阵减

void MultiMatrix(Matrix *A,Matrix *B,Matrix *C)
{
    int row=(*A).row,col=(*A).col;
    InitialMatrix(C,row,col);
    double **MA=(*A).mat,**MB=(*B).mat;
    for(int i=0;i<row;i++)
    for(int j=0;j<col;j++)
    for(int k=0;k<row;k++)
        (*C).mat[i][j]+=MA[i][k]*MB[k][j];
}//矩阵乘法

double MeanMatrix(Matrix *T)
{
    int row=(*T).row,col=(*T).col;
    double Average=0,**MT=(*T).mat;
    for(int i=0;i<row;i++)
    for(int j=0;j<col;j++)
        Average+=MT[i][j];
    return Average/row/col;
}//矩阵元素均值

void SubMatrix(Matrix *T1,Matrix *T2,int BeginRow,int BeginCol,int EndRow,int EndCol)
{
    int row,col;
    InitialMatrix(T2,row=EndRow-BeginRow+1,col=EndCol-BeginCol+1);
    double **M1=(*T1).mat,**M2=(*T2).mat;
    for(int i=0;i<row;i++)
    for(int j=0;j<col;j++)
        M2[i][j]=M1[i+BeginRow][j+BeginCol];
}//求T1的子矩阵T2;

Matrix A,C;

int main()
{
    //freopen("In.txt","r",stdin);
    int op,row,col;
    while(scanf("%d",&op))
    {
        if(op==0)return 0;
        Matrix A,B,C;
        if(op==1)
        {
            InputMatrix(&A);
            printf("%lf\n",MeanMatrix(&A));
        }
        else if(op==2)
        {
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&A,row,col);
            printf("%lf",MeanMatrix(&A));
        }
        else if(op==3)
        {
            InputMatrix(&A);
            InputMatrix(&B);
            AddMatrix(&A,&B,&C);
            PrintfMatrix(&C);
        }
        else if(op==4)
        {
            InputMatrix(&A);
            InputMatrix(&B);
            MinusMatrix(&A,&B,&C);
            PrintfMatrix(&C);
        }
        else if(op==5)
        {
            InputMatrix(&A);
            InputMatrix(&B);
            MultiMatrix(&A,&B,&C);
            PrintfMatrix(&C);
        }
        else if(op==6)
        {
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&A,row,col);
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&B,row,col);
            AddMatrix(&A,&B,&C);
            PrintfMatrix(&C);
        }
        else if(op==7)
        {
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&A,row,col);
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&B,row,col);
            MinusMatrix(&A,&B,&C);
            PrintfMatrix(&C);
        }
        else if(op==8)
        {
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&A,row,col);
            scanf("%d%d\n",&row,&col);
            InitialMatrixRand(&B,row,col);
            MultiMatrix(&A,&B,&C);
            PrintfMatrix(&C);
        }
        else if(op==9)
        {
            InputMatrix(&A);
            int sr,er,sc,ec;
            scanf("%d%d%d%d",&sr,&er,&sc,&ec);
            SubMatrix(&A,&C,sr,er,sc,ec);
            PrintfMatrix(&C);
        }
    }
}

函数

CodeForces Technocup 2020 - Elimination Round 3 Wrong Answer on test 233

题意

给定一个数列 $A$，长度 $l \leq 2\cdot 10^5$ 。

现在构造一个数列 $B$，对于 $i\in [1,l]$，若有 $A_i=B_i$，则记B的价值+1，若不等则+0，数列 $B$ 最终价值记为 $V_B$

再基于数列 $B$ 构造数列 $C$ ，其中 $Ci$ = $B{(i+1 \mod n)}$

数列 $C$ 最终价值记为 $V_C$

问有多少种构造 $B$ 使得 $V_C>V_B$ ，对结果$\mod 998244353$

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
66
#include <iostream>
#include <cstdio>
#define li long long
using namespace std;
const int mod=998244353,N=2e5+5;
 
inline int input()
{
    char c=getchar();int o;
    while(c>57||c<48)c=getchar();
    for(o=0;c>47&&c<58;c=getchar())o=(o<<1)+(o<<3)+c-48;
    return o;
}
 
li A[N],n,k,res=1,cnt=0,JC[N],inv[N],Pow2[N],Powk[N];
 
void init()
{
    JC[0]=1;
    for(int i=1;i<=cnt;i++)JC[i]=JC[i-1]*i%mod;
    inv[0]=inv[1]=1;
    for(int i=2;i<=cnt;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=2;i<=cnt;i++)inv[i]=inv[i]*inv[i-1]%mod;
    Pow2[0]=Powk[0]=1;
    for(int i=1;i<=cnt;i++)
    {
        Pow2[i]=(Pow2[i-1]<<1)%mod;
        Powk[i]=(Powk[i-1]*(k-2))%mod;
    }
}
 
li C(li a,li b){return JC[a]*inv[b]%mod*inv[a-b]%mod;}
 
void DP()
{
    li ans=0;
    for(int i=0;i<cnt;i++,ans%=mod)
        if((cnt-i)&1)ans=ans+((C(cnt,i)*Powk[i])%mod*Pow2[cnt-i-1]%mod);
        else ans=ans+(((C(cnt,i)*Powk[i])%mod*(Pow2[cnt-i]-C(cnt-i,(cnt-i)/2)+mod))%mod*inv[2]%mod);
    res=res*(ans+mod)%mod;
}
 
int main()
{
    //freopen("In.txt","r",stdin);
    n=input();k=input();
    for(int i=1;i<=n;i++)
    {
        A[++cnt]=input();
        if(A[cnt]==A[cnt-1])cnt--,res=res*k%mod;
    }
    if(A[cnt]==A[1])cnt--,res=res*k%mod;
    init();
    if(k==1){puts("0");return 0;}
    else if(k==2)
    {
        li ans=0;
        for(int i=0;i<(cnt+1)/2;i++,ans%=mod)ans=ans+C(cnt,i);
        res=res*ans%mod;
        printf("%lld\n",res);
        return 0;
    }
    DP();
    printf("%lld",res);
    return 0;
}