锐客网

  1. 首页 > it技术 > >

搜索|NOIP2011

NOIP2011 DAY1,DAY2数据，标程，题目，题解合集：
http://download.csdn.net/detail/junjie435/8054741


DAY1： p1：铺地毯 搜索|NOIP2011
文章图片

搜索|NOIP2011
文章图片

这是一道模拟题目：只需要询问一个点所以，从头到尾扫一遍就行了

#include #include #include #define maxn 10010 using namespace std; /* 模拟 */ struct carpet { int x,y; int lx,ly; }ca[maxn]; int x,y,ans,n; void init() { freopen("carpet.in","r",stdin); freopen("carpet.out","w",stdout); } void readdate() { cin>>n; for(int i=1; i<=n; i++) scanf("%d%d%d%d",&ca[i].x,&ca[i].y,&ca[i].lx,&ca[i].ly); cin>>x>>y; } void work() { ans=-1; for(int i=1; i<=n; i++) if(ca[i].x<=x&&ca[i].y<=y&&ca[i].x+ca[i].lx>=x&&ca[i].y+ca[i].ly>=y) ans=i; printf("%d\n",ans); }int main() { init(); readdate(); work(); return 0; }


p2：选择客栈 搜索|NOIP2011
文章图片


搜索|NOIP2011
文章图片


/*这道题考试的时候抽了，样例都没过*/
【搜索|NOIP2011】给几种代码：
#include #include#define maxk 51 #define maxn 200010int sum[maxn],color[maxn],value[maxn],f[maxk+1][4]; int main() { freopen("hotel.in","r",stdin); freopen("hotel.out","w",stdout); int n,k,p,ans=0; sum[0]=0; scanf("%d%d%d",&n,&k,&p); for(int i=1,x; i<=n; i++) { scanf("%d%d",&color[i],&value[i]); sum[i]=sum[i-1]+(value[i]<=p); //可行前缀和； } color[0]=maxk+1; //边界判断； for(int i=1; i<=n; i++) { int tot=f[color[i]][1]; if(f[color[i]][3]

#include #include #include using namespace std; /* 用dp[i]维护i这种颜色在当前客栈颜色为i时可行的方案数。 */int n,k,p; long long ans=0; int num[50+10],dp[50+10]; int main() { freopen("hotel.in","r",stdin); freopen("hotel.out","w",stdout); int color,price; scanf("%d%d%d",&n,&k,&p); for(int i=1; i<=n; i++) { scanf("%d%d",&color,&price); if(price<=p)//当前客栈价格小于p时，之前color有多少就增加多少方案。 { ans+=num[color]; for(int j=0; j


#include #include using namespace std; /// const int MAXN = 200000 + 10; /// int n,k,p; int col[MAXN]; int a[MAXN]; int cnt[60]; int num[MAXN]; int head[60]; int next[MAXN]; int res; struct tree { int l,r,mini; }t[800040]; /// void fre() { freopen("hotel.in","r",stdin); freopen("hotel.out","w",stdout); } /// void read_pre() { scanf("%d %d %d",&n,&k,&p); for(int i = 1; i <= n; i++) { int color; int price; scanf("%d %d",&color,&price); col[i] = color; //记录i位置的颜色 a[i] = price; //记录i位置的价格cnt[color]++; //颜色color出现了多少次 num[i] = cnt[color]; //当前位置的color颜色出现的个数 next[head[color]] = i; //上一个颜色为color的点的下一个点为i点 head[color] = i; //颜色color的最后一个点为i点 } } /// void up(int u) { t[u].mini = min(t[u << 1].mini,t[u << 1 | 1].mini); } /// void build(int u,int l,int r) { t[u].l = l; t[u].r = r; if(l == r) { t[u].mini = a[l]; return; } int mid = (l + r) >> 1; build(u << 1,l,mid); build(u << 1 | 1,mid + 1,r); up(u); } /// int que(int u,int l,int r) { if(l <= t[u].l && t[u].r <= r) return t[u].mini; int mid = (t[u].l + t[u].r) >> 1; int ans; if(l > mid) ans = que(u << 1 | 1,l,r); else if(r <= mid) ans = que(u << 1,l,r); else ans = min(que(u << 1,l,r),que(u << 1 | 1,l,r)); return ans; } /// int main() { fre(); read_pre(); build(1,1,n); for(int i = 1; i <= n; i++) { int j = next[i]; while(j) { if(que(1,i,j) <= p) { res += cnt[col[i]] - num[j] + 1; break; }j = next[j]; } } printf("%d\n",res); return 0; }


