30%：枚举每个骰子点数 O（6^（x+y））
60%：分别枚举两个骰子的点数，计算你的点数大于对手的方案数，除以总方案数
100%：设 f [ i ] [ j ]为第 i 个骰子扔出 j 的概率，f [ i ] [ j ] = sum{ f [ i -1 ] [ j - k ] / 6 } （1<=k<=6）；
然而我不想用概率dp，所以我设了 f [ i ] [ j ] 为到了第 i 个骰子总点数为 j 的方案数会爆long long 但是精度要求低，所以用double 存就水过了……
#include<bits/stdc++.h> using namespace std; #define int long long inline int read() { int x=0,f=1; char ch; for(ch=getchar();(ch<‘0‘||ch>‘9‘)&&ch!=‘-‘;ch=getchar()); if(ch==‘-‘) f=0,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f?x:-x; } long double f[2][6010];//f[i][j]统计玩家1第i次抛出后得分为j的方案数 long double g[2][6010];//……玩家2…… int x,y,t1,t2; long double sum1,sum2; signed main() { x=read(),y=read(); f[0][0]=g[0][0]=1*0.001; for(int i=1;i<=x;++i) { t1^=1; for(int k=0;k<=6*i;++k) f[t1][k]=0; for(int j=1;j<=6;++j) { for(int k=6*i;k>=j;--k) { f[t1][k]+=f[t1^1][k-j]; } } } for(int i=1;i<=y;++i) { t2^=1; for(int k=0;k<=6*i;++k) g[t2][k]=0; for(int j=1;j<=6;++j) { for(int k=6*i;k>=j;--k) { g[t2][k]+=g[t2^1][k-j]; } } } for(int i=1;i<=6*x;++i) { for(int j=1;j<=6*y;++j) { sum1+=f[t1][i]*g[t2][j]; if(i>j) sum2+=f[t1][i]*g[t2][j]; } } double sum=sum2/sum1*100.0; printf("%.2lf",sum); putchar(‘%‘); return 0; }
10%：输出0
40%：无脑 n^2
100%：无脑三分
至于为什么是单谷函数：假设一开始集合位置pos在1，sum1为pos左边人的权值，sum2为pos右边人的权值，每次pos向右边移动一个位置，ans+=（sum1-sum2）
然而sum1递增，sum2递减，所以函数是单谷的
但是你都推出这个来了为什么要三分？排完序扫一遍不完事了？
#include<bits/stdc++.h> using namespace std; #define int long long inline int read() { int x=0,f=1; char ch; for(ch=getchar();(ch<‘0‘||ch>‘9‘)&&ch!=‘-‘;ch=getchar()); if(ch==‘-‘) f=0,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f?x:-x; } int n,pos; struct node { int id,w; inline bool operator < (const node &t) const { return id<t.id; } }a[1000010]; int sum1,sum2,ret; signed main() { pos=n=read(); for(int i=1;i<=n;++i) a[i].id=read(); for(int i=1;i<=n;++i) a[i].w=read(); sort(a+1,a+n+1); for(int i=1;i<n;++i) sum1+=a[i].w; sum2=a[n].w; while(sum1>sum2&&pos>0)//扫一遍 { --pos; sum1-=a[pos].w; sum2+=a[pos].w; } for(int i=1;i<=n;++i) ret+=(a[i].w*abs(a[i].id-a[pos].id)); printf("%lld\n",ret); return 0; }
比较高级，看了题目还以为是个啥DP，听大佬在旁边yy平衡树加单调队列优化DP一阵%%%，然而正解是基础算法……
考虑把一段点分成一组，其中最大纵坐标为maxy，最小为miny，那么线段取在（maxy+miny）/ 2 处代价最小；
所以可以二分一个代价，从前向后扫点，每次扫到一个点，看看加入这个点会不会令代价超过mid，不超过就加入上一个集合，超过就新开一个集合，可以拿到80pts
继续优化：每次都要为区间找一个右端点，这个右端点的取值和max和min有关，那么可以用st表预处理出区间最大/最小值，每次确定了左端点后二分区间长度，康康最大值和最小值是否满足要求；
#include<bits/stdc++.h> using namespace std;//开long long 见祖宗 inline int read() { int x=0,f=1; char ch; for(ch=getchar();(ch<‘0‘||ch>‘9‘)&&ch!=‘-‘;ch=getchar()); if(ch==‘-‘) f=0,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f?x:-x; } int n,m,tyx,tot,maxn,minn=1e9+7; struct node { int x,y; inline bool operator < (const node &t) const { return x<t.x; } }a[1000010]; int g[1000010][21][2]; inline bool check(int d) { int sum=0,now=1; while(now<=n) { int r=now,maxn=0,minn=1e9+7; for(int i=20;i>=0;--i) { if(r+(1<<i)-1>n) continue; int tmin=g[r][i][0],tmax=g[r][i][1]; if(max(tmax,maxn)-min(tmin,minn)<=d) { maxn=max(maxn,tmax); minn=min(minn,tmin); r+=(1<<i); } } now=r; if(++sum>m) return 0; } return 1; } signed main() { n=read(); for(int i=1;i<=n;++i) { a[i].x=read(),a[i].y=read(),maxn=max(a[i].y,maxn); } sort(a+1,a+n+1); for(int i=1;i<=n;++i) g[i][0][0]=g[i][0][1]=a[i].y; for(int i=1;i<=20;++i) { for(int j=1;j+(1<<i)-1<=n;++j) { g[j][i][0]=min(g[j+(1<<(i-1))][i-1][0],g[j][i-1][0]); g[j][i][1]=max(g[j+(1<<(i-1))][i-1][1],g[j][i-1][1]); } } tyx=read(); while(tyx--) { m=read(); int l=1,r=maxn,ret=0; while(l<=r) { double mid=(l+r)>>1; if(check(mid)) ret=mid,r=mid-1; else l=mid+1; } if(ret&1) printf("%.1lf\n",((double)(ret>>1)+0.5)); else printf("%d\n",ret>>1); } return 0; }
原文：https://www.cnblogs.com/knife-rose/p/11747794.html
