作者归档：Jack

CSP 201903-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 <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int arr[100005];

int main(){
    int n;
    scanf("%d",&n);
    int t;
    int max_num,min_num,mid_num=0;
    double mid_num_d=0;
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    max_num=max(arr[0],arr[n-1]);
    min_num=min(arr[0],arr[n-1]);
    bool flag=false;
    if(n%2==1){
        mid_num=arr[n/2];
    }else{
        mid_num=arr[n/2]+arr[n/2-1];
        if(mid_num%2==0){
            mid_num/=2;
        }else{
            mid_num_d=(double)mid_num/2;
            flag=true;
        }
    }
    if(!flag)
        printf("%d %d %d\n", max_num, mid_num, min_num);
    else
        printf("%d %.1lf %d\n", max_num, mid_num_d, min_num);
}

CSP 201909-3 字符画

发表评论

相对于其他CSP的第三题大模拟，已经比较好写了。。但是还是有坑点。。
一个是在读颜色的时候，理所当然的认为read一个int，之后判断小于<0xf,0xfff即可。后来才考虑到，#00000f这种的颜色就错了。[捂脸] 还有计算平均值的时候块大小循环的时候边界错了。。 大模拟坑最多了。。。烦。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int m, n, p, q, u, v;
unsigned char arr[2000][2000][3];
unsigned char arrAvg[2000][2000][3];
char strs[1000];
char chColor[] = "\x1b[48;2;%d;%d;%dm";
char rstColor[] = "\x1b[0m";

int transNum1(char c) {
    if ('0' <= c && c <= '9')return c - '0';
    else if ('a' <= c && c <= 'f')return c - 'a' + 10;
    else if ('A' <= c && c <= 'F')return c - 'A' + 10;
    else return -1;
}
int transNum2(char c1, char c2) {
    return 16 * transNum1(c1) + transNum1(c2);
}
void input() {
    scanf("%d %d %d %d", &m, &n, &p, &q);
    u = m / p;
    v = n / q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" #");
            scanf("%s", strs);
            int len = strlen(strs);
            int result = 0;
            if (len == 1) {
                int low4 = transNum1(strs[0]);
                arr[i][j][0] = arr[i][j][1] = arr[i][j][2] = low4 * 0x11;
            }
            else if (len == 3) {
                int low4 = transNum1(strs[0]);
                int low8 = transNum1(strs[1]);
                int low12 = transNum1(strs[2]);
                arr[i][j][0] = low4 * 0x11;
                arr[i][j][1] = low8 * 0x11;
                arr[i][j][2] = low12 * 0x11;
            }
            else {
                arr[i][j][0] = transNum2(strs[0], strs[1]);
                arr[i][j][1] = transNum2(strs[2], strs[3]);
                arr[i][j][2] = transNum2(strs[4], strs[5]);
            }
        }
    }
}
inline void calculateAvgSub(int blockX, int blockY) {
    unsigned long long x = 0, y = 0, z = 0;
    for (int i = blockX * q; i < (blockX + 1) * q; i++) {
        for (int j = blockY * p; j < (blockY + 1) * p; j++) {
            x += arr[i][j][0];
            y += arr[i][j][1];
            z += arr[i][j][2];
        }
    }
    arrAvg[blockX][blockY][0] = x / q / p;
    arrAvg[blockX][blockY][1] = y / q / p;
    arrAvg[blockX][blockY][2] = z / q / p;
}
void calculateAvg() {
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < u; j++) {
            calculateAvgSub(i, j);
        }
    }
}
inline void printChar(int ch) {
    printf("\\x%02X", ch);
}
inline void printStr(const char* s) {
    while (*s) {
        printChar(*s);
        s++;
    }
}
inline void setColor(unsigned char* color1, unsigned char* color2) {
    color1[0] = color2[0];
    color1[1] = color2[1];
    color1[2] = color2[2];
}
inline bool cmpColor(unsigned char* color1, unsigned char* color2) {
    return color1[0] == color2[0] && color1[1] == color2[1] && color1[2] == color2[2];
}
void output() {
    unsigned char blackColor[3] = { 0, 0, 0 };
    unsigned char color[3] = { 0, 0, 0 };
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < u; j++) {
            unsigned char* curColor = arrAvg[i][j];
            if (!cmpColor(color, curColor)) {
                if (cmpColor(blackColor, curColor))
                    sprintf(strs, rstColor);
                else
                    sprintf(strs, chColor, curColor[0], curColor[1], curColor[2]);
                setColor(color, curColor);
                printStr(strs);
            }
            printChar(' ');
        }
        if (!cmpColor(color, blackColor)) {
            setColor(color, blackColor);
            printStr(rstColor);
        }
        printChar('\n');
    }
}
int main() {
    input();
    calculateAvg();
    output();
}

