（CCF CAT 训练二）2023-2024年中国计算机应用技术大赛- 全国算法精英大赛

Flower

反悔贪心，按照时间对花朵进行排序，从0到n-1遍历花朵，如果当前堆中元素小于当前花朵的绽放时间t，直接放入堆中，否则花朵金币数放入堆中并弹出堆中金币数最小值，最后如果堆中元素个数大于k，一直弹出堆中最小金币数直到元素个数等于k

#include #include #include #include using namespace std;const int N=1e5+5;int t[N], w[N];int main(){int n, k;cin>>n>>k;for(int i=0;i<n;i++){cin>>t[i];}for(int i=0;i<n;i++){cin>>w[i];}vector<pair<int,int>> v;for(int i=0;i<n;i++){v.push_back({t[i], w[i]});}priority_queue<int, vector<int>, greater<int>> pq;sort(v.begin(), v.end(), [](const pair<int,int>& p1, const pair<int,int>&p2){return p1.first < p2.first;});int ans = 0;for(int i=0;i<n;i++){if(v[i].first > int(pq.size())){pq.push(v[i].second);ans+=v[i].second;}else{ans+=v[i].second - pq.top();pq.push(v[i].second);pq.pop();}// if(pq.size())}// cout<<pq.size()<<" ";while(int(pq.size()) > k){ans-=pq.top();pq.pop();}cout<<ans;}

Tree

先构造二叉搜索树，询问的时候再进行递归求节点深度

#include #include #include #include using namespace std;struct node{node* l = nullptr,*r = nullptr;int v;node(int v1):v(v1){}};node* root = nullptr;void insert(int i){if(root==nullptr){root = new node(i);}else{node* pre = root;node* tmp = root->v>i" />->l:root->r;while(tmp!=nullptr){pre = tmp;tmp = tmp->v>i? tmp->l:tmp->r;}tmp = new node(i);if(pre->v > i){pre->l = tmp;}else{pre->r = tmp;}}}int find(int i){node* tmp = root;int deep = 1;while(tmp!=nullptr){tmp = tmp->v>i? tmp->l:tmp->r;deep++;}return deep;}int main(){int n;cin>>n;for(int i=0;i<n;i++){int a;cin>>a;insert(a);}for(int i=0;i<n;i++){int a;cin>>a;cout<<find(a)<<endl;}}

Best Travel Plans

使用动态规划， 遍历1到n座城市，dp[i][j]表示到达第i座城市且花费j时间的最大旅行活动数
转移方程 $dp[i][j]=max(dp[i][j],dp[i-1][k]+在第i座城市花费j-k-t[i]获得旅行活动数)$
这里代码超时了，还没想好优化思路，后面有时间再补上
用枚举加贪心，枚举前$i$个城市, 除去旅行时间，剩下remain时间，遍历前$i$个城市，每次选择最大活动数量，时间复杂度O( n 2m)O(n^2m) O(n2m) 代码如下

//动态规划超时#include #include #include #include#include using namespace std;const int N = 1e2+5;const int M = 2e4+5;int e[N], d[N], t[N];long long dp[N][M];int main(){int n, m;cin>>n>>m;for(int i=2;i<=n;i++){cin>>t[i];}for(int i=1;i<=n;i++){cin>>e[i];}for(int i=1;i <= n;i++){cin>>d[i];}memset(dp, -1, sizeof dp);dp[1][0]= 0;for(int i=1;i<=m;i++){if(e[1] - d[1]*(i-1) >=0 )dp[1][i] = dp[1][i-1] + e[1] - d[1]*(i-1);else{dp[1][i] = dp[1][i-1];}// cout<<i<<" "<<dp[1][i]<<endl;}long long ans = 0;for(int i=2;i<=n;i++){// dp[i]for(int j=0; j<=m;j++){// dp[i][j] = dp[i-1][j];for(int k=0;k<=j-t[i]; k++){if(dp[i-1][k]!=-1)dp[i][j] = max(dp[i][j], dp[i-1][k] + (long long)e[i]*(j-k-t[i]) - (long long)(j-k-t[i])*(j-k-t[i] -1)*d[i]/ 2);// cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j]<<endl;}ans=max(ans, dp[i][j]);// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;}// cout<<}cout<<ans;}