#include #include #include #define MAXK 50+10 #define MAXN 200000+10 using namespace std; struct hotel { int col; int val; }h[MAXN]; int sum[MAXN],dp[MAXK]; int temp[MAXN],col_sum[MAXN]; int n,k,p,ans=0; void init() { freopen("hotel.in","r",stdin); freopen("hotel.out","w",stdout); } void readdate() { scanf("%d%d%d",&n,&k,&p); sum[0]=0; for(int i=1; i<=n; i++) { scanf("%d%d",&h[i].col,&h[i].val); if(h[i].val<=p) sum[i]=sum[i-1]+1; else sum[i]=sum[i-1]+0; } } void work() { for(int i=1; i<=n; i++) { int tot=dp[h[i].col]; if(col_sum[h[i].col]





p3：mayan 游戏 搜索|NOIP2011
文章图片
搜索|NOIP2011
文章图片
搜索|NOIP2011
文章图片
这就是一道裸DFS，看都数据范围，整个人都好了 代码中有详细解释
#include #include #include #include #define MAXN 6 #define MAXH 8 using namespace std; /* 崩溃：结构体未清零 特殊数据 in 1 2 2 3 2 0 4 4 3 4 0 3 3 0 5 5 3 5 3 5 0 4 4 3 4 4 0 out 3 4 -1 */ struct node { int h[MAXN]; //当前竖列高度 int c[MAXN][MAXH]; //当前列方块的map }map; int n,ans[MAXN][3]; //用ans来记录路径 bool flag,b[MAXN][MAXH],ok=false; void init() { freopen("mayan.in","r",stdin); freopen("mayan.out","w",stdout); }void readdate() { int x; scanf("%d",&n); for(int i=1; i<=5; i++) { scanf("%d",&x); while(x!=0) { map.h[i]++; map.c[i][map.h[i]]=x; scanf("%d",&x); } } }node clear_struct(node now) { for(int i=1; i<=5; i++) { now.h[i]=0; for(int j=1; j<=8; j++) now.c[i][j]=0; } return now; }bool check(node now)//是否完成 { for(int i=1; i<=5; i++) { if(now.h[i]!=0) { return false; } } return true; }void print()//输出路径 { //printf("\n"); for(int i=1; i<=n; i++) printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]); ok=true; return; }node move(node now) { node next; next=clear_struct(next); for(int i=1; i<=5; i++) { for(int j=1; j<=now.h[i]; j++) { if(now.c[i][j]!=0&&!b[i][j]) { next.h[i]++; next.c[i][next.h[i]]=now.c[i][j]; } } } return next; }node clear(node now) { node next; //next=clear_struct(next); bool flag=false; //是否进行了消除更改了地图 memset(b,0,sizeof(b)); for(int i=1; i<=5; i++) { for(int j=1; j<=now.h[i]; j++) { if(i<=3) { if(now.c[i][j]==now.c[i+1][j]&&now.c[i][j]==now.c[i+2][j]) { b[i][j]=b[i+1][j]=b[i+2][j]=true; flag=true; } } if(j<=now.h[i]-2) { if(now.c[i][j]==now.c[i][j+1]&&now.c[i][j]==now.c[i][j+2]) { b[i][j]=b[i][j+1]=b[i][j+2]=true; flag=true; } } } } if(flag) { next=move(now); //print(); return clear(next); //可能同时被消除所以需要再处理 } else return now; }void dfs(node now,int step) /* 对于每个节点（枚举[i][j]）进行搜索 当i==5时不可向右移 当i==1时不可向左移 右移时： 当右边一列的格子高度不足j时 当前列的高度-1，右边一列的高度+1； 格子右移——>[i][j]=0; [i+1][j]=格子的数 把当前列的格子从j到h[i]都下移一位 进行消除操作 更新ans dfs(next,step+1) 当右边一列的格子高度足够j时 把两个格子的值进行交换 进行消除操作 更新ans dfs(next,step+1) 左移时：【与右移类似】 当左边一列的格子高度不足j时 ...... 当左边一列的格子高度足够j时 //其实，我们可以发现 // 当左格子与右格子交换和右格子与左格子交换是一样的 //所以为了防止TLE 于是就可以把此情况删掉 ......*/ { node next; //next=clear_struct(next); flag=check(now); if(flag==true) { if(step>n) print(); elsereturn; }if(ok==true) return; if(step>n) return; for(int i=1; i<=5; i++) { for(int j=1; j<=now.h[i]; j++) { if(i<5) { if(j>now.h[i+1]) {next=now; next.h[i+1]++; next.c[i+1][next.h[i+1]]=next.c[i][j]; next.c[i][j]=0; next.h[i]--; for(int k=j; k<=next.h[i]; k++) next.c[i][k]=next.c[i][k+1]; next=clear(next); ans[step][0]=i-1; ans[step][1]=j-1; ans[step][2]=1; dfs(next,step+1); if(ok==true) return; } else {next=now; int t=next.c[i][j]; next.c[i][j]=next.c[i+1][j]; next.c[i+1][j]=t; next=clear(next); ans[step][0]=i-1; ans[step][1]=j-1; ans[step][2]=1; dfs(next,step+1); if(ok==true) return; } } if(i>1) { if(j>now.h[i-1]) { next=now; next.h[i-1]++; next.c[i-1][next.h[i-1]]=next.c[i][j]; next.c[i][j]=0; next.h[i]--; for(int k=j; k<=next.h[i]; k++) next.c[i][k]=next.c[i][k+1]; next=clear(next); ans[step][0]=i-1; ans[step][1]=j-1; ans[step][2]=-1; dfs(next,step+1); if(ok==true) return; } /* else { next=now; int t=next.c[i][j]; next.c[i][j]=next.c[i-1][j]; next.c[i-1][j]=t; next=clear(next); ans[step][0]=i-1; ans[step][1]=j-1; ans[step][2]=-1; dfs(next,step+1); if(ok==true) return; } */} } } }int main() { init(); readdate(); dfs(map,1); if(ok==false) printf("-1\n"); return 0; }




