日度归档：29 3 月, 2021

CSP 201912-1 报数

发表评论
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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int n;
int a[4];

bool hasSeven(int n){
    while(n){
        if(n%10==7)return true;
        n/=10;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    int cnt=0;
    for(int i=0;cnt<n;i++){
        if((i+1)%7==0||hasSeven(i+1)){
            a[i%4]++;
        }else{
            cnt++;
        }
    }
    for(int i=0;i<4;i++){
        cout<<a[i]<<"\n";
    }
}

CSP 202006-4 1246

发表评论

48分题解：|S|=1
推导：
1->2
2->4
4->{1,6}
6->{6,4}
则有：
a1’=a4
a2’=a1
a4’=a2+a6
a6’=a4+a6
矩阵快速幂：
\begin{bmatrix}
a_{1}^{\prime} \\
a_{2}^{\prime} \\
a_{4}^{\prime} \\
a_{6}^{\prime}
\end{bmatrix} =
\begin{bmatrix}
a_4 \\
a_1 \\
a_2 + a_6 \\
a_4 + a_6
\end{bmatrix} =
\begin{bmatrix}
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1
\end{bmatrix} *
\begin{bmatrix}
a_1 \\
a_2 \\
a_4 \\
a_6
\end{bmatrix}

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 <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

const long long MOD = 998244353;
const int maxtrixN = 4;

struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (const matrix& m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 0,0,1,0,1,0,0,0,0,1,0,1,0,0,1,1 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getResult(long long n, int index){
    matrix re=quickpow(n);
    return re.arr[index][0] % MOD;
}
int main() {
    ios::sync_with_stdio(false);
    long long n, s;
    cin>>n>>s;
    if(n==0){
        if(s==1){
            cout<<"1";
        }else{
            cout<<"0";
        }
    }else if(s==1){
        cout<<getResult(n, 0);
    }else if(s==2){
        cout<<getResult(n, 1);
    }else if(s==4){
        cout<<getResult(n, 2);
    }else if(s==6){
        cout<<getResult(n, 3);
    }
}

待完善96分题解。

CSP 202006-2 稀疏向量

发表评论
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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;
long long n,a,b;
long long ai[500005],av[500005];
long long bi[500005],bv[500005];

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=0;i<a;i++)
        cin>>ai[i]>>av[i];
    for(int i=0;i<b;i++)
        cin>>bi[i]>>bv[i];
    int i=0,j=0;
    long long sum=0;
    while(i<a&&j<b){
        if(ai[i]==bi[j]){
            sum+=av[i]*bv[j];
            i++;
            j++;
        }
        else if(ai[i]<bi[j])
            i++;
        else if(ai[i]>bi[j])
            j++;
    }
    cout<<sum;
}

CSP 202006-1 线性分类器

发表评论
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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int n,m;
long long x[1005], y[1005];
char type[1005];
long long theta0,theta1,theta2;

bool checkPointPos(long long x,long long y){
    return theta0+theta1*x+theta2*y > 0;
}

bool checkLine(){
    char typ = type[0];
    bool pos = checkPointPos(x[0], y[0]);
    for(int i=1;i<n;i++){
        if(typ==type[i] && pos!= checkPointPos(x[i], y[i]) ||
                typ!=type[i] && pos== checkPointPos(x[i], y[i])){
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>type[i];
    for(int i=0;i<m;i++){
        cin>>theta0>>theta1>>theta2;
        if(checkLine()){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
}