//枚举和贪心#include#include#include#include#includeusing namespace std;const int N = 1e2 + 5;const int M = 2e4 + 5;int t[N], e[N], d[N];int pos[N];int main(){// ios_base::sync_with_stdio(false);// cin.tie(NULL);int n, m;// cin>>n>>m;scanf("%d%d", &n, &m);t[1] = 0;for (int i = 2; i <= n; i++) {// cin>>t[i];scanf("%d", &t[i]);}for (int i = 1; i <= n; i++) {// cin>>e[i];scanf("%d", &e[i]);}for (int i = 1; i <= n; i++) {// cin>>d[i];scanf("%d", &d[i]);}std::vector<std::vector<int>> p(n + 1);for (int i = 1; i <= n; ++i) {for (int j = 0; e[i] - j * d[i] > 0 && j <= m; ++j) {p[i].emplace_back(e[i] - j * d[i]);}}int ans = 0;int travel = 0;for (int i = 1; i <= n; i++) {travel += t[i];memset(pos, 0, sizeof pos);int remain = m - travel;if(remain <= 0)break; //这里一定要加上判断int tmp_ans = 0;while (remain) { //否则remain为负数会进入循环，一直没找到这个错误int id = -1, mx = 0;for (int j = 1; j <= i; j++) {if(pos[j] == p[j].size())continue;if (p[j][pos[j]] > mx) {id = j;mx = p[j][pos[j]];}}if (id != -1) {tmp_ans += p[id][pos[id]];pos[id] ++;remain--;}else {break;}}ans = max(ans, tmp_ans);}printf("%d", ans);}

Hearthstone

思路动态规划，有点麻烦的是需要连接成环，这里就是分三种情况，分别是第1次分别选择1，2，3所对应的卡片，再取三种情况的最大值，中间的转移方程比较简单，就是要枚举满足条件（任何一个位置的卡牌都要比相邻的两张卡牌的法力消耗值都高或都低）的状态就ok了

#include #include #include #include#include using namespace std;const int N = 1e5+5;long long dp[N][4][4];int arr[N][4];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>arr[i][1] >> arr[i][2]>> arr[i][3];}memset(dp, -1, sizeof dp);// dp[2][1][2] = arr[2][1] + arr[1][2];// dp[2][1][3] = arr[2][1] + arr[1][3];dp[2][2][1] = arr[2][2] + arr[1][1];// dp[2][2][3] = arr[2][2] + arr[1][3];dp[2][3][1] = arr[2][3] + arr[1][1];// cout<<dp[2][3][1]<<" ";// dp[2][3][2] = arr[2][3] + arr[1][2];for(int i=3;i<=n;i++){dp[i][1][2] = dp[i-1][2][1] + arr[i][1];dp[i][1][3] = max(dp[i-1][3][1], dp[i-1][3][2]) + arr[i][1];dp[i][2][1] = max(dp[i-1][1][2], dp[i-1][1][3]) + arr[i][2];dp[i][2][3] = max(dp[i-1][3][1], dp[i-1][3][2]) + arr[i][2];// cout<<i<<" "<<dp[i][2][3]<<" "<<endl;dp[i][3][1] = max(dp[i-1][1][3], dp[i-1][1][2]) + arr[i][3];dp[i][3][2] = dp[i-1][2][3] + arr[i][3];} long long ans = max(max(dp[n][2][1], dp[n][3][2]), dp[n][3][1]);// cout<memset(dp, -1, sizeof dp);dp[2][1][2] = arr[2][1] + arr[1][2];// dp[2][1][3] = arr[2][1] + arr[1][3];// dp[2][2][1] = arr[2][2] + arr[1][1];// dp[2][2][3] = arr[2][2] + arr[1][3];// dp[2][3][1] = arr[2][3] + arr[1][1];dp[2][3][2] = arr[2][3] + arr[1][2];for(int i=3;i<=n;i++){dp[i][1][2] = dp[i-1][2][1] + arr[i][1];dp[i][1][3] = max(dp[i-1][3][1], dp[i-1][3][2]) + arr[i][1];dp[i][2][1] = max(dp[i-1][1][2], dp[i-1][1][3]) + arr[i][2];dp[i][2][3] = max(dp[i-1][3][1], dp[i-1][3][2]) + arr[i][2];dp[i][3][1] = max(dp[i-1][1][3], dp[i-1][1][2]) + arr[i][3];dp[i][3][2] = dp[i-1][2][3] + arr[i][3];} ans = max(ans, max(max(max(dp[n][3][1], dp[n][3][2]), dp[n][1][2]), dp[n][1][3]));// cout<memset(dp, -1, sizeof dp);// dp[2][1][2] = arr[2][1] + arr[1][2];dp[2][1][3] = arr[2][1] + arr[1][3];// dp[2][2][1] = arr[2][2] + arr[1][1];dp[2][2][3] = arr[2][2] + arr[1][3];// dp[2][3][1] = arr[2][3] + arr[1][1];// dp[2][3][2] = arr[2][3] + arr[1][2];for(int i=3;i<=n;i++){dp[i][1][2] = dp[i-1][2][1] + arr[i][1];dp[i][1][3] = max(dp[i-1][3][1], dp[i-1][3][2]) + arr[i][1];dp[i][2][1] = max(dp[i-1][1][2], dp[i-1][1][3]) + arr[i][2];dp[i][2][3] = max(dp[i-1][3][1], dp[i-1][3][2]) + arr[i][2];dp[i][3][1] = max(dp[i-1][1][3], dp[i-1][1][2]) + arr[i][3];dp[i][3][2] = dp[i-1][2][3] + arr[i][3];} ans = max(ans,max(max(dp[n][1][2], dp[n][1][3]), dp[n][2][3]));cout<<ans; }

