挂惨了 \(100+1+3+0=104\)
\(rank=?\)
这里我要点名批评那位收代码的老师，她告诉我交\(ZIP\)没关系，hhx爷爷的ZIP是没问题，可能是我太弱了。
T1 珠宝 (jewel)
题意：
一个\(01\)背包，只不过个数\(n<=1e6\),询问的总花费\(k<=5e4\),每一件的花费\(c[i]<=300\),价值\(v[i]<=1e9\)
解法：
首先最朴素的\(01\)背包在此不再赘述，不会就别打OI，去采药。
普通的\(01\)背包是\(O(nk)\)的，显然过不了。但我们发现\(c[i]\)很小，这启示我们可以先根据\(c[i]\)分类。
考虑对于同一个花费的物品，如果要选肯定是先选择价值大的再选择价值小的，所以这个东西它是有单调性的。搞一个东西维护\(c[i]\)从大到小排序，再简单的一个分治就行（为什么现在很多大神喜欢用\(cdq\)命名分治？一下考场\(ZYB\)说\(cdq\),然后\(kcr\)说他也是，吓死我）。我考场忘记优先队列，就用的\(vector\)记录以后排序。为什么我能场切？看变量名有惊喜！
//kcrboshasta kcr薄纱std
//hhxqqq hhx强强强
//wqxjgman wqx金钩man
//ChiFanAKioi 字面意思
//zyb(wyb)_tql zyb(wyb)太强力
#include<bits/stdc++.h>
#define int long long
#define kcrboshastd 0
using namespace std;
struct stu{
int w;
int v;
}hhxqqq[1000001];//暴力的存储
int c,v;
char cb[40000],*cs=cb,*ct=cb;
int n,k;
int wqxjgman[305];//每一个数的出现次数
vector<int>wybtql[305];//sum
int dp[2][50001];
int g[2][50001];
int ChiFanAKioi[50001];//暴力dp
int now=1,pre=0;
void ans(int l,int r,int ql,int qr,vector<int>&wybtql,int &wqxjgman){
if(ql>qr || l>r) return;
int zyb_tjl=-1;
int mid=(ql+qr)/2;
int val=0;
for(int i=max(l,mid-wqxjgman);i<=r && i<mid;i++){
if(zyb_tjl==-1||g[0][i]+wybtql[mid-i-1]>val){
val=g[0][i]+wybtql[mid-i-1];
zyb_tjl=i;
}
}
g[1][mid]=val;
if(zyb_tjl==-1) zyb_tjl=l;
ans(l,zyb_tjl,ql,mid-1,wybtql,wqxjgman);
ans(zyb_tjl,r,mid+1,qr,wybtql,wqxjgman);
}
bool cmp(int xx,int yy){
return xx>yy;
}
signed main(){
//freopen("jewel.in","r",stdin);
//freopen("jewel.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>c>>v;
wybtql[c].push_back(v);
wqxjgman[c]++;
hhxqqq[i].w=c;
hhxqqq[i].v=v;
}
if(n<=10000 && k<=10000){
for(int i=1;i<=n;i++){
for(int j=k;j>=hhxqqq[i].w;j--){
ChiFanAKioi[j]=max(ChiFanAKioi[j],ChiFanAKioi[j-hhxqqq[i].w]+hhxqqq[i].v);
}
}
for(int i=1;i<=k;i++){
cout<<ChiFanAKioi[i]<<" ";
}
return 0;
}
for(int i=1;i<=300;i++){
if(wqxjgman[i]){
sort(wybtql[i].begin(),wybtql[i].end(),cmp);
for(int j=1;j<wqxjgman[i];j++) wybtql[i][j]+=wybtql[i][j-1];
for(int j=0;j<i;j++) {
int p=j,bk=0;
for(;p<=k;p+=i,bk++) g[0][bk]=dp[pre][p];
ans(0,bk-1,0,bk-1,wybtql[i],wqxjgman[i]);
for(p=j,bk=0;p<=k;p+=i,bk++) dp[now][p]=max(g[0][bk],g[1][bk]);
}
swap(now,pre);
}
}
for(int i=1;i<=k;i++) cout<<dp[pre][i]<<" ";
return kcrboshastd;
}
T3 迷宫 (trap)
调了我1.5h。
有四个结论：
1.一旦老鼠被困在某个叶节点(前提)，在老鼠不能动的时候把老鼠通到根节点的那一条路上的其他支路都封死，然后再把走廊擦干净，这是最佳决策。
证明：考虑如果在老鼠通往根节点的路径上进入了其他的支路，就算支路的大小为1也需要一次操作擦进去的边。如果支路的大小更大则需要更多的操作数，不如花一次操作把支路堵上
2.一旦老鼠进入一个子树内，他最终会被自己弄脏的走廊困在某个叶节点。
证明：首先老鼠肯定是走不出这个子树的。老鼠如果不待在叶子节点到跟的路径比待在叶子节点短，这样管理者的操作数就变少了，显然不优。
3.耗子决策只能是：向上主动走一些(或不走)，然后找棵子树一头钻进去，然后等待收编。
证明：首先老鼠进入钻进一棵子树就出不去了(脏了)，在钻进子树前向上走能增大步数。
4.f[i]为老鼠在进入i子树后，最后不得不回到i点消耗的最大步数。在老鼠向下走之后(前提)每次堵住通向f值最大的子树的边，一定最优。
证明 老鼠进入f值最大的子树和其他子树结果都是返回i节点，i节点的子树数量不会变，堵住支路的代价是一样的，当然先阻止老鼠进入步数大的。
#include<bits/stdc++.h>
using namespace std;
int n,t,m;
bool tag[1000001];
vector<int> v[1000001];
int f[1000001];//f[i]表示老鼠进入了节点i为根的子树，然后又把老鼠赶回节点i所需要的步数。
int sum[1000001];
int num[1000001];
int faa[1000001];
int get_f(int now,int fa){
faa[now]=fa;
int maxn=0,maxnf=0,nu=0;
int kk=v[fa].size();
//sm[now]=sm[fa]+max(0,kk-2);
kk=v[now].size();
if(kk==1 && fa!=0){
f[now]=0;
return 0;
}
for(int i=0;i<v[now].size();i++){
if(v[now][i]==fa) continue;
nu++;
int k=get_f(v[now][i],now);
if(k>maxn){
maxnf=maxn;
maxn=k;
}
else if(k>maxnf){
maxnf=k;
}
}
f[now]=nu+maxnf;
num[now]=nu;
return f[now];
}
bool check(int k){
int now=m;
int cnt=1;
while(now!=t){
int lp=0;
for(int i=0;i<v[now].size();i++){
if(tag[v[now][i]]) continue;
if(f[v[now][i]]+sum[now]>k){
if(!cnt) return false;
lp++;cnt--;
}
}
k-=lp;
if(k<0) return false;
now=faa[now];
cnt++;
}
return true;
}
int erfen(int l,int r){
if(l==r) return l;
if(l==r-1){
if(check(l)) return l;
else return r;
}
int mid=(l+r)/2;
if(check(mid)){
return erfen(l,mid);
}
else return erfen(mid+1,r);
}
int main(){
cin>>n>>t>>m;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
get_f(t,0);
for(int i=1;i<=n;i++){
sum[i]=sum[faa[i]]+num[i]-(i!=m);
}
for(int i=m;i;i=faa[i]) tag[i]=true;
/*
for(int i=1;i<=n;i++) cout<<f[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++) cout<<sum[i]<<" ";
cout<<endl;
*/
//for(int i=1;i<=n;i++) cout<<h[i]<<" ";
//cout<<endl;
cout<<erfen(0,2*n);
return 0;
}
T4 迷宫 (trap)
感恩ZYB爷爷
题意：
给定一张 n 个点 m 条边的图，q 次询问，每次询问删掉 [l_i,r_i]内的边，问这张图是否存在奇环。
解法：
这题更是逆天，写了1h,调了1.5h，写错n多
一部分的提交：
首先找奇环可以转化为判断二分图(二分图无奇环)。然后你发现直接在一个区间内操作十分的麻烦。
下图中绿色为剩余线段：
考虑将区间复制一份,这样剩余的线段就是两个l,r的中间部分
SOLVE 1
考虑当l一定时，当r的位置达到一个定值使得剩余线段是二分图，再往后肯定也是(中间部分越来越少了)，所以可以对每个i求出to[i]表示以i为l的最后一个满足剩下图不是二分图的r,显然可以整体二分。判断二分图可以用扩展域可撤销并查集。这种方法写了代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q;
int num=0;
int ld[400010],rd[400010];
int fa[400010];
int sz[400010];
int to[400010];
struct stu{
int pla1;
int pla2;
int time;
};
stack<stu> sta;
inline int cdq(int x){for(;x!=fa[x];x=fa[x]);return x;}
void segment_tree(int xx,int yy){
yy=cdq(yy);
if(xx==yy) return;
else{
if(sz[xx]>sz[yy]) swap(xx,yy);
sz[yy]=sz[xx]+sz[yy];
fa[xx]=yy;
sta.push({xx,yy,num});
}
}
bool check(int xx,int yy){
num++;
int fx=cdq(xx),fy=cdq(yy);
if(fx==fy) return true;
segment_tree(fx,yy+n);
segment_tree(fy,xx+n);
return false;
}
void treap(){
for(;sta.size() && sta.top().time==num;sta.pop()){
fa[sta.top().pla1]=sta.top().pla1;
sz[sta.top().pla2]-=sz[sta.top().pla1];
}
num--;
}
void Dirichlet(int l,int r,int L,int R){
if(l>r) return;
if(L>R) return;
if(L==R){
for(;l<=r;l++){
to[l]=L;
}
return;
}
int mid=(l+r)/2;
int i;
for(i=mid;i<=R;i++){
if(i==r+1) i=max(i,L);
if(check(ld[i],rd[i])) break;
}
to[mid]=i;
for(;i>=L && i>=mid;i--){
if(i==L-1) i=min(i,r);
treap();
}
Dirichlet(l,mid-1,L,to[mid]);
for(int i=mid;i<=r && i<=L-1;i++){
treap();
}
for(int i=max(r+1,L);i<=to[mid]-1;i++){
check(ld[i],rd[i]);
}
Dirichlet(mid+1,r,to[mid],R);
for(int i=max(L,r+1);i<=to[mid]-1;i++){
treap();
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
cin>>ld[i]>>rd[i];
ld[i+m]=ld[i];
rd[i+m]=rd[i];
}
for(int i=1;i<=2*n;i++){
fa[i]=i;
sz[i]=1;
}
ld[m*2+1]=rd[m*2+1]=1;
Dirichlet(1,m+1,1,2*m+1);
while(q--){
int ll,rr;
cin>>ll>>rr;
if(to[rr+1]<=m+ll-1){
cout<<"YES";//不是二分图，有奇环
}
else{
cout<<"NO";
}
cout<<endl;
}
return 0;
}
//考虑把边建两次，把问题转化成了两个l~r之间的段是否为二分图
//用扩展域可撤销并查集判断二分图
//记to[i]为以i边为左端点从左到右的最后一条加入后满足二分图的点
SOLVE 2(zyb神仙的TJ)
考虑二分做法最后提到的线段树分治，显然在化简完问题后这就是一个线段树分治形式，可以将询问视为时间轴，仿照其做。
但是有一个问题，边在时间轴上的区间不是连续的，我们可以隔一天加一次边将总区间数卡到 \(\frac{nq}{2}\)
个，这是不好的。
但是对于这类问题我们还有一个 LCT 做法，同二分思路一样的考虑预处理出 to，使用一个双指针，同时维护一个支持删边加边维护最小生成树的 LCT （其中边权为加入时间）就可以快速的预处理出来了。时间复杂度 \(O(n \log n + q)\)，更为优秀。
SOLVE 3( _ ChiFAN _ 神仙的TJ)
真的卡不动了，但是我感觉我的思路还是有一些价值的，就来写一篇题解吧。
考虑使用回滚莫队（不增）来维护，当区间删去一个点时相当于全局加入一条边，这个询问的本质是询问是否是二分图，所以考虑扩展值域并查集，这里使用路径压缩加按秩合并，记录下修改，在回滚时全部还原。
总复杂度是 \(O(n \sqrt n \alpha(n))\)目前还卡不过去。
蒟蒻wwh:理论上是能过去的
标签：20230717,return,int,yy,fa,xx,now From： https://www.cnblogs.com/wangwenhan/p/17584931.html