重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
CSDN第11次竞赛题解-创新互联
题解
T1
题面
分享题目：CSDN第11次竞赛题解-创新互联
网页地址：http://cqcxhl.com/article/ccpdsd.html
最近小艺酱渐渐变成了一个圆滑的形状 - 球！！ 小艺酱开始变得喜欢上球！小艺酱得到 n n n 个同心圆。
小艺酱对着
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;
} 存在 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< 已知存在
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 有 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://cqcxhl.com/article/ccpdsd.html