当前位置：首页 > news >正文

ccfcsp-202403（1、2、3、4）

news 2024/9/22 13:00:45

202403-1 词频统计

#include <bits/stdc++.h>
using namespace std;
int main(){int n, m;cin >> n >> m;vector<int> vec(m + 1, 0);unordered_map<int,int> mmap;for(int i = 0; i < n; i++){int l;cin >> l;unordered_set<int> mset;while(l--){int k;cin >> k;mmap[k]++;mset.insert(k);}for(auto it : mset){vec[it]++;}}for(int i = 0; i < m; i++) {cout << vec[i + 1] << " " << mmap[i + 1] << endl;}return 0;
}

202403-2 相似度计算

#include <bits/stdc++.h>
using namespace std;
int main(){int n, m;cin >> n >> m;unordered_set<string> mset1;unordered_set<string> mset2;string s;for(int i = 0; i < n; i++){cin >> s;string str = "";for(char c : s){if(isupper(c)){c += 32;}str += c;}mset1.insert(str);}for(int i = 0; i < m; i++){cin >> s;string str = "";for(char c : s){if(isupper(c)){c += 32;}str += c;}mset2.insert(str);}unordered_set<string> intersection;for(auto it : mset1){if(mset2.find(it) != mset2.end()){intersection.insert(it);}}cout << intersection.size() << endl << mset1.size() + mset2.size() - intersection.size();return 0;
}

202403-3 化学方程式配平

#include <bits/stdc++.h>
using namespace std;int main(){int n, m;cin >> n;while(n--){cin >> m;int l = 0;vector<vector<double>> matrix(50,vector<double>(50, 0));vector<string> vec(m);map<string,int> rowmap;//记录物质中的元素的位置（行数）int row = 0;unordered_set<string> set;//记录元素个数for(int i = 0; i < m; i++){//一个物质unordered_map<string, int> elem;cin >> vec[i];for(int j = 0; j < vec[i].size();){string element = "";string num = "";while(!isnumber(vec[i][j])){element += vec[i][j];j++;}while(isnumber(vec[i][j])){num += vec[i][j];j++;}elem[element] = stoi(num);if(rowmap.find(element) == rowmap.end()){rowmap[element] = l++;}matrix[rowmap[element]][i] = stoi(num);set.insert(element);}row = row > set.size() ? row : set.size();}//处理矩阵int flag = 0, j = -1;//考察矩阵的第一列上的元素while(flag == 0){j++;for(int i = 0; i < row; i++){if(matrix[i][j] != 0){flag = 1;break;}}}//若不全为零int a = 0;for(; j < m; j++){if(matrix[a][j] == 0){ //如果其为 0，则将该行与后面的某一个第一列非 0 的行交换，使第一行第一列的元素非0int b = a + 1;while(matrix[b][j] == 0 && b < row)b++;if(b >= row)break;for(int col = j; col < m; col++){swap(matrix[a][col], matrix[b][col]);}}//令后续所有行减去第一行的适当倍数，使得后续所有行的第一列元素为 0for(int t = j + 1; t < row; t++){double k = matrix[t][j] / matrix[a][j];for(int col = j; col < m; col++){matrix[t][col] -= matrix[a][col] * k;}}a++;}int r = 0;for(int i = 0; i < row; i++){int flag = 0;for(int j = 0; j < m; j++){if(matrix[i][j] != 0){flag = 1;break;}}if(flag)r++;}if(r < m){cout << "Y" << endl;}else{cout << "N" << endl;}}return 0;
}

202403-4 十滴水

#include <bits/stdc++.h>
using namespace std;
vector<int> vec(3e5, 0);
void dfs(int x,int c){if(x <= 0 || x > c)return;if(vec[x] >= 5){vec[x] = 0;int l = x - 1, r = x + 1;while(vec[l] == 0 && l > 0)l--;while(vec[r] == 0 && r <= c)r++;if(l > 0){vec[l]++;}if(r <= c){vec[r]++;}dfs(l,c);dfs(r,c);}
}
int main(){int c,m,n;cin >> c >> m >> n;for(int i = 0; i < m; i++){int x, y;cin >> x >> y;vec[x] = y;}for(int i = 0; i < n; i++){int x;cin >> x;vec[x]++;dfs(x,c);int res = 0;for(int j = 1; j <= c; j++){if(vec[j] != 0)res++;}cout << res << endl;}return 0;
}

满分解（使用小根堆）

int main() {int n,m,k;map<int, int> mp;cin >> n >> m >> k;for (int i = 1; i <= m; i++) {int x, w;cin >> x >> w;mp[x] = w;}priority_queue<int, vector<int>, greater<int>> pq;for (int i = 1; i <= k; i++) {int p; cin >> p;mp[p]++;if (mp[p] == 5) pq.push(p);while (!pq.empty()) {int u = pq.top(); pq.pop();mp.erase(u);auto it = mp.lower_bound(u);if (it != mp.begin()) {(--it)->second++;if (it->second == 5) pq.push(it->first);}it = mp.upper_bound(u);if (it != mp.end()) {it->second++;if (it->second == 5) pq.push(it->first);}}cout << mp.size() << endl;}return 0;
}