CSDN第11期周赛题解

文章目录

• CSDN第11期周赛题解
• • T1-圆小艺
  • • 题面
    • 算法(模拟,数学)
    • 代码(C++)
  • T2-K皇把妹
  • • 题面
    • 算法(枚举)
    • 代码(C++)
  • T3-筛选宝物
  • • 题面
    • 算法(DP,01背包)
    • 代码(C++)
  • T4-圆桌
  • • 题面
    • 算法(贪心,排序)
    • 代码(C++)

T1-圆小艺

题面

最近小艺酱渐渐变成了一个圆滑的形状-球！！ 小艺酱开始变得喜欢上球！ 小艺酱得到n个同心圆。 小艺酱对着n个同心圆进行染色。 相邻的圆范围内不能有相同的颜色。相隔一层的圆颜色相同。 小艺酱想知道圆最外层的那种颜色全部染了多少？

算法(模拟,数学)

按半径从大到小排列后, 一共有1∼n1 \sim n1∼n层， 1+2×k,(k>=0)1 + 2 \times k, (k >= 0)1+2×k,(k>=0)层颜色都相同，枚举并计算每一对相邻的有着不同颜色的同心圆的圆环面积SSS，枚举过程中累计答案即可。注意π=arccos(−1)\pi=arccos(-1)π=arccos(−1)，在C++中等价于π=acos(−1)\pi=acos(-1)π=acos(−1)，且需要引入cmath头文件。

代码(C++)

#include 
#include 
#include 
#include using namespace std;const double PI = acos(-1);
const int N = 1010;int n;
int r[N];int main()
{cin >> n;for(int i = 0; i < n; i ++) cin >> r[i];sort(r, r + n, greater());double res = 0;for(int i = 0; i < n; i += 2)res += (PI * r[i] * r[i] - PI * r[i + 1] * r[i + 1]);printf("%.3lf\n", res);return 0;
}

T2-K皇把妹

题面

存在n个节点，目标节点在m。 每个节点有自己的权值a。 在权值k内（含k值）选择一个权值非0节点且与目标节点距离最近。 节点i与节点j的距离为abs(i-j)。

算法(枚举)

按题意向目标节点的两边进行枚举即可，注意权值不大于kkk的同时，还要权值非000。

代码(C++)

#include 
#include 
#include using namespace std;const int N = 110;
int n, m, k;
int v[N];int main()
{cin >> n >> m >> k;for(int i = 1; i <= n; i ++) cin >> v[i];int res1 = 0, res2 = n;bool flag1 = false, flag2 = false;for(int i = m + 1; i <= n; i ++) // 向右边枚举答案{if(v[i] && v[i] <= k){flag1 = true;res1 = i - m;break;}}for(int i = m - 1; i >= 1; i --) // 向左边枚举答案{if(v[i] && v[i] <= k){flag2 = true;res2 = m - i;break;}}if(flag1 && flag2) cout << min(res1, res2) << endl;else if(flag1) cout << res1 << endl;else cout << res2 << endl;return 0;
}

T3-筛选宝物

题面

已知存在n个宝物，每个宝物都有自己的质量m和价值v，在考虑选择宝物时只能选择总质量小于等于M的方案，请问在最
优方案下选择宝物，能获取到最大价值V是多少？

算法(DP,01背包)

动态规划入门题，不懂的朋友可以查看csdn上的详解讲解。

代码(C++)

#include 
#include 
#include using namespace std;
const int N = 110, M = 1010;int n, m;
int w[N], v[N];
int f[N][M];int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> w[i] >> v[i];for(int i = 1; i <= n; i ++)for(int j = 0; j <= m; j ++){if(j >= w[i]){f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);}else f[i][j] = f[i - 1][j];}cout << f[n][m] << endl;return 0;
}

T4-圆桌

题面

有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边，但是每位客人希望自己左右边上分别有一些空座位，不然会觉得害羞。注意，如果一个客人所在的圆桌只有他一个人，那么他左边的空座位数量就是他右边的空座位数量。 试问主人需要准备多少个座位，才能让每个客人舒适的坐下。

算法(贪心,排序)

抽象成一个无限大圆上有若干个点，每个点的两侧的虚拟点(以单位距离扩张)需要满足一定的限制，具体是当前点的右边的虚拟点数R[i]R[i]R[i]要满足某一个点的左边虚拟点数L[j]L[j]L[j]最接近即可，于是我们将L、RL、RL、R排序，对于每一个相交的圆弧，我们需要将他们间的虚拟点数尽可能多的被同时用到，于是就可以取cnt=max(L[i],R[i])cnt = max(L[i], R[i])cnt=max(L[i],R[i])作为最大被用到的虚拟点数(每个点数被用到的次数只有两种情况：1和2)，那么相当于是空座椅的个数加上cntcntcnt，由于每个人也需要占用一个空座椅，最后的答案还需要加上人的个数nnn，数据范围为1e5×1e91e5 \times 1e91e5×1e9，会爆intintint，答案需要用longlonglong \ longlong long存储。

代码(C++)

#include 
#include 
#include using namespace std;typedef long long LL;const int N = 10010;int n;
int L[N], R[N];int main()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> L[i] >> R[i];sort(L + 1, L + 1 + n);sort(R + 1, R + 1 + n);LL res = n;for(int i = 1; i <= n; i ++) res += max(L[i], R[i]);cout << res << endl;return 0;
}