枚举/DP+排列组合
缩进优化
QAQ我当时一直在想：$min\{ \sum_{i=1}^n (\lfloor\frac{a[i]}{x}\rfloor + a[i] \ mod\ x) \}$
然而并不会做啊……一点思路也没有……主要是后面那个取模非常难受……
其实正解有点逆向思维的感觉：$ans=\sum_{i=1}^n a[i] - max\{ \sum_{i=1}^n \lfloor \frac{a[i]}{x}\rfloor *(x-1) \} $
也就是先将a[i]全部加起来，然后再使得被缩掉的部分最大。
然后……枚举x，枚举x的倍数，数一下除以x为 i 的有多少个就可以了……$O(nlogn)$
//UOJ Round #1 A
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e6+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/ int a[N],c[N],n;
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
n=getint();
LL sum=,ans=;
int mx=;
F(i,,n) a[i]=getint(),c[a[i]]++,sum+=a[i],mx=max(mx,a[i]);
D(i,mx,) c[i]+=c[i+]; F(x,,mx){
LL tmp=; int i;
for(i=;(i+)*x<=mx;i++)
tmp+=(c[i*x]-c[(i+)*x])*i;
tmp+=c[i*x]*i;
ans=max(ans,tmp*(x-));
}
printf("%lld\n",sum-ans);
return ;
}
外星人
Orz 题解
我只想到如果 x<a[i] ，那么a[i]之后放到哪里都不会有影响了……
对，我们只需要$f[i]$作为状态就够了。用$f[i]$表示$x=i$且只考虑手指数小于等于$i$的外星人的情况下的最优解与方案数。
怎么转移呢？我们在手指数小于等于$i$的外星人中选一个$a_k$作为下一个发送信息的外星人，显然这个外星人一定是有效外星人。那么考虑手指数介于$(i\ mod\ a_k , i]$的外星人，我们发现只要把他们随便插入到$f[i \ mod\ a_k]$的最优解排列中去就可以了。这个显然可以用最简单的组合数学解决。方案数即$\frac{(N_i -1)!}{N_{i\ mod\ a_k}!}$。其中$N_c$表示手指数不超过$c$的外星人个数。
//UOJ Round #1 B
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>,P=;
typedef long long LL;
/******************tamplate*********************/ int n,m,a[N],c[N],f[N][],fac[N],inv[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
n=getint(); m=getint();
int mx=m;
F(i,,n) a[i]=getint(),c[a[i]]++,mx=max(mx,a[i]);
sort(a+,a+n+);
F(i,,mx) c[i]+=c[i-]; fac[]=;
F(i,,mx) fac[i]=(LL)fac[i-]*i%P;
inv[]=inv[]=;
F(i,,mx) inv[i]=P-(LL)(P/i)*inv[P%i]%P;
F(i,,mx) inv[i]=(LL)inv[i]*inv[i-]%P; F(i,,m){
if (c[i]==) {f[i][]=i,f[i][]=;continue;}
for(int j=;a[j]<=i && j<=n;j++)
if (f[i%a[j]][]>f[i][]){
f[i][]=f[i%a[j]][];
f[i][]=(LL)fac[c[i]-]*inv[c[i%a[j]]]%P*f[i%a[j]][]%P;
}else if (f[i%a[j]][]==f[i][]){
f[i][]=(f[i][]+(LL)fac[c[i]-]*inv[c[i%a[j]]]%P*f[i%a[j]][]%P)%P;
}
}
f[m][]=(LL)f[m][]*fac[c[mx]]%P*inv[c[m]]%P;
printf("%d\n%d\n",f[m][],f[m][]);
return ;
}