1.$Des:$若干个区间,选出最多的区间个数使得区间两两不相交.
$Sol:$按右端点从小到大排序,能选则选
2.$Des:$若干个区间,每个区间有权值,选出权值和最大的区间且区间两两不相交.
$Sol:$$dp\ f_i$表示前$i$个位置的答案,对每一个区间都有一个转移:$f_r=max(f_r,f_j+w),j<l$
3.$Des:$选出最少的区间覆盖整个序列.
$Sol:$左端点排序,贪心覆盖..不知道怎么讲反正挺显然$qwq.$
4.$Des:$每个区间有代价,选出代价和最小的区间覆盖整个序列.
$Sol:$$dp\ f_i$表示覆盖了前$i$个位置的答案,对每一个区间都有一个转移:$f_r=min(f_r,f_j+w),l-1\leq j<r$
两个方法:
1.$f_i$表示以$i$结尾的最长上升子序列.
讲一下树状数组优化:显然,我们每次都是用最大的$f_j,j<i$来更新$f_i$.需要支持的操作是维护$max(f_i)$,修改$f_i$.然后这里可以用树状数组,没了.
2.$f_i$表示长度为$i$的上升子序列的末尾最小值.
依次枚举所有元素,对于当前元素$x$,找到$f$数组中比$x$大的最小值$f_y$,并令$f_y=x$.
$Des:$
你和对方各有$n$匹马,每匹马都有一个能力值.对方出马的顺序给定,你需要决定你的出马顺序是的分数最大.赢了$+200$分,输了$-200$分.
$Sol:$
如果当前能力值最大的马能赢对方能力值最大的马,就把它们匹配,继续,否则进入第二步.
如果当前能力值最小的马能赢对方能力值最小的马,就把它们匹配,继续,否则进入第三步.
否则就拿当前最小与对方最大匹配,再返回第一步.
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=2010; int n,a[N],b[N],as; int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); n=read(); go(i,1,n)a[i]=read(); go(i,1,n)b[i]=read(); sort(a+1,a+n+1); sort(b+1,b+n+1); Ri l1=1,l2=1,r1=n,r2=n; while(l1<=r1) { while(l1<=r1 && r1<=n && a[l1]>b[l2])as+=200,l1++,l2++; while(l1<=r1 && r1<=n && a[r1]>b[r2])as+=200,r1--,r2--; if(l1<=n &&r2>=1 && a[l1]<b[r2])as-=200; l1++;r2--; } printf("%d\n",as); return 0; }
$Des:$
有$n$个怪兽,打第$i$个怪兽要会减少$a_i$滴血,打完后会增加$b_i$滴血.你的初始血量为$s$.要求打怪过程中血量为正数,求是否能打完所有怪,如果能,输出打怪方案.
$Sol:$
首先对于$a_i<b_i$的怪兽一定是先打,按$a_i$从小到大排序,能打就打,最后的血量为$s1$.那么对于$a_i>b_i$的,就逆向思维倒着来,看成打怪消耗$b_i$滴血,恢复$a_i$滴血直到血量不小于$s1$.所以对于$a_i>b_i$的,就按照$b_i$从大到小排序,依次往后能打就打.
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define int long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=100010; int n,z,n1,n2; struct nd{int a,b,p;}t1[N],t2[N]; il bool cmp(nd x,nd y){return x.a<y.a;} il bool vmp(nd x,nd y){return x.b>y.b;} main() { n=read(),z=read(); go(i,1,n) { Ri x=read(),y=read(); if(x<=y)t1[++n1]=(nd){x,y,i}; else t2[++n2]=(nd){x,y,i}; } sort(t1+1,t1+n1+1,cmp); go(i,1,n1) { if(z<=t1[i].a){printf("NIE\n");return 0;} z+=t1[i].b-t1[i].a; } sort(t2+1,t2+n2+1,vmp); go(i,1,n2) { if(z<=t2[i].a){printf("NIE\n");return 0;} z+=t2[i].b-t2[i].a; } printf("TAK\n"); go(i,1,n1)printf("%d ",t1[i].p); go(i,1,n2)printf("%d ",t2[i].p); return 0; }
$Des:$
有$a$,$b$两条流水线，现在有n个工作要在这两个流水线上完成.每个工作要分别在两个流水线上完成,时间分别是$a_i$,$b_i$.并且必须先在$a$上完成才能在$b$上完成.最小化所有工作完成的时间。
$Sol:$
答案是$b$流水线工作的时间和它等待的时间,它工作的时间是一定的不能改变的,所以要最小化等待的时间.
一段等待时间一定是从某一个产品在流水线$b$上加工完开始的,一定是在某一个产品在流水线$a$上加工完结束的.发现,假设产品$i$在流水线$a$上加工完成的时间是一段等待时间的结束,那么$\sum _{k=1}^{i}a_i-\sum _{k=1}^{i-1}a_i$就是在开始加工第$i+1$个产品前流水线$b$等待的总时间.但是事实上我们只需要维护一个$nw$表示当前等待的所有时间,每到一个产品,就加上它的$a$,更新下答案(取$min$),然后在加上$b$.如果这个产品在$a$上加工完成并不是一段等待时间的结束,那么该值一定不会更新答案,所以这样做是正确的.
综上,我们要找到一种加工顺序,使得$min(nw)$最小.小小处理一下,对于每一个$a$改成$-$而不是$+$,$b$改成$+$.那么就是求$min(-nw)$,$nw$一定是负数才会更新答案,我们希望这个$nw$越大越好.于是这题就和上一题一样了.策略同上一题.
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define int long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=1010; int n,nw,n1,n2,as,a[N],b[N]; struct nd{int a,b,p;}t1[N],t2[N]; il bool cmp(nd x,nd y){return x.a<y.a;} il bool vmp(nd x,nd y){return x.b>y.b;} main() { n=read(); go(i,1,n)a[i]=read(); go(i,1,n)b[i]=read(); go(i,1,n) { if(a[i]<=b[i])t1[++n1]=(nd){a[i],b[i],i}; else t2[++n2]=(nd){a[i],b[i],i}; } sort(t1+1,t1+n1+1,cmp); go(i,1,n1) { nw-=t1[i].a; as=max(as,-nw); nw+=t1[i].b; } sort(t2+1,t2+n2+1,vmp); go(i,1,n2) { nw-=t2[i].a; as=max(as,-nw); nw+=t2[i].b; } go(i,1,n)as+=b[i]; printf("%lld\n",as); go(i,1,n1)printf("%lld ",t1[i].p); go(i,1,n2)printf("%lld ",t2[i].p); return 0; }
$Des:$
转换后的题意是:有$n$个物品,每个物品有一个权值$a_i$.你需要选出$k$个物品使得权值最大,且满足任意两个物品不相邻.
$Sol:$
首先选权值最小的物品$i$,但是这样并不一定是最优的,因为选$i-1$和$i+1$可能更优(不可能在$i-1,i+1$中只选一个的情况是更优的).所以选了$i$之后可以把$i-1,i,i+1$这三个物品换成一个物品权值为$a_{i-1}+a_{i+1}-a_i$,这样一来,如果再选这个物品,就等价于只选了$i-1$与$i+1$物品.注意选第一个物品和最后一个物品时要特判.链表和堆维护.
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define int long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=100010; int n,k,a[N],l[N],r[N],as; bool f[N]; struct nd{int d,p;}; il bool operator < (nd x,nd y){return x.d>y.d;} priority_queue<nd>q; main() { freopen("1.in","r",stdin); freopen("2.out","w",stdout); n=read()-1,k=read(); Ri x=read(),y; go(i,1,n) { y=read(),a[i]=y-x,x=y; l[i]=i-1;r[i]=i+1; q.push((nd){a[i],i}); } go(i,1,k) { int p=q.top().p;q.pop(); if(f[p]){i--;continue;} as+=a[p]; f[l[p]]=f[r[p]]=1; if(l[p]==0) { l[r[r[p]]]=0; continue; } if(r[p]==n+1) { r[l[l[p]]]=n+1; continue; } a[p]=a[l[p]]+a[r[p]]-a[p];q.push((nd){a[p],p}); l[p]=l[l[p]]; r[p]=r[r[p]]; r[l[p]]=p; l[r[p]]=p; } printf("%lld\n",as); return 0; }
$Des:$
有$n$个物品,每个物品有两个权值$a_i,b_i$.你需要确定物品的顺序,使得$max((\prod _{j=1}^{i-1}a_j)/b[i])$最小.向下取整.
$Sol:$
首先考虑两个物品$i,j$,前面的$\prod {a_i}$为$t$.
$max(\frac{t}{b_i},\frac{t*a_i}{b_j})$
若$i$放前,$j$放后,则答案为$max(\frac{t}{b_i},\frac{t*a_i}{b_j})$
若$j$放前,$i$放后,则答案为$max(\frac{t}{b_j},\frac{t*a_j}{b_i})$
现在要求$max(\frac{t}{b_i},\frac{t*a_i}{b_j})$ $<$ $max(\frac{t}{b_j},\frac{t*a_j}{b_i})$
分析一下就可以知道其实只要$\frac{t*a_i}{b_j}$比$\frac{t*a_j}{b_i}$大就好了,再去分母,其实就只要$a_i*b_i>b_i*b_j$就好了.
$Code:$
许许久久以前的$Code$
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int re() { int x=0,y=1;;char ch; ch=getchar(); while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) y=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) {x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*y; } struct node { int l,r,tot; }a[10010]; int n; int wl,wr; int ans[10000000]; void mul(int x) { for(int i=1;i<=ans[0];i++) ans[i]*=a[x].l; for(int i=1;i<=ans[0];i++){ ans[i+1]+=ans[i]/10; ans[i]%=10;} if(ans[ans[0]+1]) ans[0]++; while(ans[ans[0]]>=10){ ans[ans[0]+1]=ans[ans[0]]/10; ans[ans[0]]%=10;ans[0]++;} } int fians[10000000],num=0; void div() { int x=0,y=a[n].r; for(int i=ans[0];i>=1;i--){ x=x*10+ans[i]; if(x<y) {fians[++num]=0;continue;} else {fians[++num]=x/y;x%=y;}} } bool cmp(node x,node y) { if(x.tot==y.tot) return x.r<y.r; return x.tot<y.tot; } int main() { n=re();wl=re();wr=re(); for(int i=1;i<=n;i++){ a[i].l=re();a[i].r=re();a[i].tot=a[i].l*a[i].r;} sort(a+1,a+n+1,cmp); ans[1]=wl;ans[0]=1; for(int i=1;i<n;i++) {mul(i);} //for(int i=ans[0];i>=1;i--) cout<<ans[i];cout<<endl;cout<<a[n].r<<endl; div(); bool ff=0; for(int i=1;i<=num;i++){ if(!ff&&!fians[i]) continue; ff=1; printf("%d",fians[i]); } if(ff==0) printf("1"); return 0; }
$Des:$
有$n$个人掉到了陷阱里,需要搭人梯逃脱.陷阱的深度为$h$.第$i$个人的身高为$a_i$,臂长是$b_i$,若所有人的升高+最上面的人的臂长不小于$h$,则最上面的人可以逃脱.求最多逃脱的人数.
$Sol:$
如果$x,y$都要逃脱,且$a_x+b_x<a_y+b_y$,那么把$x$放在$y$上面应该是更优的.这样,逃脱的顺序就确定了.现在只要考虑每个人是否逃脱,这个可以$dp$.$f_i$表示逃出$i$个人时的最大高度.
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=100010; int n,h,as,f[N]; struct nd{int a,b;}t[N]; il bool cmp(nd x,nd y){return x.a+x.b<y.a+y.b;} int main() { n=read();mem(f,-1);f[0]=0; go(i,1,n)t[i]=(nd){read(),read()},f[0]+=t[i].a; h=read(); sort(t+1,t+n+1,cmp); go(i,1,n) { yes(j,n,1) if(f[j-1]+t[i].b>=h) f[j]=max(f[j],f[j-1]-t[i].a); } yes(i,n,1)if(f[i]>=0){as=i;break;} printf("%d\n",as); return 0; }
将军令 $Luogu3942$
加强版的消防局的设立$qwq$
$Des:$
给你一棵树,你需要放置最少的关键点来覆盖这棵树,一个关键点能覆盖与他距离不超过$k$的点.
$Sol:$
就这题的数据范围而言,有三个做法是可以过的.
1.复杂度$O(n*k)$
贪心:每次选取深度最深的未被覆盖的点,在距离它$k$的祖先结点设立关键点.
按照深度由大到小排序.
维护$o_i$数组表示现在被覆盖的点离$i$的最小距离.这样维护:每设立一个关键点,用这个关键点更新与它距离小于等于$k$的祖先结点的$o$,每取出一个点判断它是否被覆盖了,就依次用与它距离小于等于$k$的祖先结点更新它,这样就实现了兄弟结点之间的覆盖.
2.复杂度$O(nlog_n)$
贪心同上.排序同上.
$f_i$数组表示$i$是否被覆盖.按深度大小枚举$i$,若没被覆盖,则在与它距离为$k$的祖先结点出设立关键点(这样的祖父结点可以预处理出).然后再更新这个关键点可以覆盖到的点.由于每个点只被覆盖一次,所以复杂度$O(N)$
3.复杂度$O(N)$
咕咕咕.
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=100010; int n,k,t,b[N],ct,so[N],d[N],gr[N],c[N],as; bool f[N],vis[N]; struct nd{int v,nt;}a[N*2]; il void add(Ri u,Ri v){a[++ct]=(nd){v,b[u]};b[u]=ct;} il void build(Ri grt,Ri u,Ri fa,Ri dep) { d[u]=dep; if(dep-d[grt]>k)grt=so[grt]; gr[u]=grt; e(i,u) { Ri v=a[i].v; if(v==fa)continue; so[u]=v; build(grt,v,u,dep+1); } } il bool cmp(int x,int y){return d[x]>d[y];} il void dfs(Ri u,Ri fa,Ri d) { f[u]=1;vis[u]=1; if(d+1>k)return; e(i,u) { Ri v=a[i].v; if(v==fa)continue; if(vis[v])continue; dfs(v,u,d+1); } } int main() { n=read(),k=read(),t=read(); go(i,1,n-1){Ri u=read(),v=read();add(u,v);add(v,u);} build(1,1,0,1); go(i,1,n)c[i]=i; sort(c+1,c+n+1,cmp); go(i,1,n) { Ri p=c[i]; if(!f[p]) { as++; mem(vis,0); dfs(gr[p],0,0); } } printf("%d\n",as); return 0; }
不会
不会
$Des:$
给定$m$个有序对$(a,b$),求构造一个$n$排列,满足$m$个对中$a$均排在$b$前,且$1$尽量靠前,在$1$尽量靠前的前提下$2$尽量靠前,....以此类推.
$Sol:$
反向图最大拓扑序的$reverse$
$Summary:$
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define db double #define inf 2147483647 using namespace std; il int read() { Ri x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=100010; int T,n,m,b[N],ct,in[N],as[N]; struct nd{int v,nt;}a[N]; il void add(Ri u,Ri v){a[++ct]=(nd){v,b[u]};b[u]=ct;} priority_queue<int>q; il void init() { mem(b,0);mem(a,0);mem(in,0);ct=0; } int main() { T=read(); while(T--) { init(); n=read(),m=read();bool fl=0; go(i,1,m){Ri u=read(),v=read();add(v,u);in[u]++;} go(i,1,n)if(!in[i])q.push(i); ct=0; go(k,1,n) { if(!q.size()){fl=1;break;} Ri u=q.top();q.pop(); as[k]=u; e(i,u) { Ri v=a[i].v; in[v]--; if(!in[v])q.push(v); } } if(fl)printf("Impossible!\n"); else { yes(i,n,1)printf("%d ",as[i]); printf("\n"); } } return 0; }
$Des:$
有$n$种食物,每种食物有固定的价钱$p_i$以及保质期$s_i$.你有$m$元,购买的外送费为$f$元(可以一次购买多个一次性送达).每天必须吃一个食物.问最多可以活多少天.
$Sol:$
还是简单讲一下.
首先保证食物价格随保质期单调递增
注意到如果外卖次数确定,那么买食物的钱是确定的,这时存活天数是可以二分的.而外卖次数是可以三分的(我还是只停留在感性理解的层面上).
然后钱$s$和外卖次数$c$都确定了,那么一定是把$s$等分为$c$份是最优的.然后贪心地买食物就$ok$了.
$Code:$
#include<bits/stdc++.h> #define il inline #define Ri register int #define go(i,a,b) for(Ri i=a;i<=b;++i) #define yes(i,a,b) for(Ri i=a;i>=b;--i) #define e(i,u) for(Ri i=b[u];i;i=a[i].nt) #define mem(a,b) memset(a,b,sizeof(a)) #define int long long #define db double #define inf 2147483647 using namespace std; il int read() { int x=0,y=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();} return x*y; } const int N=210; int f,n,m,as; struct nd{int p,s;}a[N]; il bool cmp(nd x,nd y){return x.p==y.p?x.s>y.s:x.p<y.p;} il int calc(int x) { int q=m-x*f,dy=0,ret=0; if(q<=0)return 0; go(i,1,n) { int res=a[i].s-dy; if(res<=0)continue; if(res*a[i].p<=q/x)q-=res*a[i].p*x,ret+=x*res,dy=a[i].s; else return ret+q/a[i].p; } return ret; } main() { m=read(),f=read(),n=read(); go(i,1,n)a[i]=(nd){read(),read()+1}; sort(a+1,a+n+1,cmp); int l=1,r=m/f; while(r-l>=5) { int qvq=(r-l+1)/3,midl=(l+qvq-1),midr=r-qvq+1; if(calc(midl)>calc(midr))r=midr-1; else l=midl+1; } go(i,l,r)as=max(as,calc(i)); printf("%lld\n",as); return 0; }
$Des:$
没办法简化题意了.
$Sol:$
1.$O(kn)$
2.$O(n^2)$
其实和$O(kn)$的差不多,就是每次选取最优的区间,然后一直用加速器直到该区间变成两个区间.
3.$O(nlog_n)$
在$O(n^2)$的基础上,把选最优区间的这个操作用数据结构维护.
$Des:$
有一棵二叉树,现在可以选定任意一个点为根,要求使得这棵二叉树的中序遍历字典序最小.需要保证被选中的点度数为$2$,左右儿子可以随便确定.
$Sol:$
度数为$1$的结点中字典序最小的作为二叉树中序遍历的第一个.
$Code:$
原文：https://www.cnblogs.com/forward777/p/11543527.html