Hotpot

这里只需要求出一边的方案数目，总方案数目是两者乘积，如何求一边的方案数呢，可以想象位置有人状态设置，没人设置0，整个就是二进制串，需要求的是合法的二进制串数目，要求不能存在两个1相邻的情况，这不就是数位dp吗，使用dfs求

#include #include #include #include#include using namespace std;int mod=1e9+7;const int N=1e4+5;long long dp[N][2];// string str;int n;long long dfs(int i, int mask){if(dp[i][mask]!=-1)return dp[i][mask];if(i==n)return 1LL;long long ans = 0;ans = (ans+dfs(i+1, 0))%mod;if(mask!=1)ans = (ans + dfs(i+1, 1))%mod;dp[i][mask] = ans;return ans;}int main(){// int n;cin>>n;memset(dp, -1, sizeof dp);long long ans = dfs(0,0);cout<<(ans*ans)%mod;}

补充两道(CCF CAT训练一）题目

Card

当存在$i,j$，其中$1\le i\le n,1\le j\le n$，且 x i, x jx_i, x_j xi​,xj​最大公因数为1，则是满足要求的两种地铁票，还存在特殊情况是当出现 x i=1x_i=1 xi​=1，也是满足要求的，取所有满足要求的最小值即可

#include #include #include #include#include using namespace std;int x[105], v[105];int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>x[i];}for(int i=0;i<n;i++){cin>>v[i];}int ans = 0x3f3f3f3f;for(int i=0;i<n;i++){if(x[i]==1){ans=min(ans, v[i]);}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i!=j && __gcd(x[i], x[j])==1){ans=min(ans, v[i]+v[j]);}}}cout<<(ans==0x3f3f3f3f" />-1:ans);}

The diameter of a rectangle

比较经典的单调栈的题目，先使用单调栈找到每个矩形$i$最靠近它且矩形长小于它的长位置下标，比如左边为$j$，右边为$k$，则可以找到一个大矩形长宽分别为 a ia_i ai​, b j+1 + b j+2 +…+ b i+…+ b k−2 + b k−1 b_{j+1} + b_{j+2}+…+b_i+…+b_{k-2}+b_{k-1} bj+1​+bj+2​+…+bi​+…+bk−2​+bk−1​，两个取最小值作为正方形的边长，遍历1到n取面积最大值，宽的计算可以使用前缀和

#include #include #include #include#include #include using namespace std;const int N=1e6+5;int arr[N][2];int left1[N], right1[N];long long pre[N];int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>arr[i][0]>>arr[i][1];pre[i+1] = pre[i] + arr[i][1];right1[i] = n;}memset(left1, -1, sizeof left1);// memset(right1, )stack<int> l, r;for(int i=0;i<n;i++){while(!l.empty() && arr[l.top()][0] > arr[i][0]){right1[l.top()] = i;l.pop();}l.push(i);}for(int i=n-1;i>=0;i--){while(!r.empty() && arr[r.top()][0] > arr[i][0]){left1[r.top()] = i;r.pop();}r.push(i);}long long ans=0;for(int i=0;i<n;i++){// cout<<i<<" "<<left1[i]<<" "<<right1[i]<<endl;long long lo = min(pre[right1[i]] - pre[left1[i] + 1], (long long)arr[i][0]);ans=max(ans, lo*lo);}cout<<ans;}