网创优客建站品牌官网
为成都网站建设公司企业提供高品质网站建设
热线:028-86922220
成都专业网站建设公司

定制建站费用3500元

符合中小企业对网站设计、功能常规化式的企业展示型网站建设

成都品牌网站建设

品牌网站建设费用6000元

本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...

成都商城网站建设

商城网站建设费用8000元

商城网站建设因基本功能的需求不同费用上面也有很大的差别...

成都微信网站建设

手机微信网站建站3000元

手机微信网站开发、微信官网、微信商城网站...

建站知识

当前位置:首页 > 建站知识

CSDN第11次竞赛题解-创新互联

题解 T1 题面

最近小艺酱渐渐变成了一个圆滑的形状 - 球!! 小艺酱开始变得喜欢上球!小艺酱得到 n n n 个同心圆。

金秀ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18980820575(备注:SSL证书合作)期待与您的合作!

小艺酱对着 n n n 个同心圆进行染色。 相邻的圆范围内不能有相同的颜色。相隔一层的圆颜色相同。 小艺酱想知道圆最外层的那种颜色全部染了多
少?

思路

发现只有两种颜色,设最外层的那种颜色为 a a a ,另一种为 b b b 。

整个过程相当于先把大的圆染成 a a a 颜色,再把次大的染成 b b b 颜色(会覆盖原来的颜色),再把第三大的染成 a a a 颜色……

由于是同心圆,可以直接算,圆的面积是 S = π r 2 S=\pi r^2 S=πr2 ,从大往小染色更新答案,同色加上,异色减去即可(x&1相当于 x x x 除以 2 2 2 的余数)。

另,C++ 中的 π \pi π 可以使用acos(-1)

代码
#includeusing namespace std;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int a[10101010];
double ans;
signed main(){cin>>n;
	f(i,1,n)cin>>a[i];
	sort(a+1,a+n+1);
	g(i,n,1){if((n-i)&1)ans-=a[i]*a[i];
		else ans+=a[i]*a[i];
	}
	printf("%.3lf",ans*acos(-1));
	return 0;
}
T2 题面

存在 n n n 个节点,目标节点在 m m m。 每个节点有自己的权值 a a a。 在权值 k k k 内(含 k k k 值)选择一个权值非 0 0 0 节点且与目标节点距离最近。

节点 i i i 与节点 j j j 的距离为 a b s ( i − j ) abs(i-j) abs(i−j)。

思路

枚举选择的节点,先判断是否符合要求,再更新答案,C++ 有自带的绝对值函数即题面中的abs()

注意要输出的是最近的距离。

代码
#includeusing namespace std;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int a[20202020];
signed main(){cin>>n>>m>>s;l=-1e9;
	f(i,1,n)scanf("%lld",&a[i]);
	f(i,1,n)if(a[i]&&a[i]<=s){if(abs(l-m)>abs(i-m))l=i;
	}
	cout<
T3 题面

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

思路

经典 DP 题,设 d p i , j dp_{i,j} dpi,j​ 为选择前 i i i 个宝物,总质量恰好为 j j j ,能得到的大价值。

由定义得到转移式 d p i , j = max ⁡ { d p i − 1 , j , d p i − 1 , j − m i + v i } dp_{i,j}=\max\{dp_{i-1,j},dp_{i-1,j-m_i}+v_i\} dpi,j​=max{dpi−1,j​,dpi−1,j−mi​​+vi​} ,注意特判边界。

另外,只要保证状态 d p i , a dp_{i,a} dpi,a​不会向 d p i , b dp_{i,b} dpi,b​转移就可以去掉第一维 i i i,一种方法是反着循环,详情见代码。

代码
#includeusing namespace std;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int dp[2020202];
signed main(){cin>>n>>m;
	f(i,1,n){cin>>s>>l;
		g(i,m,s)dp[i]=max(dp[i],dp[i-s]+l);
	}
	s=0;
	f(i,0,m)if(s
T4 题面

有 N N N 个客人与足够多张的圆桌。主人安排每位客人坐在(任意)一张圆桌边,但是每位客人希望自己左右边上分别有一些空座位,不然会觉得害羞。

注意,如果一个客人所在的圆桌只有他一个人,那么他左边的空座位数量就是他右边的空座位数量。

试问主人需要准备多少个座位,才能让每个客人舒适的坐下。

思路

若已知第 i i i 个人左边坐着第 p i p_i pi​ 个人,那么答案就是 ∑ i = 1 n max ⁡ { l i , r p i } \sum_{i=1}^{n}\max\{l_i,r_{p_i}\} ∑i=1n​max{li​,rpi​​} 。

不可能有两个人左边坐着同一个人,所以 p p p 互不相同。

我们可以考虑一个贪心:

  1. 从 l l l 和 r r r 数组中找到一个大的值 x x x,它一定会出现在求和中某次累加时(一定有 max ⁡ { l i , r p i } = x \max\{l_i,r_{p_i}\} = x max{li​,rpi​​}=x)。

  2. 如果 x x x 是从 l l l 中取到的,那么我们还需要从 r r r 中取一个作为它左边的人,显然取的这个越大越好,我们把这两个数删掉后继续 1. 找数。

  3. 如果 x x x 是从 r r r 中取到的, 那么我们还需要从 l l l 中取一个作为它右边的人,显然取的这个越大越好,我们把这两个数删掉后继续 1. 找数。

观察发现每次取的两个数就是两个数组排序后的 l i l_i li​ 和 r i ri ri。

考场上没过写了个模拟退火,最后发现答案值域为 1 0 13 10^{13} 1013 要开long long

代码
#includeusing namespace std;
#define int long long
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int a[101010];
int b[101010];
signed main(){cin>>n;
	f(i,1,n)cin>>a[i]>>b[i];
	sort(a+1,a+n+1);sort(b+1,b+n+1);
	f(i,1,n)m+=1+max(a[i],b[i]);
	cout<
建议

把 IDE 做好一点,代码自动补全和缩进及其反人类。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文题目:CSDN第11次竞赛题解-创新互联
标题链接:http://bjjierui.cn/article/ccpdsd.html