ABC373 E/F

ABC373 E/F

E - How to Win the Election

二分答案比较好想，可是细节有点多，复杂度 $ O(n\log^2 n) $ 。一开始忘了一个特判，狂WA不止，然后调完再交，直接破防，WA一个点。接着尝试去卡，不知道怎么想的，粘错代码了。还剩半个小时，非常忙碌地调代码，但是不知道在忙什么。

赛后找到正确代码，调过hack（ $ N = M $ 的情况 ）。

代码不贴了，太丑。

F - Knapsack with Diminishing Values

正解做法

按照 $ w_i $ 分组，计算对于每个 $ w_i $ ，选择 $ j $ 个物品能达到的最大价值。具体来说，就是用堆维护该物品选择第 $ k $ 个产生的价值，贪心策略显然正确。然后就是普通的背包，复杂度最劣是一个调和级数， $ O(NW\log W) $ 。

暴力

#include<bits/stdc++.h>
const int N=1e5;
int w[N],v[N];
long long f[N];
int main(){int n,c;scanf("%d%d",&n,&c);for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);}for(int i=1;i<=n;i++){bool con=1;for(int k=1;con;k++){con=0;for(int j=c-w[i];j>=0;j--){if(f[j]+v[i]-2*k+1>f[j+w[i]])con=1,f[j+w[i]]=f[j]+v[i]-2*k+1;}}}printf("%lld",f[c]);
}

xrlong 翻最短解的时候找的这个，逆天暴力哥，而且跑飞快，可以被hack。

优化

发现hack暴力的方法不难想，只要然他前面的决策不够优秀，后面就会跑很多次。而我们伟大的 wang54321 发明了两种优化。

第一，随机化，复杂度不知道是什么，不考虑。

第二，排序，按照 $ v_i $ 降序排列，也不知道什么复杂度，但是跑得很快。(欢迎hack)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int w[N],v[N];
long long f[N];
struct node{int x,y;
}e[N];
bool cmp(node a,node b){return a.y>b.y;
}
long long cnt;
int main(){int n,c;scanf("%d%d",&n,&c);for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);e[i].x=w[i];e[i].y=v[i];}sort(e+1,e+n+1,cmp);for(int i=1;i<=n;i++){bool con=1;for(int k=1;con;k++){con=0;for(int j=c-e[i].x;j>=0;j--){if(f[j]+e[i].y-2*k+1>f[j+e[i].x])con=1,f[j+e[i].x]=f[j]+e[i].y-2*k+1;cnt++;}}}cerr<<cnt<<endl;printf("%lld",f[c]);
}