DAY2： p1：计算系数 搜索|NOIP2011
文章图片

明显的二次项展开；最后X^n*Y^m的系数应该为

a^n*b^m*杨辉三角中对应的系数，再取模
#include #include #include #include #define MAXN 1010 #define MOD 10007 using namespace std; int a,b,k,n,m; int YH[MAXN][MAXN]; int ans; void init() { freopen("factor.in","r",stdin); freopen("factor.out","w",stdout); } void readdate() { cin>>a>>b>>k>>n>>m; YH[1][0]=1; YH[1][1]=1; for(int i=2; i<=k; i++)//杨辉三角计算 { YH[i][0]=1; YH[i][i]=1; for(int j=0; j<=i-1; j++) YH[i][j]=(YH[i-1][j-1]+YH[i-1][j])%MOD; } /* for(int i=1; i<=k; i++) { for(int j=0; j<=i; j++) printf("%d ",YH[i][j]); printf("\n"); } */ } void solve() { //计算原有系数 a%=MOD; b%=MOD; int temp=a; for(int i=1; i<=n-1; i++) a=(a*temp)%MOD; temp=b; for(int i=1; i<=m-1; i++) b=(b*temp)%MOD; ans=(a*b)%MOD; //计算原有系数 //原有系数*杨辉三角对应的那个值ans=(ans*YH[k][n])%MOD; printf("%d\n",ans); } int main() { init(); readdate(); solve(); return 0; }



p2：聪明的质监员 搜索|NOIP2011
文章图片




搜索|NOIP2011
文章图片

搜索|NOIP2011
文章图片

#include #include #include using namespace std; const int N = 200000 + 10; int n, m, w[N], v[N], l[N], r[N]; long long s = 1e18, a[N], b[N], Y, S; bool calc(int W) { a[0] = b[0] = Y = 0; for(int i=1; i<=n; i++) { a[i] = a[i-1] + (w[i] >= W); b[i] = b[i-1] + (w[i] >= W) * v[i]; } for(int i=1; i<=m; i++) Y += abs((a[r[i]] - a[l[i]-1]) * (b[r[i]] - b[l[i]-1])); s = min(s, abs(S - Y)); return Y > S; } int main() { freopen("qc.in", "r", stdin); freopen("qc.out", "w", stdout); scanf("%d %d %I64d", &n, &m, &S); int p = 0, q = N, c = 1; for(int i=1; i<=n; i++) { scanf("%d %d", w+i, v+i); p = min(p, w[i]), q = max(q, w[i]); } for(int i=1; i<=m; i++) scanf("%d %d", l+i, r+i); while(q - p > 1) if(calc(c = (p + q) / 2)) p = c; else q = c; printf("%I64d\n", s); return 0; }

