[CLYZ2017]day18
子集
solution
60分
枚举中位数,枚举集合大小,贪心使平均值尽量大,取最大值.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 2005
using namespace std;
double a[N],ans,sum;
int n;
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf",&a[i]);
sort(a+1,a+1+n);
for(int i=2,k;ii;--j,--l){
sum+=a[j]+a[l];k+=2;
ans=max(ans,sum/k-a[i]);
}
}
for(int i=3,k;ii;--j,--l){
sum+=a[j]+a[l];k+=2;
ans=max(ans,sum/k-(a[i-1]+a[i])/2.0);
}
}
printf("%.5lf\n",ans);
}
int main(){
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
} 100分
\(yy\)一下发现中位数为一个数时值更大.
枚举中位数,可以发现这是一个关于集合大小的单峰函数,三分即可.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 200005
using namespace std;
int n,l,r,m1,m2;
double a[N],s[N],ans;
inline double f(int x,int i){
return (s[n]-s[n-x]+s[i]-s[i-x-1])/(x<<1|1)-a[i];
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;++i)
s[i]=s[i-1]+a[i];
for(int i=1;i<=n;++i){
l=1;r=min(n-i,i-1);
while(l+2 子串
100分
将字符串建成\(AC\)自动机,\(f[i]\)表示从节点\(i\)到结束的期望步数.
\(f[i]=1+\frac{1}{26}\sum_{j='a'}^{'z'}f[tr[i][j]]\).
如果\(i\)为结束节点,则\(f[i]=0\).
根据关系式高斯消元即可(分母移项即为整式方程).
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K 26
#define M 15
#define N 155
#define P 1000000007
using namespace std;
typedef long long ll;
int a[N][N],tr[N][K],nxt[N],f[N],n,t,cnt;
char c[M];
queue q;
inline void insert(){
int u=0,l=strlen(c+1);
for(int i=1;i<=l;++i){
c[i]-='a';
if(!tr[u][c[i]])
tr[u][c[i]]=++cnt;
u=tr[u][c[i]];
}
f[u]=1;
}
inline void bfs(int u){
for(int i=0;i>=1;
}
return ret;
}
inline int gauss(int n){
int tmp;
for(int i=0;i<=n;++i){
if(!a[i][i])
for(int j=i+1;j<=n;++j)
if(a[j][i]){
for(int k=i;k<=n+1;++k)
swap(a[i][k],a[j][k]);
break;
}
for(int j=0;j<=n;++j)
if(j!=i&&a[j][i]){
tmp=1ll*a[j][i]*rev(a[i][i])%P;
for(int k=i;k<=n+1;++k)
a[j][k]=(a[j][k]-1ll*tmp*a[i][k]%P)%P;
}
}
for(int i=0;i<=n;++i)
f[i]=1ll*a[i][n+1]*rev(a[i][i])%P;
if(f[0]<0) f[0]+=P;
return f[0];
}
inline void Aireen(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
cnt=0;
memset(f,0,sizeof(f));
memset(tr,0,sizeof(tr));
for(int i=1;i<=n;++i){
scanf("%s",c+1);insert();
}
bfs(0);
memset(a,0,sizeof(a));
for(int i=0;i<=cnt;++i)
if(f[i]){
a[i][i]=1;a[i][cnt+1]=0;
}
else{
a[i][i]=a[i][cnt+1]=26;
for(int j=0;j