( ext{C - Maximize GCD})
解法
乍一看很想二分,不过这不满足单调性。但是计算出序列的 (max) 为 (x),发现大于等于 (x) 的值是可以二分的。事实上这一部分也不需要二分,直接用表达式计算即可。
现在问题就是判断属于 ([1,x)) 的答案是否合法。我比较 ( m nt),想了个分块:对于小于 (sqrt n) 的数,(mathcal O(n)) 计算是否合法;反之,假设枚举的数为 (t),可以按照 (kt) 为界将数列分段,容易发现不超过 (frac{x}{t}) 段。
但是直接分段其实就可以了,因为 (sum_{t=1}^x frac{x}{t}) 就是 (xlog x) 级别啊。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-');
write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e5+5,B=700;
int n,a[maxn],mx;
ll k,pre[maxn];
signed main() {
n=read(9),k=read(9ll); ll s=0;
for(int i=1;i<=n;++i)
a[i]=read(9),mx=max(mx,a[i]),s+=a[i];
if(s+k>=1ll*mx*n) {
printf("%lld
",(s+k)/n);
return 0;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
pre[i]=pre[i-1]+a[i];
ll ans=1;
for(int i=mx;i>=1;--i) {
ll ret=0;
for(int j=1;(j-1)*i<mx;++j) {
int l=upper_bound(a+1,a+n+1,(j-1)*i)-a;
int r=upper_bound(a+1,a+n+1,j*i)-a-1;
if(j*i>mx) r=n;
if(l>r or a[l]>j*i)
continue;
ret+=1ll*j*i*(r-l+1)-(pre[r]-pre[l-1]);
}
if(ret<=k) {
ans=i;
break;
}
}
print(ans,'
');
return 0;
}
( ext{D - Pure Straight})
解法
首先令 (m=lceil k/2 ceil),初始下标集合 (I=(i_1,i_2,...i_k))(升序),最终下标集合 (J=(j_1,j_2,...j_k))(这是连续的)。
假如 (I,J) 已经选定,设 (d(p)=|i_p-j_p|),(dis(I,J)=sum_{p=1}^k d(p)),( m inv) 是 (I) 对应序列的逆序对数。那么最小步数就是 (dis(I,J)+ m inv)。证明就是先花费 (dis(I,J)) 将 (I) 挪到 (J) 肯定是最优的,这个证明比较经典,就不再赘述。接下来需要在 (I) 内部进行交换,使得 (A_{I_1},A_{I_2},...A_{I_k}) 变成升序,由于此时 (I_i,I_{i+1}) 都只差 (1),实际上就是逆序对数。
有这样的结论:对于 给定 的 (I),最终最优的 (J) 一定有 (i_m=j_m)。具体可以这样证明:
- 如果 (i_m<j_m),将 (J) 集合整体向左移。对于 (pin[1,m]) 都有 (d(p):=d(p)-1)。这是由于 (j_1) 到 (j_m) 的空隙是最小的情况,故对于 (pin[1,m]) 在移动前都有 (i_p<j_p)。对于 (pin (m,k]) 则有 (d(p)) 至多增加 (1)。
- 如果 (i_m>j_m),将 (J) 集合整体向右移。证明方法类似。
由于每次保证 (d(p)) 减一的区间都大于或等于 (d(p)) 至多增加 (1) 的区间,所以可以证明将 (j_m) 往靠近 (i_m) 移动,结果会变得更优。
证明了这些结论,终于可以开始愉快地写代码啦!笑死,根本写不来。
首先可以明确只需要选定合适的 (I) 即可,因为此时 (J) 是固定的。先假设 (dp_S) 为选数的权值集合为 (S) 的最小步数,(cnt(S)) 是 (S) 中 (1) 的个数。如果我们从 (1) 到 (n) 加入数字,就可以惊喜地发现,当 (cnt(S)=m) 时,此时新加入的数的下标即为 (i_m)!真的好特喵妙啊!
(mathtt{dp}) 的一个瓶颈就在于 (d(p)) 很不好计算,既然我们知道了 (i_m),是否能将 (d(p)) 拆一下,将一些值拖到 (i_m) 时再计算呢?
- 当 (pin[1,m)),(d(p)=j_p-i_p=(j_m+p-m)-i_p)。
- 当 (pin(m,k]),(d(p)=i_p-j_p=i_p-(j_m+p-m))。
其中 (p,m,i_p) 都可以即时计算。对于 (j_m),当 (k) 为奇数时其实就抵消了;为偶数时 (i_{m+1}) 没被抵消,所以在计算到 (i_m) 时需要减去 (i_m)。
总复杂度 (mathcal O(n2^k))。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-');
write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <cstring>
#include <iostream>
using namespace std;
int n,k,a[205],dp[1<<16];
int main() {
n=read(9),k=read(9);
for(int i=1;i<=n;++i)
a[i]=read(9);
int m=k+1>>1;
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int i=1;i<=n;++i)
for(int j=(1<<k)-1;j>=0;--j) {
if(!((j>>a[i]-1)&1))
continue;
int cnt=__builtin_popcount(j),fr=j^(1<<a[i]-1);
int add=__builtin_popcount(j>>a[i]);
if(cnt<m)
dp[j]=min(dp[j],dp[fr]+add-i+cnt-m);
else if(cnt>m)
dp[j]=min(dp[j],dp[fr]+add+i-cnt+m);
else
dp[j]=min(dp[j],dp[fr]+add+((k&1)?0:-1)*i);
}
print(dp[(1<<k)-1],'
');
return 0;
}
( ext{E - Infinite Operations})
解法
令 (F(A)=sum_{i<j}|A_i-A_j|),我们可以证明 (lim_{n ightarrow infty}f(n)=F(A)/2)。
首先证明 (lim_{n ightarrow infty}f(n)le F(A)/2)。可以分类讨论:
- 如果对 权值 相邻的 (A_i,A_j) 进行操作,得到了 (x) 分。(F(A)) 减少 (2x)。
- 如果对 权值 不相邻的 (A_i,A_j) 进行操作,得到了 (x) 分。(F(A)) 至少减少 (2x),因为对于 (A_i,A_j) 权值中间的数 (x),由于 (A_i,A_j) 行走的距离相等,当 (A_i,A_j) 都没有触及 (x) 时,(x) 与 (A_i,A_j) 的距离是减小的;触及 (x) 之后,距离就不变了。所以整体是减小的。
证明了答案的上界后,我们只需要证明总有一种方案可以达到 (F(A)/2)。因为每次用权值相邻的 (A_i,A_j) 操作对 (A_i,A_j) 对其它数的距离没有影响,所以直接对这两个数操作就行了啊。
代码
代码太丑了,就不挂了。