老洪的遍历
考场上直接spfa+拉斯维加斯剪枝拿到了 \(n \leq 1000\) 的65分
考虑将i到j的收益的式子展开：
\[\frac{B_iB_j}{2}*\frac{A_i-A_j}{A_i*A_j} \] \[\frac{B_iB_j}{2}*(\frac{1}{A_j}-\frac{1}{A_i}) \] \[\frac{1}{2}*(B_i*\frac{B_j}{A_j}-B_j*\frac{B_i}{A_i}) \]-
我们将第i个点放到坐标轴上，坐标 \((B_i,\frac{B_i}{A_i})\)，发现i到j的贡献就是叉积形式，又带个 \(\frac{1}{2}\)，所以就是点i，j和原点形成的有向三角形面积，且根据题目给出的限制，发现由i开始，回到i的最大收益是i所在的一个多边形的面积
-
然后因为起点任意，并且这个最大面积和起点并没有关系，我们只要找到这些点集的凸包，算它的面积就行了。
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define double long double
using namespace std;
const int maxn=1e5+10;
const double eps=1e-12;
int n,top;
struct Node{
double x,y;
Node operator - (const Node &B) const {return (Node){x-B.x,y-B.y};}
double operator ^ (const Node &B) const {return x*B.y-B.x*y;}
double Dis(const Node &B){return sqrt((x-B.x)*(x-B.x)+(y-B.y)*(y-B.y));}
}a[maxn],sta[maxn];
bool cmp(Node A,Node B){
double tmp=((A-a[1])^(B-a[1]));
return (fabs(tmp)>eps)?(tmp>eps):(A.Dis(a[1])<B.Dis(a[1]));
}
int main(){
freopen("visit.in","r",stdin);
freopen("visit.out","w",stdout);
scanf("%d",&n);
double sum=0;
for(int i=1;i<=n;++i){
double aa;scanf("%Lf",&aa);
sum+=aa;
a[i]=(Node){sum,sum/aa};
if(a[i].y<a[1].y || (a[i].y==a[1].y&&a[i].x<a[1].x)) swap(a[1],a[i]);
}
sort(a+2,a+1+n,cmp);
sta[++top]=a[1];
for(int i=2;i<=n;++i){
while(top>1&&((sta[top]-sta[top-1])^(a[i]-sta[top-1]))<=eps) --top;
sta[++top]=a[i];
}
sta[top+1]=a[1];
double ans=0;
for(int i=1;i<=top;++i) ans+=(sta[i]^sta[i+1]);
printf("%.5Lf\n",ans/2);
return 0;
}
老洪的神秘操作
-
将a[i]处理一下，在模7意义下取反（满足a[i]模7为0需要加的数），然后处理出a数组的差分数组c，这样我们对a数组区间减就只需要改c数组两个位置了，
-
显然我们要将c[1]~c[n]全变为0,有x个不为0，其实最劣可以操作x次达到目的，因为操作一次是一减一加，如果我们能同时抵消掉2个，结果会更优，
-
我们把差分数组中的负数+7变成正数，所以我们要把差分数组中的所有数按加和为7分组，每组操作次数为siz-1，我们要让这种组合出来的组数尽量多
-
我们先将贪心地将1和6，2和5,3和4两两配对，剩下的只有3种数，动态规划求出这些数能配出来的最大组数，f[i][j][k][w]表示数1用了i个，数2用了j个，数3用了k个，最后一组加和模7为w，前面配好的加和为7的最大组数，然后滚动数组优化掉x就好了
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ans,a[505],c[505],cnt[10],v[10];
int f[2][505][505][8];
int main(){
freopen("secret.in","r",stdin);
freopen("secret.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),a[i]=(7-a[i])%7;
for(int i=1;i<=n;++i) c[i]=a[i]-a[i-1],c[i]=(c[i]+7)%7;
for(int i=1;i<=n;++i) ++cnt[c[i]];
for(int i=1;i<=3;++i){
ans+=min(cnt[i],cnt[7-i]);
if(cnt[i]<cnt[7-i]) cnt[i]=cnt[7-i]-cnt[i],v[i]=7-i;
else cnt[i]-=cnt[7-i],v[i]=i;
}
for(int i=0;i<=cnt[1];++i){
int now=i&1;
memset(f[now],-0x3f,sizeof(f[now]));
if(!i) f[0][0][0][0]=0;
for(int j=0;j<=cnt[2];++j){
for(int k=0;k<=cnt[3];++k){
for(int w=0;w<7;++w){
if(i) f[now][j][k][w]=max(f[now][j][k][w],f[now^1][j][k][(w+7-v[1])%7]+(!w));
if(j) f[now][j][k][w]=max(f[now][j][k][w],f[now][j-1][k][(w+7-v[2])%7]+(!w));
if(k) f[now][j][k][w]=max(f[now][j][k][w],f[now][j][k-1][(w+7-v[3])%7]+(!w));
}
}
}
}
int tot=0;
for(int i=0;i<7;++i) tot=max(tot,f[cnt[1]&1][cnt[2]][cnt[3]][i]);
printf("%d\n",ans+cnt[1]+cnt[2]+cnt[3]-tot);
return 0;
}
老洪的数组
分块
将询问分块，固定kc次询问后重新处理出20×n的表，对于询问，首先设为表上的值，然后暴力枚举块内的改过的点，加上差值（变化量），假设m次操作中，修改和询问各占一半，那么块长 \(\sqrt{80*n}\) 最优，时间复杂度为 \(O(m\sqrt{20n})\)
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+30;
const int mod=1e9+7;
int n,m,kc,cnt;
int fac[maxn],fy[maxn],v[maxn],p[maxn],f[21][maxn];
bool vis[maxn];
int read(int x=0,bool f=0,char ch=getchar()){
for(;ch<'0' || ch>'9';ch=getchar()) f=ch=='-';
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
return f?-x:x;
}
int fp(int a,int x,int ans=1){
for(;x;x>>=1,a=(ll)a*a%mod)
if(x&1) ans=(ll)ans*a%mod;
return ans;
}
void Init(int n){
fac[0]=fy[0]=1;
for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%mod;
fy[n]=fp(fac[n],mod-2);
for(int i=n;i>1;--i) fy[i-1]=(ll)fy[i]*i%mod;
}
int C(int x,int y){
return (x<y || y<0)?0:(ll)fac[x]*fy[y]%mod*fy[x-y]%mod;
}
void rebuild(){
for(int i=1;i<=cnt;++i) f[0][p[i]]=v[p[i]],vis[p[i]]=0;
cnt=0;
for(int i=1;i<=20;++i) for(int j=1;j<=n;++j) f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
}
int main(){
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
n=read(),m=read(),kc=(int)sqrt(80*n);
for(int i=1;i<=n;++i) f[0][i]=read();
Init(n+20);
for(int i=1;i<=m;++i){
if(i%kc==1) rebuild();
int opt=read(),x=read(),y=read();
if(opt==1){
if(!vis[x]) vis[x]=1,p[++cnt]=x;
v[x]=y;
}
else{
if(!x){printf("%d\n",vis[y]?v[y]:f[0][y]);continue;}
ll ans=f[x][y];
for(int j=1;j<=cnt;++j) ans+=(ll)C(x-1+y-p[j],x-1)*(v[p[j]]-f[0][p[j]])%mod;
printf("%lld\n",(ans%mod+mod)%mod);
}
}
return 0;
}