CSP2019 考前复习
- 2019 年 10 月 22 日
- 笔记
动态规划
【NOIP2016】愤怒的小鸟（状压+思维）
多组数据题
共有i只猪，给出每只猪的坐标，鸟的飞行轨迹为经过原点的抛物线，求最少要多少只鸟能消灭所有的猪
[ 猪数量n<=18 ]
看到(n<=18)，就可以自然的想到状压或者爆搜，因为无后效性，考虑状压
想到设状态(S)为已消灭的猪的集合，有(dp[s])为当前状态下需要的最少鸟数
再设(line[i][j])为经过第i，第j头猪的抛物线能消灭的猪的集合
合理性：对于当前集合，我们总能有两个转移：
1、用一个新的抛物线来消灭第(i)位的猪（抛物线指定一个点）
2、在当前集合的基础上新增一条抛物线来消灭够着第(i)个与第(j)个猪（抛物线指定两个点，两点确立一个抛物线（经过原点）），所以，我们可以求出这条抛物线能消灭的所有的猪，然后由(S)向这个状态转移
易得:
[ dp[S|1<<(i-1)]=min(dp[S|1<<(i-1)],dp[S]+1); ]
[ dp[S | line[i][j] ]=min(dp[S | line[i][j]] ,dp[S]+1); ]
然后预处理(line[i][j])即可
有两个优化：
1、对于S集合内已消灭的点，不用进行转移（可通过其他点进行转移）
2、对于S集合的拓展，S必经点有$ S&(1<<(x−1))=0 (的)x_min$ 相当于单调性?，这次不打他以后一定会打到他，如果这次打了他就是多余运算
#include<bits/stdc++.h> #define re register #define ll long long #define puts puts("") #define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout) using namespace std; inline int read(){ int k=1,sum=0;char c=getchar(); for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1; for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-48; return sum*k; } inline ll LLread(){ int k=1;ll sum=0;char c=getchar(); for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1; for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-48; return sum*k; } int T; const int N=20; const double eps=1e-6; double x[N],y[N]; int line[N][N]; int hav[1<<20],dp[1<<20]; int n; inline void Solve(double &x,double &y,double xii,double xi,double yi,double xjj,double xj,double yj){ y=(xii*yj-xjj*yi)/(xii*xj-xjj*xi); x=(yi-xi*y)/xii; } inline int lowbit(int x){ return log(x&(-x))/log(2)+1; } int main(){ //File("testdata"); for(re int i=0;i<(1<<20);++i){ hav[i]=lowbit(~i); } T=read(); while(T--){ n=read();read(); memset(line,0, sizeof(line) ); memset(dp,0x3f, sizeof(dp) ); for(re int i=1;i<=n;++i){ scanf("%lf%lf",&x[i],&y[i]); } for(re int i=1;i<=n;++i){ for(re int j=i+1;j<=n;++j){ if(fabs(x[i]-x[j])<eps) continue; double a,b; Solve(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]); if(a>-eps) continue; for(re int k=1;k<=n;++k) if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps) line[i][j]|=(1<<(k-1)),line[j][i]=line[i][j]; } } dp[0]=0; for(re int s=0;s<(1<<n);++s){ int p=hav[s]; dp[s|(1<<(p-1))]=min(dp[s]+1,dp[s|(1<<(p-1))]); for(re int i=1;i<=n;++i){ dp[s|line[p][i]]=min(dp[s]+1,dp[s|line[p][i]]); } } cout<<dp[(1<<n)-1];puts; } return 0; } 贪心
【NOIP2016】蚯蚓（贪心+优先队列+单调队列）
(转自洛谷题解)
关键点: 发现此题中隐含的单调性.
发现先被切掉的蚯蚓分成的蚯蚓一定比后切掉的蚯蚓分成的蚯蚓大. 假设这两只蚯蚓分别为 (a,b) ,其中 (a>b) .那么它被切成 (a_1,a_2) . t秒后, (b) 被切成了 (b_1,b_2) .此时 (a_1,a_2) 的长度为 (l_{a_1}+t=pl_{a}+t,l_{a_2}+t=(1-p)l_a+t) .而 (b_1,b_2) 的长度却为 (p(l_b+t),(1-p)(1_b+t)) , 容易看出 (l_{a_1}>l_{b_1},l_{a_2}>l_{b_2}) .也就是说根本不需要用一个堆来维护, 它本来就具有一定单调性.
那么就是说如果蚯蚓 (a_1,a_2,cdots,) 满足 (a_1>a_2>cdots) ,那么以此分成两只 $a_{11},a_{12},a_{21},a_{22},cdots $ .那么 [a_{12}>a_{22}>cdots,a_{11}>a_{21}>cdots]
那么就可以将这两堆依次存储, 加上还没被切过的蚯蚓.每次要切时在这三堆里面选择最大的, 切完再依次放回去. 所以这么做时间复杂度为(Theta (m)).再优化一下细节基本上就没问题了.
*结论*: 善于发现题目中隐含的单调性.
Tip:有些细节需要仔细考虑不然会很惨
#pragma GCC optimize(3) #include<bits/stdc++.h> #define re register #define line puts("") #define ll long long #define File(x) freopen(x".in","r",stdin); freopen("Debugs.out","w",stdout) using namespace std; inline int read(){ int k=1,sum=0; char c=getchar(); for(;c<'0' || c>'9';c=getchar()) if(c=='-') k=-1; for(;c>='0' && c<='9';c=getchar()) sum=sum*10+c-48; return sum*k; } const int N=1e5+10,M=7e6+10; priority_queue<int> Q; int n,m,q,u,v,t; double p; int a[M]; int b[M],c[M],cut,cntb=0,cntc=0,tb=1,tc=1,ta=1; inline bool cmp(int a,int b){ return a>b; } inline void Find(){ if(ta>n) { if(b[tb]>c[tc]) cut=b[tb++]; else cut=c[tc++]; } else if(a[ta]>=b[tb] && a[ta]>=c[tc]) cut=a[ta++]; else if(b[tb]>=a[ta] && b[tb]>=c[tc]) cut=b[tb++]; else cut=c[tc++]; return; } int main(){ //File("testdata"); n=read();m=read();q=read();u=read();v=read();t=read(); p=(double)u/v; for(re int i=1;i<=n;++i) a[i]=read(); sort(a+1,a+n+1,cmp); int sigma=0; for(re int i=1;i<=m;++i) { Find(); cut+=sigma; int a1=cut*1.0*p,a2=cut-a1; //int a11=floor(p*(double)cut),a22=cut-a11; //cout<<"ASD"<<a1<<" "<<a11<<" "<<a2<<" "<<a22<<"ASD"<<endl; sigma+=q; a1-=sigma;a2-=sigma; b[++cntb]=a1,c[++cntc]=a2; if(i%t==0) cout<<cut<<" "; } line; for(re int i=ta;i<=n;++i) Q.push(a[i]); for(re int i=tb;i<=cntb;++i) Q.push(b[i]); for(re int i=tc;i<=cntc;++i) Q.push(c[i]); for(re int i=1;!Q.empty();++i) { if(i%t==0) cout<<Q.top()+sigma<<" "; Q.pop(); } return 0; } /* 3 7 1 1 3 1 3 3 2 */