#include #include #include #include #define MAXN 200000+10 #define INF 1000000 using namespace std; int n,m; int w[MAXN],v[MAXN]; int l[MAXN],r[MAXN]; long long S,ans=1e18; int L,R; long long sumj[MAXN],sumv[MAXN]; void init() { freopen("qc.in","r",stdin); freopen("qc.out","w",stdout); }void readdate() { scanf("%d%d%lld",&n,&m,&S); L=INF; R=-INF; for(int i=1; i<=n; i++) { scanf("%d%d",&w[i],&v[i]); L=min(L,w[i]); //找到最左端 进行二分 R=max(R,w[i]); //找到最右端 进行二分 }for(int i=1; i<=m; i++) scanf("%d%d",&l[i],&r[i]); R++; }bool check(int W) { long long temp=0; //以W划分所得到的检验值temp //计算检验值 for(int i=1; i<=n; i++) if(w[i]>=W) { sumj[i]=sumj[i-1]+1; sumv[i]=sumv[i-1]+v[i]; } else { sumj[i]=sumj[i-1]; sumv[i]=sumv[i-1]; }for(int i=1; i<=m; i++) temp+=(sumj[r[i]]-sumj[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]); //计算检验值 bool flag; if(S<=temp) flag=true; elseflag=false; ans=min(ans,abs(S-temp)); //更新ans return flag; }void work()//二分W求得最小ans { while(L<=R) { int mid=(L+R)>>1; if(check(mid)) L=mid+1; else R=mid-1; } printf("%I64d\n",ans); }int main() { init(); readdate(); work(); return 0; }



p3：观光公交 搜索|NOIP2011
文章图片

搜索|NOIP2011
文章图片

在这里我只上代码，也有较详细的注释。

至于贪心的论述将在我下一篇博文中详细解答
#include #include #include #define MAXN 1000+10 #define MAXM 10000+10 using namespace std; /* 贪心!!! */ struct NODE { long long t; int from; int to; }person[MAXM]; int n,m,k; int d[MAXN]; //i—>i+1需要的时间 long long oversum[MAXN]; //在该站点i以前有多少人下车 long long reach_time[MAXN]; //车到达站点i的时间 long long latest[MAXN]; //在站点i 最晚乘客到达的时间 long long s[MAXN]; //如更改d[i]会影响到的站点从[i+1——>s[i]] long long ans; void init() { freopen("bus.in","r",stdin); freopen("bus.out","w",stdout); }void readdate() { scanf("%d%d%d",&n,&m,&k); for(int i=1; ilatest[i+1]时 s[i]=s[i+1]; s[n]=n; s[n-1]=n; //初始最后两个站台，进行倒推 for(int i=n-2; i>1; i--) if(reach_time[i+1]<=latest[i+1]) s[i]=i+1; else s[i]=s[i+1]; //初始化ans；ans=(第i个人到达目的地的时间-他出发的时间)的总和 for(int i=1; i<=m; i++) ans+=reach_time[person[i].to]-person[i].t; //因为读入时oversum不确定，所以在这里处理oversum for(int i=1; i<=n; i++) oversum[i]=oversum[i-1]+oversum[i]; return; }void solve() /* 每次找到最大的oversum[s[i]]-oversum[i] 在这时d[i]若减小会得到最优的ans减少 */ { long long maxval=0,index; //找到最优使用加速器的地方 for(int i=1; i<=n; i++) if(maxval=1) { maxval=oversum[s[i]]-oversum[i]; index=i; } long long L=index,R=s[index]; d[index]--; //使用加速器 ans-=maxval; //更改ans if(R==n) R=n-1; //特判 //再次更新reach_time for(int i=L; i<=R; i++) reach_time[i]=max(reach_time[i-1],latest[i-1])+d[i-1]; //再次更新s[i] for(int i=R; i>=L; i--) if(reach_time[i+1]<=latest[i+1]) s[i]=i+1; else s[i]=s[i+1]; return; }void work() { //对于每一个加速器进行一次贪心 for(int i=1; i<=k; i++) solve(); printf("%I64d\n",ans); return; }int main() { init(); readdate(); pre(); work(); return 0; }


小结 对于此次考试，中等题掌握较差，两天都错在了第二题。
所以，在接下来的训练中要更加注重会的题和中等题的细致。 ！！！！！！

    推荐阅读


    上一篇：通信原理角度调制

    下一篇：BZOJ|BZOJ 1002 轮状病毒