作者归档：Jack

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

CSP 202009-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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int n,k,t,xl,yd,xr,yu;
int x[1005], y[1005];
bool visited,stayed;

inline bool checkCoord(int posx,int posy){
    return xl<=posx&&posx<=xr&&yd<=posy&&posy<=yu;
}

void checkPerson(){
    visited = stayed = false;
    int cnt=0;
    for(int i=0;i<t;i++){
        bool flag=checkCoord(x[i],y[i]);
        if(!flag)cnt=0;
        else cnt++;
        if(cnt>0)visited=true;
        if(cnt>=k){
            stayed=true;
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k>>t>>xl>>yd>>xr>>yu;
    int vis=0,stay=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<t;j++){
            cin>>x[j]>>y[j];
        }
        checkPerson();
        vis+=visited;
        stay+=stayed;
    }
    cout<<vis<<"\n"<<stay<<"\n";
}

CSP 202009-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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int n,posx,posy;
struct s{
    int dist2;
    int id;
    bool operator < (const s& s2) const{
        if(dist2!=s2.dist2)return dist2 < s2.dist2;
        return id<s2.id;
    }
}arrS[1000];
inline int calDist(int posx,int posy, int x, int y){
    return (posx-x)*(posx-x)+(posy-y)*(posy-y);
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>posx>>posy;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        arrS[i].dist2=calDist(posx,posy,x,y);
        arrS[i].id=i;
    }
    sort(arrS+1,arrS+1+n);
    for(int i=1;i<=3;i++){
        cout<<arrS[i].id<<"\n";
    }
}

CSP 202012-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
import copy

file_template = {
    "isDirectory": False,
    "fileSize": 0,
    "childSize": 0,
    "childQuota": 0,
    "descendantQuota": 0,
    "descendants": {}
}
root_directory = {
    "isDirectory": True,
    "fileSize": 0,
    "childSize": 0,
    "childQuota": 0,
    "descendantQuota": 0,
    "descendants": {}
}

def filepath_resolver(filepath: str):
    fpArr = filepath.split('/')
    fpArr.pop(0)
    return fpArr

def visit(filepath):
    if filepath == '/':
        return root_directory
    fpArr = filepath_resolver(filepath)
    fileIter = root_directory
    try:
        for file in fpArr:
            fileIter = fileIter["descendants"][file]
    except KeyError:
        return None
    return fileIter

def checkQuotaLimit(fileIter, filesize, descendants = True, child = True):
    if descendants:
        if fileIter["descendantQuota"] != 0:  # 检查后代文件配额
            if fileIter["fileSize"] + filesize > fileIter["descendantQuota"]:
                return False
    if child:
        if fileIter["childQuota"] != 0:  # 检查孩子文件配额
            if fileIter["childSize"] + filesize > fileIter["childQuota"]:
                return False
    return True

def create(filepath, filesize, isDirectory = False):
    dstIter = visit(filepath)
    update_filesize = filesize
    if dstIter is not None:
         update_filesize -= dstIter["fileSize"]

    fpArr = filepath_resolver(filepath)
    fileIter = root_directory
    for i in range(len(fpArr)):
        file = fpArr[i]
        if file not in fileIter["descendants"].keys(): # 无该目录/文件
            curFile = copy.deepcopy(file_template)
            if i != len(fpArr) - 1: # 非末端文件
                if not checkQuotaLimit(fileIter, update_filesize, True, False): return False
                curFile["isDirectory"] = True
            else: # 末端文件
                if not checkQuotaLimit(fileIter, update_filesize): return False
                curFile["isDirectory"] = isDirectory
                curFile["fileSize"] = filesize
            fileIter["descendants"][file] = curFile
        else: # 存在该目录/文件
            curFile = fileIter["descendants"][file]
            if i != len(fpArr) - 1: # 非末端文件
                if not curFile["isDirectory"]: # 欲进入的新目录文件与普通文件重名
                    return False
                else:
                    if not checkQuotaLimit(fileIter, update_filesize, True, False): return False
            else: # 末端文件
                if curFile["isDirectory"] != isDirectory: # 欲创建的同名新文件与旧文件类型冲突
                    return False
                else: # 文件已存在，替换文件大小
                    if not checkQuotaLimit(fileIter, update_filesize): return False
                    curFile["fileSize"] = filesize
        fileIter = fileIter["descendants"][file]

    fileIter = root_directory
    for i in range(len(fpArr)):
        file = fpArr[i]
        fileIter["fileSize"] += update_filesize
        if i == len(fpArr) - 1:
            fileIter["childSize"] += update_filesize
        fileIter = fileIter["descendants"][file]
    return True

