CSDN第11次竞赛题解-创新互联
最近小艺酱渐渐变成了一个圆滑的形状 - 球!! 小艺酱开始变得喜欢上球!小艺酱得到 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=1nmax{li,rpi} 。
不可能有两个人左边坐着同一个人,所以 p p p 互不相同。
我们可以考虑一个贪心:
从 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)。
如果 x x x 是从 l l l 中取到的,那么我们还需要从 r r r 中取一个作为它左边的人,显然取的这个越大越好,我们把这两个数删掉后继续 1. 找数。
如果 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://scyanting.com/article/ccpdsd.html