10.19补题记录

https://codeforces.com/gym/104821/problem/F
交换操作顺序 我们来想想什么那些操作不能交换操作顺序 每个点最后的数值只和最后一次改变这个点的大小有关 所以如果我们要保证一个点的数值不变的话我们只要保证最后一操作后不再改变这个点的数值就ok那么我们先找出那些是某些点的最后一次操作 看看可不可以和他前一个操作交换（为什么是前一个呢 因为前一个需要满足的条件比较少 并且又完成了题目的要求 那么为什么不是后一个呢 因为我们可以确保关于这个点只要前一个没有这个点 这两条操作就一定可以交换 但是对于后一条操作 我们不确定他们判断的点是那一个）可不可以交换的条件就是上一个操作有没有这个点 然后我们再遍历一下全部的操作看看有没有可以换的就okk了

// last[i]：最后修改位置 i 的操作
int last[MAXM + 10];
// OP[i]：操作 i 改了哪些位置
unordered_set OP[MAXN + 10];
// flag[i]：操作 i - 1 到 i 是否有一条连边
bool flag[MAXN + 10];

void solve() {
scanf("%d%d", &n, &m);//n个操作 m个点
memset(last, 0, sizeof(int) * (m + 3));
for (int i = 1; i <= n; i++) OP[i].clear();
memset(flag, 0, sizeof(bool) * (n + 3));

for (int i = 1; i <= n; i++) {int p; scanf("%d", &p);for (int j = 1; j <= p; j++) {int x; scanf("%d", &x);last[x] = i;//这个点的最后一次操作是第几个操作OP[i].insert(x);}
}// 边只有修改每个位置的最后一次操作可能与前面的操作有连
// 枚举每个位置，并检查最后一次操作
for (int i = 1; i <= m; i++) if (last[i] > 1) //这个点的最后一次操作不是1 看看可不可以和前面一个操作换// 如果 last[i] - 1 也改了位置 i，则两个操作之间有连边，也就是说两个操作是不可以调换顺序的if (OP[last[i] - 1].count(i)) flag[last[i]] = true;int ans = 0;
// 寻找没有与上一个操作连边的操作
for (int i = 2; i <= n; i++) if (!flag[i]) { ans = i; break; }//找一个没有连接的
if (ans > 0) {printf("Yes\n");for (int i = 1; i <= n; i++) {if (i == ans - 1) printf("%d", ans);else if (i == ans) printf("%d", ans - 1);else printf("%d", i);printf("%c", "\n "[i < n]);}
} else {printf("No\n");
}

}

https://codeforces.com/gym/104821/problem/G
一开始想是背包 但是又还有k个免费的 那就想假设我们已经知道了我们最后有哪些宝石那我们获得他们最优的方法是选k个贵的然后剩下的是我们自己买的 这样我们会发现问题变成了两个因为k个选完后我其他的就是01背包问题 再加上我们选择的k个的钱肯定大于我们自己买的钱 所以我们会想到先按钱排序然后去遍历在一段选出k在哪一段用dp
bool cmp(pp a,pp b)
{
return a.w>b.w;
}
void solve()
{
int n,W,k;
cin>>n>>W>>k;
for(int i=1;i<=n;i++)
{
cin>>bs[i].w>>bs[i].v;
}
sort(bs+1,bs+1+n,cmp);
priority_queue<int,vector,greater> p;//小根堆
//priority_queue p;//大根堆
int sum=0;
for(int i=1;i<=k;i++)
{
p.push(bs[i].v);
sum+=bs[i].v;
}
memset(dp,0,sizeof dp);
for(int i=n;i>=1;i--)
{
m[i]=0;
for(int j=W;j-bs[i].w>=0;j--)
{
dp[j]=max(dp[j],dp[j-bs[i].w]+bs[i].v);
m[i]=max(dp[j],m[i]);
}
}
//m[n+1]=0;
int ma=0;
ma=max(sum+m[k+1],ma);
for(int i=k+1;i<=n;i++)
{
if(p.size() && p.top()<bs[i].v)
{
sum-=p.top();
p.pop();
sum+=bs[i].v;
p.push(bs[i].v);
}
ma=max(ma,sum+m[i+1]);
}
cout<<ma<<endl;
}