LessonOne.md

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