G. 背包
我们要是选一个集合出来 并且免除k个宝石的话
我们一定是选最贵的k个宝石免费
这样我们的做法就是对wi排序
然后前面的做背包 后面直接贪心选vi最大的k个 这样是一定包含了最优解的
当然你可以用二分bit 也可以直接维护另一个dp
int n,tr1[200010],tr2[200010],idx;
map<int,int>mp;
int lowbit(int x){
return x&-x;
}
void add(int x,int c,int tr[]){
for(int i=x;i<=idx;i+=lowbit(i))tr[i]+=c;
}
int query(int x,int tr[]){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
void solve(){
int w,k;cin>>n>>w>>k;
vector<PII>a(n);
for(int i=0;i<n;i++){
cin>>a[i].first>>a[i].second;
mp[a[i].second]++;
}
vector<int>mpp(n+1);
for(auto [pos,w]:mp){
mp[pos]=++idx;
mpp[idx]=pos;
}
sort(all(a));
int dp[n+1][w+1];
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
auto [wi,vi]=a[i-1];
for(int j=1;j<=w;j++){
dp[i][j]=dp[i-1][j];
if(j>=wi)dp[i][j]=max(dp[i][j],dp[i-1][j-wi]+vi);
}
}
int ans=dp[n][w];
for(int i=n;i>=0;i--){
int mx=*max_element(dp[i],dp[i]+w+1);
int l=1,r=idx;
while(l<r){
int mid=l+r>>1;
int x=mid;
if(query(idx,tr1)-query(x-1,tr1)<=k)r=mid;
else l=mid+1;
}
int cnt=query(idx,tr1)-query(l-1,tr1);
if(cnt>=k){
ans=max(ans,mx+query(idx,tr2)-query(l-1,tr2)-mpp[l]*(cnt-k));
}else{
ans=max(ans,mx+query(idx,tr2)-query(l-1,tr2));
}
// cout<<mx<<' '<<query(idx,tr2)-query(l-1,tr2)<<' '<<l<<endl;
if(i) {
auto [wi,vi]=a[i-1];
add(mp[vi], 1, tr1);
add(mp[vi], vi, tr2);
}
}
cout<<ans<<endl;
}
int g[5010][5010];
void solve(){
int w,k;cin>>n>>w>>k;
vector<PII>a(n);
for(int i=0;i<n;i++){
cin>>a[i].first>>a[i].second;
mp[a[i].second]++;
}
vector<int>mpp(n+1);
for(auto [pos,w]:mp){
mp[pos]=++idx;
mpp[idx]=pos;
}
sort(all(a));
int dp[n+1][w+1];
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
auto [wi,vi]=a[i-1];
for(int j=1;j<=w;j++){
dp[i][j]=dp[i-1][j];
if(j>=wi)dp[i][j]=max(dp[i][j],dp[i-1][j-wi]+vi);
}
}
int ans=dp[n][w];
for (int i = n; i; i--) {
for (int j = k; j >= 0; j--) {
if (j >= 1) g[i][j] = max(g[i + 1][j], g[i + 1][j - 1] + a[i-1].second);
else g[i][j] = g[i + 1][j];
}
ans = max(ans, dp[i - 1][w] + g[i][k]);
}
cout<<ans<<endl;
}
F. 等价重写
我们发现我们该点的一位 只和最后这一位是什么联系
也就是最后一位必须在最后 这样我们就可以把当前与最后连起来 表示我该点必须在这个点之前
其他我都可以不管
然后拓扑排序 要是有一层是两个入队 表示我这两个谁前谁后都可以 就可以交换顺序
void solve(){
int n,m;cin>>n>>m;
vector<int>v[n+1],last(m+1);
vector<int>g[n+1],deg(n+1);
for(int i=1;i<=n;i++){
int x;cin>>x;
while(x--){
int pos;cin>>pos;
v[i].push_back(pos);
last[pos]=i;
}
}
for(int i=1;i<=n;i++){
for(auto pos:v[i]){
if(i!=last[pos]){
g[i].push_back(last[pos]);
deg[last[pos]]++;
}
}
}
vector<int>q;
for(int i=1;i<=n;i++){
if(!deg[i])q.push_back(i);
}
while(q.size()){
if(q.size()>=2){
cout<<"Yes"<<endl;
int mx=max(q[0],q[1]),mn=min(q[0],q[1]);
for(int j=1;j<=n;j++){
if(mx==j)continue;
if(j==1){
if(j==mn){
cout<<mx<<' '<<mn;
}else{
cout<<j;
}
}
else {
if(j==mn){
cout<<' '<<mx<<' '<<mn;
}else{
cout<<' '<<j;
}
}
}cout<<endl;
return;
}
vector<int>nq;
while(q.size()){
auto u=q.back();q.pop_back();
for(auto v:g[u]){
deg[v]--;
if(deg[v]==0){
nq.push_back(v);
}
}
}
q=nq;
}
cout<<"No"<<endl;
}