def remove(filepath):
    fpArr = filepath_resolver(filepath)
    dstIter = visit(filepath)
    if dstIter is None:
        return True

    fileIter = root_directory
    for file in fpArr:
        fileIter["fileSize"] -= dstIter["fileSize"]
        if fileIter["descendants"][file] == dstIter:
            if not dstIter["isDirectory"]:
                fileIter["childSize"] -= dstIter["fileSize"]
            break
        fileIter = fileIter["descendants"][file]
    fileIter["descendants"].pop(fpArr[-1])
    return True

def quota(filepath, child_quota, descendant_quota):
    dstIter = visit(filepath)
    if dstIter is None:
        return False
    if not dstIter["isDirectory"]:
        return False
    child_flag = child_quota == 0 or dstIter["childSize"] <= child_quota
    descendant_flag = descendant_quota == 0 or dstIter["fileSize"] <= descendant_quota
    if child_flag and descendant_flag:
        dstIter["childQuota"] = child_quota
        dstIter["descendantQuota"] = descendant_quota
        return True
    else:
        return False

def main():
    n = int(input())
    for loop in range(n):
        cmd = input().split()
        result = False
        if cmd[0] == "C":
            result = create(cmd[1], int(cmd[2]))
        elif cmd[0] == "R":
            result = remove(cmd[1])
        else:
            result = quota(cmd[1], int(cmd[2]), int(cmd[3]))
        if result:
            print("Y")
        else:
            print("N")
        # print(root_directory)

if __name__ == '__main__':
    main()

CSP 202012-2 期末预测之最佳阈值

1条回复

这题也不知道咋回事，我想了个异想天开的做法，也不知道行不行，交上去竟然过了！哈哈哈哈哈哈。
暴力的N^2做法可以得70，我写个异想天开的排序+前缀和做法100。
感觉有必要写个题解，在这里写一下。

本题的大致意思是，给出一堆人的学习努力程度（用一个非负整数表示）和其是否挂科（并不必然成正相关，其中可能混杂学习努力程度高的人也挂科的情况）。要求找到一个学习努力程度基准分数，使得用该基准评判学生的努力程度时，判断对的最多。

我主要利用差分的思想进行解题。对于一个分数，我们其实只需要知道通过与挂科的人数的差值即可。基准分数是否应该低于或高于某一特定学习努力程度分数，在于其能否为总人数作出贡献。例如，如果一个分数有3人通过，3人挂科，则不管选择比他低的基准还是比他高的基准，则都对总的人数做出了3的贡献，可以相互抵消。但若4人通过，3人挂科，则更应该优先选择比其低的基准，因为这样的话，判断对的就多了一个。

首先建立一个map对输入的数据进行排序。由于选择指标的时候只看努力程度不看人，因此可以将同努力程度的人们聚合起来。如果该人挂科，在是否通过的数组cnt里-1，如果通过则+1.这样就产生了一个差分的数组cnt。此时，该数组cnt表示的是在选定该分数作为基准后，通过的人比挂科的人多多少。

然后，对其进行前缀和操作。借助前缀和，我们可以得到数组presum，可以计算选择任意基准分数时，通过的人比挂科的人多多少。还可计算选择任意基准分数时，挂科的人比通过的人多多少（通过对计算值取负）。这样，我们分别计算高于基准分数通过的人比挂科的人多多少，和低于基准分数时挂科的人比通过的人多多少。将他们相加，就可以得到一个判断正确的人数的差分。统计这些差分的最大值，就可以算出对应的基准分数。

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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int m;
map<int, int> stat;
int arrSize = 0;
int y[100005], cnt[100005], presum[100005];

int main() {
    ios::sync_with_stdio(false);
    cin >> m;
    while (m--) {
        int y, result;
        cin >> y >> result;
        stat[y] += result ? 1 : -1;
    }
    for (auto iter = stat.begin(); iter != stat.end(); iter++) {
        int ind = iter->first, v = iter->second;
        y[arrSize] = ind;
        cnt[arrSize] = v;
        arrSize++;
    }
    presum[0]=cnt[0];
    for(int i=1;i<arrSize;i++){
        presum[i]=presum[i-1]+cnt[i];
    }
    int index=0, cmpValue=presum[arrSize-1];
    for(int i=1;i<arrSize;i++){
        int tmpV=presum[arrSize-1]-presum[i-1]*2;
        if(tmpV>=cmpValue){
            cmpValue=tmpV;
            index=i;
        }
    }
    cout<<y[index];
}

CSP 202012-1 期末预测之安全指数

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

int main() {
    long long sum=0,n;
    long long w,score;
    ios::sync_with_stdio(false);
    cin>>n;
    while(n--){
        cin>>w>>score;
        sum+=w*score;
    }
    cout<<max(0ll,sum);
}