40+0+30=70 rank10 这都前十……
T1，考试时就想斜率dp了，结果推出来的式子没法搞，又推了一些没用的性质，最后放弃了打了40分暴力。正解根号算法， 转移时包含的颜色最多有n√个，记录每个位置的上一个和下一个相同颜色的位置，转移时，pos[j]表示pos[j]+1~i中有不超过j种颜色，当i++时，要巧妙的转移(详见代码)，总复杂度O(nn√)#include#include #include #include #include #define N 40005using namespace std;int n,nn,m,c[N],nxt[N],pre[N],last[N],pos[N];int cnt[N];int f[N];int main(){ scanf("%d%d",&n,&m); nn=min((int)sqrt(n),m); for(int i=1;i<=n;i++){ scanf("%d",&c[i]); pre[i]=last[c[i]]; nxt[last[c[i]]]=i; last[c[i]]=i; } for(int i=1;i<=m;i++)nxt[last[i]]=n+1; for(int i=1;i<=n;i++){ f[i]=f[i-1]+1; for(int j=1;j<=nn;j++){ if(pre[i]<=pos[j]){ cnt[j]++; if(cnt[j]>j){ while(nxt[pos[j]+1]<=i)pos[j]++; pos[j]++;cnt[j]--; } } f[i]=min(f[i],f[pos[j]]+j*j); } } printf("%d\n",f[n]); return 0;}
T2，考试时大部分时间在搞这个题，结果爆零了，蜜汁flag(打的时间和分数成反比)，正解是搞一个覆盖所有的大矩形，肯定有某个小矩形是在它的某个角，暴力搜就行。。。
#include#include #include #include #include using namespace std;int n, maxx,maxy,minx,miny,ANS;struct data{ int x,y,vis;}d[20005];int vis[20005];bool flag;void dfs(int step,int l,int wh){ if(flag==1)return; if(step==4){ for(int i=1;i<=n;i++)if(!vis[i])return; flag=1;return ; } maxx=maxy=-1000000001; minx=miny=1000000001; for(int i=1;i<=n;i++){ if(!vis[i]||vis[i]>=step){ vis[i]=0; maxx=max(maxx,d[i].x);maxy=max(maxy,d[i].y); minx=min(minx,d[i].x);miny=min(miny,d[i].y); } } if(wh==1){ for(int i=1;i<=n;i++)if(!vis[i]) if(d[i].x-minx<=l&&maxy-d[i].y<=l)vis[i]=step; for(int i=1;i<=4;i++)dfs(step+1,l,i); } else if(wh==2){ for(int i=1;i<=n;i++)if(!vis[i]) if(maxx-d[i].x<=l&&maxy-d[i].y<=l)vis[i]=step; for(int i=1;i<=4;i++)dfs(step+1,l,i); } else if(wh==3){ for(int i=1;i<=n;i++)if(!vis[i]) if(d[i].x-minx<=l&&d[i].y-miny<=l)vis[i]=step; for(int i=1;i<=4;i++)dfs(step+1,l,i); } else if(wh==4){ for(int i=1;i<=n;i++)if(!vis[i]) if(maxx-d[i].x<=l&&d[i].y-miny<=l)vis[i]=step; for(int i=1;i<=4;i++)dfs(step+1,l,i); }}bool check(int x){ flag=0; for(int i=1;i<=4;i++){ dfs(1,x,i); if(flag)return 1; }return 0;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld%lld",&d[i].x,&d[i].y); maxx=max(maxx,d[i].x);maxy=max(maxy,d[i].y); minx=min(minx,d[i].x);miny=min(miny,d[i].y); } int l=1,r=max(maxx-minx,maxy-miny),mid; while(l<=r){ mid=(l+r)>>1; if(check(mid)){ANS=mid;r=mid-1;} else l=mid+1; } printf("%d\n",ANS); return 0;}
T3,线段树+推式子。
∑p[i]∗(i−l+1)∗(r−i+1)
=−∑i2∗p[i]+(l+r)∗∑i∗p[i]−(r+1)∗(l−1)∗∑p[i]
线段树维护 i2∗p[i],i∗p[i],p[i]的和即可 #include#include #include #include #include #define N 100005#define LL long long using namespace std;LL lazy[N<<3],sum1[N<<3],sum2[N<<3],sum3[N<<3];LL f[N],g[N];LL n,q;LL ans,mom,gg;#define int long long void pushdown(LL rt,LL l,LL r){ if(lazy[rt]){ lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; LL mid=(l+r)>>1; sum1[rt<<1]+=lazy[rt]*(mid-l+1); sum2[rt<<1]+=lazy[rt]*(f[mid]-f[l-1]); sum3[rt<<1]+=lazy[rt]*(g[mid]-g[l-1]); sum1[rt<<1|1]+=lazy[rt]*(r-mid); sum2[rt<<1|1]+=lazy[rt]*(f[r]-f[mid]); sum3[rt<<1|1]+=lazy[rt]*(g[r]-g[mid]); lazy[rt]=0; }}void pushup(LL rt,LL l,LL r){ if(l==r)return; sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1]+lazy[rt]*(r-l+1); sum2[rt]=sum2[rt<<1]+sum2[rt<<1|1]+lazy[rt]*(f[r]-f[l-1]); sum3[rt]=sum3[rt<<1]+sum3[rt<<1|1]+lazy[rt]*(g[r]-g[l-1]);}void update(LL rt,LL l,LL r,LL x,LL y,LL z){ if(x<=l&&r<=y){ lazy[rt]+=z; sum1[rt]+=z*(r-l+1); sum2[rt]+=z*(f[r]-f[l-1]); sum3[rt]+=z*(g[r]-g[l-1]); return ; } pushdown(rt,l,r); LL mid=(l+r)>>1; if(x<=mid) update(rt<<1,l,mid,x,y,z); if(y>mid) update(rt<<1|1,mid+1,r,x,y,z); pushup(rt,l,r);}void query(LL rt,LL l,LL r,LL x,LL y){ if(x<=l&&r<=y){ ans-=sum3[rt]; ans+=(x+y)*sum2[rt]; ans-=1ll*(y+1)*(x-1)*sum1[rt]; return ; } pushdown(rt,l,r); LL mid=(l+r)>>1; if(x<=mid) query(rt<<1,l,mid,x,y); if(y>mid) query(rt<<1|1,mid+1,r,x,y);}LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}signed main(){ scanf("%lld%lld",&n,&q); for(int i=1;i<=n;i++){ f[i]=f[i-1]+i; g[i]=g[i-1]+1ll*i*i; } char ch[3]; for(int i=1,l,r,d;i<=q;i++){ scanf("%s",ch); if(ch[0]=='C'){ scanf("%lld%lld%lld",&l,&r,&d); update(1,1,n-1,l,r-1,d); } else{ scanf("%lld%lld",&l,&r); ans=0; mom=(r-l+1)*(r-l)/2; query(1,1,n-1,l,r-1); gg=gcd(ans,mom); printf("%lld/%lld\n",ans/gg,mom/gg); } } return 0;}
define int long long ……233