本应$280$的，结果打表太大，拒绝评测，只有$180$。
Problem A 旅行
题面
现在有一段不平整的路，第$i$段的高度为$a_i$。你可以花费$|a_i-k|$，使第$i$段的高度变为$k$，使$\sum_{i=1}^{n-1}|a_i-a_{i+1}|$最小。
题解
贪心地从左到右扫一遍，枚举第$i$段路。如果要使得从$i-1$到$i+1$的体力消耗最小，那么就要两端距离间的差距最小。
- 如果$a_{i-1}$和$a_{i+1}$都小于$a_i$，那么就将$a_i$改变为$max(a_{i-1},a_{i+1})$。
- 如果$a_{i-1}$和$a_{i+1}$都大于$a_i$，那么就将$a_i$改变为$min(a_{i-1},a_{i+1})$。
代码
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN=100005;
int main(){
#ifndef FILE_IN
freopen("travel.in","r",stdin);
#endif
#ifndef FILE_OUT
freopen("travel.out","w",stdout);
#endif
ios::sync_with_stdio(false);
int n;
int a[MAXN]={0};
long long ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<n;i++){
if((a[i-1]>a[i]&&a[i]<a[i+1])){
if(a[i-1]>a[i+1]){
ans+=a[i+1]-a[i];
a[i]=a[i+1];
}
else{
ans+=a[i-1]-a[i];
a[i]=a[i-1];
}
}
else if(a[i-1]<a[i]&&a[i]>a[i+1]){
if(a[i-1]>a[i+1]){
ans+=a[i]-a[i-1];
a[i]=a[i-1];
}
else{
ans+=a[i]-a[i+1];
a[i]=a[i+1];
}
}
}
for(int i=1;i<n;i++){
ans+=abs(a[i]-a[i+1]);
}
cout<<ans<<endl;
return 0;
}Problem B 石头剪刀布
题面
小菜给出一个自然数$n$，小明和小头轮流操作，每次操作可以把$n$减去$n$所拥有的数字中的最大值或者最小值（不包括0），不能操作者输（即$n=0$ 时）。
试求双方最优策略时的胜负情况。（小明先手）
题解
递推。$$fuck_x=(!fuck_{x-findmax(x)})||(!fuck_{x-findmin(x)})$$
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=1000005;
bool fuck[MAXN]={0,1,1,1,1,1,1,1,1,1};
short findmin(int x){
short ans;
do{
ans=x%10;
x/=10;
}
while(x!=0&&ans==0);
while(x){
if(x%10<ans&&x%10>0){
ans=x%10;
}
x/=10;
}
return ans;
}
short findmax(int x){
short ans;
do{
ans=x%10;
x/=10;
}
while(x!=0&&ans==0);
while(x){
if(x%10>ans&&(x%10)){
ans=x%10;
}
x/=10;
}
return ans;
}
void dfs(int x){
fuck[x]=(!fuck[x-findmax(x)])||(!fuck[x-findmin(x)]);
}
int main(){
ios::sync_with_stdio(false);
for(int i=10;i<MAXN;i++){
dfs(i);
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
int q;
cin>>q;
if(fuck[q]){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
return 0;
}Problem C 环中环
题面
$n$个整数围成一个环，选出其中的若干数，使得选中的数所组成的环中，两个相邻数的差的绝对值不等于$1$。在满足这个前提下，问最多能取多少个数。
题解
动态规划。设$f_i$表示以$i$为终点时最多能取多少个数。$$f_i=f_j+1(abs( a_i-a_j) \neq 1)$$
由于题目要求是环形，因此可以将原数列复制一份接在后面，处理完后答案除以$2$即可。
我们发现$(abs( a_ i-a_ j ) \neq 1)$的数最多只有两个，所以我们只要记录$3$个不同的$a_i$所对应的最大的$3$个$f$的值，直接转移即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, a[200001], f[200001], tr[5000000], zl;
void find( int z, int x, int y, int l, int r ) {
if ( ( x == l ) && ( y == r ) )
zl = max( zl, tr[z] );
else {
int mid = ( x + y ) / 2;
if ( r <= mid )
find( z * 2, x, mid, l, r );
else {
if ( l > mid )
find( z * 2 + 1, mid + 1, y, l, r );
else {
find( z * 2, x, mid, l, mid );
find( z * 2 + 1, mid + 1, y, mid + 1, r );
}
}
}
}
int findx( int x, int y ) {
zl = 0;
if ( x >= 0 && y >= 0 )
find( 1, 0, 1100000, x, y );
else
return ( 0 );
return ( zl );
}
void change( int z, int x, int y, int l ) {
if ( x == y )
tr[z] = zl;
else {
int mid = ( x + y ) / 2;
if ( l <= mid )
change( z * 2, x, mid, l );
else
change( z * 2 + 1, mid + 1, y, l );
tr[z] = max( tr[z * 2], tr[z * 2 + 1] );
}
}
int main() {
ios::sync_with_stdio( false );
cin >> n;
int i, j, k;
for ( int i = 1; i <= n; i++ ) {
cin >> a[i];
a[i + n] = a[i];
}
memset( tr, 0, sizeof( tr ) );
for ( int i = 1; i <= 2 * n; i++ ) {
f[i] = max( findx( a[i] + 2, 1100000 ), max( findx( 0, a[i] - 2 ), findx( a[i], a[i] ) ) );
zl = f[i] + 1;
f[i] += 1;
change( 1, 0, 1100000, a[i] );
}
cout << ( tr[1] >> 1 ) << endl;
return 0;
}Problem D 寻找神格
题面
维护一个序列，使之支持下列操作：
- 一个区间增加一个定值。
- 求指定区间方差。
- 求指定区间和。
题解
分块。
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=100010;
const int M=350;
int n,Q,T,L[M],R[M],pos[N];
ll ans[M],add[M],sum[M],a[N],Read,f,x,y,z;
char ch;
ll read(){
Read=0;f=1;ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9')Read=(Read<<3)+(Read<<1)+ch-48,ch=getchar();
return Read*f;
}
void change(int l,int r,ll z) //修改
{
int q=pos[l],p=pos[r];
if (q==p) //一个块暴力修改
{
for (register int i=l;i<=r;i++)
ans[q]+=2*(a[i]+add[q])*z+z*z,a[i]+=z,sum[q]+=z;
return;
}
for (register int i=l;i<=R[q];i++)
ans[q]+=2*(a[i]+add[q])*z+z*z,a[i]+=z,sum[q]+=z;
for (register int i=L[p];i<=r;i++) //分开
ans[p]+=2*(a[i]+add[p])*z+z*z,a[i]+=z,sum[p]+=z;
for (register int i=q+1;i<p;i++) //lazy修改
add[i]+=z,ans[i]+=2*sum[i]*z+z*z*(R[i]-L[i]+1),sum[i]+=z*(R[i]-L[i]+1);
}
ll ask1(int l,int r) //询问和
{
int q=pos[l],p=pos[r];
ll s=0;
if (q==p){
for (register int i=l;i<=r;i++) s+=(ll)(a[i]+add[q]); //暴力求和
return s;
}
for (register int i=l;i<=R[q];i++) s+=(ll)(a[i]+add[q]);
for (register int i=L[p];i<=r;i++) s+=(ll)(a[i]+add[p]);
for (register int i=q+1;i<p;i++) s+=sum[i];
return s;
}
ld ask2(int l,int r) //询问方差
{
int q=pos[l],p=pos[r];
ll Ans=0,Sum=0;
if (q==p){
for (register int i=l;i<=r;i++) //暴力
Sum+=a[i]+add[q];
ld Ave=(ld)Sum/(ld)(r-l+1),s=0.0;
for (register int i=l;i<=r;i++)
s+=((ld)a[i]+(ld)add[q]-Ave)*((ld)a[i]+(ld)add[q]-Ave);
return (ld)s/(ld)(r-l+1);
}
for (register int i=l;i<=R[q];i++) //左边
{
Ans+=(a[i]+add[q])*(a[i]+add[q]);
Sum+=a[i]+add[q];
}
for (register int i=L[p];i<=r;i++) //右边
{
Ans+=(a[i]+add[p])*(a[i]+add[p]);
Sum+=a[i]+add[p];
}
for (register int i=q+1;i<p;i++) //中间直接利用lazy
{
Ans+=ans[i];
Sum+=sum[i];
}
ld Ave=(ld)Sum/(ld)(r-l+1);
return ((ld)Ans-2.0*(ld)Sum*Ave+(ld)(r-l+1)*Ave*Ave)/(ld)(r-l+1);
//完全平方公式输出
}
int main()
{
freopen("find.in","r",stdin);
freopen("find.out","w",stdout);
n=read(),Q=read();
for (register int i=1;i<=n;i++)
a[i]=read();
T=sqrt(n);
if (T*T<n) T++;
for (register int i=1;i<=T;i++){
L[i]=R[i-1]+1;
R[i]=min(i*T,n);
for (register int j=L[i];j<=R[i];j++){
pos[j]=i;
ans[i]+=a[j]*a[j];
sum[i]+=a[j];
}
}
while (Q--){
x=read();
if (x==0){
x=read(),y=read();
change(x,x,y);
}
else if (x==1){
x=read(),y=read(),z=read();
change(x,y,z);
}
else if (x==2){
x=read(),y=read();
printf("%lld\n",ask1(x,y));
}
else if (x==3){
x=read(),y=read();
printf("%0.3Lf\n",ask2(x,y));
}
}
return 0;
}版权声明：本文是原创文章，版权归 星雾月雨 所有。
本文链接：https://www.ariels.xyz/archives/459.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。