CSP 201909-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
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int a[1005];
bool drop[1005];
inline int getMOD(int x) {
    return (x + n) % n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int sum = 0;
    int dropCnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> m;
        int t;
        for (int j = 0; j < m; j++) {
            cin >> t;
            if (t > 0) {
                if (j != 0 && t < a[i])
                    drop[i] = true;
                a[i] = t;
            }
            else
                a[i] += t;
           
        }
        sum += a[i];
        if (drop[i])
            dropCnt++;
    }
    int group = 0;
    for (int i = 0; i < n; i++) {
        if (drop[getMOD(i - 1)] && drop[getMOD(i)] && drop[getMOD(i + 1)])
            group++;
    }
    cout << sum << " " << dropCnt << " " << group;
}

CSP 201909-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
#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int a[1005],b[1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    int sum = 0;
    int clearMaxID = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int t;
        for (int j = 0; j < m; j++) {
            cin >> t;
            b[i] += t;
        }
        sum += a[i] + b[i];
        if (b[i] < b[clearMaxID])
            clearMaxID = i;
    }
    cout << sum << " " << clearMaxID + 1 << " " << -b[clearMaxID];
}

CSP 201912-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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>

using namespace std;

struct coord {
    long long x, y;
    coord(){}
    coord(long long x, long long y) :x(x), y(y) {}
    bool operator == (const coord& coord2) const {
        return x == coord2.x && y == coord2.y;
    }
    bool operator < (const coord& coord2) const {
        if (x != coord2.x)return x < coord2.x;
        return y < coord2.y;
    }
}arr[10005];
int n;
int XArr[] = {0,0,1,-1,1,1,-1,-1};
int YArr[] = {1,-1,0,0,1,-1,1,-1};
int stat[5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i].x >> arr[i].y;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        int cnter = 0;
        for (int j = 0; j < 4; j++) {
            coord tmp(arr[i].x + XArr[j], arr[i].y + YArr[j]);
            if (*lower_bound(arr, arr + n, tmp) == tmp)
                cnter++;
        }
        if (cnter != 4)continue;
        cnter = 0;
        for (int j = 4; j < 8; j++) {
            coord tmp(arr[i].x + XArr[j], arr[i].y + YArr[j]);
            if (*lower_bound(arr, arr + n, tmp) == tmp)
                cnter++;
        }
        stat[cnter]++;
    }
    for (int i = 0; i < 5; i++) {
        cout << stat[i] << "\n";
    }
}

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

CSP 202009-3 点亮数字人生

发表评论

拓扑排序，另外这道题字符串处理太多了，麻烦死了。这种第三题全都是大模拟。非常麻烦。

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

using namespace std;

struct node {
    string type;
    int input;
    string signals[10];
    bool value;
};

void topoSortDegreeMinus(int id, vector<int> &inDegree, const vector<vector<int>> &edges) {
    if (inDegree[id] != 0)return;
    inDegree[id] = -1;
    vector<int> storage;
    for (int i = 0; i < edges[id].size(); i++) {
        inDegree[edges[id][i]]--;
        if (inDegree[edges[id][i]] == 0)
            storage.push_back(i);
    }
    for (int i = 0; i < storage.size(); i++) {
        topoSortDegreeMinus(storage[i], inDegree, edges);
    }
}

