题目大意
给出一个数列ai,每次可以选择一个区间[l,r]进行全体+1或全体-1,需要满足区间长度len=r-l+1为奇质数p,且操作过程中ai非负
求最少操作次数使得最终ai不减
n<=2e3,1<=ai<=1e5,Σn<=2e4
题解
ai不减显然要差分,设差分得到b[i],使得最终b[i]>=0
发现原操作等于选择一个奇质数p,对b[i]+x,b[i+p]-x
注意p是奇质数一开始没有注意,所以i和i+p奇偶性不同,每次选择一对来对bi,bi+p操作
发现
code
ozy写的
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2005;
const int inf=1e9+7;
int n;
int a[N],b[N];
struct qq{int x,y,z,last;}e[N*N*2];
int num,last[N];
int st,ed;
void init (int x,int y,int z)
{
if (z==0) return ;
// printf("%d %d %d\n",x,y,z);
num++;
e[num].x=x;e[num].y=y;e[num].z=z;
e[num].last=last[x];
last[x]=num;
swap(x,y);z=0;
num++;
e[num].x=x;e[num].y=y;e[num].z=z;
e[num].last=last[x];
last[x]=num;
}
int h[N];
bool Bt ()
{
memset(h,-1,sizeof(h));h[st]=1;
queue<int> q;
q.push(st);
while (!q.empty())
{
int x=q.front();q.pop();
for (int u=last[x];u!=-1;u=e[u].last)
{
int y=e[u].y;
if (e[u].z>0&&h[y]==-1)
{
h[y]=h[x]+1;
q.push(y);
}
}
}
return h[ed]!=-1;
}
int dfs (int x,int f)
{
if (x==ed) return f;
int s1=0;
for (int u=last[x];u!=-1;u=e[u].last)
{
int y=e[u].y;
if (e[u].z>0&&h[y]==h[x]+1&&s1<f)
{
int lalal=dfs(y,min(e[u].z,f-s1));
s1+=lalal;
e[u].z-=lalal;
e[u^1].z+=lalal;
}
}
if (s1==0) h[x]=-1;
return s1;
}
vector<int> pri;
bool check (int x)
{
for (int u=2;u*u<=x;u++)
if (x%u==0)
return false;
return true;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
num=1;memset(last,-1,sizeof(last));
scanf("%d",&n);
pri.clear();
for (int u=3;u<=n;u++)
if (check(u))
pri.push_back(u);
for (int u=1;u<=n;u++) scanf("%d",&b[u]);
a[1]=b[1];
for (int u=2;u<=n;u++) a[u]=b[u]-b[u-1];
a[n+1]=inf;n++;
// for (int u=1;u<=n;u++) printf("%d ",a[u]);
// printf("\n");
st=n+1;ed=st+1;
for (int u=1;u<=n;u++)
{
int tmp=a[u];
if (tmp<0) tmp=-tmp;
if (u&1) init(st,u,tmp);
else init(u,ed,tmp);
for (auto xx:pri)
{
if (u+xx<=n&&(LL)a[u]*a[u+xx]<0)
{
if (u&1) init(u,u+xx,inf);
else init(u+xx,u,inf);
}
}
}
int ans=0;
while (Bt()) ans=ans+dfs(st,inf);
int pos1=0,neg1=0;
for (int u=last[st];u!=-1;u=e[u].last)
{
int y=e[u].y;
// printf("%d %d\n",y,a[y]);
if (a[y]>=0) pos1=pos1+e[u].z;
else neg1=neg1+e[u].z;
}
int pos2=0,neg2=0;
for (int u=last[ed];u!=-1;u=e[u].last)
{
int y=e[u].y;
if (a[y]>=0) pos2=pos2+a[y]-e[u].z;
else neg2=neg2+(-a[y])-e[u].z;
}
//printf("%d %d %d %d %d\n",ans,neg1,pos1,neg2,pos2);
if (pos1>=neg1) ans=ans+2*neg1;
else ans=ans+2*pos1+3*(neg1-pos1);
if (pos2>=neg2) ans=ans+2*neg2;
else ans=ans+2*pos2+3*(neg2-pos2);
printf("%d\n",ans);
}
return 0;
}
- Programming Collegiate Provincial Contest 104337programming collegiate provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming collegiate provincial counting programming provincial collegiate sponsored 2023 programming collegiate provincial 题解programming collegiate provincial heilongjiang programming collegiate provincial