CSDN第11期周赛总结
一觉醒来九点多,作为正儿八经的‘懒学生’,牙没刷脸没洗下床打开电脑就参加周赛了。
可能一开始脑子比较晕乎,第一题愣是没看懂????
因为最初不知道可以换题(我记得之前是只能一题一题写的)
最初还以为嘚零鸭蛋的说T_T
发现可以一次性查看所有题目后,果断先跳题!
看一题,一题看不懂........(可恶!是我阅读理解不太行)
看到第三题终于发现看的懂的了
结果是自己还没认真学的背包问题(呸呸呸,最近事件很多,看样子得等寒假才有足够的时间让自己傲游算法的世界....可是要学的东西又不单单只有算法....哎)
看了第四题,脑回路有点更不上,只好硬着头皮开始A了
圆小艺
最近小艺酱渐渐变成了一个圆滑的形状-球!! 小艺酱开始变得喜欢上球! 小艺酱得到n个同心圆。 小艺酱对着n个同心圆 进行染色。 相邻的圆范围内不能有相同的颜色。相隔一层的圆颜色相同。 小艺酱想知道两种颜色最大中最外层圆的那种颜 色染了多少?
原来给的是每个圆的半径,只要按半径大小排完序之后,外往里加减即可
对来Π的精度要高一点
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<double> nums;
double num,result=0;
int N;
scanf("%d",&N);
for(int z=0;z<N;z++){
scanf("%lf",&num);
nums.push_back(num);
}
sort(nums.begin(),nums.end());
int flag = (nums.size()-1) % 2;
for(int z=nums.size()-1;z>=0;z--){
if(z%2==flag) {
result += 3.14159265359 * nums[z] * nums[z];
}else {
result -= 3.14159265359 * nums[z] * nums[z];
}
}
printf("%.3f",result);
return 0;
}
K皇把妹
存在n个节点,目标节点在m。 每个节点有自己的权值a。 在权值k内选择一个权值非0节点且与目标节点距离最近。 节点 i与节点j的距离为abs(i-j)。
................
数据量比较小,直接全遍历即可
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,M,K,nums[1001];
cin >> N >> M >>K;
for(int z=1;z<=N;z++) cin >> nums[z];
int result = N;
for(int z=1;z<=N;z++){
if(z!=M && nums[z]>0){
if(nums[z]<=K){
result = min(result,abs(z-M));
}
}
}
cout << result << endl;
return 0;
}
筛选宝物
已知存在n个宝物,每个宝物都有自己的质量m和价值v,在考虑选择宝物时只能选择总质量小于等于M的方案,请问在最 优方案下选择宝物,能获取到最大价值V是多少? (请选择C、C++、Java、Javascript、python中的任意一种语言 进行作答。选择其他编程语言作答可能影响笔试成绩,感谢配合)
这题很奇怪,一模一样的代码,结果第一次提交通过部分样例,第二次直接编译错误????
而且我用的编译器一直都是C++,当时我也反复确认编译器好几次了
t_T,别人直接用01背包的解法秒A,我还是傻傻的用自己方法,结果有俩测试点没过,还有我后面修改后的提交直接给我编译错误???成绩报告只找到我第一次有效提交时候的代码
#include<bits/stdc++.h>
using namespace std;
struct Node{
int m,v;
}nums[1001];
bool cmp(Node x,Node y){
return x.m < y.m;
}
int main()
{
int N,M;
cin >> N >> M;
for(int z=0;z<N;z++) cin >> nums[z].m >> nums[z].v;
sort(nums,nums+N,cmp);
if(nums[0].m>M) cout << 0 << endl;
else
{
vector<pair<int,int>> key;
int result=nums[0].v;
key.emplace_back(0,0);
key.emplace_back(nums[0].m,nums[0].v);
for(int z=1;z<N;z++){
if(nums[z].m>M) break;
int len = key.size();
for(int z1=0;z1<len;z1++){
auto x = key[z1];
if(x.first+nums[z].m<=M){
result = max(result,x.second+nums[z].v);
key.emplace_back(x.first+nums[z].m,x.second+nums[z].v);
}
}
}
cout << result << endl;
}
return 0;
}
圆桌
有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边,但是每位客人希望自己左右边上分别有一些空座位, 不然会觉得害羞。注意,如果一个客人所在的圆桌只有他一个人,那么他左边的空座位数量就是他右边的空座位数量。 试 问主人需要准备多少个座位,才能让每个客人舒适的坐下。
想到要按左右间隔人数排序了,结果想多了...看来别人的代码,原来只要排完序
result += max(left[n],right[n])+1;即可....
我一开始发现左右相等的人自己独自座一桌肯定就是最小解,结果在这上面钻牛角尖了
错误代码仅参考个人想法(靠多设了一个flag多此一举,不然说不定就能过了)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Node{
int id;
LL r,l;
}nums1[10001],nums2[10001];
bool cmp1(Node x,Node y){
return x.l > y.l;
}
bool cmp2(Node x,Node y){
return x.r > y.r;
}
bool apr[10001] = {false};
int main()
{
long long result=0;
int N;
cin >> N;
for(int z=0;z<N;z++) {
nums1[z].id = nums2[z].id = z;
scanf("%lld %lld",&nums1[z].l,&nums1[z].r);
nums2[z].l = nums1[z].l;
nums2[z].r = nums2[z].r;
}
sort(nums1,nums1+N, cmp1);
sort(nums2,nums2+N, cmp2);
for(int z=0;z<N;z++) {
if(nums1[z].r==nums1[z].l){
apr[nums1[z].id] = true;
result += max(nums1[z].r, nums1[z].l) + 1;
}
}
for(int z=0;z<N;z++){
if(apr[nums1[z].id]) continue;
apr[nums1[z].id] = true;
if(nums1[z].l==nums1[z].r){
result+=nums1[z].l+1;
continue;
}
long long flag = min(nums1[z].l,nums1[z].r);
long long key=max(nums1[z].l,nums1[z].r)+1;
// cout << key << endl;
for(int z1=0;z1<N;z1++){
if(!apr[nums2[z1].id]){
if(max(nums2[z1].l,nums2[z1].r)<=flag){
flag = min(nums2[z1].l,nums2[z1].r);
// cout << flag << endl;
key+=flag;
apr[nums2[z1].id] = true;
}
}
}
result+=key;
// cout << z << " " << result << endl;
}
cout << result;
return 0;
}
最后感觉这次题目还是挺不错的,而且前30有奖品,比之前前10多,刚好捡了个书包~