bool checkCircle(int n, unordered_map<string, node> &nodeMap) { //Topological sort
    vector<int> inDegree;
    inDegree.resize(n+1);
    vector<vector<int>> edges;
    edges.resize(n+1);

    for (int i = 1; i <= n; i++) {
        string nodeID = "O" + to_string(i);
        const node &curNode = nodeMap[nodeID];
        for (int j = 0; j < curNode.input; j++) {
            if (curNode.signals[j][0] == 'O') {
                inDegree[i]++;
                int edgeStart = strtol(&curNode.signals[j].c_str()[1], NULL, 10);
                edges[edgeStart].push_back(i);
            }
        }
    }

    bool flag = false;
    do {
        flag = false;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                topoSortDegreeMinus(i, inDegree, edges);
                flag = true;
            }
        }
    } while (flag);

    for (int i = 1; i <= n; i++) {
        if (inDegree[i] > 0)
            return true;
    }
    return false;
}

bool calculateLogicDFS(unordered_map<string, node> &nodeMap,
                       unordered_map<string, bool> &visited, string ID) {
    node &curNode = nodeMap[ID];
    if (visited[ID])return curNode.value;
    visited[ID] = true;
    if (ID[0] == 'I')return curNode.value;
    if (curNode.type == "NOT") {
        calculateLogicDFS(nodeMap, visited, curNode.signals[0]);
        curNode.value=!nodeMap[curNode.signals[0]].value;
    } else if (curNode.type == "AND") {
        curNode.value = true;
        for(int i=0;i<curNode.input;i++){
            calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
            curNode.value &= nodeMap[curNode.signals[i]].value;
            if(!curNode.value)break;
        }
    } else if (curNode.type == "OR") {
        curNode.value = false;
        for(int i=0;i<curNode.input;i++){
            calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
            curNode.value |= nodeMap[curNode.signals[i]].value;
            if(curNode.value)break;
        }
    } else if (curNode.type == "XOR") {
        curNode.value = false;
        for(int i=0;i<curNode.input;i++){
            calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
            curNode.value ^= nodeMap[curNode.signals[i]].value;
        }
    } else if (curNode.type == "NAND") {
        curNode.value = true;
        for(int i=0;i<curNode.input;i++){
            calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
            curNode.value &= nodeMap[curNode.signals[i]].value;
            if(!curNode.value)break;
        }
        curNode.value=!curNode.value;
    } else if (curNode.type == "NOR") {
        curNode.value = false;
        for(int i=0;i<curNode.input;i++){
            calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
            curNode.value |= nodeMap[curNode.signals[i]].value;
            if(curNode.value)break;
        }
        curNode.value=!curNode.value;
    }
    return curNode.value;
}

void calculateLogic(unordered_map<string, node> &nodeMap) {
    unordered_map<string, bool> visited;
    for(auto iter=nodeMap.begin();iter!=nodeMap.end();iter++){
        if(!visited[iter->first])
            calculateLogicDFS(nodeMap,visited,iter->first);
    }
}

void solve() {
    // Read Part 1
    int m, n;
    cin >> m >> n;
    unordered_map<string, node> nodeMap;
    for (int i = 1; i <= n; i++) {
        node curNode;
        cin >> curNode.type >> curNode.input;
        for (int j = 0; j < curNode.input; j++) {
            cin >> curNode.signals[j];
        }
        nodeMap["O" + to_string(i)] = curNode;
    }

    // Check Circle: Topological Sort
    bool haveCircle = checkCircle(n, nodeMap);

    // Read Part 2
    int s;
    cin >> s;
    vector<vector<int>> inputs;
    inputs.resize(s);
    for (int i = 0; i < s; i++) {
        inputs[i].push_back(m);
        int t;
        for (int j = 0; j < m; j++) {
            cin >> t;
            inputs[i].push_back(t);
        }
    }
    vector<vector<int>> outputs;
    outputs.resize(s);
    for (int i = 0; i < s; i++) {
        int k;
        cin >> k;
        outputs[i].push_back(k);
        int t;
        for (int j = 1; j <= k; j++) {
            cin >> t;
            outputs[i].push_back(t);
        }
    }

    if (haveCircle) {
        cout << "LOOP\n";
        return;
    }
    for (int i = 0; i < s; i++) {
        for (int j = 1; j <= m; j++) {
            node tmpNode;
            tmpNode.value = inputs[i][j];
            nodeMap["I" + to_string(j)] = tmpNode;
        }
        calculateLogic(nodeMap);
        for(int j=1;j<=outputs[i][0];j++){
            cout<<nodeMap["O"+to_string(outputs[i][j])].value<<" ";
        }
        cout<<"\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
        solve();
}