The Morning Star
统计 $ x,y,x-y,x+y $
开 $ long long $
Ntarsis'Set
考场降智
删除数实质是降低排名.
显然答案有单调性,直接二分答案.每次减小排名.判断是否合法.
Code
#include<cstdio>
#define int long long
using namespace std;
const int N=2e5+5;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,k;
int a[N];
int check(int x){
int i=n,K=k;
while(K--){
while(a[i]>x)
i--;
x-=i;
}
return x>0;
}
void work(){
n=read(),k=read();
for(int i=1;i<=n;i++)
a[i]=read();
if(a[1]!=1){
printf("1\n");
return ;
}
int l=1,r=n*k+n;
int ans=r;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
printf("%lld\n",ans);
}
signed main(){
// freopen("set_.in","r",stdin);
int T=read();
while(T--){
work();
}
return 0;
}
删除不好实现,但我们知道答案之后位置为1.我们可以从最后状态往回加.每次操作查看有多少个 $ a_i-i<ans $
Team Work
感谢打表log的式子.
打表式的证明
\[设 f(n,k) 为 最后答案 \]\[f(n,k) = \sum _{i=1}^{n} C_{n}^{i} i^k \]\[f(n,k) = n \sum _{i=1}^{n} C_{n-1}^{i-1} i^{k-1} \]\[C_{n}^{i} = ( C_{n-1}^{i}+ C_{n-1}^{i-1} ) \]\[f(n,k) = n \sum _{i-1}^{n} C_{n}^{i} i^{k-1} - C_{n-1}^{i} i^{k-1} =n*(f(n,k)-f(n-1,k)) \]\[f(n,0) = 2^{n}-1 \]还有斯特林数做法.
Make Equal
恶心的DP.
令最大值加上\(x\),$ 答案是 \sum _{i=1}^{n} popcount(x+max-a_i) 的最小值 $
我们令 $ a_i=max-a_i $, 我们直接决策 x 就好 . 按为考虑DP , 发现其会被进位影响,但我们不能保存所有进位情况.我们可以发现越大越容易进位,所以我们按第j从大到小排序就好,然后只要记录上一位进位情况.
$ 设 dp[i][j] 是前i为有j个进位的最优解,有四种情况. $
设 \(cnt\)是这一位为1的个数,tot是前\(j\)为1的个数.
1.上一次进位,这一位为 1 个数是 \(tot\)
2.上一次进位,这一次为 0 的个数 \(j-tot\)
3.上一次不进位,这一位为 1 个数是 \(cnt-tot\)
4.上一次不进位,这一次为 0 的个数 \((n-j)-(cnt-tot)\)
考虑转移
1.\(x\) 这一位为1。1,2,3进位,1,4为1.
\(dp[i+1][tot+(j-tot)+(cnt-tot)]=min(dp[i+1][tot+(j-tot)+(cnt-tot)],dp[i][j]+tot+(n-j)-(cnt-tot))\)
2.\(x\) 这一位为0。1进位,2,3为1.
\(dp[i+1][tot]=min(dp[i+1][tot],dp[i][j]+(j-tot)+(cnt-tot))\)
Code
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n;
int a[N],mx;
int dp[65][N];
int nowk;
bool cmp(int x,int y){
return (x&((1ll<<nowk)-1))>(y&((1ll<<nowk)-1));
}
bool cmp1(int x,int y){
return x>y;
}
signed main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+1+n,cmp1);
for(int i=n;i>=1;i--)
a[i]=a[1]-a[i];
for(int i=0;i<=62;i++){
for(int j=0;j<=n;j++){
dp[i][j]=1e15;
}
}
dp[0][0]=0;
for(int i=0;i<=61;i++){
nowk=i;
if(i)
sort(a+1,a+1+n,cmp);
// for(int j=1;j<=n;j++)
// printf("%lld ",a[i]);
// printf("\n");
int cnt=0,tot=0;
int k=(1ll<<i);
for(int j=1;j<=n;j++)
cnt+=(a[j]&k)?1:0;
for(int j=0;j<=n;j++){
tot+=(a[j]&k)?1:0;
// printf("%lld \n",tot);
dp[i+1][j+cnt-tot]=min(dp[i+1][j+cnt-tot],dp[i][j]+tot+(n-j)-(cnt-tot));
dp[i+1][tot]=min(dp[i+1][tot],dp[i][j]+(j-tot)+(cnt-tot));
}
}
printf("%lld ",dp[62][0]);
return 0;
}